一.闲话
由于我太菜了，打不动了就来写题解了
A.A Simple Problem about election
贪心即可
先给自己票数加1，多余的尽量给票数增加后对自己排名无影响的人
如果还有剩，则排名=现在排名+剩下的票数(每给剩余人一票一定会使得自身排名+1)
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int a[N],b[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
++a[1];--m;
if(m){
for(int i=2;i<=n;++i){
if(a[i]>=a[1]){
++a[i];--m;
}else if(a[i]+1<a[1]){
++a[i];--m;
}
if(!m){
break;
}
}
}
int ans=0;
for(int i=1;i<=n;++i){
ans+=(a[i]>=a[1]);
}
printf("%d\n",ans+m);
}
return 0;
} B.看到几何脑壳痛，直接跳qwq
C.一道以前做过的后缀数组题，不过忘了qwq，就不想做了qwq(我好菜啊)
D.Deploy the medical team
超简单的数学题，先从m名队长中选一名作队长(因为队长唯一，所以无重复)，保证队伍一定有队长，剩下的随便选
答案即:
套个快速幂即可~
代码:
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
inline int ksm(int x,int y){
int ans=1;
while(y){
if(y&1){
ans=(1LL*ans*x)%mod;
}
x=(1LL*x*x)%mod;
y>>=1;
}
return ans;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
int ans=(1LL*m*ksm(2,n-1))%mod;
printf("%d\n",ans);
}
return 0;
} E盲猜差分约束，然而我spfa超时了qwq(估计有玄学的做法qwq我好菜啊)
F.Figure out the sequence
设表示第i次变换后，编号为j的字母的个数(我们最好将'A'-'Z'依次编为0-25,'a'-'z'依次编为26-51,这样方便输出)
读题目后，发现和菲波拉契很像(只是把数字的加法变成了字符串的加法而已)
所以，有递推式:
i=1和2时直接分别统计s,t串即可
代码:
#include<bits/stdc++.h>
using namespace std;
int dp[41][52];
int main(){
string x,y;
cin>>x>>y;
int n;
scanf("%d",&n);
int len=x.size(),ten=y.size();
for(int i=0;i<len;++i){
if(x[i]>='a'&&x[i]<='z'){
++dp[1][x[i]-'a'+26];
}else{
++dp[1][x[i]-'A'];
}
}
for(int i=0;i<ten;++i){
if(y[i]>='a'&&y[i]<='z'){
++dp[2][y[i]-'a'+26];
}else{
++dp[2][y[i]-'A'];
}
}
for(int i=3;i<=n;++i){
for(int j=0;j<52;++j){
dp[i][j]=dp[i-1][j]+dp[i-2][j];
}
}
for(int i=0;i<52;++i){
if(dp[n][i]){
if(i<26){
printf("%c: %d\n",char(i+'A'),dp[n][i]);
}else{
printf("%c: %d\n",char(i+'a'-26),dp[n][i]);
}
}
}
return 0;
} G.Game Strategy
直接模拟枚举即可，我们枚举最后剩下的数就行了，Alice取所有剩下的数中最大的那个方案，Bob取最小的那个方案，当Alice和Bob取的数确定时，Cindy取的数就固定了，我们直接算一遍就行了
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=101;
int a[N],b[N],c[N];int n;
inline int dfs2(int now){
int ans=2e9;
for(int i=1;i<=n;++i){
if(abs(now+c[i])<abs(ans)){
ans=now+c[i];
}else if(abs(now+c[i])==abs(ans)){
ans=max(ans,now+c[i]);
}
}
return ans;
}
inline int dfs1(int now){
int res=2e9;
for(int i=1;i<=n;++i){
res=min(res,dfs2(now+b[i]));
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i){
scanf("%d",&b[i]);
}
for(int i=1;i<=n;++i){
scanf("%d",&c[i]);
}
int ans=-2e9;
for(int i=1;i<=n;++i){//枚举Alice
ans=max(ans,dfs1(a[i]));
}
printf("%d",ans);
return 0;
} H.Hinnjaku
这题真有趣(滑稽)
直接模拟字符串就行了
先判断是否有zawaluduo，有的话，就按题目说的将对方秒掉（记得优先Dio）
然后，再判断是否可以attact对方
如果有一个人Hp=0的话，退出然后比较Hp大小即可
代码:
#include<bits/stdc++.h>
using namespace std;
char kil[10]={'z','a','w','a','l','u','d','u','o'};
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,H;
scanf("%d%d",&n,&H);
string x,y;
cin>>x>>y;
int LH=H,RH=H;
for(int i=2;i<n;++i){
bool kil1=1,kil2=1;
if(i>=8){
for(int j=i-8;j<=i;++j){
kil1&=(x[j]==kil[j-i+8]);
kil2&=(y[j]==kil[j-i+8]);
}
}
if(i<8){
kil1=kil2=0;
}
if(kil2){
LH=0;
break;
}
if(kil1){
RH=0;
break;
}
int ht1=0,ht2=0;
ht1=(x[i-2]=='o'&&x[i-1]=='r'&&x[i]=='a');
if(i>2){
ht2=(y[i-3]=='m'&&y[i-2]=='u'&&y[i-1]=='d'&&y[i]=='a');
}
RH-=ht1,LH-=ht2;
if(!LH||!RH){
break;
}
}
if(LH!=RH){
if(LH>RH){
puts("Wryyyyy");
}else{
puts("Hinnjaku");
}
}else{
puts("Kono Dio da");
}
}
return 0;
} I.Interesting Matrix Problem
简单数学题，考虑二分答案，那么，我们只需要尽快计算出矩形中小于等于x的数字的个数
注意到，(i,j)的值为i*j
那么，我们有:
第i行中，小于等于x的数字的个数为:
所以答案就是:
这样就是个明显的整数分块模板题了。。。
(之前为了防止bug，代码中多个地方用了min,有些其实并不需要)
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,q;
inline int calc(int x){//矩阵中值小于等于x的数的个数
int ans=0;
//ans=sum(i=1,n,min(m,[x/i]))
//=>整数分块
for(int r,l=1;l<=min(x,n);l=r+1){
r=min(n,x/(x/l));
ans+=(min(m,x/l)*(r-l+1));
}
return ans;
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&q);
while(q--){
int x;
scanf("%lld",&x);
int l=1,r=x,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(calc(mid)>=x){
ans=mid;r=mid-1;
}else{
l=mid+1;
}
}
printf("%lld\n",ans);
}
return 0;
} J.Jogging along the Yangtze River
首先，发现输入数字只有一个，那么。。。肯定找规律啊(滑稽)
写了个暴力,打了个表:
2,6,22,90,394
观测了一会儿，没想法，直接上OEIS
发现规律:
预处理出
再枚举i即可计算
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1,mod=998244353;
int C[N],g[N];
int main(){
C[0]=g[0]=g[1]=1;
for(int i=2;i<N;++i){
g[i]=(1LL*g[mod%i]*(mod-mod/i))%mod;
}
int x;
scanf("%d",&x);
for(int i=1;i<=x;++i){
C[i]=(1LL*C[i-1]*(x-i+1))%mod;
C[i]=(1LL*C[i]*g[i])%mod;
}
int now=1;int ans=0;
for(int i=1;i<=x;++i){
now=(2LL*now)%mod;
ans=(ans+((1LL*now*((1LL*C[i]*C[i-1])%mod))%mod))%mod;
}
ans=(1LL*ans*g[x])%mod;
cout<<ans;
return 0;
} 
京公网安备 11010502036488号