比赛链接:https://atcoder.jp/contests/abc365
solve:ABC
开头:
感觉好久没打abc了,这场被D单防了qwq,该好好练练dp了
A. Leap Year
思路:
签到题,闰年判断
代码:
#include<bits/stdc++.h>
using i64=long long;
void solve(){
int n;
std::cin>>n;
if(n%400==0){
std::cout<<366;
}
else if(n%100==0&&n%400!=0){
std::cout<<365;
}
else if(n%4==0){
std::cout<<366;
}
else{
std::cout<<365;
}
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}
B. Second Best
思路:
也是签到题
代码:
#include<bits/stdc++.h>
using i64=long long;
void solve(){
int n;
std::cin>>n;
std::vector<int> a(n+1),b(n+1);
for(int i=1;i<=n;i++){
std::cin>>a[i];
b[i]=a[i];
}
sort(a.begin()+1,a.end());
for(int i=1;i<=n;i++){
if(b[i]==a[n-1]){
std::cout<<i;
return;
}
}
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}
C. Transportation Expenses
思路:
标准的二分答案,如果所有人的费用总和比预算少,那么限额就可以是无限大
代码:
#include<bits/stdc++.h>
using i64=long long;
std::vector<i64> a;
i64 n,m;
bool check(i64 x){
i64 sum=0;
for(i64 i=1;i<=n;i++){
sum+=std::min(a[i],x);
}
if(sum<=m){
return true;
}
else{
return false;
}
}
void solve(){
std::cin>>n>>m;
a.resize(n+1);
i64 sum=0;
i64 ma=0;
for(i64 i=1;i<=n;i++){
std::cin>>a[i];
sum+=a[i];
ma=std::max(ma,a[i]);
}
if(sum<=m){
std::cout<<"infinite";
return;
}
i64 l=1;i64 r=ma-1;
while(l<r){
i64 mid=l+r+1>>1;
if(check(mid)){
l=mid;
}
else{
r=mid-1;
}
//std::cout<<l<<' '<<r<<'\n';
}
std::cout<<r<<'\n';
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}
D. AtCoder Janken 3
思路:
是很简单的dp,但我好久没做dp了,一直在用贪心求
每一局有三种状态,即可以出剪刀石头布,当出剪刀时,上一局就不能是剪刀,同时如果这局对面出的是布,就赢了,如果对面出的是石头,那么就输了,就给它赋值为无穷小,最后求最大
代码:
#include<bits/stdc++.h>
using i64=long long;
void solve(){
int n;
std::cin>>n;
std::string s;
std::cin>>s;
s='0'+s;
int INF=0x3f3f3f3f;
std::vector<std::vector<int>> dp(n+1,std::vector<int>(3,-INF));
dp[0][0]=0;dp[0][1]=0;dp[0][2]=0;
for(int i=1;i<=n;i++){
dp[i][0]=std::max(dp[i-1][1],dp[i-1][2])+(s[i]=='S');//状态转移方程
dp[i][1]=std::max(dp[i-1][0],dp[i-1][2])+(s[i]=='R');
dp[i][2]=std::max(dp[i-1][0],dp[i-1][1])+(s[i]=='P');
if(s[i]=='R'){
dp[i][2]=-INF;
}
else if(s[i]=='P'){
dp[i][0]=-INF;
}
else{
dp[i][1]=-INF;
}
}
std::cout<<std::max({dp[n][0],dp[n][1],dp[n][2]})<<'\n';
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}
E. Xor Sigma Problem(待补)
思路:
还有点没搞懂,先放个代码在这
代码:
#include<bits/stdc++.h>
using i64=long long;
void solve(){
int n;
std::cin>>n;
std::vector<int> a(n+1);
for(int i=1;i<=n;i++){
std::cin>>a[i];
}
std::vector<std::vector<int>> sum(n+1,std::vector<int>(30,0));
for(int i=1;i<=n;i++){
for(int j=0;j<30;j++){
sum[i][j]=(a[i]>>j&1);
sum[i][j]^=sum[i-1][j];
}
}
i64 res=0;
std::vector<std::vector<int>> cnt(30,std::vector<int>(2,0));
for(int i=1;i<=n;i++){
for(int j=0;j<30;j++){
res+=1LL*cnt[j][sum[i][j]^1]*(1<<j);
cnt[j][sum[i-1][j]]+=1;
}
}
std::cout<<res<<'\n';
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}