The Game of Eating

题目大意

有n个人，m道菜，总共要点k道菜。

给出每个人对每道菜的喜爱度，问如果每个人只考虑最终点的菜使得自己对这些菜的喜爱度之和最大，最终会点到哪些菜，按升序排列。

从第1个人开始点到第n个人，点完后再从第1个人点到第n个人，点到k道菜为止。

解题思路

考虑贪心，每个人考虑菜时，如果后面的人会点自己喜欢的菜，那么它不必考虑这样菜，直接点后面的人不会点的菜中喜爱度最大的菜。

如此可直接转化为倒着贪心点菜，每次取还没点过的喜爱度最大的菜。

复杂度分析

时间复杂度：

参考代码

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
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long ll;
typedef pair<int,int> pii;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=1;
const int N=2e3+10;
bool st[N];
int pos[N];

struct Node{
    int v,id;
    bool operator<(const Node &w){
        return v>w.v;
    }
}a[N][N];

void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) pos[i]=1;
    memset(st,0,(m+1)*sizeof(bool));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j].v;
            a[i][j].id=j;
        }
    }
    for(int i=1;i<=n;i++){
        sort(&a[i][1],&a[i][1+m]);
    }
    int cur=(k-1)%n+1;
    while(k--){
        while(st[a[cur][pos[cur]].id]){
            pos[cur]++;
        }
        st[a[cur][pos[cur]].id]=true;
        cur=((cur-1)+n-1)%n+1;
    }
    for(int i=1;i<=m;i++){
        if(st[i]) cout<<i<<' ';
    }
    cout<<endl;
}

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

    return 0;
}

Square

题目大意

给定一个x，找到一个y，k，使得，输出y

解题思路

观察到k的可能范围只有0~18，而固定k后满足单调性，因此直接枚举k对y做二分。

复杂度分析

时间复杂度：

参考代码

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'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long ll;
typedef pair<int,int> pii;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=1;

int p10[19];

inline int cal(int y,int k){
    return y*y/p10[k];
}

void solve(){
    int x;
    cin>>x;
    for(int k=0;k<=18;k++){//遍历k，二分枚举y
        int l=0,r=1000000000ll;
        while(l<r){
            int mid=l+r>>1;
            if(cal(mid,k)>=x) r=mid;//大于等于
            else l=mid+1;
        }
        if(cal(l,k)==x){
            cout<<l<<endl;
            return;
        }
    }
    cout<<-1<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;	

    p10[0]=1;
    for(int i=1;i<=18;i++) p10[i]=p10[i-1]*10;

    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Link with Chess Game

题目大意

给定一个的棋盘，给定为红、绿、蓝三个棋子的位置（棋子可重叠），两人轮流移动一个棋子到附近的一格，若移动后状态与之前出现过的状态相同则输，对方赢。输出最优策略下谁赢。

解题思路

sg函数打表找规律。

n从1到10遍历，每个n遍历每个棋子可能的状态。考虑状态转移，每次状态转移即取其中一个棋子向附近一个移动并且此时的状态不能已经出现过，记录每个状态所能到达状态的sg值（即这里的数组dp）取mex。

代码如下：

因为这里不需要拆分产生sg值异或操作，所以这里的sg值数组即dp数组定义成了bool类型，减少运行时间同时也使输出结果更加清晰

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
const int N=110;
int dx[6]={1,-1,0,0,0,0},dy[6]={0,0,1,-1,0,0},dz[6]={0,0,0,0,1,-1};
bool dp[N][N][N],vis[N][N][N];

int mex(auto v){
    unordered_set<int> S;
    for(auto it:v){
        S.insert(it);
    }
    for(int i=0;;i++){
        if(!S.count(i)) return i;
    }
}

void calc(int n){
    for(int x=1;x<=n;x++){
        for(int y=1;y<=n;y++){
            for(int z=1;z<=n;z++){
                memset(dp,0,sizeof dp);
                memset(vis,0,sizeof vis);
                auto sg=[&](auto self,int r,int g,int b)->void{
                    set<int> s;
                    vis[r][g][b]=true;
                    for(int k=0;k<6;k++){
                        int X=r+dx[k],Y=g+dy[k],Z=b+dz[k];
                        if(X>=1&&X<=n&&Y>=1&&Y<=n&&Z>=1&&Z<=n&&!vis[X][Y][Z]){
                            self(self,X,Y,Z);
                            s.insert(dp[X][Y][Z]);
                        }
                    }
                    dp[r][g][b]=mex(s);
                };
                sg(sg,x,y,z);
                cout<<"n="<<n<<':'<<x<<' '<<y<<' '<<z<<"->"<<dp[x][y][z]<<endl;
            }
        }
    }
    cout<<endl;
}

void solve(){
    for(int i=1;i<=10;i++){
        calc(i);
    }

    // int n,a,b,c;
    // cin>>n>>a>>b>>c;
    // if(n%2==0||(a+b+c)%2==0){
    //     cout<<"Alice"<<endl;
    // }else{
    //     cout<<"Bob"<<endl;
    // }
}

这里取其中的一部分：

n=1,{x,y,z}=1 1 1->0

n=2,{x,y,z}=1 1 1->1
n=2,{x,y,z}=1 1 2->1
n=2,{x,y,z}=1 2 1->1
n=2,{x,y,z}=1 2 2->1
n=2,{x,y,z}=2 1 1->1
n=2,{x,y,z}=2 1 2->1
n=2,{x,y,z}=2 2 1->1
n=2,{x,y,z}=2 2 2->1

n=3,{x,y,z}=1 1 1->0
n=3,{x,y,z}=1 1 2->1
n=3,{x,y,z}=1 1 3->0
n=3,{x,y,z}=1 2 1->1
n=3,{x,y,z}=1 2 2->0
n=3,{x,y,z}=1 2 3->1
n=3,{x,y,z}=1 3 1->0
n=3,{x,y,z}=1 3 2->1
n=3,{x,y,z}=1 3 3->0
n=3,{x,y,z}=2 1 1->1
n=3,{x,y,z}=2 1 2->0
n=3,{x,y,z}=2 1 3->1
n=3,{x,y,z}=2 2 1->0
n=3,{x,y,z}=2 2 2->1
n=3,{x,y,z}=2 2 3->0
n=3,{x,y,z}=2 3 1->1
n=3,{x,y,z}=2 3 2->0
n=3,{x,y,z}=2 3 3->1
n=3,{x,y,z}=3 1 1->0
n=3,{x,y,z}=3 1 2->1
n=3,{x,y,z}=3 1 3->0
n=3,{x,y,z}=3 2 1->1
n=3,{x,y,z}=3 2 2->0
n=3,{x,y,z}=3 2 3->1
n=3,{x,y,z}=3 3 1->0
n=3,{x,y,z}=3 3 2->1
n=3,{x,y,z}=3 3 3->0

n=4,{x,y,z}=1 1 1->1
n=4,{x,y,z}=1 1 2->1
n=4,{x,y,z}=1 1 3->1
n=4,{x,y,z}=1 1 4->1
n=4,{x,y,z}=1 2 1->1
n=4,{x,y,z}=1 2 2->1
n=4,{x,y,z}=1 2 3->1
n=4,{x,y,z}=1 2 4->1
n=4,{x,y,z}=1 3 1->1
n=4,{x,y,z}=1 3 2->1
n=4,{x,y,z}=1 3 3->1
n=4,{x,y,z}=1 3 4->1
n=4,{x,y,z}=1 4 1->1
n=4,{x,y,z}=1 4 2->1
n=4,{x,y,z}=1 4 3->1
n=4,{x,y,z}=1 4 4->1
n=4,{x,y,z}=2 1 1->1
n=4,{x,y,z}=2 1 2->1
n=4,{x,y,z}=2 1 3->1
n=4,{x,y,z}=2 1 4->1
n=4,{x,y,z}=2 2 1->1
n=4,{x,y,z}=2 2 2->1
n=4,{x,y,z}=2 2 3->1
n=4,{x,y,z}=2 2 4->1
n=4,{x,y,z}=2 3 1->1
n=4,{x,y,z}=2 3 2->1
n=4,{x,y,z}=2 3 3->1
n=4,{x,y,z}=2 3 4->1
n=4,{x,y,z}=2 4 1->1
n=4,{x,y,z}=2 4 2->1
n=4,{x,y,z}=2 4 3->1
n=4,{x,y,z}=2 4 4->1
n=4,{x,y,z}=3 1 1->1
n=4,{x,y,z}=3 1 2->1
n=4,{x,y,z}=3 1 3->1
n=4,{x,y,z}=3 1 4->1
n=4,{x,y,z}=3 2 1->1
n=4,{x,y,z}=3 2 2->1
n=4,{x,y,z}=3 2 3->1
n=4,{x,y,z}=3 2 4->1
n=4,{x,y,z}=3 3 1->1
n=4,{x,y,z}=3 3 2->1
n=4,{x,y,z}=3 3 3->1
n=4,{x,y,z}=3 3 4->1
n=4,{x,y,z}=3 4 1->1
n=4,{x,y,z}=3 4 2->1
n=4,{x,y,z}=3 4 3->1
n=4,{x,y,z}=3 4 4->1
n=4,{x,y,z}=4 1 1->1
n=4,{x,y,z}=4 1 2->1
n=4,{x,y,z}=4 1 3->1
n=4,{x,y,z}=4 1 4->1
n=4,{x,y,z}=4 2 1->1
n=4,{x,y,z}=4 2 2->1
n=4,{x,y,z}=4 2 3->1
n=4,{x,y,z}=4 2 4->1
n=4,{x,y,z}=4 3 1->1
n=4,{x,y,z}=4 3 2->1
n=4,{x,y,z}=4 3 3->1
n=4,{x,y,z}=4 3 4->1
n=4,{x,y,z}=4 4 1->1
n=4,{x,y,z}=4 4 2->1
n=4,{x,y,z}=4 4 3->1
n=4,{x,y,z}=4 4 4->1

n=5,{x,y,z}=1 1 1->0
n=5,{x,y,z}=1 1 2->1
n=5,{x,y,z}=1 1 3->0
n=5,{x,y,z}=1 1 4->1
n=5,{x,y,z}=1 1 5->0
n=5,{x,y,z}=1 2 1->1
n=5,{x,y,z}=1 2 2->0
n=5,{x,y,z}=1 2 3->1
n=5,{x,y,z}=1 2 4->0
n=5,{x,y,z}=1 2 5->1
n=5,{x,y,z}=1 3 1->0
n=5,{x,y,z}=1 3 2->1
n=5,{x,y,z}=1 3 3->0
n=5,{x,y,z}=1 3 4->1
n=5,{x,y,z}=1 3 5->0
n=5,{x,y,z}=1 4 1->1
n=5,{x,y,z}=1 4 2->0
n=5,{x,y,z}=1 4 3->1
n=5,{x,y,z}=1 4 4->0
n=5,{x,y,z}=1 4 5->1
n=5,{x,y,z}=1 5 1->0
n=5,{x,y,z}=1 5 2->1
n=5,{x,y,z}=1 5 3->0
n=5,{x,y,z}=1 5 4->1
n=5,{x,y,z}=1 5 5->0
n=5,{x,y,z}=2 1 1->1
n=5,{x,y,z}=2 1 2->0
n=5,{x,y,z}=2 1 3->1
n=5,{x,y,z}=2 1 4->0
n=5,{x,y,z}=2 1 5->1
n=5,{x,y,z}=2 2 1->0
n=5,{x,y,z}=2 2 2->1
n=5,{x,y,z}=2 2 3->0
n=5,{x,y,z}=2 2 4->1
n=5,{x,y,z}=2 2 5->0
n=5,{x,y,z}=2 3 1->1
n=5,{x,y,z}=2 3 2->0
n=5,{x,y,z}=2 3 3->1
n=5,{x,y,z}=2 3 4->0
n=5,{x,y,z}=2 3 5->1
n=5,{x,y,z}=2 4 1->0
n=5,{x,y,z}=2 4 2->1
n=5,{x,y,z}=2 4 3->0
n=5,{x,y,z}=2 4 4->1
n=5,{x,y,z}=2 4 5->0
n=5,{x,y,z}=2 5 1->1
n=5,{x,y,z}=2 5 2->0
n=5,{x,y,z}=2 5 3->1
n=5,{x,y,z}=2 5 4->0
n=5,{x,y,z}=2 5 5->1
n=5,{x,y,z}=3 1 1->0
n=5,{x,y,z}=3 1 2->1
n=5,{x,y,z}=3 1 3->0
n=5,{x,y,z}=3 1 4->1
n=5,{x,y,z}=3 1 5->0
n=5,{x,y,z}=3 2 1->1
n=5,{x,y,z}=3 2 2->0
n=5,{x,y,z}=3 2 3->1
n=5,{x,y,z}=3 2 4->0
n=5,{x,y,z}=3 2 5->1
n=5,{x,y,z}=3 3 1->0
n=5,{x,y,z}=3 3 2->1
n=5,{x,y,z}=3 3 3->0
n=5,{x,y,z}=3 3 4->1
n=5,{x,y,z}=3 3 5->0
n=5,{x,y,z}=3 4 1->1
n=5,{x,y,z}=3 4 2->0
n=5,{x,y,z}=3 4 3->1
n=5,{x,y,z}=3 4 4->0
n=5,{x,y,z}=3 4 5->1
n=5,{x,y,z}=3 5 1->0
n=5,{x,y,z}=3 5 2->1
n=5,{x,y,z}=3 5 3->0
n=5,{x,y,z}=3 5 4->1
n=5,{x,y,z}=3 5 5->0
n=5,{x,y,z}=4 1 1->1
n=5,{x,y,z}=4 1 2->0
n=5,{x,y,z}=4 1 3->1
n=5,{x,y,z}=4 1 4->0
n=5,{x,y,z}=4 1 5->1
n=5,{x,y,z}=4 2 1->0
n=5,{x,y,z}=4 2 2->1
n=5,{x,y,z}=4 2 3->0
n=5,{x,y,z}=4 2 4->1
n=5,{x,y,z}=4 2 5->0
n=5,{x,y,z}=4 3 1->1
n=5,{x,y,z}=4 3 2->0
n=5,{x,y,z}=4 3 3->1
n=5,{x,y,z}=4 3 4->0
n=5,{x,y,z}=4 3 5->1
n=5,{x,y,z}=4 4 1->0
n=5,{x,y,z}=4 4 2->1
n=5,{x,y,z}=4 4 3->0
n=5,{x,y,z}=4 4 4->1
n=5,{x,y,z}=4 4 5->0
n=5,{x,y,z}=4 5 1->1
n=5,{x,y,z}=4 5 2->0
n=5,{x,y,z}=4 5 3->1
n=5,{x,y,z}=4 5 4->0
n=5,{x,y,z}=4 5 5->1
n=5,{x,y,z}=5 1 1->0
n=5,{x,y,z}=5 1 2->1
n=5,{x,y,z}=5 1 3->0
n=5,{x,y,z}=5 1 4->1
n=5,{x,y,z}=5 1 5->0
n=5,{x,y,z}=5 2 1->1
n=5,{x,y,z}=5 2 2->0
n=5,{x,y,z}=5 2 3->1
n=5,{x,y,z}=5 2 4->0
n=5,{x,y,z}=5 2 5->1
n=5,{x,y,z}=5 3 1->0
n=5,{x,y,z}=5 3 2->1
n=5,{x,y,z}=5 3 3->0
n=5,{x,y,z}=5 3 4->1
n=5,{x,y,z}=5 3 5->0
n=5,{x,y,z}=5 4 1->1
n=5,{x,y,z}=5 4 2->0
n=5,{x,y,z}=5 4 3->1
n=5,{x,y,z}=5 4 4->0
n=5,{x,y,z}=5 4 5->1
n=5,{x,y,z}=5 5 1->0
n=5,{x,y,z}=5 5 2->1
n=5,{x,y,z}=5 5 3->0
n=5,{x,y,z}=5 5 4->1
n=5,{x,y,z}=5 5 5->0

容易发现，n为偶数时或x+y+z为偶数时，sg值为1即先手必胜，否则先手必败。

复杂度分析

时间复杂度:

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(){
    // for(int i=1;i<=10;i++){
    //     calc(i);
    // }

    int n,a,b,c;
    cin>>n>>a>>b>>c;
    if(n%2==0||(a+b+c)%2==0){
        cout<<"Alice"<<endl;
    }else{
        cout<<"Bob"<<endl;
    }
}

Link with Centrally Symmetric Strings

题目大意

给定一个字符串，问这个串是否有多个连续的中心对称的子串构成。

字母o,s,x,z是中心对称的；若字符串S中心对称，那么bSq∣dSp∣pSd∣qSb∣nSu∣uSn∣oSo∣sSs∣xSx∣zSz|也中心对称。

解题思路

i从左往右遍历，考虑能与当前位置右侧能构成中心对称的最近子串，若能i跳到该子串右侧（若i位置字符中心对称，i跳到下一位置），若都不能则原串不是中心对称字符串。

按照这个思路，从左往右哈希，然后把所有能构成一对中心对称的字符变成一对中的另一个，再从右往左哈希，即可O（1）判断一段区间从左往右和从右往左的哈希值是否相等来判断是否中心对称。

复杂度分析

时间复杂度：O(n)

参考代码

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long LL;
typedef pair<int,int> PII;
typedef unsigned long long ULL;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=1;
const int N=1e6+10,P=131;
ULL h1[N],p1[N];
ULL h2[N],p2[N];
char s1[N],s2[N];
unordered_map<char,char> mp={{'b','q'},{'d','p'},{'p','d'},{'q','b'},{'n','u'},{'u','n'},{'o','o'},{'s','s'},{'x','x'},{'z','z'}};//记录所有形成中心对称的一对字符
int n;

void init1(char s[]){
    p1[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        h1[i] = h1[i - 1] * P + s[i];
        p1[i] = p1[i - 1] * P;
    }
}

void init2(char s[]){
    p2[n+1] = 1;
    for (int i = n; i >=1; i -- )
    {
        h2[i] = h2[i + 1] * P + s[i];
        p2[i] = p2[i + 1] * P;
    }
}

ULL get1(int l, int r)
{
    return h1[r] - h1[l - 1] * p1[r - l + 1];
}

ULL get2(int l, int r)
{
    return h2[l] - h2[r + 1] * p2[n+1-(r - l + 1)];
}

void solve(){
    cin>>s1+1;
    n=strlen(s1+1);

    init1(s1);//正序哈希

    for(int i=1;i<=n;i++){
        if(mp.find(s1[i])!=mp.end()) s2[i]=mp[s1[i]];
        else s2[i]=s1[i];
    }

    init2(s2);//逆序哈希

    for(int i=1;i<=n;i++){
        if(s1[i]=='o'||s1[i]=='s'||s1[i]=='x'||s1[i]=='z'){
            continue;
        }
        if(mp.find(s1[i])==mp.end()){//遇到不可能形成中心对称的字符直接No
            cout<<"No"<<endl;
            return;
        }
        int j=i;
        while(j<=n){
            if(mp.find(s1[i])==mp.end()){//遇到不可能形成中心对称的字符直接No
                cout<<"No"<<endl;
                return;
            }
            if(get1(i,j)==get2(i,j)){
                i=j;
                break;
            }
            j++;
        }
        if(j>n){//i往右找不到能形成中心对称的区间
            cout<<"No"<<endl;
            return;
        }
    }
    cout<<"Yes"<<endl;
}

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

    return 0;
}

0 and 1 in BIT

题目大意

给定一个n，m分别表示事件长度和询问次数，然后给定n个事件，然后给出q次在线询问，每次询问给出tl，tr，x，根据所给表达式算出真正的l，r，求x经过事件l分别做到事件r后的值。

事件有A或B，A表示将x的0、1翻转，B表示将x加1，若进位后超出x的总长度，则变成全0。

解题思路

模拟易得，一个数翻转后加1再翻转即原数减1，那么我们只需要知道从l到r总共加了翻转了几次，又加减了几个1。

直接预处理事件，遇到B时按照前面A的奇偶性判断是加1还是减1，然后计算B事件的加减1的前缀和，再预处理A事件数量的前缀和，使得每次可以直接获取l到r的B事件的贡献以及翻转次数。

然后对于每次询问将x转化为十进制进行运算再转换为二进制输出。

复杂度分析

时间复杂度：O(n+q|x|)

参考代码

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
78
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long ll;
typedef pair<int,int> pii;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=0;
const int N=2e5+10;
int n,q;
char s[N];
int sum[N];
int cnt[N];

void solve(){
    cin>>n>>q;
    cin>>s+1;
    int flag=1;
    for(int i=1;i<=n;i++){
        if(s[i]=='A'){//预处理B事件的前缀贡献
            sum[i]=sum[i-1];
            flag=-flag;
        }else{
            sum[i]=sum[i-1]+flag;
        }
        cnt[i]=cnt[i-1]+(s[i]=='A');//预处理A事件的数量
    }
    int lares=0;
    while(q--){
        int tl,tr;
        string x;
        cin>>tl>>tr>>x;
        int qn=(int)x.size();
        int l=min((lares^tl)%n+1,(lares^tr)%n+1);
        int r=max((lares^tl)%n+1,(lares^tr)%n+1);
        int num=0;
        int tmp=1;
        int mod=(int)(1ll<<qn);
        for(int i=(int)x.size()-1;i>=0;i--){//将x转换为十进制
            num+=(x[i]=='1')*tmp;
            tmp*=2;
        }
        
        int tt=sum[r]-sum[l-1];
        if(cnt[l-1]%2==1){//例如我从l开始，那么每碰到A之前的B应该是加1的贡献，而由于前面的A的数量为奇数，而会变成加一的贡献，因此需要特判
            tt=-tt;
        }
        int res=((num+tt%mod)%mod+mod)%mod;
        if((cnt[r]-cnt[l-1])%2==1){//若l到r中A事件数量为奇数，则需要对x的01翻转。
            res=mod-1-res;
        }
        lares=res;
        for(int i=qn-1;i>=0;i--){
            cout<<(res>>i&1);
        }
        cout<<endl;
    }
}

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

    return 0;
}

Link with Gomoku

题目大意

给定两个数n,m，要求你构造出一个n*m大小的平局的五子棋棋盘，黑棋用’x’表示，白棋用’o’表示。

1<=n,m<=1e3

解题思路

这里要注意两个点：不能横竖斜出现连续五个相同颜色棋子；黑棋数量应等于白棋，或比白棋多一个。

我们可以先构造这样的情况：

xoxoxoxoxoxoxo

oxoxoxoxoxoxox

xoxoxoxoxoxoxo

…….

但由于斜角会出现连续5个相同颜色棋子，我们可以考虑每四行交换其中的两行。这是就得考虑n的行数，因为我们不能交换最后一行最后一行的下一行，否则就会出现白棋数量多于黑棋的情况。

那么如果n%4!=2，那么我们每次都交换每4行中的2、3两行，否则我们每次都交换每4行中的1、2两行。

复杂度分析

时间复杂度：O(n*m）

参考代码

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
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long ll;
typedef pair<int,int> pii;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=1;
const int N=1010;
char s[N][N];

void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){//先构建出每个相邻两个棋子不同的情况
        for(int j=0;j<m;j++){
            if(i%2==0){
                s[i][j]=((j%2==0)?'x':'o');
            }else{
                s[i][j]=((j%2==0)?'o':'x');
            }
        }
    }
    int t;//根据n来设定t，t表示每四行中的t,t+1行要交换，但因为我从0开始，所以t都相应的减1了
    if(n%4!=2){
        t=1;
    }else{
        t=0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i%4==t||i%4==t+1){//交换即分别取反
                s[i][j]=(char)('o'+'x'-s[i][j]);
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<s[i][j];
        }
        cout<<endl;
    }
}

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

    return 0;
}

Box

题目大意

给定一排数量为n的盒子，告诉你每个盒子的价值和上面是否有一个盖子，每个盖子可以往左或往右移动一格或不动，移动后若该盒子上有盖子则可以获得这个盒子的价值，问价值总和的最大值。

解题思路

dp状态机模型，每个盖子有3种状态，分别是左移、不变和右移。

那么我们可以预处理出所有盒子的位置数组c，对这个数组做dp，考虑状态的转移。

将左边那个盒子与这个盒子的距离分别为1，2和大于2的三种情况讨论状态的转移。

表示第i个盒子向左（j=0)、不变(j=1)、向右(j=2)

复杂度分析

时间复杂度：O（n)

参考代码

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
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long ll;
typedef pair<int,int> pii;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=0;
const int N=1e6+10;
int a[N];
int b[N];
int dp[N][3];

void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    vector<int> c;
    c.push_back(-5);//为了不用考虑边界情况使c从1开始遍历，前面多加了一个元素
    for(int i=1;i<=n;i++){
        if(b[i]==1){
            c.push_back(i);//找到所有b[i]=1时的位置
        }
    }
    int tot=(int)c.size()-1;
    for(int i=1;i<=tot;i++){//对c数组进行dp
        if(c[i-1]+1==c[i]){
            dp[i][0]=dp[i-1][0]+a[c[i]-1];
            dp[i][1]=max({max(dp[i-1][0],dp[i-1][1])+a[c[i]],dp[i-1][2]});
            dp[i][2]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+a[c[i]+1];
        }else if(c[i-1]+2==c[i]){
            dp[i][0]=max(max(dp[i-1][0],dp[i-1][1])+a[c[i]-1],dp[i-1][2]);
            dp[i][1]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+a[c[i]];
            dp[i][2]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+a[c[i]+1];
        }else{
            for(int j=0;j<3;j++){
                dp[i][j]=max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+a[c[i]+j-1];
            }
        }
    }
    //由于c数组中第0位和第n+1位对应的a值都为0，显然不是最优解，在dp取max中会舍弃这种情况，所以无需特判。
    cout<<max({dp[tot][0],dp[tot][1],dp[tot][2]})<<endl;
}

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

    return 0;
}