A. Puzzle From the Future
思路:要使得值最大 那么数应该在前面出现的越多越好并且长度不缩减低
所以我们首先把第一个位置作为1 用pre标记1出现最近的位置
从前往后推
所以输出1有3种情况
如果前一个数大于我而且我输出的位置刚好pre=1 那么输出1
如果前一个数小于我 那么输出1
如果前一个数等于我且pre>1 那么输出1
反之输出0
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
char str[N];
int main(){
int T;
cin>>T;
while(T--){
int n;
scanf("%d",&n);
scanf("%s",str+1);
printf("1");
int pre=1;
for(int i=2;i<=n;i++){
if((str[i-1]>str[i]&&i-pre==1)||(str[i]==str[i-1]&&i-pre>=2)||str[i-1]<str[i]){
printf("1");
pre=i;
}
else printf("0");
}
puts("");
}
return 0;
}
B. Different Divisors
有一个很好想但是不正确
即答案为 (1+n)*(1+n+n)
但因为(1+n)如果不是质数那么他是能被分解的
所以我们要找的答案应该是
大于等于(1+n)的最小质数x1
和比x1 大n的最小质数x2
这里我们线性筛找出所有1e5内的质数 然后二分查找(遍历应该不太行吧)即可
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
char str[N];
int primes[N],cnt;
bool st[N];
void init(int n){
for(int i=2;i<=n;i++){
if(!st[i])primes[++cnt]=i;
for(int j=1;primes[j]<=n/i;j++){
st[i*primes[j]]=1;
if(i%primes[j]==0)break;
}
}
}
int main(){
int T;
cin>>T;
init(N-1);
while(T--){
int n;
scanf("%d",&n);
int x1=*lower_bound(primes+1,primes+1+cnt,n+1);
int x2=*lower_bound(primes+1,primes+1+cnt,n+x1);
cout<<x1*x2<<endl;
}
return 0;
}
C. Array Destruction
由题意 我们可以知道 必须选择剩余数中最大的那个数
然后我们依次枚举都会用到最大的那个数
所以我们一开始将数组排序 然后从后往前枚举即可 用vector记录答案即可
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
bool st[N];
int main(){
int T;
cin>>T;
while(T--){
int n;
scanf("%d",&n);
n=n*2;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
int flag=0;
vector<int>ans;
for(int i=1;i<=n-1;i++){
memset(st,0,sizeof st);
int sum=a[n]+a[i];
st[i]=1;
ans.clear();
ans.push_back(sum);
ans.push_back(a[n]);
ans.push_back(a[i]);
sum=a[n];
int pre=a[n];
for(int j=n-1;j>=1;j--){
sum=pre;
if(st[j])continue;
int flag=0;
for(int k=1;k<j;k++)
if(a[j]+a[k]==sum&&!st[k]){
st[k]=1;
flag=k;
break;
}
if(!flag)break;
else {
ans.push_back(a[j]);
ans.push_back(a[flag]);
}
pre=a[j];
}
if(ans.size()==n+1)break;
}
if(ans.size()==n+1){
puts("Yes");
printf("%d\n",ans[0]);
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);
if((i-1)&1)printf("\n");
}
}
else puts("No");
}
return 0;
}
D - Cleaning
我们考虑第一个石头和最后一个石头只能被第二个石头和倒数第二个石头消去
然后我们分别从前往后 从后往前求出pre[] 和 suf[]
分别记录从i-1点转移到i时剩余的石头数量 （用第 i 石头消去 i-1 石头后剩余多少石头）
和从i+1转移到i时的剩余石头数量（用第 i 石头消去 i+1 石头后剩余多少石头）
如果不能那么后续转移均为-1
如果已经pre[n]=0或者suf[n]=0了那么答案显然就是yes 因为所有石头都被消掉了
接着我们只要枚举即可 当时suf[r]和pre[l]不为-1时
我们交换l+1和r-1堆石头 在此之前判断是否分别能大于前缀 后缀
然后用r-1堆的石头减去前缀l的石头数 用l+1堆的石头减去后缀r的石头 如果相等即为yes
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e5+10;
int a[N],pre[N],suf[N];
bool st[N];
int main(){
int T;
cin>>T;
while(T--){
int n;
memset(suf,0,sizeof suf);
memset(pre,0,sizeof pre);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
if(a[i]<pre[i-1]||pre[i-1]==-1)pre[i]=-1;
else pre[i]=a[i]-pre[i-1];
}
if(pre[n]==0){
puts("Yes");
continue;
}
for(int i=n;i>=1;i--){
if(a[i]<suf[i+1]||suf[i+1]==-1)suf[i]=-1;
else suf[i]=a[i]-suf[i+1];
}
if(suf[1]==0){
puts("Yes");
continue;
}
int flag = 0;
for(int l=0,r=3;l<=n-2&&r<=n+1;l++,r++){//依次进行交换2个
if(pre[l]==-1&&suf[r]==-1) break;
if(pre[l]==-1||suf[r]==-1) continue;
if(pre[l]<=a[r-1]&&suf[r]<=a[l+1]&&a[r-1]-pre[l]==a[l+1]-suf[r]){flag=1;break;}
}//交换后用r-1堆的石头减去前缀l的石头数 用l+1堆的石头减去后缀r的石头 如果相等即为yes
if(flag)
puts("Yes");
else puts("No");
}
return 0;
}
![查找算法之二分查找查找算法之二分查找[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)