2020.10.27【CSP-J/S】普及组模拟赛总结

题号	题目
T1	魔法阵~
T2	小biu放牛
T3	小A的游戏
T4	小Biu闯关
得分	137/380

---

T1

思路

举几个例子，发现能组成的正多边形边数一定是原来的正多边形的边数的约数。
这时，只要枚举每种正多边形可能的情况并维护最大值即可。

代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int t[200010];
int c[200010];
int n,js,n_ans;
int check(int x)
{
	int k=1,sum=0,ans=-2147483647;
	while(k<=n/x)
	 {
	 	for(int i=k; i<=n; i+=n/x)
	 	   sum+=t[i];
	 	ans=max(ans,sum);
	 	k++,sum=0;
	 }
	return ans;
}
int main()
{
	cin>>n;
	for(int i=1; i<=n; i++)
	 {
	   scanf("%d",&t[i]);
	   n_ans=n_ans+t[i];
	 }
	for(int i=3; i<=n/2; i++)
	 if(n%i==0)
	   c[++js]=i;
	for(int i=1; i<=js; i++)
	   n_ans=max(check(c[i]),n_ans);
    cout<<n_ans;
	return 0;
}

T2

思路

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

代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,x,m,ans,l,r,mid;
int mz[100010];
bool check(int mi)
{
	int sp=x;
	for(int i=1; i<=n; i++)
	 {
	 	sp=max(mz[i]-mi,sp);
	 	if(sp>mz[i]+mi)
	 	  return false;
	 	sp+=x*2;
	 	if(sp>m+x)
	 	  return false;
	 }
	return true;
}
int main()
{
	cin>>n>>x>>m;
	for(int i=1; i<=n; i++)
	   scanf("%d",&mz[i]);
    if(m/(x*2)<n)
	 {
	 	cout<<-1;
	 	return 0;
	 }
	else
	 {
	 	l=0,r=m;
	 	while(l<=r)
	 	 {
	 	 	mid=(l+r)/2;
	 	 	if(check(mid)==1)
	 	 	  r=mid-1;
	 	 	else
	 	 	  l=mid+1;
		 }
	 }
	cout<<r+1;
	return 0;
}

T3

思路

本题通过找规律可以发现，
当两个重复数字的最小距离 < = <= <= 删除字符就不可猜。
如果两个相同字符挨在一起也不可猜。
其余情况可猜。

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int t,sb,w,ans;
int sz[27][3];
string s;
int main()
{
	cin>>t;
	while(t--)
	 {
	 	w=0;
	 	cin>>s>>sb;
	 	if(sb>=s.size())
	 	 {
	 	 	cout<<"Certain"<<endl;
	 	 	continue;
		 }
	 	memset(sz,0,sizeof(sz));
	 	for(int i=1; i<=26; i++)
	 	   sz[i][3]=128;
	 	for(int i=0; i<=s.size()-1; i++)
	 	 {
	 	   sz[s[i]-96][1]++;
	 	   if(sz[s[i]-96][1]>=2)
	 	     sz[s[i]-96][3]=min(i-sz[s[i]-96][2],sz[s[i]-96][3]);
		   sz[s[i]-96][2]=i;
		 }
		for(int i=1; i<=26; i++)
		 {
		   if(sz[i][3]==1)
		    {
		      cout<<"Uncertain"<<endl;
		      w=1;
		      break;
			}
		   if(sz[i][3]<=sb&&sz[i][3]!=0)
		    {
		     cout<<"Uncertain"<<endl;
		     w=1;
             break;
			}
		 }
		if(w==0)
		  cout<<"Certain"<<endl;
	 }
	return 0;
}

T4

思路

首先我们可以知道：它可以覆盖 [ a , b ] , [ 2 a , 2 b ] , [ 3 a , 3 b ] … … [ k a , k b ] ( k > 0 ) [a,b], [2a,2b], [3a,3b]……[ka,kb](k>0) [a,b],[2a,2b],[3a,3b]……[ka,kb](k>0)
那我们来想怎样计算答案
分类讨论

1. 未出现区间交集
   通过等差数列求和公式，我们可以算出
   ( ( b − a ) + ( ( p − 1 ) ∗ b − ( p − 1 ) ∗ a ) ) ∗ ( p − 1 ) / 2 ((b-a)+((p-1)*b-(p-1)*a))*(p-1)/2 ((b−a)+((p−1)∗b−(p−1)∗a))∗(p−1)/2
   其中p表示当完整的区间的个数
   这个式子就是求 [ a , b ] , [ 2 a , 2 b ] , [ 3 a , 3 b ] … … [ p a , p b ] ( p > 0 ) [a,b], [2a,2b], [3a,3b]……[pa,pb](p>0) [a,b],[2a,2b],[3a,3b]……[pa,pb](p>0) 可以覆盖总共的数字个数
   化简得
   ( ( b − a ) + ( ( p − 1 ) ∗ ( b − a ) ) ) ∗ ( p − 1 ) / 2 ((b-a)+((p-1)*(b-a)))*(p-1)/2 ((b−a)+((p−1)∗(b−a)))∗(p−1)/2
   p ∗ ( b − a ) ∗ ( p − 1 ) / 2 p*(b-a)*(p-1)/2 p∗(b−a)∗(p−1)/2
   然后加上要求的数的位置和区间右端点 − - − 最后一个区间的起始位置即可
   即 m i n ( x x , p ∗ b ) − p ∗ a + 1 min(xx,p*b)-p*a+1 min(xx,p∗b)−p∗a+1
   为什么是 min ⁡ \min min 呢，因为直接用xx的话最后有一些没有覆盖到的区间会被算进去，所以要和最后的那个区间的右端点取个 min ⁡ \min min
   所以就是
   p ∗ ( p − 1 ) ∗ ( b − a ) / 2 + p − 1 + m i n ( x x , p ∗ b ) − p ∗ a + 1 p*(p-1)*(b-a)/2+p-1+min(xx,p*b)-p*a+1 p∗(p−1)∗(b−a)/2+p−1+min(xx,p∗b)−p∗a+1
2. 出现区间交集
   其实和上面差不多
   k ∗ ( k − 1 ) ∗ ( b − a ) / 2 k*(k-1)*(b-a)/2 k∗(k−1)∗(b−a)/2
   其中k代表在区间开始出现交集的那个区间的编号
   此式子和上面的化简过程一样
   再加上要求的数的位置 − - − 最后一个不完整的区间的起始位置就可以了
   即 x x − k ∗ a + 1 xx-k*a+1 xx−k∗a+1
   所以就是
   k ∗ ( k − 1 ) ∗ ( k − a ) / 2 + k − 1 + x x − k ∗ a + 1 k*(k-1)*(k-a)/2+k-1+xx-k*a+1 k∗(k−1)∗(k−a)/2+k−1+xx−k∗a+1

代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long T,a,b,x,y,k;
long long solve(long long xx)
{
	long long p=xx/a;
	if(k<=p)
	  return (b-a)*k*(k-1)/2+k-1+(xx-k*a+1);
	else
	  return (b-a)*p*(p-1)/2+p-1+(min(xx,p*b)-p*a+1);
}
int main()
{
	cin>>T;
	while(T--)
	 {
	 	cin>>a>>b>>x>>y;
	 	k=(a-1)/(b-a)+1;
	 	cout<<solve(y)-solve(x-1)<<endl;
	 }
	return 0;
}