CFR-843(Div.2)解题报告

发表于 分类于

比赛传送门

C. Interesting Sequence

题意：给你 n,xn,x，求最小的 m≥nm\ge n，使 n&(n+1)&(n+2)&⋯&m=xn\&(n+1)\&(n+2)\&\cdots\&m=x，或判断无解。

首先每一位独立，分别考虑。与运算每一位都越来越小，所以 xx 的每一位都不能大于 nn，否则直接无解。于是一位的情况只剩 n0x0,n1x0,n1x1 这三种情况。对于第一种 n0x0 的情况，任意 mm 都合法，因为 nn 这一位不会从 00 变成 11。对于第二种情况，要求选的 mm 足够大，使得能够将 nn 这一位 1->0。对于第三种情况，要求选的 mm 足够小，使得不能将 nn 这一位 1->0。处理出每一位 nn 为 11 的位要想改变成 00 的 mm 的分界线，最后合并信息即可。

By jiangly

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

using i64 = long long;

void solve() {
    i64 n, x;
    std::cin >> n >> x;

    std::vector<i64> f(60);
    for (int i = 0; i < 60; i++) {
        if (~n >> i & 1) {
            f[i] = n;
        } else {
            f[i] = (n & ~((1LL << i) - 1)) + (1LL << i);
        }
    }

    i64 m = n;
    for (int i = 0; i < 60; i++) {
        if (~x >> i & 1) {
            m = std::max(m, f[i]);
        }
    }
    for (int i = 0; i < 60; i++) {
        if (x >> i & 1) {
            if (m >= f[i]) {
                std::cout << -1 << "\n";
                return;
            }
        }
    }

    std::cout << m << "\n";
}

D. Friendly Spiders

题意：有 nn 个点，有点权，两个点之间有边当且仅当这两个点的点权不互质。给定两个点，输出最短路。

两个点的点权不互质等价于有公共的质因数，于是可以考虑质因数分解，并对每个质数建虚点。如果两个点同时连向一个虚点就相当于连边。在此图上跑 01BFS 或 Dijkstra 即可。

By SSRS_

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
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }
  int s, t;
  cin >> s >> t;
  s--;
  t--;
  int MAX = 0;
  for (int i = 0; i < n; i++){
    MAX = max(MAX, a[i]);
  }
  MAX++;
  vector<vector<int>> E(n + MAX * 3);
  for (int i = 0; i < n; i++){
    E[i].push_back(n + a[i]);
  }
  for (int i = 2; i < MAX; i++){
    for (int j = i; j < MAX; j += i){
      E[n + j].push_back(n + MAX + i);
      E[n + MAX + i].push_back(n + MAX * 2 + j);
    }
  }
  for (int i = 0; i < n; i++){
    E[n + MAX * 2 + a[i]].push_back(i);
  }
  vector<int> d(n + MAX * 3, -1);
  d[s] = 0;
  vector<int> p(n + MAX * 3, -1);
  queue<int> Q;
  Q.push(s);
  while (!Q.empty()){
    int v = Q.front();
    Q.pop();
    for (int w : E[v]){
      if (d[w] == -1){
        d[w] = d[v] + 1;
        p[w] = v;
        Q.push(w);
      }
    }
  }
  if (d[t] == -1){
    cout << -1 << endl;
  } else {
    vector<int> ans;
    for (int v = t; ; v = p[v]){
      if (v < n){
        ans.push_back(v);
      }
      if (v == s){
        break;
      }
    }
    reverse(ans.begin(), ans.end());
    t = ans.size();
    cout << t << endl;
    for (int i = 0; i < t; i++){
      cout << ans[i] + 1;
      if (i < t - 1){
        cout << ' ';
      }
    }
    cout << endl;
  }
}

E. The Human Equation

题意：有一个数组，每次操作可以选一个子序列，将其所有奇数项 +1+1、偶数项 −1-1，或偶数项 +1+1、奇数项 −1-1。问最少多少次操作能变为全 00。n≤2×105,∣a∣≤109n\le 2\times 10^5,|a|\le 10^9。

做法一

首先变为全零一定可行，因为可以每次只选一位单独加或减。选子序列的操作看起来非常复杂，没法直接操作，于是先找一找性质。

首先可以发现已经为 00 的项永远不会操作，因为一次操作后变成非零，还要操作变回来，两次操作通过改变一些顺序可以省掉改变 00 的操作。于是现在只有正负两种数，考虑将连续的极长同号元素分段，一段正一段负，则思考可以发现，同一段内操作哪个元素是等价的，所以可以将一段用它们的和代替。

此时，每次操作一定是全选整个数组（正负交替），进行若干次逼近 00 的操作直至数组中出现 00（操作次数为元素的最小绝对值），然后把 00 段删掉，合并相邻两段，反复操作即可。实现上，可以用链表维护段，并用 set<pair> 或 map<set> 维护每个值在链表上的对应位置，从小到大处理即可。

By cxm1024

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int v[600010],lst[600010],nxt[600010],cnt=0;
signed main() {
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        vector<int> a;
        for(int i=1;i<=n;i++) {
            int x;
            cin>>x;
            if(x==0) continue;
            if(a.empty()||(a.back()>0)!=(x>0)) a.push_back(x);
            else a.back()+=x;
        }
        map<int,set<int> > mp;
        int lstt=0;
        for(int x:a) {
            v[++cnt]=abs(x),lst[cnt]=lstt,nxt[cnt]=cnt+1,lstt=cnt;
            mp[abs(x)].insert(cnt);
        }
        nxt[cnt]=0;
        int ans=0;
        for(auto &[x,s]:mp) {
            ans=max(ans,x);
            while(!s.empty()) {
                int tmp=*s.begin();
                s.erase(s.begin());
                if(v[tmp]==0) continue;
                v[tmp]=0;
                int l=lst[tmp],r=nxt[tmp];
                nxt[l]=lst[r]=0;
                if(l!=0&&r!=0) {
                    v[++cnt]=v[l]+v[r]-x;
                    mp[v[l]].erase(l),mp[v[r]].erase(r);
                    mp[v[cnt]].insert(cnt);
                    lst[cnt]=lst[l],nxt[cnt]=nxt[r];
                    if(lst[cnt]) nxt[lst[cnt]]=cnt;
                    if(nxt[cnt]) lst[nxt[cnt]]=cnt;
                }
            }
        }
        cout<<ans<<endl;
        while(cnt) v[cnt]=lst[cnt]=nxt[cnt]=0,cnt--;
    }
    return 0;
}

做法二

考虑进行操作之后其前缀和数组会怎样变化。如果第一位从 +1+1 开始，则为每个相邻 [+1,−1)[+1,-1) 的位置区间 +1+1；如果第一位从 −1-1 开始，则为每个相邻 [−1,+1)[-1,+1) 的位置区间 −1-1。由于 +1,−1+1,-1 的位置可以任意选，前缀和数组也可以任意修改，每次选任意段独立区间 +1+1 或 −1-1。于是，每次操作可以将前缀和中全体正数都 −1-1，或全体负数都 +1+1，答案即为“正数的最大值”加上“负数的最小值的绝对值”，即数组的 max⁡−min⁡\max-\min。

By jiangly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<i64> s(n + 1);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + a[i];
    }

    auto ans = *std::max_element(s.begin(), s.end()) - *std::min_element(s.begin(), s.end());
    std::cout << ans << "\n";
}

F. Laboratory on Pluto

题意：在网格中按照网格放单位正方形可以构成一些图形，问在面积为 nn 时的最小周长，以及形成该最小周长的方案数（不考虑旋转，只要正面看不同就不同）。T≤2×105,n≤4×105T\le 2\times 10^5,n\le 4\times 10^5。

思考可以发现，图案一定趋近于类似正方形的形状（也可能是非常接近正方形的长方形），并从角上去掉多余的格子。对于最小周长，可以从严格正方形附近枚举几个长度取最小值（事实上正方形一定是最小值，附近的长方形可能与其相等）。问题转化为，确定了一些长方形 p×qp\times q，删掉角上若干个方块的方案数。首先有一个性质，删掉的多余方块数量 m<p,qm<p,q，否则可以删掉一行/一列让周长减小，这个性质保证各个角删除方块不会冲突，因为删除方块连不起两个角来。考虑每行左边/右边删的方块数量，一定是单调非增/非降的，等价于非降。问题即为选四个非降序列，和为 nn 的方案数。接下来用 DP 求方案数。

做法一

考虑如下 DP：f[i][j]f[i][j] 表示和为 ii，最后一个数为 jj 的方案数，则 f[i][j]=∑k≤jf[i−1][k]f[i][j]=\sum\limits_{k\le j} f[i-1][k]。其中求和操作可以用前缀和省掉。算完一个角后，进行一次卷积可以得到两个角：g[i]=∑f[j]∗f[i−j]g[i]=\sum{f[j]*f[i-j]}（因为两个角是独立的，所以相乘），再进行一次即可得到四个角。

By cxm1024

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[670][670],s[670][670],g[670],h[670];
int sqt(int x) {
    int res=sqrt(x);
    while(res*res<x) res++;
    while((res-1)*(res-1)>=x) res--;
    return res;
}
signed main() {
    int t,u,m=998244353;
    cin>>t>>u;
    if(u==2) cin>>m;
    f[0][0]=s[0][0]=1;
    for(int j=1;j<=660;j++) s[0][j]=1;
    for(int i=1;i<=660;i++) {
        for(int j=1;j<=i;j++)
            (f[i][j]+=s[i-j][j])%=m;
        for(int j=1;j<=660;j++)
            s[i][j]=(s[i][j-1]+f[i][j])%m;
    }
    for(int i=0;i<=660;i++)
        for(int j=0;j<=i;j++)
            (g[i]+=s[j][660]*s[i-j][660]%m)%=m;
    for(int i=0;i<=660;i++)
        for(int j=0;j<=i;j++)
            (h[i]+=g[j]*g[i-j]%m)%=m;
    while(t--) {
        int n;
        cin>>n;
        int tmp=sqt(n),x=tmp+(n+tmp-1)/tmp;
        vector<pair<int,int> > v;
        for(int i=0;i<=100;i++) {
            int p=tmp+i,q=(n+p-1)/p;
            if(p+q<x) v.clear(),v.push_back({p,q}),x=p+q;
            else if(p+q==x) v.push_back({p,q});
        }
        if(u==1) {
            auto [p,q]=v[0];
            cout<<p<<" "<<q<<endl;
            for(int i=1;i<=p*q;i++) {
                if(i<=n) cout<<"#";
                else cout<<".";
                if(i%q==0) cout<<endl;
            }
            continue;
        }
        int ans=0;
        for(auto [p,q]:v)
            (ans+=h[p*q-n]*(p!=q?2:1)%m)%=m;
        cout<<x*2<<" "<<ans<<endl;
    }
    return 0;
}

做法二

考虑交换 DP 的两维：f[i][j]f[i][j] 表示当前序列考虑只添加 1∼i1\sim i，和为 jj 的方案数，则 f[i][j]=∑kf[i−1][j−ki]f[i][j]=\sum\limits_k f[i-1][j-ki]（即考虑在 1∼i−11\sim i-1 的基础上添加 kk 个 ii，kk 可以等于 00）。用完全背包的优化转化为 f[i][j]=f[i−1][j]+f[i][j−i]f[i][j]=f[i-1][j]+f[i][j-i]。对于四个角，设 f[i][x][j]f[i][x][j] 表示当前考虑只添加 1∼i1\sim i，但是只考虑前 xx 个角能添加 ii（1∼i−11\sim i-1 全部考虑完），则 f[i][x][j]=f[i][x−1][j]+f[i][x][j−i]f[i][x][j]=f[i][x-1][j]+f[i][x][j-i]。由于转移的单调性，可以省掉 i,xi,x 两维，优化空间和代码难度。

By cxm1024 From jiangly

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
#include<bits/stdc++.h>
using namespace std;
int f[670];
int sqt(int x) {
    int res=sqrt(x);
    while((res+1)*(res+1)<=x) res++;
    while(res*res>x) res--;
    return res;
}
signed main() {
    int t,u,m;
    cin>>t>>u;
    if(u==2) {
        cin>>m;
        f[0]=1;
        for(int i=1;i<=660;i++)
            for(int x=1;x<=4;x++)
                for(int j=i;j<=660;j++)
                    (f[j]+=f[j-i])%=m;
    }
    while(t--) {
        int n;
        cin>>n;
        int x=sqt(n),y=(n+x-1)/x;
        if(u==1) {
            cout<<x<<" "<<y<<endl;
            for(int i=1;i<=x*y;i++) {
                if(i<=n) cout<<"#";
                else cout<<".";
                if(i%y==0) cout<<endl;
            }
            continue;
        }
        while((x+1)*(y-1)>=n) x++,y--;
        int ans=0;
        while(1) {
            (ans+=f[x*y-n]%m)%=m;
            if((x-1)*(y+1)>=n) x--,y++;
            else break;
        }
        cout<<(x+y)*2<<" "<<ans<<endl;
    }
    return 0;
}