A.数字游戏

因为每两次操作中必定有一次二操作，而二操作一定使最高位降低，所以可以直接暴力计算

时间复杂度 $O(Tlogn)O(T\backslash \; log\backslash \; n)$

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll n,x,g,now,ans;
ll read()
{
	char c=getchar();
	ll ds=0,fs=1;
	while (c<'0'||'9'<c) {if (c=='-') fs=-1;c=getchar();}
	while (c>='0'&&c<='9') ds=(ds<<3)+(ds<<1)+c-48,c=getchar();
	return ds*fs;
}
int main()
{
	n=read();
	while(n--){
		x=read();
		now=1;
		g=0;
		for(int i=0;i<32;++i){
			if(x&now)g++;
			now<<=1;
		}
		ans=0;
		if(g&1)x^=1,ans++;
		while(x){
			while(!(x&now))now>>=1;
			x^=now;
			ans++;
			if(!x)break;
			x^=1;
			ans++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

B.跳跳跳

观察题目跳的方法，发现跳过的位置是一个区间，而跳相当于在当前跳过的区间左/右边扩展一格

那么可以先复制一遍数组，处理环的情况

设 $f_{i,j}f\_\{i,j\}$ 为左端点在i，右端点在j的最大贡献，每次考虑跳哪边求max即可

时间复杂度 $O(n^2)O(n^2)$

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 4010
using namespace std;
ll n,ans,a[N],f[N][N];
int main()
{
	scanf("%lld",&n);
	memset(f,-127/3,sizeof(f));
	for(ll i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		a[i+n]=a[i];
		f[i][i]=a[i];
		f[i+n][i+n]=a[i];
	}
	for(ll len=2;len<=n;++len)
		for(ll i=1;i<=n*2-len+1;++i){
			ll j=i+len-1;
			f[i][j]=max(f[i][j],max(f[i+1][j]+a[i]*len,f[i][j-1]+a[j]*len));
		}
	for(ll i=1;i<=n;++i)
		ans=max(ans,f[i][i+n-1]);
	printf("%lld",ans);
	return 0;
}

C.数字匹配

题目要求最长公共子串长度大于k，那么可以转化一下，改为存在长度为k的公共子串

因为字符串长度小于10，可以直接枚举x,y，然后求所有长为k的子串，用个数组存下来求匹配

时间复杂度 $O(n^{2}logn)O(n^2\backslash \; log\backslash \; n)$

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 100100
using namespace std;
int n,k,pp,x,y,now,s,p[N],ans;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j){
			pp=0;
			x=i;
			now=s=0;
			while(x){
				now+=(x&1)*(1<<s);
				if(s==k)now/=2;
				else s++;
				x/=2;
				if(s==k)p[now]++;
			}
			x=j;
			now=s=0;
			while(x){
				now+=(x&1)*(1<<s);
				if(s==k)now/=2;
				else s++;
				x/=2;
				if(s==k&&p[now]){
					pp=1;
					break;
				}
			}
			x=i;
			now=s=0;
			while(x){
				now+=(x&1)*(1<<s);
				if(s==k)now/=2;
				else s++;
				x/=2;
				if(s==k)p[now]--;
			}
			if(pp)ans++;
		}
	printf("%d",ans);
	return 0;
}

D.优美字符串

因为要相邻的不同，所以在原串相邻相同的字符中加一个其他的即可，那么直接计算相邻相同的字符即可

时间复杂度 $O(n)O(n)$

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 100100
using namespace std;
int T,n,m;
char s[N];
int main()
{
	scanf("%d",&T);
	while(T--){
		scanf("%s",s+1);
		n=strlen(s+1);
		m=n;
		for(int i=2;i<=n;++i)
			if(s[i]==s[i-1])m++;
		printf("%d\n",m);
	}
	return 0;
}

E.分组

当一个组的最大人数为k时可以满足条件，那么最大人数为k+1时也可以满足条件，所以满足单调性

那么可以先对类别排序，然后二分枚举最大人数，再考虑做少分多少组，如果小于m就是合法的

时间复杂度 $O(nlogn)O(n\backslash \; log\backslash \; n)$

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 100100
using namespace std;
int n,m,now,num,l,r,a[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	now=0;
	num=0;
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i)
		if(a[i]!=a[i-1])now++;
	if(now>m){
		puts("-1");
		return 0;
	}
	l=1;
	r=n;
	while(l<r){
		int mid=l+r>>1;
		now=num=0;
		for(int i=1;i<=n;++i)
			if(a[i]!=a[i-1]||num==mid)now++,num=1;
			else num++;
		if(now<=m)r=mid;
		else l=mid+1;
	}
	printf("%d",l);
	return 0;
}

F.过桥

因为每一步的代价都是1，且最多走到n个点，所以可以直接bfs搜索

时间复杂度 $O(n^2)O(n^2)$

code

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 2021
using namespace std;
int n,a[N],b[N];
queue<int>d;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	memset(b,127/3,sizeof(b));
	b[1]=0;
	d.push(1);
	while(!d.empty()){
		int x=d.front();
		d.pop();
		if(a[x]>0){
			for(int i=x+1;i<=min(n,x+a[x]);++i)
				if(b[x]+1<b[i]){
					b[i]=b[x]+1;
					d.push(i);
				}
		}
		else{
			for(int i=1;i<=i+a[x];++i)
				if(b[x]+1<b[i]){
					b[i]=b[x]+1;
					d.push(i);
				}
		}
	}
	if(b[n]>n)puts("-1");
	else printf("%d",b[n]);
	return 0;
}

G.空调遥控

可以把每个人适宜的温度视为一个区间，那么题目就是要求一个点覆盖最多的区间，区间可以用查分求，然后跑一遍就好了

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 2000210
using namespace std;
int n,p,x,now,ans,a[N];
int main()
{
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		a[max(x-p,1)]++;
		a[x+p+1]--;
	}
	now=0;
	for(int i=1;i<=2e6;++i){
		now+=a[i];
		ans=max(ans,now);
	}
	printf("%d",ans);
	return 0;
}

H.来点gcd

对于每组数据，想得出一个数，就只能取它的倍数，那么可以枚举所有数，然后枚举倍数（调和级数），如果有就求gcd，查询直接O(1)查

时间复杂度理论时$O(nlo{g}^{2}nO(n\backslash \; log^2\backslash \; n$)，但如果两个数互质时会跑不满，所以应该是 $O(nlogn)O(n\backslash \; log\backslash \; n)$的

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 1000100
using namespace std;
int T,n,m,x,now,p[N];
int gcd(int x,int y)
{
	if(!y)return x;
	return gcd(y,x%y);
}
int main()
{
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i)p[i]=0;
		for(int i=1;i<=n;++i){
			scanf("%d",&x);
			p[x]=1;
		}
		for(int i=1;i<=n;++i){
			now=0;
			for(int j=1;i*j<=n;++j)
				if(p[i*j]){
					if(!now)now=j;
					else if(j%now)now=gcd(now,j);
					if(now==1)continue;
				}
			if(now==1)p[i]=1;
			else p[i]=0;
		}
		for(int i=1;i<=m;++i){
			scanf("%d",&x);
			if(p[x])puts("YES");
			else puts("NO");
		}
	}
	return 0;
}

I.体操队形

考虑状压DP，设f_S为状态为S的方案数，每次找一个点不是任何未选点的诉求点加入状态，最后答案就是所有点都选了的状态

时间复杂度 $O(2^n{n}^2)O(2^nn^2)$

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 20
using namespace std;
ll n,pp,a[N],f[100000];
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		if(a[i]==i)a[i]=0;
	}
	f[0]=1;
	for(ll i=0;i<(1<<n);++i)
		for(ll j=1;j<=n;++j)
			if(!(i&(1ll<<j-1))){
				pp=0;
				for(ll k=1;k<=n;++k)
					if(!(i&(1ll<<k-1))&&a[k]==j){
						pp=1;
						break;
					}
				if(pp)continue;
				f[i|(1ll<<j-1)]+=f[i];
			}
	printf("%lld",f[(1<<n)-1]);
	return 0;
}