2022jscpc题解

发表于 更新于 分类于 阅读次数： Changyan：

A. PENTA KILL!

签到题，直接O($n^2$)遍历每一个五杀的开始点然后计算是否符合规则即可。规则就是一个人必须连续杀死五个不同的敌人，这个五杀者可在此过程中死亡。

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
const int N=200010,M=N*2,mod=1e9+7;
int n,m,k,a[N];
struct F{
	string p,q;
}v[N];
map<string,set<string>> mp;

void solve(){
	cin >> n;
	rep(i,1,n){
		cin >> v[i].p >> v[i].q;
	}
	bool ok=false;
	for(int i=1;i<=n;++i){
		string p=v[i].p,q=v[i].q;
		mp[p].clear();
		for(int j=i;j<=n;++j){
			if(v[j].p==p){
				if(mp[p].count(v[j].q)) break;
				else{
					mp[p].insert(v[j].q);
					if(mp[p].size()==5) {ok=true; break;}
				}
			}
		}
	}
	if(ok) cout << "PENTA KILL!\n";
	else cout<<"SAD:(\n";
}

B. Prime Ring Plus

大意：给定1~n，n个数，让你构造k个环是的环上相邻数字和为质数。

这道题在赛场上我是先看的题目，想了一遍常规方法发现并不是很好解决。不知道是不是比赛的时候把数据范围给看错了，赛后刷了知乎后又看了遍题目，才发现这道二分图还是蛮明显的。

建图方式：

1.建立源点S和汇点T，将n个数分成奇数和偶数

2.从S向所有奇数连容量为2的边，从所有偶数向T连容量为2的边，然后奇数向所有与之和为质数的偶数连容量为1的边（因为每个点在环上都相当于和两个数相连接，因此当两数之间满流的时候说明两数存在一个环内）

3.遍历所有中间容量为1的正向边，如果满流则说明当前跑出来的可行解中这两个点在一个环内，我在这里先根据所有点的度数判断解存不存在，然后dfs出最终答案。

Code

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
const int N = 100010,INF=0x3f3f3f3f, M = 5000*2500*2+10000;
bool numlist[N];
int prime[N],cnt;
void Eular(int n=20000){
    for(int i=2;i<=n;i++){
        if(!numlist[i])
            prime[++cnt]=i;
        for(int j=1;prime[j]<=n/i;j++){
            numlist[i*prime[j]] =true;
            if(i%prime[j]==0)
                break;
        }
    }
    return ;
}
int n,m,F,D,S,T;
int e[M],ne[M],h[N],f[M],idx=0;
int cur[M],q[N],d[N];
int du[N],vis[N];
vector<int> edge[N];
vector<int> ans[N];
int dx=0;

void add(int a,int b,int c){
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

int find(int u,int limit){
    if(u == T) return limit;
    int flow = 0;
    
    for(int i=cur[u];~i && flow < limit ;i=ne[i]){
        cur[u] = i;
        int ver = e[i];
        if(d[ver] == d[u] + 1 && f[i]){
            int t = find(ver,min(f[i],limit - flow));
            if(!t ) d[ver] = -1;
            f[i] -= t, f[i^1] += t, flow += t;
        }
    }
    return flow;
}

bool bfs(){
    memset(d,-1,sizeof d);
    int hh = 0, tt = 0;
    q[0] = S, cur[S] = h[S], d[S] = 0;
    
    while(hh <= tt){
        int u = q[hh ++];
        for(int i=h[u];~i;i=ne[i]){
            int ver = e[i];
            if(d[ver] == -1 && f[i]){
                d[ver] = d[u] + 1;
                cur[ver] = h[ver];
                if(ver == T) return true;
                q[++ tt] = ver;
            }
        }
    }
    return false;
}

int dinic(){
    int ans = 0, flow = 0;
    while(bfs()) while(flow = find(S,INF)) ans += flow;
    return ans;
}

void dfs(int u){
	vis[u]=1;
	ans[dx].push_back(u);
	for(auto v:edge[u]){
		if(!vis[v]){
			dfs(v);
		}
	}
}

void solve(){
	n=read();
	S=0,T=n+5;
	for(int i=1;i<=n;++i){
		if(i&1) add(S, i, 2);
		else add(i, T, 2);
	}
	for(int i=1;i<=n;i+=2){
		for(int j=1;j<=n/2;++j){
			if(!numlist[i+2*j]){
				add(i, 2*j, 1);
			}
		}
	}
	dinic();
	// int cc=0;
	for(int i=0;i<idx;i+=2){
		if(e[i]!=T&&e[i^1]!=S&&!f[i]){
			int a=e[i^1],b=e[i];
			// printf("%d---->%d:%d\n",e[i^1],e[i],f[i]);
			du[a]++,du[b]++;
			// cc++;
			edge[a].push_back(b);
			edge[b].push_back(a);
		}
	}
	// debug(cc);
	bool ok=true;
	for(int i=1;i<=n;++i)
		if(du[i]!=2) {
			ok=false;
			break;
		}
	if(!ok){
		print(-1);
		return ;
	}
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			++dx;
			dfs(i);
		}
	}
	print(dx);
	for(int i=1;i<=dx;++i){
		printf("%d ",ans[i].size());
		for(auto u:ans[i]){
			printf("%d",u);
			if(u!=ans[i].back()) printf(" ");
		}
		printf("\n");
	}
}

倒是补题中途被欧拉筛坑了几下，最大的可能出现的质数应该是2e4以内，我一开始开小了…

C. Jump and Treasure

C题的DP式子很简单，就是令f[i]表示在i位置的最大值，有$f[i]=max\{f[i-k\cdot j]\} (k\cdot j \le p)$,其中j表示当且为jlevel.

然后我的第一反应是写线段树，当时计算了一下发现3e8感觉有点悬。然后队友说这有点向单调队列优化的背包（模数优化），然后我反应过来确实单调队列可以行，然后就正常写即可，复杂度为$O(nlogn)$

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
#define int LL 
const int N = 1000010;
const LL INF = 1e17;
LL n,m,p,a[N],ans[N];
vector<int> qry[N];
vector<LL> vec;
int q[N],hh,tt;

void solve(){
	n=read(),m=read(),p=read();
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=m;++i){
		int x=read();
		if(x>p) ans[i]=-INF;
		else qry[x].push_back(i);
	}
	for(int i=1;i<=n;++i){
		if(qry[i].size()){
			vec.clear();
			vec.push_back(0);
			for(int j=i;j<=n;j+=i)
				vec.push_back(j);
			vec.push_back(n+1);
			vector<LL> f(vec.size()+20,-INF);
			f[0]=0;
			hh=0,tt=-1;
			q[++tt]=0;
			for(int j=1;j<vec.size();++j){
				while(hh<=tt&&vec[j]-vec[q[hh]]>p) hh++;
				f[j]=max(f[j], f[q[hh]]+a[vec[j]]);
				while(hh<=tt&&f[q[tt]]<=f[j]) tt--;
				q[++tt]=j;
			}
			for(auto id:qry[i])
				ans[id]=f[vec.size()-1];
		}
	}
	for(int i=1;i<=m;++i){
		if(ans[i]==-INF) puts("Noob");
		else print(ans[i]);
	}	
}

J. Balanced Tree

赛时是队友打表过的，当时一开始想着记忆化然而发现并不行。看了一下题解，是用递推来算。我想了一下，大概是用记忆化拆开后发现利用了影响2*i-1和2*i的是相同的两个数，因此写成两个数的递推关系。

令$g(n)=a\cdot g(x)+b\cdot g(x-1)+c$

若x为偶数，则有$g(n)=a\cdot g(\frac{x}{2})+(a+2b)\cdot g(\frac{x}{2}-1)+a+c$

若x为奇数，则有$g(n)=(2a+b)\cdot g(\frac{x-1}{2})+b\cdot g(\frac{2-1}{2}-1)+b+c$

然后$logn$层递推$g(n)=xg(1)+yg(0)+z$就是最终答案，如果大于等于64就是0，否则直接输出相应2的幂次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ULL n;

LL dfs(ULL x,LL a,LL b,LL c){
	if(x==0) return 0;
	if(x==1){
		return c; 
	}
	if(x&1)
		return dfs((x-1)/2,2ll*a+b,b,b+c);
	else 
		return dfs(x/2,a,a+2ll*b,a+c);
}

void solve(){
	cin >> n;
	LL res=dfs(n,1,0,0);
	if(res>=64) cout << 0 << "\n";
	else {
		ULL ans=1;
		rep(i,1,res) ans *= 2;
		cout << ans << "\n"; 
	}
}

K. aaaaaaaaaaA heH heH nuN

这道构造题和五月份昆明的那一道几乎是一样的套路，用二进制拼凑的思想。我们发现对于ha...ak个a的贡献是$2^k-1$,而如果以h...ha(p个h)结尾的贡献是p,那么我们只要按位凑出来再最后把1加上去即可。

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
int n;
vector<int> pos;
 
void solve(){
	pos.clear();
	cin >> n;
	int cnt=0;
	for(int i=30;i>=0;--i)
		if(n>>i&1) 
			pos.push_back(i);
	if(n==0){
		cout << ("h\n");
		return ;
	}
	else if(n==1){
		cout << ("nunhehheha\n");
		return ;
	}
	if(pos.back()==0) cnt++,pos.pop_back();
	cnt += pos.size(); 
	string ans="nunhehheh";
	for(int i=0;i<pos.size();++i){
		if(i==pos.size()-1){
			int tmp=pos[i];
			rep(j,1,tmp-1) ans += "a";
			rep(j,1,cnt) ans += "h";
			ans+="a";
			break;
		}
		int tmp=pos[i]-pos[i+1];
		rep(j,1,tmp) 
			ans += "a";
		ans += "h";
	}
	cout << ans << "\n";
}

I. Cutting Suffix

很经典的一道诈骗题，刚看到的时候想到了各种奇奇怪怪的字符串算法，但是看到过题人数很快我就知道大概是个思维之类的。很快发现：

如果这个字符串由单一字符构成，那么我们就只把最后一个后缀(单个字母)放在一个集合，其他的放在另外一个集合，答案为s.size()-1

否则，随便选择一个字符，把所有这个字符开头的后缀都放进一个集合中，其他的放入另一个集合，因此答案就是0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string p;
int num[29];
 
void solve(){
	int cnt=0;
	cin >> p;
	for(int i=0;i<p.size();++i){
		num[p[i]-'a'] ++;
		if(num[p[i]-'a']==1) cnt++;
	}
	if(cnt==1){
		print(p.size()-1);
		return ;
	}
	print(0);
}

L. Collecting Diamonds

L题很可惜啊，当时做这道题还有将近1h40min,只要能搞出来就是金牌了，but性质之类的都想出来了，卡在最后代码没写好….

我又简洁了一下做法，延续着我比赛时候的思路：

首先双指针与处理出每一段形如A...ABC...C形式的字符串（舍弃B左右不含A或者C的）。

性质：

1.删AC可以在没有删完的情况下一直删，且不影响后面串的奇偶性

2.删B只能对于每一段删一次，而且删完之后这一段剩余的AC就没有用了，但是删B可以改变后面串奇偶性使得后面可以可持续化删AC。因此删B的妙处就在这里

3.如果对于删AC或者删B都行的但是只能删一次的ABC我们删B更优

总结一下：在每一段都能删B的情况下我们尽量把所有能删的AC都删了，这就是贪心策略

因此遍历整个串的每一段，分成两种情况：

1.前面还没有能够改变奇偶性的

此时如果只能删AC那就ans++

否则选择删B,ans++并且被删B的数量的计数器cnt++,意味着后面的奇偶性能够被改变了

2.前面已经有能够改变后面奇偶性的B出现了

能删的次数就是min(q[i].x, (q[i].y==0)+cnt+1)

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define x first
#define y second
typedef pair<int,int> pii;
string s;
int n,hh,tt;
pii q[N];

void solve() {
    hh=0,tt=-1;
    cin >> s;
    for(int i=0;i<s.size();++i){
        if(s[i]!='B') continue;
        int l=i,r=i;
        while(l-1>=0 && s[l-1]=='A') l--;
        while(r+1<s.size() && s[r+1]=='C') r++;
        if(min(r-i,i-l)>0)
			q[++tt]=make_pair(min(r-i,i-l),(i+1)%2);
        i=r;
    }

    int ans=0,cnt=0; //答案和可以删B的次数
	for(int i=0;i<=tt;++i){
		if(cnt==0){
			if(q[i].y==0){
				if(q[i].x==1) ans++;
				else ans += 2, cnt ++;
			}
			else
				ans ++,cnt ++;
		}
		else{
			ans += min(q[i].x, (q[i].y==0)+cnt+1);
			cnt ++;
		}
	}
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

相关推荐：

我的JSCPC小结