AtCoder Beginner Contest 365(A~E)
A
问题陈述
给你一个介于 \(1583\) 和 \(2023\) 之间的整数 \(Y\) 。
求公历 \(Y\) 年的天数。
在给定的范围内， \(Y\) 年的天数如下：
- 如果 \(Y\) 不是 \(4\) 的倍数，则为 \(365\) 天；
- 如果 \(Y\) 是 \(4\) 的倍数，但不是 \(100\) 的倍数，则为 \(366\) 天；
- 如果 \(Y\) 是 \(100\) 的倍数，但不是 \(400\) 的倍数，则为 \(365\) 天；
- 如果 \(Y\) 是 \(400\) 的倍数，则为 \(366\) 天。
Solution
#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
scanf("%d",&n);
if(n%400==0 || (n%4==0 && n%100!=0)) printf("366");
else printf("365");
return 0;
}
B
问题陈述
给你一个长度为 \(N\) 的整数序列 \(A=(A_1,\ldots,A_N)\)。这里， 都 \(A=(A_1,\ldots,A_N)\) 是不同的。
在 \(A\) 中，哪个元素是第二大元素？
Solution
维护最大值和第二大的值即可。时间复杂度 \(O(n)\) 。
#include <bits/stdc++.h>
using namespace std;
const int N=105;
int n,a[N],max1,max2;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
if(a[i]>max1) max2=max1,max1=a[i];
else if(a[i]>max2) max2=a[i];
}
for(int i=1;i<=n;++i){
if(a[i]==max2){
printf("%d",i);
return 0;
}
}
return 0;
}
C
问题陈述
有 \(N\) 人参加一项活动， \(i\) /人的交通费用是 \(A_i\) 日元。
活动组织者高桥(Takahashi)决定设定交通补贴的最高限额为 \(x\) 。 \(i\) 人的补贴为 \(\min(x, A_i)\) 日元。这里， \(x\) 必须是一个非负整数。
高桥的预算为 \(M\) 日元，他希望所有 \(N\) 人的交通补贴总额最多为 \(M\) 日元，那么补贴限额 \(x\) 的最大可能值是多少？
如果补贴限额可以无限大，请报告。
Solution
若补贴限额可以无限大，则 \(\sum_{i=1}^nA_i\le M\) 。
如果不可以无限大， \(x\) 一定越小越好，具有单调性，考虑二分。
时间复杂度 \(O(nlogn)\) 。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2e5+5;
int n,a[N];
LL m,ans,L=1,R=2e14,sum[N];
bool chk(LL x){
int pos=lower_bound(a+1,a+n+1,x)-a-1;
return x*(n-pos)+sum[pos]<=m;
}
int main(){
scanf("%d %lld",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
for(int i=1;i<=n;++i){
sum[i]=sum[i-1]+a[i];
}
while(L<=R){
LL mid=L+R>>1;
if(chk(mid)) L=mid+1,ans=mid;
else R=mid-1;
}
if(ans==2e14) printf("infinite");
else printf("%lld",ans);
return 0;
}
D
问题陈述
高桥和青木玩了 \(N\) 次石头剪刀布。注：在这个游戏中，石头赢剪刀，剪刀赢纸，纸赢石头。
青木的动作由长度为 \(N\) 的字符串 \(S\) 表示，字符串由 "R"、"P "和 "S "组成。 \(S\) 的 \(i\) -th字符表示青木在 \(i\) -th对局中的棋步：R "表示 "石头"，"P "表示 "纸"，"S "表示 "剪刀"。
高桥的棋步满足以下条件：
- 高桥从未输给过青木。
- 对于 \(i=1,2,\ldots,N-1\) ，高桥在 \(i\) 对局中的棋步与他在 \((i+1)\) 对局中的棋步不同。
请确定高桥的最大胜局数。
可以保证存在一个满足这些条件的高桥的下棋顺序。
Solution
考虑动态规划。设 \(dp_{i,0}\) 表示第 \(i\) 局平局时的最大胜局数， \(dp_{i,1}\) 表示第 \(i\) 局获胜时的最大胜局数， \(ans_i\) 表示赢 \(S_i\) 的棋步。
若 \(S_i\ne S_{i-1}\) ，则 \(dp_{i,0}=\max(dp_{i,0},dp_{i-1,0})\) 。
若 \(S_i \ne ans_{i-1}\) ，则 \(dp_{i,0}=max(dp_{i,0},dp_{i-1,1})\) 。
若 \(ans_i\ne S_{i-1}\) ，则 \(dp_{i,1}=max(dp_{i,1},dp_{i-1,0}+1)\) 。
若 \(ans_i\ne ans_{i-1}\) ，则 \(dp_{i,1}=max(dp_{i,1},dp_{i-1,1}+1)\) 。
时间复杂度 \(O(n)\) 。
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,dp[N][2];
char s[N],ans[N];
int main(){
scanf("%d %s",&n,s+1);
for(int i=1;i<=n;++i){
if(s[i]=='R') ans[i]='P';
else if(s[i]=='P') ans[i]='S';
else ans[i]='R';
}
dp[1][1]=1;//1表示赢第i局
for(int i=2;i<=n;++i){
if(s[i]!=s[i-1]) dp[i][0]=max(dp[i][0],dp[i-1][0]);
if(s[i]!=ans[i-1]) dp[i][0]=max(dp[i][0],dp[i-1][1]);
if(ans[i]!=s[i-1]) dp[i][1]=max(dp[i][1],dp[i-1][0]+1);
if(ans[i]!=ans[i-1]) dp[i][1]=max(dp[i][1],dp[i-1][1]+1);
}
printf("%d",max(dp[n][0],dp[n][1]));
return 0;
}
E
问题陈述
给你一个长度为 \(N\) 的整数序列 \(A=(A_1,\ldots,A_N)\) 。求以下表达式的值：
\[\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N (A_i \oplus A_{i+1}\oplus \ldots \oplus A _j) \]关于位向 XOR 的说明 非负整数 \(A\) 和 \(B\) 的位向 XOR 定义如下，记为 \(A \oplus B\) ：
- 在 \(A \oplus B\) 的二进制表示中，当且仅当 \(A\) 和 \(B\) 的二进制表示中 \(2^k\) 位上的数字是 \(1\) 时， \(2^k\) ( \(k \geq 0\) )位上的数字是 \(1\) ；否则，它是 \(0\) 。
例如， \(3 \oplus 5 = 6\) (二进制： \(011 \oplus 101 = 110\) )。
一般来说， \(k\) 个整数 \(p_1, \dots, p_k\) 的比特 XOR 定义为 \((\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)\) 。可以证明这与 \(p_ 1, \dots, p_k\) 的阶数无关。
Solution
对于区间 \([L,R]\) ，异或和的二进制结果的第 \(i\) 位为 \(1\) 的充要条件是 \(A_L\) 到 \(A_R\) 的所有数中第 \(i\) 位是 \(1\) 的数有奇数个。
设 \(cnt_{i,j}\) 表示前 \(i\) 个数中第 \(j\) 位是 \(1\) 的数的个数，那么\(A_L\) 到 \(A_R\) 的所有数中第 \(i\) 位是 \(1\) 的数的个数可以表示为
\[cnt_{R,i}-cnt_{L-1,i} \]枚举右端点 \(R\) ，若 \(L\) 满足 \(cnt_{L-1,i}\) 与 \(cnt_{R,i}\) 奇偶性不同，则 \(2^i\) 对答案有贡献。对于每个 \(R\) ，只需记录 \(L\) 的个数即可。
时间复杂度 \(O(33n)\) 。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+5;
int n,a[N],cnt[N][40];
LL ans,cnt0,cnt1,sum;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
sum+=a[i];
for(int j=0;j<=32;++j){
cnt[i][j]=cnt[i-1][j];
if(a[i]&(1ll<<j)) cnt[i][j]++;
cnt[i][j]%=2;
}
}
// for(int i=1;i<=n;++i){
// for(int j=0;j<=3;++j){
// printf("%d ",cnt[i][j]);
// }
// printf("\n");
// }
for(int i=0;i<=32;++i){
cnt0=1,cnt1=0; //cnt0=1将左端点为1的加上
for(int j=1;j<=n;++j){
if(cnt[j][i]==1){
cnt1++;
ans+=cnt0*(1ll<<i);
}
else{
cnt0++;
ans+=cnt1*(1ll<<i);
}
}
}
printf("%lld",ans-sum);
return 0;
}