A - Leap Year
思路
模拟即可;
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;
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 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;
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 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,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;
}