比赛链接
A - Leap Year
算法:模拟
题目大意
给你一个年份,判断当前年份有多少天
算法思路
没什么可说的,直接判断当前年份是闰年还是平年
代码
#include<bits/stdc++.h>
#define ll long long
const int N = 1e5+7;
using namespace std;
void slove() {int y;cin>>y;if((y%4==0 && y%100!=0) || y%400==0)cout<<366;else cout<<365;
}
int main() {int t = 1;
// cin>>t;while(t--) {slove();cout<<endl;}return 0;
}B - Second Best
算法:模拟
题目大意
给你一个数组,找到第二大的数
算法思路
直接用sort排序以后输出第二大的数的下标即可
代码
#include<bits/stdc++.h>
#define ll long long
const int N = 1e5+7;
using namespace std;
struct Node{int a;int len;bool operator<(const Node& b) const {return a>b.a;}
};
Node a[N];
void slove() {int n;cin>>n;for(int i=1;i<=n;++i) {cin>>a[i].a;a[i].len = i;}sort(a+1,a+n+1);cout<<a[2].len;
}
int main() {int t = 1;
// cin>>t;while(t--) {slove();cout<<endl;}return 0;
}C - Transportation Expenses
算法:二分
题目大意
有 N 个人参加一项活动，每个人的交通费用用 ( A_i ) 表示。
- 活动组织者高桥设定了一个交通补贴的最高限额 x，每个人可以获得的补贴是 ( \min(x, A_i) ) 日元，其中 x 必须是非负整数。
- 高桥有一个预算 M 日元，他希望所有 N 个人的交通补贴总额不超过这个预算。
- 问题要求找出补贴限额 x 的最大可能值。
- 如果补贴限额可以无限大，意味着 x 可以取到任意大的值，而不会超出预算 M。
- 在这种情况下，题目要求报告补贴限额可以无限大。
算法思路
因为我们需要找到x的最大值,直接通过二分查找X即可.
对于补贴可以无限大的情况,当且只有数组的总和小于等于M才行
代码
#include<bits/stdc++.h>
#define ll long long
const int N = 2e5+7;
const ll M = 2e16+7;
using namespace std;
ll a[N];
ll n,m;
bool check(ll x) {ll ans = 0;for(int i=1; i<=n; ++i) {ans += min(x,a[i]);}if(ans<=m) return true;else return false;
}
void slove() {cin>>n>>m;for(int i=1; i<=n; ++i) cin>>a[i];ll ans = 0;for(int i=1; i<=n; ++i) {ans+=a[i];}if(ans<=m) {cout<<"infinite";return;}ll l = 0,r = M;while (l < r) {int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}cout<<l;}
int main() {int t = 1;
// cin>>t;while(t--) {slove();cout<<endl;}return 0;
}D - AtCoder Janken 3
算法:动态规划
题目大意
A与B进行猜拳,已知A的出手顺序.
B的出手顺序满足:
- 不能输
- 不能出连续相同的
再满足这个条件下,B赢得最多次数.
算法思路
对于B的顺序,我们无法直接通过贪心来得到我们需要的答案,因为我们可以可以通过故意平手来达到控制我们出手顺序的结果.
对于这个题目,我们可以发现无后效性,对于当前出什么,只受到前面一个出手的影响.
那么我们就可以通过dp来考虑.
对于这一次出什么,我们把两种情况(平手或者胜利)都考虑了.
代码
#include<bits/stdc++.h>
#define ll long long
const int N = 2e5+7;
using namespace std;
//前i场出j时赢得最大次数
int dp[N][5];
void slove() {int n;cin>>n;string s;cin>>s;s=" "+s;//1->3 2->1 3->2for(int i=1; i<=n; ++i) {if(s[i]=='R') {dp[i][2]=max(dp[i-1][1],dp[i-1][3])+1;dp[i][1]=max(dp[i-1][2],dp[i-1][3]);} else if(s[i]=='P') {dp[i][3]=max(dp[i-1][1],dp[i-1][2])+1;dp[i][2]=max(dp[i-1][3],dp[i-1][1]);} else {dp[i][1]=max(dp[i-1][2],dp[i-1][3])+1;dp[i][3]=max(dp[i-1][1],dp[i-1][2]);}}cout<<max({dp[n][1],dp[n][2],dp[n][3]});return;
}
int main() {slove();return 0;
}E - Xor Sigma Problem
算法:位运算+枚举
题目大意
给定一个数组 A，我们需要完成以下任务：
- 分别求出数组
A的每个子段的异或和。 - 对于每组满足条件
1 ≤ L < R ≤ n的L和R，求出数组中从第L个元素到第R个元素的异或和。 - 最后，计算所有这些子段异或和的总和，并输出这个值。
代码思路
这题和蓝桥杯某一个很像
只需要在这个的基础上减去自身即可.
详细解释请看洛谷的解释
代码
#include<bits/stdc++.h>
#define ll long long
const int N = 2e5+7;
using namespace std;
int a[N],pre[N],cnt[10];void slove() {int n;cin>>n;ll sum=0;for(int i=1; i<=n; ++i) {cin>>a[i];sum+=a[i];}ll ans = 0;//统计每一个的贡献度for(int i=0; i<31; ++i) {for(int j=1; j<=n; ++j) {if((a[j]>>i)&1) pre[j]=pre[j-1]^1;else pre[j] = pre[j-1];}cnt[0] = cnt[1] = 0;for(int j=0; j<=n; ++j) cnt[pre[j]]++;ans+=(1ll<<i) * cnt[0] * cnt[1];}cout<<ans-sum<<endl;return;
}
int main() {slove();return 0;
}
