从简单的开始。
C F B E A G
C：签到题。
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
double t,sum,n,flag,add;
char c;
cin>>t;
while(t--)
{
sum=0;
cin>>n;
c=getchar();
for(add=0;add<n;add++)
{
flag=1;
c=getchar();
while(c!=10)
{
if(c=='2'&&flag)
{
flag=0;
sum++;
}
c=getchar();
}
}
sum=sum/n;
printf("%lf\n",sum);
}
return 0;
}F：记每次操作的得分为p1，p2，p3...易证p1>=p2>=p3>=...，又有第一个人的得分为p1+p3+p5+...，第二个人的得分为p2+p4+p6+...故第一个人必胜。
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
cout<<"Yes"<<endl;
}
return 0;
}B：简单的运算。写复杂了，还能简化，并且可以通过数组实现多重括号的运算。
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
char p[100002]={0};
int main()
{
long long flag=0,sum1=0,sum2=0,add=0,n,times,k,flag2;
char c;
c=getchar();
while(c!=10)
{
p[add++]=c;
c=getchar();
}
n=add;
for(add=0;add<n;add++)
{
times=0;
flag2=0;
if(flag==0)
{
if(p[add]=='C'||p[add]=='H'||p[add]=='O')
{
if(p[add]=='C') k=13;
if(p[add]=='H') k=1;
if(p[add]=='O') k=17;
while(p[add+1]<='9'&&p[add+1]>='0')
{
times=times*10;
times+=p[add+1]-'0';
add++;
flag2=1;
}
if(!flag2)
times=1;
sum1+=k*times;
}
else if(p[add]=='(')
flag=1;
}
else
{
if(p[add]=='C'||p[add]=='H'||p[add]=='O')
{
if(p[add]=='C') k=13;
if(p[add]=='H') k=1;
if(p[add]=='O') k=17;
while(p[add+1]<='9'&&p[add+1]>='0')
{
times=times*10;
times+=p[add+1]-'0';
add++;
flag2=1;
}
if(!flag2)
times=1;
sum2+=k*times;
}
else if(p[add]==')')
{
flag=0;
while(p[add+1]<='9'&&p[add+1]>='0')
{
times=times*10;
times+=p[add+1]-'0';
add++;
flag2=1;
}
if(!flag2)
times=1;
sum1+=sum2*times;
sum2=0;
}
}
}
printf("%lld",sum1);
return 0;
}E：体力题。首先将十六进制转化为二进制，通过二分查找找到对应数值，再转回十六进制。
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int s[100000],r[8],zz[32],yy;
long long j[100000];
int main()
{
long long k[31];
k[0]=1;
int n,m,p,add,x,sum;
char c;
scanf("%d %d %d",&n,&m,&p);
for(add=1;add<=30;add++)
{
k[add]=k[add-1]*2;
}
for(add=0;add<k[m-p];add++)
{
scanf("%lld",&j[add]);
j[add]=j[add]*100000+add;
}
sort(j,j+k[m-p]);
for(add=0;add<k[m-p];add++)
{
s[add]=j[add]%100000;
j[add]=j[add]/100000;
}
cin>>x;
while(x--)
{
c=getchar();
for(add=0;add<8;add++)
{
c=getchar();
if(c<='9'&&c>='0')
r[add]=c-'0';
else
r[add]=c-'A'+10;
}
for(add=0;add<8;add++)
{
zz[add*4]=r[add]/8;
if(zz[add*4]) r[add]-=8;
zz[add*4+1]=r[add]/4;
if(zz[add*4+1]) r[add]-=4;
zz[add*4+2]=r[add]/2;
if(zz[add*4+2]) r[add]-=2;
zz[add*4+3]=r[add];
}
sum=0;
for(add=0;add<32-p;add++)
{
sum=sum*2;
sum+=zz[add];
}
for(add=0;add<k[m-p];add++)
{
if(sum==j[add])
break;
}
if(add==k[m-p])
{
cout<<"interrupt!"<<endl;
continue;
}
else
{
yy=s[add];
for(add=0;add<32-p;add++)
{
if(yy>=k[32-p-add-1])
{
zz[add]=1;
yy-=k[32-p-add-1];
}
else
zz[add]=0;
}
for(add=0;add<8;add++)
{
r[add]=0;
for(int add2=0;add2<4;add2++)
{
r[add]=r[add]*2;
r[add]+=zz[add*4+add2];
}
if(r[add]<10)
cout<<r[add];
else
printf("%c",r[add]-10+'A');
}
cout<<endl;
}
}
return 0;
}A：从这题开始略有难度。首先可以将题转化为 将n/k分解成三个互质的且不为一的数。
令n=n/k。考虑n为偶数，则三个数一定为偶+奇+奇，不妨设a=2，b=n/2-1,c=n/2+1，如果b和c为偶数则b--，c++。
若n为奇数，考虑n%3==0，则a=n/3-2,b=n/3,c=n/3+2。考虑n%3==2，则a=(n-2)/3-2,b=(n-2)/3,c=(n-2)/3
+2+2。此时会出现a与c都是3的倍数的情况，则a-=2,b+=2。考虑n%3==4也就是n%3==1,a=(n-4)/3-2,b=(n-4)/3+2,c=(n-4)/3+2+2。此时会出现a与c都是3的倍数的情况，则b-=2，c+=2。
易证使用上面的方法不会出现abc不互质的情况，但需要排除abc为1的情况，即n<=9，n=11，13，17
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
long long t,n,k,a,b,c;
cin>>t;
while(t--)
{
cin>>n>>k;
if(n%k!=0)
{
printf("-1 -1 -1\n");
continue;
}
n=n/k;
if(n<=9||n==11||n==13||n==17)
{
printf("-1 -1 -1\n");
continue;
}
if(n%2==0)
{
a=2;
b=(n-2)/2-1;
c=(n-2)/2+1;
if(b%2==0)
{
b--;
c++;
}
}
else
{
if(n%3==0)
{
a=n/3-2;
b=n/3;
c=n/3+2;
}
else if(n%3==2)
{
a=(n-2)/3-2;
b=(n-2)/3;
c=(n-2)/3+2+2;
if(c%3==0)
{
a-=2;
b+=2;
}
}
else if(n%3==1)
{
a=(n-4)/3-2;
b=(n-4)/3+2;
c=(n-4)/3+2+2;
if(c%3==0)
{
b-=2;
c+=2;
}
}
}
a=a*k,b=b*k,c=c*k;
printf("%lld %lld %lld\n",a,b,c);
}
}G：没有全过，回头再找一下疏漏。
大体思路是用dp。将问题转化在2n+1个数中取n个不相邻的数，找最大的和。假设取1 3 5 7...2n-1，那么可以将问题转化为：将两个空格插入已经取好的数列中。即：将两个空格安排再2n+1个数中间。因此设立数组zz[200020][3]，其中zz[a][b]表示到第a个数已经用了b个空格的情况下，可能的最大值。
例：有1 3 6 2 4 8 9 7
zz[1][0]=1
zz[1][1]=-1e17
zz[1][2]=-1e17 注意到取第一个数的话，不可能是已经使用了一个或两个空格的状态
zz[2][0]=-1e17 注意到取第二个数的话，不可能是没有使用空格的状态
zz[2][1]=3
zz[2][2]=-1e17
zz[3][0]=zz[1][0]+6=7 不使用空格，那么应该取第1 3个数
zz[3][1]=-1e17
zz[3][2]=6 两个空格，即第1和第2都不取，直接取第3
zz[4][1]=max(zz[2][1],zz[1][0])+2 要么从1跳过来，要么从2顺延过来。换句话说，一种是取1 4，一种是取2 4，两种都是用了一个空格的情况。
zz[5][0]=zz[3][0]+4=11 取第1 3 5个数
zz[5][2]=max(zz[3][2],zz[1][0])+4 要么从1跳过来，要么从3顺延过来。换句话说，一种是取1 5，一种是取3 5，两种都是用了两个空格的情况。
...
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
long long j[200020],v[200020]={0},zz[200020][3];
int main()
{
long long find(int left,int right);
long long n,x,add,lmax,lmm,rmax,rmm,sumt,summax=-1e16;
cin>>n>>x;
for(add=1;add<=n;add++)
scanf("%lld",&j[add]);
if(n%2==0)
{
sumt=0;
for(add=1;add<n;add+=2)
{
sumt+=j[add];
v[add]=1;
}
summax=sumt;
for(add=n-1;add>0;add-=2)
{
sumt-=j[add];
sumt+=j[add+1];
v[add]=0;
v[add+1]=1;
if(summax<sumt&&v[x]) summax=sumt;
}
cout<<summax;
return 0;
}
if(x%2==0)
{
sumt=0;
for(add=2;add<=n;add+=2)
sumt+=j[add];
summax=sumt;
for(add=2;add<x;add+=2)
{
sumt-=j[add];
sumt+=j[add-1];
if(sumt>summax) summax=sumt;
}
sumt=summax;
for(add=n-1;add>x;add-=2)
{
sumt-=j[add];
sumt+=j[add+1];
if(sumt>summax) summax=sumt;
}
cout<<summax;
return 0;
}
if(x!=1&&x!=n)
{
sumt=0;
for(add=1;add<x;add+=2)
sumt+=j[add];
lmax=sumt;
sumt=0;
for(add=x+2;add<=n;add+=2)
sumt+=j[add];
rmax=sumt;
lmm=find(1,x-2);
rmm=find(x+2,n);
if(lmm+rmax>rmm+lmax) summax=lmm+rmax;
else summax=rmm+lmax;
cout<<summax+j[x];
return 0;
}
if(x==n)
cout<<find(1,n-2)+j[x];
else
cout<<find(3,n)+j[x];
return 0;
}
long long find(int left,int right)
{
long long max(long long a,long long b);
long long max3(long long a,long long b,long long c);
long long n=right-left+1,add,ans;
zz[left][0]=j[left];
zz[left+1][1]=j[left+1];
zz[left+2][0]=zz[left][0]+j[left+2];
zz[left+2][2]=j[left+2];
for(add=left+3;add<=right;add++)
{
if((add-left)%2==1)
zz[add][1]=max(zz[add-3][0]+j[add],zz[add-2][1]+j[add]);
else
{
zz[add][0]=zz[add-2][0]+j[add];
zz[add][2]=max3(zz[add-4][0]+j[add],zz[add-3][1]+j[add],zz[add-2][2]+j[add]);
}
/*cout<<add<<endl;
for(add2=0;add2<3;add2++) cout<<zz[add][add2]<<" ";
cout<<endl;*/
}
if(n==1) return 0;
if(n==3) return max3(j[left],j[left+1],j[left+2]);
ans=max3(zz[right-2][0],zz[right-1][1],zz[right][2]);
return ans;
}
long long max(long long a,long long b)
{
if(a>=b)
return a;
return b;
}
long long max3(long long a,long long b,long long c)
{
if(a>=b&&a>=c)
return a;
if(b>=c)
return b;
return c;
}
京公网安备 11010502036488号