模拟赛2

1.魔法阵


解题思路

由于要求删除后仍然是一个正多边形，这就保证剩余的点数一定是n的因子，只有这样才能均匀删除
所以我们只需要枚举n的因子作为剩余多边形的顶点数，对答案取max即可
总时间复杂度为O(nlogn)

AC代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,s,answer,a[20005];
int main()
{
   
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
   
		scanf("%d",&a[i]);
		s+=a[i];//不删除
	}
	int answer=-2147483647;//初值
	for(int i=1;i<=n;i++)//枚举约数
	 if(n%i==0&&n/i>=3)
	  for(int j=0;j<i;j++)//每个约数中再枚举初始点
	  {
   
	  	int ans=0;
	  	for(int k=j;k<=n;k+=i)ans+=a[k];//累加
	 	answer=max(answer,ans);//求max 
	  }
	printf("%d",max(s,answer)); 
	return 0;	
}

2.小biu放牛



注意：“输出格式”中的“码头”是“农场”

解题思路

首先由于要求最大值最小，最先想到的应该是二分+检查正确性
这样我们就知道最长绳子的长度，于是我们选择从左到右贪心的去放置每一头牛
假设我们已经放置X头牛，那么如果第X+1头牛紧贴在第X头牛放置是合法的，那么则紧贴着放
置
否则我们检查一下第X头牛能放置的最左位置，把它放置在能放置的最左位置即可
当出现某个木桩在第X头牛的左侧，而且如果要在绳子长度内放置下一头牛，下一头牛和当前牛重叠，则说明不合法
如果最终总长度超过M，也说明不合法，否则都是合法的情况
总时间复杂度为O(nlogn)

注意：绳子长度可以为0

AC代码

#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,x,m,l,r,a[50005];
bool check(int xmid)//检查正确性
{
   
	int beg=0,end=0;//beg为牛头位置，end为牛尾位置
	for(int i=1;i<=n;i++)
	{
   
		beg=max(end,a[i]-xmid-x);//找最靠左的牛头的位置
		if(abs(beg-a[i]+x)>xmid)return true;//判断绳子长度是否超过xmid
		end=beg+2*x;//尾
		if(end>m)return true;
	}
	return false;
}
int main()
{
   
	scanf("%d%d%d",&n,&x,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	r=m;//初值
	while(l<=r)//二分
	{
   
		int mid=(l+r)/2;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
	if(l>m)printf("-1");//输出
	else printf("%d",l);
	return 0;
}

3.小A的游戏


解题思路

考虑如果出现两个相同字符之间的距离小于等于k时，小A一定可以删除这连续的一段，让小B无法判断他删除的是前面的字符还是后面的字符，否则则小B一定能判断
所以当且仅当出现两个相同字符之间的距离小于等于k时，答案为Uncertain，否则答案为Certain

注意：可能全删掉，就是“Certain”

AC代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int t,k,last[26];
string s;
int main()
{
   
	scanf("%d",&t);
	while(t)
	{
   
		t--;
		cin>>s;
		scanf("%d",&k);
		int l=s.size();//长度
		if(l==k)printf("Certain\n"); //特判，全删掉 
		else 
		{
   
			int ok=1;//初值
			memset(last,-1,sizeof(last));//初值
			for(int i=0;i<l;i++)//核心思路
			{
   
				int j=s[i]-'a';
				if(last[j]!=-1&&i-last[j]<=k){
   ok=0;printf("Uncertain\n");break;}//看两个相同字母的距离
				last[j]=i;
			}
			if(ok)printf("Certain\n"); //其他情况
		}
	}
	return 0;
}

4.小Biu闯关


解题思路

因为根据推理我们可以得出：
[a,b]可以表示[2a,2b]，[3a,3b]，[4a,4b]……[ka,kb]
长度分别为2b-2a+1，3b-3a+1，4b-4a+1……kb-ka+1
当kA<=(k-1)B时，区间就发生重合，之后的数就全部都能凑出来
于是，我们可以暴力求k，顺便求结果
核心

if(nextl<=r)//判断是否重叠
{
   
	ans+=(Y-max(X,l)+1);//求出结果
	break;
}
else ans+=(min(Y,r)-max(X,l)+1);//累加不能表达数的个数

但是，我们要考虑k的初始值
假如样例为这样
1
3 3 10 10
按照我的思路
设k的初始值为1
到ans+=(min(Y,r)-max(X,l)+1)这一步时就会累加负数
所以k要初值

if(B<X)i=X/B+1;//初值

就OK了

AC代码

#include<cstdio>
#include<algorithm>
using namespace std;
long long t,A,B,X,Y;
int main()
{
   
	scanf("%lld",&t);
	while(t)
	{
   
		t--;
		scanf("%lld%lld%lld%lld",&A,&B,&X,&Y);
		long long i=1,ans=0;//初值
		if(B<X)i=X/B+1;//初值
		while(1)
		{
   
			long long l=i*A,r=i*B,nextl=(i+1)*A;//方便后面
			if(l>Y)break;//如果l大于要表示最大的数Y，就退出
			if(nextl<=r)//判断是否重叠
			{
   
				ans+=(Y-max(X,l)+1);//求出结果
				break;
			}
			else ans+=(min(Y,r)-max(X,l)+1);//累加结果
			i++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

总结

分数
预估：10+100+20+10=140
实际：27+5+0+0=32
第二题二分l和r的初值没赋值好
其他题有点不会

谢谢