A. Long Comparison

Title: Portal

Question meaning: give two numbers and the number of zeros after these two numbers respectively. Who is bigger and who is smaller after these two combined numbers, output '>', '<' or '=';

Solution idea: direct violent simulation, first look at the number of digits after combination, and then cycle simulation from front to back. I use string to store the previous digits. When the length is the same, add '0' of the same digits to the back of the two strings to avoid crossing the boundary;

AC Code:

void solve(){
    int x, y;
    string s, c;
    cin>>s>>x;
    cin>>c>>y;
    int l1 = s.length()+x, l2 = c.length()+y;
    if(l1 == l2){
        int flag = 0;
        s+="0000000";
        c+="0000000";
       for(int i = 0; i<min(s.length(), c.length()); i++){
           if(s[i]>c[i]){
               flag = 1;
               break;
           }
           if(s[i]<c[i]){
               flag = -1;
               break;
           }
       }
       if(flag == 0){
           puts("=");
       }
       else if(flag == 1){
           puts(">");
       }
       else {
           puts("<");
       }
       return;
    }
    else if(l1>l2){
        puts(">");
        return;
    }
    else{
        puts("<");
        return;
    }
    return;
}
 
int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        solve();
    }
    return 0;
}

B. Absent Remainder

Title: Portal

Topic meaning: a topic with a very simple idea. I haven't seen QAQ at first sight. For group t test samples, give an array a with length N and find n/2 (rounded down) logarithms (x, y), which meet the following requirements:
1,x != y;
2. Both x and y belong to the number in array a;
3. The value of x%y does not belong to array a;

Solution idea: the value of x%y must be less than y. directly find the smallest number in the a array, and then look for n/2 numbers to match them for output. At first glance, I haven't seen this idea. It's really naive;

AC Code:

const int N = 2e5+5;
int a[N];
int st[1000006];
 
bool cmp(int x, int y){
    return x>y;
}
 
void solve(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i<=n; i++) scanf("%d", &a[i]);
    sort(a+1, a+n+1);
    int cnt = 0;
    for(int i = 2; i<=n/2+1; i++){
        printf("%d %d\n", a[i], a[1]);
    }
    return;
}
 
int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        solve();
    }
    return 0;
}

C. Poisoned Dagger

Title: Portal

Meaning: the brave man fights the dragon. For the t group of test samples, an array A and a value h are given each time. h represents the blood volume of the dragon. Array a represents the time when the brave man reaches the ai, he will apply a bleeding debuff to the dragon. The bleeding debuff will cause the dragon to lose a drop of blood every second for K seconds. This debuff will not be superimposed, that is, if the previous debuff is not over, If you apply bleeding debuff to the dragon, then the last debuff state is over. Now what is the minimum k that requires the brave to kill the dragon;

Solution idea: I really feel that this problem is better than the second one. After translation, you can see the wf algorithm used - bisection; For the classic binary answer question, do a binary answer for the value of k, judge whether the function simulates the current value of k to kill the dragon and find the smallest k;

AC Code:

const int N = 105;
ll a[N];
ll n, h;
 
bool check(ll x){
    ll res = 0;
    for(int i = 2; i<=n; i++){
        ll ans = a[i]-a[i-1];
        res+=min(ans, x);
    }
    res+=x;
    if(res>=h) return true;
    else return false;
}
 
void solve(){
    scanf("%lld%lld", &n, &h);
    for(int i = 1; i<=n; i++) scanf("%lld", &a[i]);
    sort(a+1, a+n+1);
    ll l = 1, r = 1e18;
    while(l<r){
        ll mid = l+r>>1;
        if(check(mid)) r = mid;
        else l = mid+1;
    }
    printf("%lld\n", l);
    return;
}
 
int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        solve();
    }
    return 0;
}

D. MEX Sequences

Title: Portal

Question meaning: define MEX(x1... xk) as the smallest non negative integer that does not appear in x1~xk. For t groups of test samples, each group gives an array to find how many subsequences meet the conditions - conditions:

|xi-MEX(x1...xi)|<=1
For example, | x1-mex (x1) | < = 1 when i=1, and | x1-mex (x1) | < = 1 and | x2-mex (x1, x2) | < = 1 when I = 2

Problem solving idea: look at the data range and find the subsequence. It is a dp that has not run (there may also be a higher algorithm). According to the description of the problem, there are only two conditions for forming the subsequence that meets the conditions:
1. The sequence from 0 is monotonic and non decreasing and continuous:
2. In the front, it starts from 0 and is monotonically non decreasing and continuous. In the back, it is several x, several x+2, several x
Similar to: 0, 1, 1, 2, 4, 4, 2, 2, 4, 4

According to these two cases, the state transition equation is derived;
For case 1 (easier to write):

dp1[0] = 1;
For each value x of the array, dp1[x] += dp1[x] (sequence with X-1 in front) + dp[x-1] (sequence without x-1);

For case 2:

For each value x of the array, dp2[x] = 2, dp2[x+2] = 2, each x and x+2 can be put or not put;
And when x is greater than 1, dp2[x] += dp1[x-2] * * is combined;

AC Code:

typedef long long ll;

const int mod = 998244353;
const int N = 5e5+5;

ll dp[2][N];

void solve()
{
	int n;
	scanf("%d", &n);
	dp[0][0] = 1;
	int x;
	for(int i=1; i<=n; i++){
		scanf("%d", &x); x++;
		dp[0][x] = (dp[0][x]*2ll+dp[0][x-1])%mod;
		dp[1][x] = dp[1][x]*2ll%mod;
		dp[1][x+2] = dp[1][x+2]*2ll%mod;
		if(x>=2) dp[1][x] = (dp[1][x]+dp[0][x-2])%mod;
	}
	ll sum = 0;
	for(int i=1; i<=n+1; i++) sum+=dp[0][i]+dp[1][i], sum%=mod;
	printf("%lld\n", sum);
	for(int i = 0; i<=n+1; i++) dp[0][i] = 0, dp[1][i] = 0;
	return;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        solve();
    }
    return 0;
}

Finish scattering flowers!