A. Subtraction Game

题意

有两个正整数 a,b (a<b)a,b\ (a<b)。
现在有一个游戏：初始有 nn 个石子，每个玩家每回合可以拿走 aa 个或 bb 个石子。
请求出一个 nn，使得在这个状况下，后手必胜。

解法

显然 a+ba+b 一定是一个后手必胜的解。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(int kase){
    int a=read(),b=read();
    printf("%d\n",a+b);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

B. Permutations & Primes

题意

求出一个 1∼n (1≤n≤2⋅105)1\sim n\ (1 \le n \le 2 \cdot 10^5) 的排列，使得满足 MEK⁡(al,…,ar)\operatorname{MEK}(a_l,\dots,a_r) 为质数的二元组 (l,r)(l,r) 最多。

解法

观察到这个区间中必须要包含 11。如果不包含 11，那么 MEK⁡=1\operatorname{MEK}=1，不是质数。所以我们考虑把 11 放在中间。

接下来考虑 22。如果一个区间中有 11 没有 22，那么 MEK⁡=2\operatorname{MEK}=2，是质数，所以我们把 22 放在最左边，这样就满足了右半边的全部都合法。

在考虑包含 22 的区间，如果这个区间里面不含 33，那么 MEK⁡=3\operatorname{MEK}=3，是质数，所以我们把 33 放在最右边，让包含 22 的区间尽量不包含 33。

其他数随便填，不会对答案造成影响。

对于 n≤3n\le 3 的情况直接特判。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;

int ans[N];
void solve(int kase){
    int n=read();
    if(n==1)puts("1");
    else if(n==2)puts("1 2");
    else if(n==3)puts("3 1 2");
    else{
        ans[1]=2;ans[n]=3;
        int pos1 = (1+n)/2;
        ans[pos1]=1;
        int now = 4;
        for(int i=pos1+1;i<n;i++){
            ans[i]=now++;
        }
        for(int i=2;i<pos1;i++){
            ans[i]=now++;
        }
        for(int i=1;i<=n;i++){
            printf("%d ",ans[i]);
        }
        puts("");
    }
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

C. Particles

题意

有 nn 个整数，−109≤ci≤109-10^9 \le c_i \le 10^9，每次操作可以选择一个数删去，然后将它两边的数（如果有）加起来，合并为一个新的数。求出最后剩下的数的最大值。

解法

考虑最后剩下的数是哪些的和。

通过对这个操作进行分析，我们得到了结论：最后剩下的数为奇数/偶数位中选出至少一个数的和。

于是可以把奇数位的正数和偶数位的正数加起来，比大小。如果全是负数，直接特判。

注意开 long long。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
ll a[N];
void solve(int kase){
    int n=read();
    bool flag = 0;
    for(int i=0;i<n;i++){
        a[i]=read();
        if(a[i]>0)flag=1;
    }

    if(!flag){
        printf("%lld\n",*max_element(a,a+n));
        return;
    }

    ll ans1=0,ans2=0;
    for(int i=0;i<n;i++){
        if(a[i]<0)continue;
        if(i%2==0){
            ans1+=a[i];
        }else{
            ans2+=a[i];
        }
    }
    printf("%lld\n",max(ans1,ans2));
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

D. Row Major

题意

给定 n (n≤106)n\ (n\le10^6)，构造长度为 nn 的字符串，使得这个字符串在变形成任意矩阵后都不存在两个相邻字符相同。

要求构造的字符串中不同的字符数最少。

解法

首先不难发现，下标相邻的字符必须不同，即 si≠si+1s_i \ne s_{i+1}。

设 ff 为 nn 的一个因数，那么 si≠si+fs_i \ne s_{i+f}。

我们考虑直接构造一个字符串。设 xx 为最小的不被 nn 整除的整数。
我们可以发现，不同的字符个数至少要 xx 个。（因为 ax≠ax−1,ax≠ax−2,⋯ ,ax≠ax−(x−1)=a1a_x\ne a_{x-1}, a_x\ne a_{x-2}, \cdots, a_x \neq a_{x-(x-1)}=a_1，因此 axa_x 与所有前面的字符都不同）

并且，如果构造一个循环节长度为 xx 的字符串，那么一定是合法的。
证明：在循环节长度为 xx 的字符串中，相邻字符的下标差一定是 kxkx，而 x∤n  ⟹  kx∤nx \nmid n \implies kx \nmid n，所以不会违反规则，一定合法。

复杂度 O(n)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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N = 1e6+5;

void solve(int kase){
    int n=read();
    for(int x=2;x<=26;x++){
        if(n%x!=0){
            for(int i=0;i<n;i++){
                putchar('a'+(i%x));
            }
            puts("");
            return;
        }
    }
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

E. Great Grids

题意

我们称满足如下三个条件的字符矩阵称作伟大矩阵。

  • 任意字符都是 A，B 或 C。
  • 相邻（上下左右）字符不同。
  • 任意 2×22\times 2 子矩阵中都包含 A，B 和 C 三个字母。

现在，给定 kk 组相等关系，要求每组给定的两个格子必须相同，而且给定的格子保证是对角的格子。

求是否有能满足这些相等关系的伟大矩阵。

解法

目标：找规律，我们要找到伟大矩阵的一个充要条件。考虑把 A，B 或 C 看作 0,1,20,1,2，然后分析这个矩阵。

比如说这样一个伟大矩阵。

BABCCBCABABC\begin{matrix} \text{B} &\text{A} &\text{B} &\text{C}\\ \text{C} &\text{B} &\text{C} &\text{A}\\ \text{B} &\text{A} &\text{B} &\text{C}\\ \end{matrix}

我们考虑每个左右和上下格子的差（在模 33 意义下）。

1→20→11→10↓1↓1↓1↓12→21→12→11↓2↓2↓2↓21→20→11→10\begin{matrix} 1 & \xrightarrow{2} & 0 & \xrightarrow{1} & 1 & \xrightarrow{1} & 0\\ \downarrow \scriptsize\!1 & & \downarrow \scriptsize\!1 & & \downarrow \scriptsize\!1 & &\downarrow \scriptsize\!1 \\ 2 & \xrightarrow{2} & 1 & \xrightarrow{1} & 2 & \xrightarrow{1} & 1\\ \downarrow \scriptsize\!2 & & \downarrow \scriptsize\!2 & & \downarrow \scriptsize\!2 & &\downarrow \scriptsize\!2 \\ 1 & \xrightarrow{2} & 0 & \xrightarrow{1} & 1 & \xrightarrow{1} & 0\\ \end{matrix}

可以观察到，上下的箭头相同，左右的箭头相同，且箭头上只有 1,21,2。
这是伟大矩阵的充要条件。

证明：
(⇒)(\Rightarrow) 不妨枚举在每一个 2×22\times 2 矩阵中，右箭头的数字和下箭头的数字，不难发现只要相同，每一个的组合都是合法的伟大矩阵。
(⇐)(\Leftarrow) 不妨枚举在每一个 2×22\times 2 矩阵中，所有的合法伟大矩阵，不难发现数字都相同。

因此，若 (x,y+1)=(x+1,y)(x,y+1)=(x+1,y)，则第 xx 行的箭头和第 yy 列的箭头数字一样。

(x,y)→a(x,y+1)↓a(x+1,y)(x+1,y+1)\begin{matrix} (x,y) & \xrightarrow{a} & (x,y+1) \\ \downarrow \scriptsize\!a & & \\ (x+1,y) & & (x+1,y+1)\\ \end{matrix}

若 (x,y)=(x+1,y+1)(x,y)=(x+1,y+1)，事实上，(x,y)=(x+1,y+1)  ⟺  (x+1,y)≠(x,y+1)(x,y)=(x+1,y+1) \iff (x+1,y)\ne (x,y+1)。则第 xx 行的箭头和第 yy 列的箭头数字不一样。

(x,y)→a(x,y+1)↓b(x+1,y)(x+1,y+1)\begin{matrix} (x,y) & \xrightarrow{a} & (x,y+1) \\ \downarrow \scriptsize\!b & & \\ (x+1,y) & & (x+1,y+1)\\ \end{matrix}

因此，在代码中只需要维护这 kk 组相等或不等关系即可。为此，可以直接进行黑白染色。
建一张带权无向图，边权为 00 代表两端点颜色相同，边权为 11 代表两端点颜色不同。

复杂度 O(n+m+k)O(n+m+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
67
68
69
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}


const int N = 4e3+5;
struct Edge{
    int v,w;
};
vector<Edge> G[N];

int color[N]; // 颜色
bool ok;

void dfs(int u,int c){
    if(color[u]!=-1){
        if(color[u]!=c)ok=0;
        return;
    }
    color[u]=c;
    for(auto e:G[u]){
        dfs(e.v,c^e.w);
    }
}

void solve(int kase){
    int n=read(),m=read(),k=read();
    
    for(int i=1;i<=n+m;i++)G[i].clear();

    for(int i=0;i<k;i++){
        int x1=read(),y1=read(),x2=read(),y2=read();
        int x=x1,y=min(y1,y2)+n;
        int val=(y2==y1+1);
        G[x].push_back({y,val});
        G[y].push_back({x,val});
    }

    ok=1;
    memset(color,-1,sizeof(color));
    for(int i=1;i<=n+m;i++){
        if(color[i]==-1)dfs(i,0);
    }

    if(ok)YES;
    else NO;
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}