A - Leap Year
思路
模拟即可;
AC代码
#include<bits/stdc++.h>#define endl '\n'#define int int long long#define pb push_back#define bs bitsetusing namespace std;typedef pair<char,int> PCI;typedef pair<int,int> PII;typedef priority_queue<int> PQ;const int N = 2e5+10, MAX = 1e9, INF = -1e9;int n;signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;if(n%4!=0)cout<<365<<endl;else{if(n%100!=0)cout<<366<<endl;else{if(n%400!=0)cout<<365<<endl;else cout<<366<<endl;}}return 0;}
B - Second Best
思路
模拟即可;
AC代码
#include<bits/stdc++.h>#define endl '\n'#define int int long long#define pb push_back#define bs bitsetusing namespace std;typedef pair<char,int> PCI;typedef pair<int,int> PII;typedef priority_queue<int> PQ;const int N = 2e5+10, MAX = 1e9, INF = -1e9;int n;PII a[N];int e;bool cmp(PII a,PII b){return a.first>b.first;}signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>e;a[i].first=e;a[i].second=i;}sort(a+1,a+1+n,cmp);cout<<a[2].second<<endl;return 0;}
C - Transportation Expenses
思路
其实二分\(x\)就可以了，我还使用了前缀和，最后的复杂度是\(O(nlogn+logxlogn)\);
AC代码
#include<bits/stdc++.h>#define endl '\n'#define int int long long#define pb push_back#define bs bitsetusing namespace std;typedef pair<char,int> PCI;typedef pair<int,int> PII;typedef priority_queue<int> PQ;const int N = 2e5+10, MAX = 1e9, INF = -1e9;int n,m;vector<int> v;int sum=0;int e;int s[N];int counts(int x){int p=upper_bound(v.begin(),v.end(),x)-v.begin();return s[p-1]+(n-p+1)*x;}int f(int l,int r){while(l<r){int mid=(l+r+1)>>1;if(counts(mid)<=m)l=mid;else r=mid-1;}return l;}signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;v.pb(0);s[0]=0;for(int i=1;i<=n;i++){cin>>e;sum+=e;v.pb(e);}sort(v.begin(),v.end());for(int i=1;i<=n;i++){s[i]=s[i-1]+v[i];}if(sum<=m)cout<<"infinite"<<endl;else{cout<<f(1,1e9+1)<<endl;}return 0;}D - AtCoder Janken 3
思路
动态规划，很简单的转移；
AC代码
#include<bits/stdc++.h>
#define endl '\n'
#define int int long long
#define pb push_back
#define bs bitset
using namespace std;
typedef pair<char,int> PCI;
typedef pair<int,int> PII;
typedef priority_queue<int> PQ;const int N = 2e5+10, MAX = 1e9, INF = -1e9;int n;
char c;
int dp[N][4];signed main()
{ios::sync_with_stdio(false);cin.tie(0);cin>>n;memset(dp,0,sizeof(dp));for(int i=1; i<=n; i++) {cin>>c;if(c=='R') {dp[i][1]=max(dp[i-1][2],dp[i-1][3]);dp[i][2]=-10086;dp[i][3]=max(dp[i-1][2],dp[i-1][1])+1;}if(c=='S') {dp[i][2]=max(dp[i-1][1],dp[i-1][3]);dp[i][3]=-10086;dp[i][1]=max(dp[i-1][2],dp[i-1][3])+1;}if(c=='P') {dp[i][3]=max(dp[i-1][1],dp[i-1][2]);dp[i][1]=-10086;dp[i][2]=max(dp[i-1][1],dp[i-1][3])+1;}}cout<<max(dp[n][1],max(dp[n][2],dp[n][3]))<<endl;return 0;
}
