2020 CCPC Wannafly camp day7 题解

Solved	A	B	C	D	E	F	G	H	I	J	K	L
11/12	O	Ø	O	.	O	O	O	O	Ø	O	O	O

O for passing during the contest
Ø for passing after the contest
! for attempted but failed
· for having not attempted yet

比赛链接

A

题目描述

已知$ {1} $到 ${n} $的一个排列$s_{1…n}$。

现在给定一个数$ {k}$，对于这个排列的一个长度大于等于$ {2} $的子序列 $s=(s_1,…,s_p)$ ，$p \ge 2$，对于每一个下标 ${i}$，如果满足（1）$i \lt p$且 $s_i<k<s_{i+1} $；或者（2）$i \lt p$且$s_i>k>s_{i+1}$ ，那么得分加$1$。

例如，当$ {k=2}$ 时，子序列$ {5134}$的得分就是 ${2}$。

现在询问当 ${k} $取遍$ {1}$ 到$ {n} $时，所有给定排列的子序列的得分和是多少，答案$\bmod 10^9+7$。

解题思路

solved by nikkukun

枚举数$k$，定义$a_i=(s_i<k)$，那么$a_i$为一个$01$串，且在每次修改时只会改动两个位置的值。

题目所求即是$0-1$或$1-0$对的贡献之和。不妨看一个$0-1$对的贡献：设第$i$位为$1$，第$j$位为$0$，那么这一个对的贡献为$2^{i-1}\times 2^{n-j}$，故用线段树分别维护$0$和$1$的”左端点和”和“右端点和”即可。

AC代码 - by nikkukun

点击

// 16:05 - 16:22
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define lch (o << 1)
#define rch (o << 1 | 1)
 
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;
 
const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
 
ll pow2[N];
 
struct SegTree{
    ll sumL[N*4][2], sumR[N*4][2], sum[N*4];
     
    void Maintain(int o, int L, int M, int R){
        sum[o] = (sum[lch] * pow2[R-M] + sum[rch] * pow2[M-L+1]) % MOD;
        for(int x=0; x<=1; x++){
            sumL[o][x] = (sumL[lch][x] + sumL[rch][x] * pow2[M-L+1]) % MOD;
            sumR[o][x] = (sumR[lch][x] * pow2[R-M] + sumR[rch][x]) % MOD;
            sum[o] = (sum[o] + sumL[lch][x] * sumR[rch][x^1]) % MOD;
        }
    }
 
    void Build(int o, int L, int R){
        if(L == R){
            sumL[o][0] = sumR[o][0] = 0;
            sumL[o][1] = sumR[o][1] = 1;
            sum[o] = 0;
            return;
        }
        int M = (L+R) / 2;
        Build(lch, L, M);
        Build(rch, M+1, R);
        Maintain(o, L, M, R);
    }
 
    // -1 0 1
    void Modify(int o, int L, int R, int pos, int x){
        if(L == R){
            sumL[o][0] = sumR[o][0] = 0;
            sumL[o][1] = sumR[o][1] = 0;
            sum[o] = 0;
            if(x >= 0)
                sumL[o][x] = sumR[o][x] = 1;
            return;
        }
        int M = (L+R) / 2;
        if(pos <= M) Modify(lch, L, M, pos, x);
        else Modify(rch, M+1, R, pos, x);
        Maintain(o, L, M, R);
    }
 
    ll Query(){
        return sum[1];
    }
};
 
SegTree seg;
int a[N], pos[N];
 
int main(){
    ios::sync_with_stdio(0);
 
    pow2[0] = 1;
    for(int i=1; i<N; i++)
        pow2[i] = pow2[i-1] * 2 % MOD;
 
    int n; cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        pos[a[i]] = i;
    }
     
    seg.Build(1, 1, n);
 
    for(int i=1; i<=n; i++){
        if(i > 1){
            seg.Modify(1, 1, n, pos[i-1], 0);
        }
        seg.Modify(1, 1, n, pos[i], -1);
        ll ans = seg.Query();
        cout << (ans + MOD) % MOD << endl;
    }
 
    return 0;
}

B

题目描述

给一个在区间上符合四边形不等式的函数，求拓展一个在集合上符合四边形不等式的函数。

解题思路

太神秘了这个思维题…

一个集合必然包含几个区间，然后这题就做完了

……

AC代码

点击

#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<set>
#include<unordered_map>
#include<vector>
typedef long long ll;
using namespace std;
#define N 1<<21
ll f[N];
int n;
ll getf(int x){
    ll ans=0;
    int i,flag=0,last=0;
    for(i=0;i<=n;i++){
        if(!flag){
            if(x>>i&1)flag=1,last=i;
        }else{
            if(!(x>>i&1)){
                flag=0;
                ans+=f[(1<<i)-(1<<last)];
            }
        }
    }
    return f[x]=ans;
}
int main(){
    int i,j;
    scanf("%d",&n);
    memset(f,-1,sizeof(f));f[0]=0;
    for(i=0;i<n;i++)
        for(j=i;j<n;j++)
            scanf("%lld",&f[((1<<(j-i+1))-1)<<i]);
    for(i=0;i<(1<<n);i++)if(f[i]==-1)f[i]=getf(i);
    for(i=0;i<(1<<n);i++)printf("%lld%c",f[i]," \n"[i==(1<<n)-1]);
    return 0;
}

C

题目描述

有一个卡牌游戏，$1…n$的牌每个$4$张，规则是玩家选择$3k+1$张牌，再获取一个随机的牌（可能导致玩家某种牌存在五个），如果这$3k+2$张牌能够构成一组对子和$k$组面子（连续的三张牌、相同的三张牌都可以成为面子），那么就获胜。

给定$L,n$，请你输出$3k+1$张牌，使得能让玩家胜利的牌的数量恰好为$L$。

解题思路

构造题，先确定获胜范围$1-L$；因为面子是相同的三张牌，根据$L$模$3$的余数分类构造，通过对子和三张牌构造出答案。注意构造过程中，$L+1$不可以获胜。

AC代码

点击

#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<set>
#include<unordered_map>
#include<vector>
typedef long long ll;
using namespace std;
int main(){
    int i,t,n,l;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&l);
        if(l==1)printf("1\n1 1 1 1\n");
        else if(l==2)printf("1\n1 1 2 2\n");
        else if(l==3)printf("2\n1 1 2 2 2 3 3\n");
        else{
            if(l%3){
                printf("%d\n",(l/3*3+4)/3);
                if(l%3==1)printf("1 1 1 2");
                else printf("2 2 2");
                for(i=3;i<l;i++)printf(" %d",i);
                printf(" %d %d\n",l-1,l-1);
            }else{
                printf("%d\n",(2*(l-4)+9)/3);
                printf("1 1 1 2 2 2 3 3 3");
                for(i=4;i<l;i++)printf(" %d %d",i,i);
                puts("");
            }
        }
    }
    return 0;
}

D

题目描述
给一个$n\times n(1\leq n\leq 500)$的方阵和$Q$次修改操作，每次修改后输出方阵的行列式。

解题思路
？

AC代码
点击
1
2

E

题目描述
给定$n$，问有多少$1…n$的排列满足可以不重不漏地分为一个上升子序列和一个下降子序列。

解题思路
oeis

题解做法是$f[n][k]$表示能分成一个下降序列、最后一个元素不超过$k$的上升序列的$1…n$的排列个数，枚举$1$的位置和左边不超过$k$的数个数转移，学不来.jpg

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
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<set>
#include<unordered_map>
#include<vector>
typedef long long ll;
using namespace std;
#define N 250
ll inv[N],invs[N],fac[N],q[N],p;
ll c(int n,int m){return fac[n]*inv[m]%p*inv[n-m]%p;}
int main(){
    int i,n;
    scanf("%d%lld",&n,&p);
    invs[0]=invs[1]=inv[0]=fac[0]=q[0]=1;
    for(i=1;i<210;i++){
        if(i!=1)invs[i]=invs[p%i]*(p-p/i)%p;
        fac[i]=fac[i-1]*i%p,inv[i]=inv[i-1]*invs[i]%p,q[i]=(q[i-1]<<1)%p;
    }
    ll ans=c(2*n,n);
    for(i=0;i<n;i++)(ans-=c(2*i,i)*q[n-i-1])%=p;
    printf("%lld",(ans+p)%p);
    return 0;
}

F

题目描述
有一个$n\times m$的空棋盘，有个人站在$(x,y)$上。

每天早上每个格子里$+1s$，每天下午这个人跑到它上下左右的格子或不动，每天晚上收获所在格子的时间，问前$k$天最多能续多久。

$n,m\leq 10^9$。

解题思路
如果$n\neq 1,m\neq 1$：那么必然有方案可以不重不漏地经过每一个格子并回到起点，故如果可以遍历全部那么就在原地等几天再环游一圈，否则直接环游。

如果$n=1$（$m=1$同理，故设$m>1$）：分三种方案：一直向空格子多的那边走；遍历；先向少的那边走一点再回到起点再遍历多的那一边。

细节：第一天可以瞬移“改变”一次初始位置，故第一种情况里$n\times m$为奇数时可以保证自己能走哈密顿路径或哈密顿回路；第二种情况里的$1$、$3$种情况中可以向少的那一边一格。

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<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<set>
#include<unordered_map>
#include<vector>
typedef long long ll;
using namespace std;
const ll mod=998244353;
ll inv2;
ll f(ll l,ll r){
    l%=mod;r%=mod;
    return ((l+r)*(r-l+1)%mod*inv2%mod+mod)%mod;
}
ll qp(ll a,int p){
    ll ans=1;
    for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
    return ans;
}
int main(){
    int i,t;
    inv2=qp(2,mod-2);
    scanf("%d",&t);
    while(t--){
        ll n,m,x,y,k;
        scanf("%lld%lld%lld%lld%lld",&n,&m,&x,&y,&k);
        if(n<m)swap(n,m),swap(x,y);
        if(m>1){
            if(k<=n*m)printf("%lld\n",f(1,k));
            else printf("%lld\n",f(k-n*m+1,k));
        }else{
            int ml=max(min(x-1,n-x)-1,0ll);
            if(k>ml+n)printf("%lld\n",f(k-n+1,k));
            else if(k>n-ml){
                int len=n-ml-1;
                int upl=(k-len)/2;
                printf("%lld\n",f(1+upl,k));
            }
            else printf("%lld\n",f(1,k));
        }
    }
    return 0;
}

G

题目描述

与上题类似，但不是空棋盘，每个格子有$a_{ij}$，且$n\times m\leq 12$，$n\times m$为偶数。

解题思路

solved by qxforever

类似，如果能遍历那就等一手，否则暴力搜索即可。

AC代码 - by qxforever

点击

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
 
const int N = 13;
int n,m,x,y;ll k;
 
ll a[N][N];
ll dp[N*N];
int id(int x,int y)
{
    return (x-1)*m+y;
}
ll ans;
void dfs(int x,int y,int dep,ll sum,vector<int> vis)
{
    if(vis[id(x,y)]<0) sum+=a[x][y];
    sum+=dep-max(vis[id(x,y)],0);
    vis[id(x,y)]=dep;
    if(dep==k-1) {ans=max(ans,sum);return ;}
    if(x<n) dfs(x+1,y,dep+1,sum,vis);
    if(x>1) dfs(x-1,y,dep+1,sum,vis);
    if(y<m) dfs(x,y+1,dep+1,sum,vis);
    if(y>1) dfs(x,y-1,dep+1,sum,vis);
}
 
int main()
{
    cin>>n>>m>>x>>y>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) scanf("%lld",&a[i][j]);
    }
    if(k>=n*m){
        k-=n*m;
        ll ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) ans+=a[i][j];
        }
        ll ans2=ans;
        ans+=k*n*m;
        for(int i=1;i<=n*m;i++) ans+=i-1;
        ans2+=(k+n*m)*(n*m)-(1+n*m)*(n*m)/2;
        assert(ans==ans2);
        cout<<ans;return 0;
    }
    vector<int> vis(13,-1);
    dfs(x,y,0,0,vis);
    cout<<ans;
}

H

题目描述
有$1…n$数字各一个，每一轮只要有超过一个数字，那么任选两个数字删去，如果这两个数字互质那么加一分，问期望总得分。

解题思路
考虑每个互质对被选中的概率是等价的，所以答案就是所有互质对的个数除以总对数。

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
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<set>
#include<unordered_map>
#include<vector>
typedef long long ll;
using namespace std;
int main(){
    int i,j;
    ll ans=0,n,b;
    scanf("%lld",&n);
    for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)ans+=__gcd(i,j)==1;
    ans=n/2*ans*2;
    if(!ans)b=1;
    else{
        b=n*(n-1);
        ll g=__gcd(ans,b);
        ans/=g;b/=g;
    }
    printf("%lld/%lld",ans,b);
    return 0;
}

I

题目描述
有$n$个人围成一个圆，但他们并不一定站在$n$等分点上。求最短的总移动距离使得他们能够最终位于$n$等分点上。$1\leq n\leq 100000$。

解题思路
solved by qxforever

容易发现所有点都一定保持相对位置（左右）不变，故钦定每个人的最终位置，然后求出距离的中位数，移动这个“最终位置”的起始点这些距离即可。

AC代码 - by qxforever
点击
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int maxn = 1e5+23;
double a[maxn],ans,sum;
int n;
multiset<double> s;
double dis[maxn];
int main()
{
    cin>>n;ans=1e19;
    double d=360.0/n;
    int mid=(n+1)/2;int rk=mid;
    for(int i=1;i<=n;i++) scanf("%lf",a+i);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        dis[i]=(i-1)*d-a[i];
        s.insert(dis[i]);
    }
    double now;int t;auto it=s.begin();
    for(t=1;t<=mid;t++,it++){
        if(t==mid) now=*it;
    }
    for(int i=1;i<=n;i++) sum+=abs(dis[i]-now);
    ans=min(ans,sum);
    return 0*printf("%.10f",ans/360*2*acos(-1));
}

J

题目描述

序列$(a_1,a_2,\ldots,a_n)$是胖的当且仅当存在实数$j\ge 1$满足

$a_1 = \lfloor j \rfloor$
对于所有的$i\in [2,n]$,存在 ${x, y}$ 满足 $\lfloor x\rfloor = a_{i-1}, \lfloor y\rfloor = a_{i}, x \times j = y$

给定序列$B=(b_1,\ldots,b_m)$，请问$B$的最长胖子串有多长，$1\leq n\leq 100000$？

解题思路

solved by nikkukun

子串是连续的，故可以枚举开头找结尾。

找出每个$(a_i,a_{i+1})$所限制的$j$的范围$(\frac {a_{i+1}}{a_i+1},\frac {a_{i+1}+1}{a_i})$，$ST$表维护一下最大最小值二分查询结尾位置即可。

AC代码 - by nikkukun

点击

#include<bits/stdc++.h>
using namespace std;
  
#define fi first
#define se second
#define lch (o << 1)
#define rch (o << 1 | 1)
  
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;
  
const int N = 1e5 + 5;
const int K = 20 + 2;
const int INF = 0x3f3f3f3f;
const double INF_D = 1e100;
const double EPS = 1e-8;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
  
struct Data{
    ll a, b;
    bool operator < (Data rhs){
        return a * rhs.b < b * rhs.a;
    }
    bool operator > (Data rhs){
        return a * rhs.b > b * rhs.a;
    }
};
  
Data max(Data a, Data b){
    return (a > b) ? a : b;
}
  
Data min(Data a, Data b){
    return (a < b) ? a : b;
}
  
ll a[N];
Data mxl[N][K], mnr[N][K];
  
void Build(int n){
    for(int j=1; j<K; j++)
        for(int i=1; i + (1 << j-1) <= n; i++){
            mxl[i][j] = max(mxl[i][j-1], mxl[i + (1 << j-1)][j-1]);
            mnr[i][j] = min(mnr[i][j-1], mnr[i + (1 << j-1)][j-1]);
        }
}
  
Data qL, qR;
  
void Query(int L, int R){
    int k = __lg(R - L + 1);
    qL = max(mxl[L][k], mxl[R - (1 << k) + 1][k]);
    qR = min(mnr[L][k], mnr[R - (1 << k) + 1][k]);
}
  
int main(){
    ios::sync_with_stdio(0);
  
    int n; cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        if(i == 1) {
            mxl[i][0]=(Data){0,1};
            mnr[i][0]=(Data){100001,1};
        }
        mxl[i][0] = (Data){a[i], a[i-1] + 1};
        mnr[i][0] = (Data){a[i] + 1, a[i-1]};
    }
      
    Build(n);
  
    int ans = 0;
    for(int i=1; i<=n; i++){
        int L = i+1, R = n+1;
        while(L < R){
            int M = (L+R) / 2;
            Query(i+1, M);
            Data l = max((Data){a[i], 1}, qL);
            Data r = min((Data){a[i] + 1, 1}, qR);
            if(l < r) L = M + 1;
            else R = M;
        }
        ans = max(ans, L - i);
    }
  
    cout << ans << endl;
  
    return 0;
}

K

题目描述

两个人，分别有属性$a_1,a_2$，能力值$v_1,v_2$，每天$v_1+=a_1,v_2+=a_2$，且可以$a_1++$或$a_2++$。

当满足$\exist i, v_1>b_{i1},v_2>b_{i2}$的时候就通关了，求最短通关时间。

解题思路

solved by nikkukun

容易想到，即为求一个时间$t$，使得$x+y\leq \frac{(1+t)t}{2}$。

AC代码 - by nikkukun

点击

// 13:17 - 13:22
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define lch (o << 1)
#define rch (o << 1 | 1)
 
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;
 
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
 
ll a1, a2, b1, b2;
 
int main(){
    ios::sync_with_stdio(0);
 
    cin >> a1 >> a2;
    int n; cin >> n;
    int ans = INF;
    for(int i=1; i<=n; i++){
        cin >> b1 >> b2;
        for(int t=1; ; t++){
            ll x = max(b1 - t * a1, 0LL);
            ll y = max(b2 - t * a2, 0LL);
            ll sum = 1LL * (1 + t) * t / 2;
            if(sum >= x + y){
                ans = min(ans, t);
                break;
            }
        }
    }
    cout << ans << endl;
 
    return 0;
}

L

题目描述

一个 ${n} $个点的有向图，初始每个顶点都有一个颜色，黑或白，初始状态为第 ${0}$ 轮。

每一轮，对于每个顶点，如果在上一轮，有奇数个黑色顶点连向他，那么这个顶点会变成黑的；如果在上一轮，有偶数个黑色顶点连向他，那么这个顶点会变成白的。

对于某一个点，从第$ {0}$ 轮开始，最少过了几轮，使得它在这几轮结束的时候，顶点是黑色的次数大于等于$ {k}$次（第$ {0} $轮结束也算）？

解题思路

solved by qxforever

预处理出来循环节长度和顶点是黑色的次数前缀和，询问的时候二分查找即可。

AC代码 - by qxforever

点击

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
 
const int N = 21;
int vis[1<<N];
 
int n,m,q,st,ed;
vector<int> g[N];
int a[(1<<20)+3][N],b[N];
int pre[N][(1<<20)+3];
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) scanf("%d",&a[1][i]);
    for(int i=0,j,k;i<m;i++){
        scanf("%d%d",&j,&k);
        g[k].push_back(j);
    }
    int now=0;
    for(int i=1;i<=n;i++) now+=a[1][i]<<(i-1);
    vis[now]=1;now=0;
    for(int t=2;;t++,now=0){
        for(int j=1;j<=n;j++){
            for(int k:g[j]) a[t][j]^=a[t-1][k];
            now+=a[t][j]<<(j-1);
        }
        if(vis[now]){
            st=vis[now];ed=t-1;
            break;
        }
        //printf("now : %d\n",now);
        vis[now]=t;
    }
    //printf("!! %d %d\n",st,ed);
    for(int i=1;i<=ed;i++){
        for(int j=1;j<=n;j++) pre[j][i]=pre[j][i-1]+a[i][j];
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=ed;j++) printf("->%d ",pre[i][j]);puts("");
    }
    */
    while(q--){
        int x;ll k;
        scanf("%d%lld",&x,&k);
        if(k==0){printf("0\n");continue;}
        if(k>pre[x][ed]){
            if(pre[x][ed]==0) printf("-1\n");
            else{
                ll ans=ed;k-=pre[x][ed];
                int dif=pre[x][ed]-pre[x][st-1];
                if(dif==0) {printf("-1\n");continue;}
                ll t=(k-1)/dif;ans+=t*(ed-st+1);k-=t*dif;
                //printf("x k %d %lld ",x,k);
                //cout<<lower_bound(pre[x]+st,pre[x]+ed,k-pre[x][st-1])-pre[x]<<endl;
                ans+=lower_bound(pre[x]+st,pre[x]+ed+1,k+pre[x][st-1])-(pre[x]+st-1);
                printf("%lld\n",ans-1);
            }
        }
        else printf("%d\n",lower_bound(pre[x],pre[x]+ed+1,k)-pre[x]-1);
    }
}
/*
4 6 100
1 1 0 0
2 1
3 1
4 1
1 2
1 3
1 4
 
3 3 100
1 1 0
1 2
2 3
3 1
 
*/