题出的好！难度适中，覆盖知识点广，题目又着切合实际的背景，解法比较自然。给出题人点赞 ！
然而我太菜了，只会8/13，差不多一半不会
A: 文远知行β
题目加粗，n个时刻速度均大于0.
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int t,n;
int main()
{
cin>>t;
while(t--)
{
bool ok=1;
int x;
cin>>n;
for(int i=1;i<=n;i++){cin>>x;if(!x)ok=0;}
if(ok)puts("WeRide.ai");
else puts("Transform Mobility With Autonomous Driving");
}
return 0;
} B: 学姐是野兔先辈β
原来是0不变，原来非0一半概率x-lowbit（x），一半概率x+lowbit（x），期望还是x，因此不管怎么操作答案就是原数列的值。
所以用前缀和就出来了。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int t,n,m,a[100005];
char type[105],name[105];
int l,r,num;
int sum[100005];
int main()
{
//freopen("input.in","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sum[1]=a[1];
for(int i=2;i<=n;i++)sum[i]=sum[i-1]+a[i];
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&num,&l,&r);
if(num==2)
{
printf("%d\n",sum[r]-sum[l-1]);
}
}
}
return 0;
} C: 名为青春的悖论β
以一个点为基准点，用一个数组s[]记录每个点与基准点的距离，开个桶have[x]==0or1记录是否存在一个点与基准点距离为x，要形成矩形，就是选两条直径，对应的4个点一定能围成矩形，设tot为直径条数，矩形个数为c（tot，2）。
要求出tot，只需在从基准点开始的半圆内枚举每一个点，看另半个圆里是否有点与此点距离为半圆周长。如果圆周长为奇数，那么一定不存在两点位于一条直径上，因为点间距离都是整数。
复杂度o（n）
#include<iostream>
#include<cstring>
using namespace std;
int n,s[305],cir;
bool have[4505];
int main()
{
//freopen("input.in","r",stdin);
while(cin>>n)
{
memset(have,0,sizeof(have));
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]+=s[i-1];
have[s[i]]=1;
}
cir=s[n]/2;
int tot=(have[cir]);
for(int i=1;s[i]<cir;i++)if(have[s[i]+cir])tot++;
if(s[n]&1)cout<<0<<endl;
else cout<<tot*(tot-1)/2<<endl;
}
return 0;
} D: 明日会吹明日的风？β
用gets（）每次读入一行，判断第一个字符就可以知道是哪种类型了。不知道为什么开始用scanf+strcmp一直wa，感觉情况都处理到了啊。。最后一小时换成gets（）马上就过了。。
//时隔一周，终于找到了错，原来在写strcmp时写的strcmp(type,"double "),double后面多了个空格。。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int t,n;
char name[100005];
int main()
{
//freopen("input.in","r",stdin);
scanf("%d",&t);
while(t--)
{
int ans=0;
scanf("%d",&n);
getchar();
for(int i=1;i<=n;i++)
{
fgets(name,10000,stdin);
if(name[0]=='i')ans+=4;
else if(name[0]=='f')ans+=4;
else if(name[0]=='d')ans+=8;
else if(name[0]=='l')ans+=8;
else if(name[0]=='c')ans+=1;
else if(name[0]=='b')ans+=1;
}
if(ans%1024==0)printf("%d\n",ans/1024);
else printf("%d\n",(ans/1024+1));
}
return 0;
} E: 把所有的谎言献给你β
把一个自然数划分为若干个不重复的数的和，使这些数之积最大。
首先，如果是把x划分为n份，可以每份相等，则乘积最大时每份都是x/n。（a+1）（a-1）=a*a-1，可以这么不准确地理解一下。自己对数字很不敏感，开始时认为乘积最大对应的每份都不相等，实际上是相等的。
划分的每份相等，那么划分多少次呢？如果不要求每份为整数，答案是每份为e，划分为x/e份。
推导见图：把k划分为n份
那么，如果是把一个自然数划分为若干个可重复的数的和，使这些数之积最大，只需根据x%3，尽可能多划分出3，剩下的划分为2.
把一个自然数划分为若干个不重复的数的和，使这些数之积最大。对于这个问题，详尽的思路参考这篇bloghttps://blog.csdn.net/u012879957/article/details/82382460
大体意思就是依次拆成2，3，4，5......k剩下的不能k+1的放到2~k之上。
#include<iostream>
using namespace std;
int main()
{
int t,n;
cin>>t;
while(t--)
{
long long ans=1;
cin>>n;
int k=2;
while((2+k+1)*(k-1+1)/2<=n)k++;
int t=k-(n-(2+k)*(k-1)/2)+1;
for(int i=2;i<=k;i++)ans*=(i<t?i:i+1);
if(t==1)ans=ans/(k+1)*(k+2);
if(n==1)cout<<"1 1\n";
else if(n==2)cout<<"2 2\n";
else cout<<n-1<<" "<<ans<<"\n";
}
return 0;
} F: 那天的延长线在今天β
模拟
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int t,n,a[10005];
int main()
{
//freopen("input.in","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int ans=1;
int pos=2;
while(pos<=n)
{
int i;
for(i=pos;i<=n;i++)
{
if(a[i]!=a[i-1]+1)break;
}
ans=max(ans,i-pos+1);
pos=i;
pos++;
}
printf("%d\n",ans);
}
return 0;
} G: 活在无尽梦境的后续 β
围成半圆
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define pi (acos(-1))
int t,n,m,a[100005];
char type[105],name[105];
int l,r,num;
int sum[100005];
int main()
{
//freopen("input.in","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%f\n",n*n/pi/2);
}
return 0;
} H: 以行走般的速度β
参考样例，自己手推，原数字与另一个数字互相正负转化4次后，回到原数字。因为转换后就不能再使用这个转换方式了，以n=6为例，2-4是4*2=8，2-6是4*3=12，3-6是4*2=8，其余2~6每个数字本身正负转换一次答案是33。可以假设每个数转化为它的所有因数一次，它的因数不转化为它。这样就是4-2，6-2，6-3，其余正负转化。
用这样的思路预处理就好了。
#include<cstdio>
using namespace std;
long long n,a[100005];
int main()
{
for(int i=2;i<=100000;i++)a[i]=1;
for(int i=2;i<=50000;i++)
{
for(int j=i*2;j<=100000;j+=i)
{
a[j]+=4*j/i;
}
}
for(int i=3;i<=100000;i++)a[i]+=a[i-1];
while(~scanf("%lld",&n))printf("%lld\n",a[n]);
return 0;
} I: 灰暗而空虚的景色β
三个要点：
1.假设有3个数：i<j<k,题目从前往后是jik,则先处理j，后处理i，和不处理j是一样的，处理完i，处理k，i~k由第二次操作确定，k~n由第三次操作确定。故从后往前看，只有当前处理的位置比后面处理的位置靠左边才做处理。
2. 1^2+2^2+3^2+......+n^2==n*(n+1)*(2*n+1)/6
3.x/y%k==x%(y*k)/y
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int t,n,q;
int query[100005];
long long ans;
long long fac(long long n)
{
long long ret=1;
ret=ret*n%(6*123456789);
ret=ret*(n+1)%(6*123456789);
ret=ret*(2*n+1)%(6*123456789);
ret/=6;
return ret;
}
int main()
{
// freopen("input.in","r",stdin);
scanf("%d",&t);
while(t--)
{
ans=0;
scanf("%d%d",&n,&q);
for(int i=1;i<=q;i++)scanf("%d",&query[i]);
long long last=n+1,pos=q,num=(1<<30);
while(pos>=1)
{
if(query[pos]>=num)pos--;
else
{
ans+=fac(last-query[pos]);
ans%=123456789;
last=query[pos];
num=query[pos];
pos--;
}
}
printf("%lld\n",ans);
}
return 0;
} J: 温柔的手彼此相系β
将电话号码标准化为数字或者字符串，用map<string,int>或map<int,int >来存，最后遍历时因为map本身就是按照key排序的，因此直接遍历一遍map就好了。比赛时忘了这个性质，用了好多东西，代码又臭又长。
自己是标准化为数字，这样就要注意电话号码第一位或者第四位为0时，输出要补0，直接输出的话就空了一位，好在最后一个小时终于看出来了。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<cctype>
#include<map>
using namespace std;
int n,cnt[100005];
vector<int> v,ans;
map<int,int> vis;
int num[26]={2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,0,7,7,8,8,8,9,9,9,0};
char s[1005];
int to[100005];
bool cmp(int x,int y)
{
return ans[x]<ans[y];
}
int main()
{
//freopen("input.in","r",stdin);
while(scanf("%d",&n)!=EOF)
{
vis.clear();
ans.clear();
memset(cnt,0,sizeof(cnt));
while(n--)
{
v.clear();
scanf("%s",s);
int len=strlen(s);
for(int i=0;i<len;i++)if(s[i]!='-')
{
if(isdigit(s[i]))v.push_back(s[i]-'0');
else v.push_back(num[s[i]-'A']);
}
int number=0;
for(int i=0;i<7;i++)number=number*10+v[i];
if(vis.count(number))
{
for(int i=0;;i++)
{
if(ans[i]==number)
{
cnt[i]++;
break;
}
}
}
else
{
ans.push_back(number);
cnt[ans.size()-1]++;
vis[number]=1;
}
}
n=ans.size();
for(int i=0;i<n;i++)to[i]=i;
sort(to,to+n,cmp);
bool ok=0;
for(int i=0;i<n;i++)if(cnt[i]>1)ok=1;
if(!ok)printf("No duplicates.\n");
else
for(int i=0;i<n;i++)
{
int pos=to[i];
if(cnt[pos]==1)continue;
printf("%03d-%04d %d\n",ans[pos]/10000,ans[pos]%10000,cnt[pos]);
}
}
return 0;
} K: Complex Congratulation β
题目两个要求
1.影响力之和越大越好（恰好每个影响力都非负）
2.至少一半的人支持A&&至少一半的人支持B
既支持a又支持b的对1有好处又对2有好处，全部选中。支持1的和支持2的成对选中，对1有好处，对2没影响。剩下的光支持一方但无法配对的和都不支持的选中影响力最大的k个人，k=同时支持ab的人数。
#include<cstdio>
#include<algorithm>
using namespace std;
int n,ab,a,b,no,ans;
int power[4][400005];
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
//freopen("input.in","r",stdin);
int x,y;
while(scanf("%d",&n)!=EOF)
{
ans=ab=a=b=no=0;
for(int i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
if(x==11){ab++;power[0][ab]=y;}
else if(x==10){a++;power[1][a]=y;}
else if(x==1){b++;power[2][b]=y;}
else {no++;power[3][no]=y;}
}
for(int i=1;i<=ab;i++)ans+=power[0][i];
sort(power[a>b?1:2]+1,power[a>b?1:2]+1+(a>b?a:b),cmp);
for(int i=1;i<=min(a,b);i++)ans+=power[1][i]+power[2][i];
for(int i=min(a,b)+1;i<=(a>b?a:b);i++)power[3][++no]=power[a>b?1:2][i];
sort(power[3]+1,power[3]+1+no,cmp);
for(int i=1;i<=ab;i++)ans+=power[3][i];
printf("%d\n",ans);
}
return 0;
} L: 只有我不在的世界β
lcm/a==b/gcd，故数量==b/gcd的个数==gcd的个数，枚举就行了。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define pi (acos(-1))
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int t,n,m,a[100005];
char type[105],name[105];
int l,r,num;
int sum[100005];
int cnt[1005];
int main()
{
//freopen("input.in","r",stdin);
scanf("%d",&t);
while(t--)
{
int tot=0;
memset(cnt,0,sizeof(cnt));
scanf("%d",&n);
for(int i=1;i<=1000;i++)
{
int ans=gcd(n,i);
if(!cnt[ans])
{
cnt[ans]=1;
tot++;
}
}
printf("%d\n",tot);
}
return 0;
} M: 在那天的雪停息之前β
模拟
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int t,n,m,a[100005];
char type[105],name[105];
int l,r,num;
int sum[100005];
int main()
{
//freopen("input.in","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
while(n!=1)
{
if(n&1)
{
printf("%d*3+1=%d\n",n,3*n+1);n=n*3+1;
}
else
{
printf("%d/2=%d\n",n,n/2);n=n/2;
}
}
if(t)puts("");
}
return 0;
}
京公网安备 11010502036488号