CF1537
A:
三种情况：
- 直接相等.
- 小于长度，输出1.
- 大于长度，补充0.
#include<bits/stdc++.h>
using namespace std;
int T,n,b;
int main(){
cin>>T;
while(T--){
cin>>n; int ans=0,sum=0;
for(int i=1;i<=n;i++) cin>>b,sum+=b;
if(sum==n) cout<<0<<endl;
else if(sum<n) cout<<1<<endl;
else cout<<sum-n<<endl;
}
// system("pause");
return 0;
}
B:
肯定是两个顶点啊.....
printf("%d %d %d %d\n",1,1,n,m);
C:
贪心考虑：将原数组从小到大排序，找到差分最小值，地址为 \(pos\)。
然后输出从 \([pos,n]\) 和 \([1,pos]\) 即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=2e5+5;
int a[M],T,n,imin,pos;
int main(){
cin>>T;
while(T--){
cin>>n; imin=0x3f3f3f3f,pos=0;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
if(n==2){
printf("%d %d\n",a[1],a[2]);continue;
}
for(int i=2;i<=n;i++)if(a[i]-a[i-1]<imin)imin=a[i]-a[i-1],pos=i;
for(int i=pos;i<=n;i++)printf("%d ",a[i]);
for(int i=1;i<pos;i++)printf("%d ",a[i]);puts("");
}
return 0;
}
D:
依旧是分类讨论的题目。
- \(n\) 为奇数
- \(n\) 为偶数不为 \(2\) 的幂
- 是 \(2\) 的幂。
第一种情况其实可以转化成第二种情况，但是过程不一样。
接下来我们要证明面对这种情况是必胜的。
由于 \(n\) 是偶数但不是 \(2\) 的幂，那么一定存在一个奇数非 \(1\) 约数 \(k\).
考虑让 \(n\) 减掉这个 \(k\)，就转化为第 \(1\) 种情况。而这样循环会在哪一步结束呢？很显然是在第 \(1\) 种情况结束.
而第一种情况会在为质数的时候停止。
因此，第一种情况必败，第二种情况必胜。
第三种情况，我们可以转化成第二种情况，也可以转化成第三种情况。
因为第二种必胜，那么我们只能对半减去，这样是最优抉择。
是 2 的奇数次幂，必败，偶数次幂必胜。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll T,x,p;
int main(){
cin>>T;
while(T--){
cin>>x; p=2;
while(p<x) p*=4;
if(p==x||x%2==1) cout<<"Bob"<<endl;
else cout<<"Alice"<<endl;
}
return 0;
}
E1：
直接暴力计算即可，比较简单。
这里就一起说两题的代码了。
E2:
证明以下结论：
最优解一定是通过先执行操作 1，后执行操作 2 来得到的。
因为如果最优解是执行了一些操作 2 之后，再执行的操作 1，那么我们发现把操作 1 放到操作 2 之前操作一定会使答案变得不劣。
所以问题就转化成给定一个字符串 \(s\)，需要保留 \(s\) 的一个前缀 \(pre\)，同时让 \(pre\) 复制若干次，得到一个长度为 \(k\) 的字符串（多余的部分删去）。目标是让最终的字符串的字典序最小。
暴力即可解决问题一。
- 若 \(s[i]>s[i\%p]\)，直接跳出循环。
- 若 \(s[i]<s[i\%p]\)，我们发现用前缀 \(s[0\sim i]\) 比前缀 \(s[0\sim p-1]\) 更优，于是令 \(p\gets i+1\)
- 若 \(s[i]=s[i\%p]\)，这并不能说明什么，我们只能什么都不做。
#include<bits/stdc++.h>
using namespace std;
int n,k; string s;
int main()
{
cin>>n>>k>>s;
int p=1,n=s.length();
for(int i=0;i<n;i++){
if(s[i]>s[i%p]) break;
if(s[i]<s[i%p]) p=i+1;
}
for(int i=0;i<k;i++) putchar(s[i%p]); puts("");
// system("pause");
return 0;
}