0 vs 1

题目大意

zero和one进行一场博弈，每个人会选择最优策略。

给定一个01字符串，zero每轮只能拿走最左边或最右边的0，one每轮只能拿走最左边或最右边的1，不能拿的人输，如果所有字符串都被拿完则平局。

若zero先手，输出游戏结果。

解题思路

模拟+贪心。

设左右两端点分别为l，r

如果f拿（f即zero或one），我们进行分类讨论：

若左右两端不同，则只有唯一选择拿f；

若左右两端都为!f，则f输，!f赢；

若左右两端相同且都为f：

若s[l+1]或s[r-1]也为f，以s[l+1]=f为例，拿l，此时!f无法操作，f赢；

若s[l+1]或s[r-1]都不为f，我们可以贪心的去取①左右两边l+1与其右边构成的!f数量与r-1与其左边构成的!f数量少的那个方向的字符。（原因如下：因为取对方少的那边我才有更多的获胜机会，取少的那边的策略一定比取多的那边策略优，例如左边的少，我取了左边的，此时对方也一定得取左边，一旦我左边没得取了只能取右边，但这过程稿中一旦我出现了连续两个我则赢，但如果我取右边，右边对手数量一定大于等于2，那么我必然还得去左边，不仅让我左边的主动权没了让对方获得了右边的主动权，而且我左边出现2个及以上的情况不能像刚才一样直接获胜，因此此时取左边一定更优），这里还有一个问题如何快速得到①，我们可以先分别从左到右和从右到左预处理出每个字符左右两边连续部分有多少个与自己相同的字符（算上自己）

这样每种情况我们都有确定的选择方向，直接模拟即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

bool multi=1;

char flip(char &f){
    return f=(f=='0'?'1':'0');
}

const int N=1e5+10;
int rcnt[2][N],lcnt[2][N];

void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    string t=s;
    int l=0,r=n-1;
    char f='0';
    int cnt0=0,cnt1=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='0') cnt0++,lcnt[0][i]=cnt0,cnt1=0;
        else cnt1++,lcnt[1][i]=cnt1,cnt0=0;
    }
    cnt0=cnt1=0;
    for(int i=n;i>=1;i--){
        if(s[i]=='0') cnt0++,rcnt[0][i]=cnt0,cnt1=0;
        else cnt1++,rcnt[1][i]=cnt1,cnt0=0;
    }

    while(l<r){
        if(s[l]!=s[r]){
            if(s[l]==f){
                l++;
            }else{
                r--;
            }
        }else{
            if(s[l]!=f){
                cout<<flip(f)<<'\n';
                return;
            }else{
                if(s[l]==s[l+1]||s[r]==s[r-1]){
                    cout<<f<<'\n';
                    return;
                }
                if(rcnt[1-(f-'0')][l+1]>lcnt[1-(f-'0')][r-1]){
                    r--;
                }else{
                    l++;
                }
            }
        }
        flip(f);
    }
    if(l==r){
        if(s[l]==f){
            cout<<-1<<'\n';
        }else{
            cout<<flip(f)<<'\n';
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

Solubility

题目大意

总共n个液体，告诉你m对混溶关系，且这种混溶关系具有传递性，接下来给你k个液体的类型，问是否混溶。

解题思路

注意：这题wa了一发，一时找不到哪里有问题，原来是没读入完就输出return了，导致下一个开始读入的数据是这一轮还没读完的数据导致了RE，犯了一个非常低级的错误，再此将错误写在这。

并查集板子题。m对关系分别做合并集合操作，k个液体分别跟第1个液体判断是否在一个集合即可。

并查集，时间复杂度线性。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

struct DSU {
    vector<int> p, siz;
    DSU(int n) : p(n+1), siz(n+1, 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) {
        return p[x] == x ? x : p[x] = find(p[x]);
    }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        siz[x] += siz[y];
        p[y] = x;
        return true;
    }
    int size(int x) { return siz[find(x)]; }
};

bool multi=1;

void solve(){
    int n,m;
    cin>>n>>m;
    DSU dsu(n);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        dsu.merge(a,b);
    }
    int k;
    cin>>k;
    vector<int> a(k);
    bool f=1;
    for(int i=0;i<k;i++){
        cin>>a[i];
        if(!dsu.same(a[i],a[0])){
            f=0;
        }
    }
    
    cout<<(f?"YES":"NO")<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

Rikka with Square Numbers

题目大意

给定两个不同的数，每次可以对加减一个平方数，问把变成的最小操作次数。

解题思路

当相同时，最小操作显然为（题目保证了不同，所以不用判断）

这里我们令，原问题就转化为将d变为0得最小操作次数

一个偶数的平方：① ③

一个奇数的平方：②

②-①，得：4k+1，它在模4意义下得1

③-②，得，4k+3，它在模4意义下得3

如果d模4得0，，由于d%4==0，因此，则d/2依然是个偶数，

那么2和d/2的平均数不会得到小数，则令平均数为，2或d/2与x的差值为，则，也可以用两个完全平方数加减获得。

也就是说d模4不等于2的情况都可以用两个数的平方加减得到。

接下来讨论的情况：

这里的可能只有2、3两种操作次数的可能，因为如果前面的4k+1再加上一个1的完全平方数就能得到任意模4余2的结果，因此最多3中操作次数的可能。而对于是否能用两次操作获得，我们可以直接枚举所有的平方数与d作差是否仍为平方数。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

bool multi=1;

bool check(int x){
    return((int)sqrt(x)*(int)sqrt(x)==x);
}

void solve(){
    int a,b;
    cin>>a>>b;
    int d=abs(a-b);
    //1的情况
    if(check(d)){
        cout<<1<<'\n';
        return;
    }
    //2的情况
    if(d%4!=2){
        cout<<2<<'\n';
        return;
    }
    for(int i=1;i<=100000;i++){
        if(check(abs(d-i*i))){
            cout<<2<<'\n';
            return;
        }
    }
    //剩下的情况都是3
    cout<<3<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}