A.

13/31，17/71，37/73，随便怎么样，我的暴力也过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
  string s;
  cin >> s;
  int n=9;
  rp(i,n)rep(j,i+1,n){
    int x=s[i]-'0';
    int y=s[j]-'0';
    int k=x*10+y;
    if(isprime(k)){
      cout<<k<<"\n";
      return;
    }
  }
  cout<<"-1\n";
}

B.

只要找到相同位置的 “01” 就可以了，随便怎么样，我的暴力也过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve() {
  string s,t;
  cin>>s>>t;
  int n=sz(s);
  vc<vi> p(n);
  rp(i,n)rep(j,i,n){
    char c=s[i];
    if(s[i]==c && s[j]==c && t[i]==c && t[j]==c) {
      p[i].pb(j);
    }
  }
  vi ok(n+1);
  ok[0]=1;
  rp(i,n){
    for(auto j:p[i])ok[j+1]|=ok[i];
  }
  if(ok.back()){
    cout<<"YES\n";
  }else{
    cout<<"NO\n";
  }
}

C.

在没有 0 1 的时候是不知道状态的，我们考虑将第 $c$ 个 ‘+’ 当成 $c$ 放进栈里面。然后每次 1 操作可以动态查询里面有没有负数，如果有，就已经冲突了。否则我们锁定当前栈里的全是正数。然后 $0$ 的时候就看有没有被锁定过。然后贪心的改最后一个就可以了。

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
void solve() {
  string s;
  cin>>s;
  int n=sz(s);
  vi a;
  int c=1;
  bool ok=true;
  vi t(n+1);
  int neg=0;
  int mx=0;
  rp(i,n){
    if(s[i]=='+'){
      a.pb(c);
      c+=1;
    }
    if(s[i]=='-'){
      if(a.back()<0)neg--;
      a.pop_back();
    }
    if(s[i]=='1'){
      if(neg>0){
        ok=false;
        break;
      }
      if(sz(a)) cmax(mx,a.back());
    }
    if(s[i]=='0'){
      if(a.size()<=1){
        ok=false;
        break;
      }
      if(a.back()>0&&a.back()<=mx){
        ok=false;
        break;
      }
      if(a.back()>0) a.back()=-a.back(),neg++;
    }
  }
  if(ok){
    cout<<"YES\n";
  }else{
    cout<<"NO\n";
  }
}

D.

比较容易的 D，就考虑一次操作只能改变相邻两个的大小关系。

然后就是一段绝对值减，一段绝对值增，最后对前面那一段进行-1。

当然不要忘记只有一段的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve() {
  int n;
  cin>>n;
  vi a(n);
  rp(i,n)cin>>a[i];
  int asd=0;
  rep(i,1,n)if(a[i-1]>=a[i])++asd;
  int ans=asd;
  int dec=0;
  for(int i=1;i<n;i++){ // [0,i), [i,n)
    if(a[i-1]>=a[i])--asd;
    cmin(ans,dec+asd+1);
    if(a[i-1]<=a[i])++dec;
  }
  cmin(ans,dec+1);
  cout<<ans<<"\n";
}

E.

考虑几种我知道的做法。

  • 第一种，将 $dp_{i,j,k}$ 定义为考虑了 $i$ 个数字，后 $j$ 个数字互不相同，已经分成了 $k$ 段。
  • 第二种，考虑只管 $dp_{i,j}$，当 $j=K$ 的时候直接让丢给 $ans$，每次计算 ans 的时候 $\times K$（其实就是差分。）
  • 第三种，考虑 $F_i$ 为 $i$ 结尾刚好构成一个 $[1,k]$ 的排列且 $[1,i)$ 没有构成长度为 $k$ 的排列的方案数。令 $F$ 是一个多项式，然后答案就是 $\sum x^i \times k^{n-i}$。

F.

https://www.luogu.com.cn/blog/jiangly/educational-codeforces-round-154-rated-for-div-2-post