Four Checked-in Issues ~~~

A.Luntik and Concerts

Headline: Given three integers a , b , c a,b,c a,b,c, which represent the numbers you have now 1 , 2 , 3 1,2,3 Number of 1,2,3, having at least one. Requires that the stack of numbers be divided into two parts to minimize the difference between the two parts.

Idea analysis: First we need to be clear: because there is at least one of the three numbers. So these numbers must be able to make up [ 1 , s u m ] [1, sum] All numbers between [1,sum]. To minimize the interpolation, we need to make the sum of the two parts as close as possible. Obviously for s u m sum If the sum is even, it must be composed s u m 2 \frac {sum}{2} 2sum, the difference is 0 0 0; about s u m sum If the sum is odd, the minimum difference is similarly known 1 1 1.

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline void solve(){
    int a, b, c; cin >> a >> b >> c;
    int sum = a + b * 2 + c * 3;
    if(sum % 2) puts("1");
    else puts("0"); 
}

signed main(){
    int t = 0; cin >> t;
    while(t--) solve();
}

B.Luntik and Subsequences

Topic Analysis: Given a sequence, set the sequence and as s u m sum sum, requires finding the equal s u m sum Number of sum subsequences.

Idea analysis: We do not consider how the subsequences are constructed, but from the point of view of deleting elements from the total sequence: c n t 0 cnt_0 cnt0 0 0 0， c n t 1 cnt_1 cnt1 1 1 1.

• delete 0 0 0, for sequence and no effect, so 0 0 0 Delete at will, scheme total 2 c n t 0 2^{cnt_0} 2 cnt0 species;
• delete 1 1 1, one must be deleted at a time and at most one must be deleted, total scheme C c n t 1 1 C_{cnt_1}^{1} Ccnt1 1 species.

So the total number of scenarios is C c n t 1 1 × 2 c n t 0 C_{cnt_1}^{1} \times 2^{cnt_0} Ccnt1 1 × 2cnt0 species.

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
inline void solve(){
    int n = 0, cnt0 = 0, cnt1 = 0; cin >> n;
    for(int i = 1; i <= n; i++){
        int num; cin >> num;
        if(num == 1) cnt1++;
        else if(num == 0) cnt0++;
    }
    int ans = cnt1 * (1ll << cnt0);
    cout << ans << endl;
}
 
signed main(){
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}

C.Grandma Capa Knits a Scarf

Headline: Given a string, several identical letters can be deleted, and only one letter can be deleted. Seeks if the sequence is a palindrome sequence after deleting several of the letters.

Idea Analysis: Enumeration 26 26 26 letters in English, each violent judgment palindrome string can be.

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 10, INF = 1e7 + 10;
char str[N];
 
inline int check(int lenn, char ch){
    int l = 1, r = lenn, cnt = 0;
    while(l < r){
        if(str[l] == str[r]){ l++, r--; continue; }
        else if(str[l] != str[r] && str[l] == ch){ l++, cnt++; continue; }
        else if(str[l] != str[r] && str[r] == ch){ r--, cnt++; continue; }
        return INF;
    }
    return cnt;
}
 
inline void solve(){
    int len = 0; cin >> len >> str + 1;
    int ans = INF;
    for(char i = 'a'; i <= 'z'; i++)
        ans = min(ans, check(len, i));
    cout << (ans > N ? -1 : ans) << endl;
}
 
signed main(){
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}

D.Vupsen, Pupsen and 0

Headline: Requires for a given sequence { a i } \{a_i\} {ai} find a sequence { b i } \{b_i\} {bi}, so that ∑ ( a i × b i ) = 0 \sum(a_i \times b_i) = 0 ∑(ai​×bi​)=0.

Idea analysis: Need parity discussion:

• For even-length sequences, the direct reverse sequence elements can be output in the opposite direction.
• For a sequence of odd length, the first three elements are first constructed into a sum of 0 0 0 multiplier sequence, and then the opposite number output is symmetrical for the remaining elements.

How the first three elements of an odd length sequence are constructed requires extra attention a [ 1 ] + a [ 2 ] = = 0 ∣ ∣ a [ 2 ] + a [ 3 ] = = 0 a[1] + a[2] == 0 || a[2] + a[3] == 0 a[1]+a[2]==0_a[2]+a[3]==0.

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N];

inline void solve(){
    int n = 0; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    if(n & 1){
        if(a[1] + a[2] != 0) cout << -a[3] << " " << -a[3] << " " << a[1] + a[2] << " ";
        else if(a[2] + a[3] != 0) cout <<a[2] + a[3]<<" "<< -a[1] << " " << -a[1] << " ";
        else cout << -a[2] << " " << a[1] + a[3] << " " << -a[2] << " ";
        for(int i = 4; i <= 4 + (n - 3) / 2 - 1; i += 1) cout << -a[n - i + 4] << ' ';
        for(int i = 4 + (n - 3) / 2; i <= n; i++) cout << a[n - i + 4] << ' ';
    }
    else{
        for(int i = 1; i <= n / 2; i++) cout << -a[n - i + 1] << ' ';
        for(int i = n / 2 + 1; i <= n; i++) cout << a[n - i + 1] << ' ';
    }
    cout << endl;
}

signed main(){
    int t = 0; cin >> t;
    while(t--) solve();
    return 0;
}