A Download More RAM

Topic meaning: upgrade memory. Given the initial memory, use the given n software to upgrade memory. The ith software startup requires at least a memory, and b memory can be permanently added to find the maximum memory
Idea: just sort greedy

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
typedef long long ll;
const int N = 100 + 10;
int t,n,k;
struct node
{
	int a,b;
}no[N];
bool cmp(node a,node b)
{
	if(a.a == b.a) return a.b>b.b;
	return a.a < b.a;
}
int main()
{
	ios
    cin>>t;
    while(t--)
    {
    	cin>>n>>k;
    	for(int i = 0 ; i < n ; i ++ )	cin>>no[i].a;
    	for(int i = 0 ; i < n ; i ++ )	cin>>no[i].b;
    	sort(no,no+n,cmp);
    	ll ans = 0;
    	for(int i = 0 ; i < n ; i ++ )
    	{
    		if(k < no[i].a)	break;
    		k += no[i].b;
    	}
    	cout<<k<<"\n";
    }
    return 0;
}

B - GCD Arrays

Question meaning: give an interval and ask whether the maximum common divisor of all numbers remaining in the interval after operation can be greater than 1 in k operations
Idea: it can be seen that the maximum common divisor of even and odd numbers can only be 1, so the odd number is eliminated, so the maximum common divisor becomes 2. Therefore, it depends on whether the number of odd numbers in the interval is less than or equal to k, and the length of the interval is 1

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
typedef long long ll;
const int N = 100 + 10;
int t,l,r,k;
int main()
{
	ios
    cin>>t;
    while(t--)
    {
    	cin>>l>>r>>k;
    	int ans = 0;
    	vector<int> ve;
    	int len = r - l + 1;
    	if(l %2 != 0 && len %2 != 0)	ans = len / 2 + 1;
    	else ans = len / 2;
    	
    	if(k == 0 && l-r == 0)
    	{
    		if(l > 1)	puts("YES");
    		else puts("NO");
    	}
    	else if(ans <= k)	puts("YES");
    	else puts("NO");
    }
    return 0;
}

C - Meximum Array

For an array a, create the largest array b according to a. the operation is as follows: select the first k numbers, delete them, and add the mex of the first k numbers to b.
The MEX of a set of non negative integers is the minimum value of non negative integers not in the set. For example, M E X ( 1 , 2 , 3 ) = 0 MEX({1,2,3}) =0 MEX(1,2,3)=0 , M E X ( 0 , 1 , 2 , 4 , 5 ) = 3 MEX({0,1,2,4,5}) =3 MEX(0,1,2,4,5)=3.
Output the length and array of b.
Idea: use the map to record the remaining number of the same number, mark the same id of the same group, and add it to the b array every time. You can find the current now++

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int t,n;
int a[N],b[N];
vector<int> ve;
map<int,int> mp;
int main()
{
	ios
    cin>>t;
    int id = 1;//id records the same group
    while(t--)
    {
    	ve.clear();
    	mp.clear();
    	cin>>n;
    	for(int i = 0 ; i < n ; i ++ )	cin>>a[i],mp[a[i]] ++;
    	int now = 0;
    	for(int i = 0 ; i < n ; i ++ )
    	{
    		b[a[i]] = id;//sign
    		mp[a[i]] --;
    		while(b[now] == id)	now ++;//Can be found, now++
    		if(!mp[now])
    		{
    			ve.push_back(now);
    			id ++;//Replace another set
    			now = 0;
    		}
    	}
    	cout<<ve.size()<<"\n";
    	for(auto v:ve)
    	{
    		cout<<v<<" ";
    	}
    	cout<<"\n";
    }
    return 0;
}

D - Peculiar Movie Preferences

Question meaning: give n strings with a length of no more than 3. After deleting any one, ask whether the sequence connection of the remaining strings is a palindrome string
Idea: after thinking, only the following situations can generate palindrome strings

• Only the length is 1 or all consist of 1 letter
• If the length is 2, find the exact opposite without looking at the order, or a combination with the length of 3 appearing earlier, such as abc and ba
• If the length is 3, find the exact opposite without looking at the order, or a combination with the length of 2 appearing earlier, such as ab and cba
  Therefore, open two map s to record, one to record the original string array, and one to record some letters with a length of 3 in front of it, so as to facilitate the judgment of the second case

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int t,n;
string s[N];
map<string,int> mp,mp1;
int main()
{
	ios
    cin>>t;
    while(t--)
    {
    	mp.clear();
    	mp1.clear();//It is required to keep the previous ones in order
    	cin>>n;
    	bool flag = false;
    	for(int i = 0 ; i < n ; i ++ )	cin>>s[i];
    	for(int i = 0 ; i < n ; i ++ )
    	{
    		mp[s[i]] ++;
    		if(s[i].size() == 1)
    		{
    			flag = true;
    			break;
    		} 
    		else if(s[i].size() == 2 && s[i][0] == s[i][1])
    		{
    			flag = true;
    			break;
    		}	
    		else if(s[i].size() == 3 && s[i][0] == s[i][1] && s[i][0] == s[i][2])
    		{
    			flag = true;
    			break;
    		}
    		else if(s[i].size() == 2)
    		{
    			string s1 = "";
    			s1 += s[i][1] , s1 += s[i][0];
    			if(mp[s1] || mp1[s1])
    			{
    				flag = true;
    				break;
    			}	 
    		}
    		else if(s[i].size() == 3)
    		{
    			string s1 = "";
    			s1 += s[i][2] , s1 += s[i][1] , s1 += s[i][0];//Find the opposite
    			string s2 = "";
    			s2 += s[i][0] , s2 += s[i][1];
    			mp1[s2] ++;//For use with length 2 at the back
    			string s3 = "";
    			s3 += s[i][2] , s3 += s[i][1];//Find the length that can be matched in the front is 2
    			if(mp[s1] || mp[s3])
    			{
    				flag = true;
    				break;
    			}
    			
    		}
    	}
    	if(flag)	cout<<"YES";
    	else cout<<"NO";
    	cout<<"\n";
    }
    return 0;
}