A. Cipher Shifer

题意

给定一个加密过的字符串，要求求出原串。
加密方法为：对每个字符，在其后添加任意（可能为零）个与其不同的字符后，再多添加一个自己。

解法

显然对于每个字符，只用往后找到第一个与其相等的字符即可。

AC 代码

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
#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 = 105;
char s[N];
void solve(){
    int n=read();
    scanf("%s",s);
    char now = s[0];
    for(int i=1;i<n;i++){
        if(s[i]==now){
            putchar(now);
            now='?';
        }
        else if(now=='?')now=s[i];
    }
    puts("");
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

B. Binary Cafe

题意

有 kk 个物品，编号为 0∼k−10 \sim k-1，编号为 ii 的物品价值 2i2^i 元。
你有 nn 元，请问由几种购买方案？（包括全部都没有买的方案）

1≤n,k≤1091\le n,k \le 10^9

解法

  1. 考虑全部都能买的情况，即 n≥2k−1n\ge 2^k-1，此时每个物品都可以买或不买，一共有 2k2^k 种方案。
  2. 考虑部分能买的方案，此时从 0∼n0 \sim n 元，每一个钱数唯一对应一种购买方案，所以有 n+1n+1 种方案。

最终答案为 min⁡(2k,n+1)\min\left(2^k,n+1\right)。

AC 代码

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
#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")
#define LOCAL

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 n=read(),k=read();
    // 防止溢出
    if(k<=30 && n>=pow(2,k)-1) printf("%d\n",(int)pow(2,k));
    else printf("%d\n",n+1);
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

C. Ski Resort

题意

给定一个序列 a1,a2,a3,…,ana_1, a_2, a_3, \dots, a_n，求出每个数都小于等于 qq，且长度大于等于 kk 的连续区间数。

解法

显然序列的值不用关心，只需要关心是否小于等于 qq。我们先 O(n)O(n) 遍历一遍，找出所有小于等于 qq 的连续区间，长度记为 ll。

  1. l<kl<k：此时没有合法区间
  2. l≥kl\ge k：此时长度为 kk 的区间有 (l−k+1)(l-k+1) 个，长度为 (k+1)(k+1) 的区间有 (l−k)(l-k) 个，故总个数为 ∑i=1l−k+1i=(l−k+2)(l−k+1)2\sum_{i=1}^{l-k+1}i = \dfrac{(l-k+2)(l-k+1)}{2}

AC 代码

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
#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")
#define LOCAL

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 n=read(),k=read(),q=read();

    ll ans = 0;
    int len = 0;
    for(int i=1;i<=n;i++){
        if(read()<=q)len++;
        else{
            if(len>=k){
                int a = 1;
                int b = len-k+1;
                ans += (ll)(a+b)*(b)/2;
            }
            len=0;
        }    
    }
    if(len>=k){
        int a = 1;
        int b = len-k+1;
        ans += (ll)(a+b)*(b)/2;
    }
    printf("%lld\n",ans);
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

D. Wooden Toy Festival

题意

给定一个序列 a1,a2,a3,…,ana_1, a_2, a_3, \dots, a_n，试确定三个整数 x1,x2,x3x_1,x_2,x_3，使

max⁡i=1n{min⁡k=13∣ai−xk∣}\max_{i=1}^{n}\left\{\min_{k=1}^3|a_i-x_k|\right\}

最小。

解法

看到最大值最小问题，显然就是二分答案，接下来我们考虑如何判定能否使 min⁡k=13∣ai−xk∣\min_{k=1}^3|a_i-x_k| 的最大值小于等于 NN。

对序列中的每一个数 aia_i，可接受的区间为 [ai−N,ai+N][a_i-N,a_i+N]，在这个区间中必须要有一个 xkx_k 在其中。

则问题可以转化为区间最少选点问题，复杂度为 O(nlog⁡n)O(n\log n)（因为要排序）。

加上二分答案，总复杂度为 O(nlog⁡nlog⁡M)O(n\log n \log M) (M=109)(M=10^9)。

AC 代码

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
#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")
#define LOCAL

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 n;
int a[N];

bool cmp(const pii& a,const pii& b){
    return a.second<b.second;
}

bool check(int x){
    vector<pair<int,int> > v;
    for(int i=1;i<=n;i++){
        v.push_back({max(1,a[i]-x),min(1000*1000*1000,a[i]+x)});
    }

    sort(begend(v));

    int ed = 0;
    int cnt = 0;
    for(auto s:v){
        if(s.first<=ed)continue;
        else{
            ed = s.second;
            cnt++;
        }
    }
    return cnt<=3;
}

void solve(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    int l=0,r=1e9;
    while(l<r){
        int m = (l+r)>>1;
        if(check(m))r=m;
        else l=m+1;
    }
    printf("%d\n",l);
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

E. Character Blocking

题意

给定两个长度相等的字符串，以及 qq 个操作。第 ii 个操作在第 ii 秒。

一共有三种操作：

  1. 冻结：冻结第 ii 位的字符 tt 秒，在 tt 秒内，这位上的字符不用参与比较。
  2. 交换：交换任意两个未冻结的字符（两个字符可能来自同一个字符串，也可能来自两个字符串）。
  3. 查询：判断两个字符串在现在是否相等。

解法

维护当前不同的位置个数 cntcnt 即可。（维护思想）

  1. 冻结操作：
    如果冻结的那一位上的字符是不相等的，cnt←cnt−1cnt\leftarrow cnt-1。
    然后用一个队列维护所有冻结的位和时间，在每个查询开头判断，如果队首的时间到了就弹出，如果解冻的位上的字符是不相等的，那么 cnt←cnt+1cnt\leftarrow cnt+1。

  2. 交换操作：
    设交换的两位是 p1,p2p_1,p_2。只需要判断这两位之前不同的个数和交换之后不同的个数作比较即可。

  3. 比较操作
    如果 cnt=0cnt=0，输出 YES，否则输出 NO。

AC 代码

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
#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")
#define LOCAL

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;

char s1[N],s2[N];

void solve(){
    scanf("%s%s",s1,s2);

    int cnt = 0;
    int l = strlen(s1);
    for(int i=0;i<l;i++){
        if(s1[i]!=s2[i])cnt++;
    }

    queue<pii> unfz; // 解冻队列
    int t=read(),q=read();
    for(int i=1;i<=q;i++){
        //解冻
        while(unfz.size() && unfz.front().first <= i){
            auto frnt = unfz.front();unfz.pop();
            if(s1[frnt.second] != s2[frnt.second])cnt++;
        }

        int o =read();
        if(o==1){
            int p=read()-1;
            if(s1[p]!=s2[p]){
                cnt--;
                unfz.push({i+t,p});
            }
        }
        else if(o==2){
            int x1=read(),p1=read()-1;
            int x2=read(),p2=read()-1;
            if(p1==p2){
                if(x1==1 && x2==1)swap(s1[p1],s1[p2]);
                if(x1==1 && x2==2)swap(s1[p1],s2[p2]);
                if(x1==2 && x2==1)swap(s2[p1],s1[p2]);
                if(x1==2 && x2==2)swap(s2[p1],s2[p2]);
                continue;
            }
            int before = (int)(s1[p1]!=s2[p1]) + (int)(s1[p2]!=s2[p2]);

            if(x1==1 && x2==1)swap(s1[p1],s1[p2]);
            if(x1==1 && x2==2)swap(s1[p1],s2[p2]);
            if(x1==2 && x2==1)swap(s2[p1],s1[p2]);
            if(x1==2 && x2==2)swap(s2[p1],s2[p2]);

            int after = (int)(s1[p1]!=s2[p1]) + (int)(s1[p2]!=s2[p2]);
            cnt -=  before-after;
        }
        else{
            if(cnt==0)YES;
            else NO;
        }
    }
}


int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

F. Railguns

题意

在 t=0t=0 时刻，你在 (0,0)(0,0)，现在要走到 (n,m)(n,m)。

设你目前在 (i,j)(i,j)，你可以执行三个操作：

  1. 移动到 (i+1,j)(i+1,j)。
  2. 移动到 (i,j+1)(i,j+1)。
  3. 不移动，等待一秒。

同时，在某些时刻会有水平或垂直的激光，总共有 rr 条，在那一时刻不能在激光覆盖区域。

求：最少到达 (n,m)(n,m) 的时间。如果无法到达，输出 -1。

解法

做的时候没想出来第三维这么设计，这样想第三维这样设计果然很方便。

三维 dp。设 dp[i][j][k]dp[i][j][k] 代表目前在 (i,j)(i,j)，停顿了 kk 次是否能到达这个格子。

可以证明，停顿次数不会超过激光条数 rr。（因为每次停顿都是为了躲避某个激光）

则 dp[i][j][k]dp[i][j][k] 代表时刻 t=i+j+kt=i+j+k。

若 tt 时刻有激光经过 (i,j)(i,j)，则 dp[i][j][k]=0dp[i][j][k]=0。

否则 dp[i][j][k]=dp[i][j][k−1] ∣ dp[i−1][j][k] ∣ dp[i][j−1][k]dp[i][j][k]=dp[i][j][k-1] \,|\, dp[i-1][j][k] \,|\, dp[i][j-1][k]。

复杂度 O(nmr2)O(nmr^2)，够过了。

AC 代码

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
#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=1e5+5;
int n,m,r;

struct Node{
    int x,y;
    int t;
};

struct Ray{
    int t,d,coord;
    bool operator<(const Ray& rhs)const{
        return t<rhs.t;
    }
}ray[105];

bool danger(int x,int y,int t){
    for(int i=1;i<=r;i++){
        if(ray[i].t != t)continue;
        if((ray[i].d==1 && ray[i].coord==x)||
           (ray[i].d==2 && ray[i].coord==y))return 1;
    }
    return 0;
}

void solve(){
    n=read(),m=read();
    r=read();
    for(int i=1;i<=r;i++){
        ray[i].t=read();
        ray[i].d=read();
        ray[i].coord=read();
    }
    sort(ray+1,ray+1+r);
    
    vector<vector<vector<bool>>> dp(n+1,vector<vector<bool>>(m+1,vector<bool>(r+1,0)));
    dp[0][0][0]=1;

    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=r;k++){
                if(danger(i,j,i+j+k))continue;

                if(k!=0){ // 从 dp[i][j][k-1] 转移过来
                    dp[i][j][k]=dp[i][j][k]||dp[i][j][k-1];
                }
                if(i!=0){ // 从 dp[i-1][j][k] 转移过来
                    dp[i][j][k]=dp[i][j][k]||dp[i-1][j][k];
                }
                if(j!=0){ // 从 dp[i-1][j][k] 转移过来
                    dp[i][j][k]=dp[i][j][k]||dp[i][j-1][k];
                }
            }
        }
    }


    for(int i=0;i<=r;i++){
        if(dp[n][m][i]){
            printf("%d\n",n+m+i);
            return;
        }
    }
    puts("-1");
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

G1. In Search of Truth (Easy Version)

题意

交互题。有一个 1∼n1\sim n 的排列在圆上。告诉你一开始的数字，每次你可以选择顺时针旋转 kk 个格子或逆时针旋转，然后得到旋转后达到的位置。试求出 nn。

1≤n≤1061\le n \le 10^6，最多不能询问超过 20232023 次。

解法

对于这个问题，有一个询问次数为 2N2\sqrt{N} 的解法（NN 为 nn 最大值）。
具体来说，先询问 N−1\sqrt{N}-1 次顺时针移动 11 个格子，得到 a1,a2,…,aNa_1,a_2,\dots ,a_{\sqrt{N}}，如果 n≤Nn\le \sqrt{N}，此时有重复，就可以得到结果。

然后继续询问顺时针移动 N\sqrt{N} 个格子，如果此时得到的在 a1,a2,…,aNa_1,a_2,\dots ,a_{\sqrt{N}} 之中，那么就可以确定出 nn 的值。这样可以不重不漏的找到所有的 nn。

AC 代码

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

map<int,int> mp;

void solve(){
    int x=read();
    mp[x]=1;
    for(int i=2;i<=1000;i++){
        puts("+ 1");fflush(stdout);
        int x=read();
        if(mp.count(x)){
            printf("! %d\n",i-mp[x]);
            return;
        }
        mp[x]=i;
    }

    for(int i=2;;i++){
        puts("+ 1000");fflush(stdout);
        int x=read();
        if(mp.count(x)){
            printf("! %d\n",1000*i - mp[x]);
            return;
        }
    }
}

int main(){
    solve();
    return 0;
}