2023.5.16练习赛总结
T1 魔法阵
题目描述
小Biu潜心学习魔法，他发现魔法阵一定是一个正多边形（边数至少为3），而且正多边形的每个点上都有一个魔力值，整个魔法阵的魔力值就是正多边形的顶点上每个魔力值的和，现在小Biu有一个正n边形魔法阵，小Biu可以删掉这个魔法阵上的一些点，但是要保证删除之后这仍是一个魔法阵，也就是说删除一些点之后，剩余点仍然可以组成一个正多边形（边数至少为3），问小Biu能得到的魔力值最大的魔法阵的魔力值是多少?
思路
当 n= \(8\)，因为要考虑到所有点，所以要在 \(3\)~\(7\) 中找 \(8\) 的因数，因为只有 \(4\)，所以只能变成正四边形，如图，只需要枚举两次，因为第三次之后就重复了。那么答案就是对这两种可能求和再取最大值。
\(code\)
//我这里对于a数组用了前缀和
for(int i=3;i<n;i++)
if(n%i==0)
for(int j=0;j<n/i;j++){
int res=0;
for(int p=j;p<n;p+=n/i)
res+=a[p];
ans=max(res,ans);
}
T2 小biu放牛
题目描述
小Biu最喜欢的活动就是放牛，但是由于他比较懒，所以他喜欢把牛拴在木桩上，小Biu有N头牛和N个木桩，农场的总长度为M，每头牛的身长为2*x，N个木桩为位置分别为p[i],现在小Biu想把所有的牛排成一排，并且每只牛都必须栓在木桩上，小Biu一般选择在牛身的中间栓绳子，所以可以认为绳子的位置距离牛头和牛尾的距离都是x。而且一个木桩只能栓一个牛，牛和牛的身体间不能重叠，现在小Biu想知道，如果他想把这N只牛拴在这N个木桩上，需要的所有绳子中的最长的那个绳子长度最小为多少，如果农场不能放下所有的牛，输出-1。
思路
我们要贪心把牛放在最前面，那么牛头的位置就是 \(i-t-x\) ；但是题目要求不能重叠，用 \(max\) 比较一下，确定牛头的位置在哪，这样保证了靠前。再用头部的位置，判断是否越界。最后还要判断一下尾部有没有越界（前面因为这个卡了好久）。
每次没必要一个一个贪心，可以通过二分优化
\(code\)
bool pd(int t){ //贪心
int head=0,tail=0;
for(int i=1;i<=n;i++){
head=max(tail,a[i]-t-x);
if(abs(head-a[i]+x)>t) return false;
tail=head+2*x;
if(tail>m) return false;
}
return true;
}
T3 小A的游戏
题目描述
小A在和小B玩一个游戏，小A有一个字符串S，现在小A删除了其中K个字符，给出删除前的字符串S，和删除后的字符串S'，现在小A想知道，是否无论怎样删除，小B都能猜中他删除了哪些位置上的字母。
若一定，输出 Certain ，否则输出 Uncertain 。
当删除一些位置后，从剩下的一段看不出来删除的哪些位置。如果 \(S\) 串中存在这样的模型，那就是 Unsertain。
思路
我们发现当两个字符及以上相同，如：luqyousbb，当删除 \(b\)，那么这个 \(b\) 可能在 \(8\) ，可能在 \(9\)，这时就不能确定删除了哪里。
另外当 k==l ( \(l\) 是字符串的长度)，也要输出 Certain，因为是全部删除，删除后的串为空，当然猜得到删了哪里。
\(code\)
if(k==l){ //判断特殊情况
cout<<"Certain\n";
continue;
}
int flag=0;
for(int i=1;i<=l;i++){
for(int j=i+1;j<=l;j++)
if(s[i]==s[j]){
if(j-i<=k) flag=1;
break;
}
if(flag) break;
}
if(flag) cout<<"Uncertain\n";
else cout<<"Certain\n";
T4 小Biu闯关
题目描述
小Biu现在在玩一个闯关游戏，他手上有[A,B]区间上的每个数字，现在关卡中有很多boss，第一个boss的血量为x，第二个boss的血量为x+1，第三个boss的血量为x+2...最后一个boss的血量为y，小Biu闯每一关的时候都可以多次重复使用手上的数字，当且仅当他恰好可以用手上的数字组成某个boss的血量时，它可以击杀那个boss，boss没有先后顺序，也就是说不需要依次击杀，现在小Biu想知道他可以击杀多少Boss。
思路
首先考虑用 \([A,B]\) 区间能凑成的区间为 \([A,B],[2A,2B],[3A,3B]....[kA,kB]\)
当 \(kA<=(k−1)B\) 时 区间就发生重合 之后的数就全部都能凑出来
所以我们只需要快速找到这个 \(k\) 即可 我们发现 \(kA-(k-1)B\) 满足单调性 所以我们可以二分这个 \(k\)
int solve(int n,int x,int y){
int a=(x-1)/(y-x)+1,b =n/x;
if(a<=b) return a*(a-1)/2*(y-x)+a-1+n-a*x+1;
return b*(b-1)/2*(y-x)+b-1+min(n,b*y)-b*x+1;
}
int x=read(),y=read(),L=read(),R=read(); //对于每组数据
cout<<solve(R,x,y)-solve(L-1,x,y)<<endl;