十一挑战赛#23 题解

egogaming

2025-10-07 22:15:12

发布于：广东

34阅读

0回复

0点赞

十一挑战赛#23 题解

T1

按题意枚举即可。

#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int cnt=0;
	cin>>s;
	for(int i=3;i<s.size();i++){
		if(s[i-3]=='N' && s[i-2]=='O' && s[i-1]=='O' && s[i]=='N') cnt++;
	}
	cout<<cnt;
}

T2

观察到 $a_i$ 的值域较小，考虑先将所有值为 $a_i$ 的装进 $t_{a_i}$ 的桶里。
接下来直接枚举 $b_1+b_2$ 的值，值域是 $[2,10000]$ ，然后扫一遍桶过去就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50;
int n;
int a[N];
int t[N];
int ma,mi=1e9;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		t[a[i]]++;
		ma=max(ma,a[i]);
		mi=min(mi,a[i]);
	}
	int ans=0;
	for(int i=mi*2;i<=ma*2;i++){
		int tmp=0;
		for(int j=max(mi,i-ma);j<=i/2;j++){
			if(j==i-j) tmp+=t[j]/2*2;
			else tmp+=min(t[j],t[i-j])*2;
		}
		ans=max(ans,tmp);
	}
	printf("%d",ans);
}

T3

考虑枚举最后所有石头放在哪个位置，然后前缀后缀和跑一遍就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
int n;
ll k;
ll a[N];
ll qz[N],q2[N],hz[N],h2[N];
int main(){
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",a+i);
		qz[i]=qz[i-1]+a[i];
		q2[i]=q2[i-1]+(qz[i-1]+k-1)/k;
	}
	ll ans=8e18;
	for(int i=n;i>=1;i--){
		hz[i]=hz[i+1]+a[i];
		h2[i]=h2[i+1]+(hz[i+1]+k-1)/k;
		ans=min(ans,q2[i]+h2[i]);
	}
	printf("%lld",ans);
}

T4

很显然，对于一盏灯的操作只会是全是加法或全是减法，不然不优。
我们令 $c_i=(a_i-b_i) \bmod m$ ，这就是一盏灯减法的代价，则它加法的代价为 $(m-c_i)\bmod m$ ，则总共的花费次数就是使用加法的代价最大值加上使用减法的代价最大值。

我们将 $c_i$ 排序，显然我们应该选前若干个用减法，其它的用加法，枚举即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50;
int T;
int n,m;
int a[N],b[N];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%d",a+i);
		}
		for(int i=1;i<=n;i++){
			scanf("%d",b+i);
			a[i]=(a[i]-b[i]+m)%m;
		}
		sort(a+1,a+n+1);
		a[n+1]=m;
		int ans=1e9;
		for(int i=0;i<=n;i++){
			ans=min(ans,a[i]+(m-a[i+1]));
		}
		printf("%d\n",ans);
	} 
}

T5

显然，我们可以对迷宫进行 bfs，如果走的方向相对应的颜色和该格子相同，那么花费为 $0$ ，否则为 $1$ ，那么用 deque 做一个 0-1 bfs 就行了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+50;
const int inf=1e9+7;
typedef pair<int,int> PII; 
int T;
int n,m,k;
vector<string> G;
int dis[N];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char col[4]={'G','B','Y','O'};
bool bfs(){
	if(n==1 && m==1) return true;
	for(int i=1;i<=n*m;i++) dis[i]=inf;
	deque<PII> dq;
	dis[1]=0;
	dq.push_front({1,1});
	while(dq.size()){
		int x=dq.front().first,y=dq.front().second;
		dq.pop_front();
		int p=(x-1)*m+y;
		if(dis[p]==inf) continue;
		if(x==n && y==m) return dis[p]<=k;
		for(int i=0;i<4;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx<1 || ny<1 || nx>n || ny>m) continue;
			int pp=(nx-1)*m+ny;
			int tmp=0;
			if(col[i]!=G[x][y]) tmp=1;
			if(dis[p]+tmp<dis[pp] && dis[p]+tmp<=k){
				dis[pp]=dis[p]+tmp;
				if(tmp) dq.push_back({nx,ny});
				else dq.push_front({nx,ny});
			}
		}
	}
	return false;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m>>k;
		G.resize(n+2,"");
		for(int i=1;i<=n;i++){
			cin>>G[i];
			G[i]=" "+G[i];
		}
		if(bfs()) cout<<"YES\n";
		else cout<<"NO\n";
	}
}

T6

一开始应该是数据造假了，不然看这么简单的题不可能大佬们 ~~（和 AI 们）~~ 都过不去。

根据限制二，我们只要枚举修改哪一个字符串，再加起来就行了。

我们重点于关注限制三：容易发现，只要和相邻的两个字符串符合要求就行了。那么我们就考虑将 $m$ 个字母分成 $3$ 部分：必须选的，必须不选的，可选可不选的。设可选可不选的个数为 $x$ ，那么根据限制一，修改该字符串的方案总数就是 $2^x-1$ （减掉于原来相同的）。

最后，通过观察可以发现，可选可不选的字母就是左右两边的字符串都有的字母个数，可以用二进制压一下，取并就行了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+50;
int T;
int n,m;
string a[N];
int cnt[N];
inline int check(int x){
	int res=0;
	while(x){
		if(x&1) res++;
		x>>=1;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cnt[i]=0;
			cin>>a[i];
			for(int j=0;j<a[i].size();j++){
				cnt[i]|=(1<<(a[i][j]-'a'));
			}
		}
		long long ans=0;
		cnt[0]=(1<<m)-1;
		cnt[n+1]=(1<<m)-1;
		for(int i=1;i<=n;i++){
			ans+=(1<<check(cnt[i-1]&cnt[i+1]))-1;
		}
		cout<<ans<<'\n';
	}
}