Codeforces Round #750 (Div. 2) A.B.C.D

签到四题～～～

题目大意：给定三个整数 a , b , c a,b,c a,b,c，分别表示现在拥有的数字 1 , 2 , 3 1,2,3 1,2,3的个数，至少拥有一个。要求将这堆数字分成两部分，求两部分差值的最小值。

思路分析：首先我们需要明确：由于三个数字至少有一个。那么这些数字一定能够组成 [ 1 , s u m ] [1, sum] [1,sum]之间的全部数字。由于要使插值最小，那么我们需要让两个部分的和尽可能地接近。显然对于 s u m sum sum为偶数的情况下，一定可以组成 s u m 2 frac {sum}{2} 2sum​，此时差值为 0 0 0；对于 s u m sum sum为奇数的情况下，同理可知最小差值为 1 1 1。

#include 
#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();
}

题目分析：给定一个序列，设序列和为 s u m sum sum，要求找出等于 s u m − 1 sum - 1 sum−1子序列个数。

思路分析：我们不从子序列的构造方式考虑，而是从总序列删除元素的角度去考虑：设现在序列中有 c n t 0 cnt_0 cnt0​个 0 0 0， c n t 1 cnt_1 cnt1​个 1 1 1。

• 删除 0 0 0，对序列和无影响，因此 0 0 0任意删，方案总共 2 c n t 0 2^{cnt_0} 2cnt0​种；
• 删除 1 1 1，每次必须删一个且最多删除一个，方案总共 C c n t 1 1 C_{cnt_1}^{1} Ccnt1​1​种。

那么总方案个数就是 C c n t 1 1 × 2 c n t 0 C_{cnt_1}^{1} times 2^{cnt_0} Ccnt1​1​×2cnt0​种。

#include 
#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;
}

题目大意：给定一个字符串，可以删除若干个相同字母，且只能删除同一个字母。求删除若干个该字母后，序列是否为回文序列。

思路分析：枚举 26 26 26个英文字母，每次暴力判断回文串即可。

#include 
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;
}

题目大意：要求对于给定的序列 { a i } {a_i} {ai​}求一个序列 { b i } {b_i} {bi​}，使得 ∑ ( a i × b i ) = 0 sum(a_i times b_i) = 0 ∑(ai​×bi​)=0。

思路分析：需要分奇偶进行讨论：

• 对于长度为偶数的序列，直接反序列元素取相反输出即可；
• 对于长度为奇数的序列，首先将前三个元素构造一个和为 0 0 0乘数序列，然后对于剩下的元素同样对称取相反数输出即可。

奇数长度序列前三个元素的构造方式，需要额外注意判断一下 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 
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 <> t;
    while(t--) solve();
    return 0;
}