码题集习题

 目录

数对连图

小码哥的花园

最短字符串

找四边形

寻找正多边形

数字串解密

芯片刻蚀

骑士锦标赛

序列加法

---

        

        

数对连图

可以看出给出的图其实是不完整的无向图，而k的数对其实是一个完整的无向图。那么就要考虑n和k的大小关系了：

• 当n小于等于k的时候（这个比较简单），完整的无向图必定包含不完整的，所以一定可以代替全部的边。

• 当n比k大1时，因为在给每个点编号时一共1~n-1号点都可以分到唯一的编号，而n点就多出来了，那么这个点是不是就一定分配不到编号了呢？ 额！其实不是的，这个多出来的点其实可以分配1~n-1编号中的任意一个编号，只需要保证没有用到重复的数对即可。

 所以这个题就转化成了：图中必有两个点的编号相同的情况，我们只需要每两个点取同一个编号的情况，然后看看该情况下有多少个重复的数对即可，然后有多少就扣掉多少个。就是一种答案

红色的是原顶点号，绿色的是我们赋值的编号，可以看出有两个顶点的编号是一样（4和5的编号都是4），然后只需要<2,5>和<2,4>这个两个边扣除掉一个就行。

#include 
using namespace std;
const int N=107;
int k,n,m,ma[N][N],ans;
int main(){
	cin>>k>>n>>m;
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;ma[u][v]=ma[v][u]=1;
	}
	if(n<=k){
		cout<
	}
	else{
		for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)//枚举所有的组合方案
		{
			int cnt=0;
			for(int l=1;l<=n;l++)
				if(ma[l][i]&&ma[l][j])cnt++;
			ans=max(ans,m-cnt);
		}
		cout<
	}
	return 0;
}

        

        

小码哥的花园

就是在说在下一个点，使得图中存在的最大的正方形。

注意不要陷入思维僵局，你判断是否存在正方形时，不要想着直接就去选四个点，然后判断一下位置关系，这样子没法做的。

我们去考虑一下正方形的性质，什么情况下可以唯一确定一个正方形呢？并不是边，而是对角线。

也就是说，我们只需要选两个点作为对角点，那么另外两个点既然已经唯一确定了，那么当然可以直接求出来的。求出来后去判断一个有几个点是春之花，如果是4个或3个，那么再看看能不能在这里种下一个春之花，最终取最优解 

不妨设1,2,3,4的坐标为(x1,y1),(x2,y2),(x3,y3),(x4,y4) 

易发现：x1+x2=x3+x4     y1+y2=y3+y4

注意还有：y1-y2=x4-x3    x1-x2=y3-y4

联立四个式子求解：

2x4=x1+x2+y1-y2

2x3=x1+x2-y1+y2

2y3=y1+y2+x1-x2

2y4=y1+y2-x1+x2

#include 
using namespace std;
int n,ans;
char ma[107][107];
int main(){
	cin>>n;
	for(int i=0;i>ma[i];
	int x1,x2,y1,y2,x3,x4,y3,y4;
	for(int x1=0;x1
	for(int y1=0;y1
		for(int x2=0;x2<=x1;x2++)//保证2号点在1号点的左上方，以便去重
		for(int y2=0;y2<=y1;y2++){
			x3=x1-y1+x2+y2;y3=x1+y1-x2+y2;x4=x1+y1+x2-y2;y4=-x1+y1+x2+y2;
			if(x3&1|x4&1|y3&1|y4&1) continue;
			x3/=2;y3/=2;x4/=2;y4/=2;
			if(x3<0||x3>=n||y3<0||y3>=n||x4<0||x4>=n||y4<0||y4>=n) continue;
			int cnt=0;
			if(ma[x1][y1]=='B'||ma[x2][y2]=='B'||ma[x3][y3]=='B'||ma[x4][y4]=='B')continue;
			if(ma[x1][y1]=='J')cnt++;
			if(ma[x2][y2]=='J')cnt++;
			if(ma[x3][y3]=='J')cnt++;
			if(ma[x4][y4]=='J')cnt++;
			if(cnt>=3)ans=max(ans,(x3-x1)*(x3-x1)+(y3-y1)*(y3-y1));
		}
	}
	cout<
	return 0;
}

        

        

最短字符串

就是s1，s2，s3进行全排列，然后对每种情况枚举找最优解，我们需要预处理3个子串中两两子串的共同前缀个数和共同后缀个数，之后模拟时候直接使用就行。

不过有个坑就是要注意某一个串是另一个串的子串的情况。这个时候可以直接忽略掉一方，不过你又要写两个两个排列的代码了，工作量又会增加。

有一种更好的办法，就是把被包含的那个子串变成包含它的那个串，然后依然使用原来的f函数也能处理。

#include 
using namespace std;
int ans=(int)1e9;
string s1,s2,s3;
string merge(string a,string b){
	int l1=a.size(),l2=b.size();
	int minn=min(l1,l2);
	for(int i=minn;i>=1;i--){//注意要从长到短来
		string aa=a.substr(l1-i);
		string bb=b.substr(0,i);
		if(aa==bb)return a+b.substr(i);
	}
	return a+b;
}
int f(string a,string b,string c){
	int len=merge(merge(a,b),c).size();
	return len;
}
int main(){
	cin>>s1>>s2>>s3;
	if(s1.find(s2)!=-1)s2=s1;
	if(s2.find(s1)!=-1)s1=s2;
	if(s1.find(s3)!=-1)s3=s1;
	if(s3.find(s1)!=-1)s1=s3;
	if(s2.find(s3)!=-1)s3=s2;
	if(s3.find(s2)!=-1)s2=s3;
	ans=min(ans,f(s1,s2,s3));
	ans=min(ans,f(s1,s3,s2));
	ans=min(ans,f(s2,s1,s3));
	ans=min(ans,f(s2,s3,s1));
	ans=min(ans,f(s3,s2,s1));
	ans=min(ans,f(s3,s1,s2));
	cout<
	return 0;
}

        

        

找四边形

不要见到图就想着跑图啊，这个题其实只是让你走两步而已（你跑那么多步干嘛）

还有一点是不要想着去模拟，仔细想想答案肯定很大的，模拟出来一个就ans++是一定不行的。

应该换一种更快的方式去统计答案，其实不难想象到a到d很可能是有很多条路径的，那么这个路径中的任意两个组合都是一种答案。即C(n,2)种

所以就转化成了我们求a点走两步能到哪些点，b点走两步能到哪些点，c点……然后全部加起来

#include 
using namespace std;
const int N=3e3+7;
vector<int>ve[N];
int n,m,sum[N][N],ans;
int main(){
	cin>>n>>m;int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;ve[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
	for(int j: ve[i])//i的孩子
		for(int k: ve[j])//i的孩子的孩子
			if(k!=i)sum[i][k]++;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
		ans+=sum[i][j]*(sum[i][j]-1)/2;//求C(n,2)
	cout<
	return 0;
}

        

        

寻找正多边形

不难想到正多边形的顶点肯定是要等差的，然后枚举每个起点开始的正三边形，正四边形，正五边形……是否存在

#include 
using namespace std;
const int N=1e5+7;
int n,a[N];
bool check(int s,int step){
	for(int i=s;i<=n;i+=step){
		if(a[i]==0)return false;
	}
	return true;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=3;i<=n;i++){
		if(n%i)continue;//这种情况根本不存在这样的多边形
		int step=n/i;
		for(int s=1;s
			if(check(s,step)){
				cout<<"YES";return 0;
			}
		}
	}cout<<"NO";
	return 0;
}

        

         

数字串解密

观察规律，怎么加过来的，怎么减回去。

最开始39和-15：x1+x2=39  x1-x2=-15 所以x1是12  ，x2是27

从而得出x1=(a+b)/2   x2=(a-b)/2。

从而完成整个推导：

#include 
using namespace std;
const int N=260;
int n,cnt,a[N],b[N];
 
int main(){
	while(cin>>n,n){
		for(int i=0;i>a[i];
		for(int i=1;i!=n;i*=2){
			cnt=0;
			for(int j=0;j
				b[cnt++]=(a[j]+a[j+i])/2;
				b[cnt++]=(a[j]-a[j+i])/2;
			}
			memcpy(a,b,cnt*sizeof(int));//这里千万别写sizeof
		}
		for(int i=0;i-1;i++) cout<" ";
		cout<-1]<<'\n';
	}
	return 0;
}

        

         

芯片刻蚀

思路就是模拟这个过程。

怎么模拟呢？首先要明白这个蚀刻的矩形大小是固定的，但是我们并不确定这个矩形的最佳大小。

我们我们对每个大小的矩形全部枚举一下，看一下当前的矩形能不能恰好完成蚀刻任务，如果能的话需要多少次？

其实如果当前矩形是合法的(可以蚀刻出整个芯片)，那么这个次数可以由总蚀刻值，除以矩形的面积直接算出，所以如果这个次数不是一个整数，那么当前就不用考虑当前的矩形了（它一定是不合法的）。

然后还有可以优化的一点是：

我们要的是最少的次数，必然是矩形面积越大，次数越少，那么我们就考虑面积从大到小来跑，只要发现当前的矩形是合法的就可以直接输出答案，剩下的就不用再跑了。

#include 
using namespace std;
const int N=107;
int n,m,sum,ans,ma[N][N],ma2[N][N];
int check(int l,int w){
	for(int i=1;i<=n-l+1;i++)
	for(int j=1;j<=m-w+1;j++){
		int num=ma2[i][j];
		for(int x=0;x
		for(int y=0;y
			int xx=i+x,yy=j+y;
			ma2[xx][yy]-=num;
			if(ma2[xx][yy]<0)return 0;
		}
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		if(ma2[i][j]!=0)return 0;
	}
	return 1;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		cin>>ma[i][j];sum+=ma[i][j];
	}
	for(int l=n;l>=1;l--)//倒着找最优解，找到就结束程序
	for(int w=m;w>=1;w--){
		if(sum%(l*w)!=0)continue;
		memcpy(ma2,ma,sizeof(ma));
		if(check(l,w)){
			ans=sum/(l*w);
			cout<return 0;
		}
	}
	return 0;
}

        

        

骑士锦标赛

其实求最少的比赛天数，我们肯定是要把那些能在一天内比赛的人都在一天内完成。什么样的人可以在同一天内比赛呢？题上说——每人每天进行一场比赛，说明不同的人可以在同一天内比赛，这是要解决的第一个问题。

另一个问题是要满足每个人的挑战顺序，这个也容易实现；对于i人能不能在今天去比赛，取决于i的对手的下一个对手是不是i，如果是的话，i就可以在今天和其对手比赛，否则就不能。

#include 
using namespace std;
const int N=1e3+7;
vector<int>ve[N];
int n,vis[N],id[N];//id是每个人的指针
int main(){
	cin>>n;int x;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n-1;j++){
		cin>>x;ve[i].push_back(x);
	}
	int ans=0;
	while(1){
		memset(vis,0,sizeof(vis));int f=0;
		for(int i=1;i<=n;i++){
			if(vis[i]||id[i]==n-1) continue;
			int j=ve[i][id[i]];
			if(vis[j]||id[j]==n-1||ve[j][id[j]]!=i)continue;
			f=1;vis[i]=1;vis[j]=1;
			id[i]++;id[j]++;	
		}
		if(!f)break;
		else ans++;
	}
	int f=0;
	for(int i=1;i<=n;i++){
		if(id[i]!=n-1){
			f=1;break;
		}
	}
	if(f)ans=-1;
	cout<
	return 0;
}

        

        

序列加法

一看就是在线的做法。直接模拟着处理每个操作对所有点的影响的话是很头疼的事情，不过我们可以考虑之前每次操作对某个点的影响：

对于操作1，既然下标是x的倍数的数都有影响，那就不妨把这些影响都保存下来，然后在操作2中对于要输出的y坐标，直接看一下之前的操作改变的下标有那些是y的因数，是的话就直接加上！

那么就转化成了求某个数的因数，可以采用O(根号N)去枚举出来。不过要小心平方数，只能加一次哦 

#include 
using namespace std;
const int N=1e6+7;
int a[N],n,m,t[N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	while(m--){
		int num;cin>>num;
		if(num==1){
			int x,y;cin>>x>>y;t[x]+=y;
		}
		if(num==2){
			int i;cin>>i;
			int ans=a[i];
			for(int j=1;j<=i/j;j++){
				if(i%j==0){
					if(j*j==i)ans+=t[j];
					else ans+=t[j]+t[i/j];
				}
			}
			cout<'\n';
		}
	}
	return 0;
}