Educational Codeforces Round 71 (Rated for Div. 2)
A - There Are Two Types Of Burgers
思路:价格高的优先取
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; int st[205][205],vis[205][205]; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; void solve(){ int ans=0; int b,p,f;cin>>b>>p>>f; int h,c;cin>>h>>c; if(h>=c){ int cp=min(b/2,p); b-=cp*2; ans+=cp*h; int cf=min(b/2,f); ans+=cf*c; }else{ int cf=min(b/2,f); b-=cf*2; ans+=cf*c; int cp=min(b/2,p); ans+=cp*h; } cout<<ans<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //init(); cin>>t; while(t--){ solve(); } return 0; }View Code
思路:遍历每个点,若以该点为左上角的2*2矩阵都为1,则取该点,并将b对应的点都覆盖为1,最后判断a、b是否相等
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=50+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; int a[N][N],b[N][N]; void solve(){ int n,m;cin>>n>>m; vector<PII>ans; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j)cin>>a[i][j]; } for(int i=1;i<n;++i){ for(int j=1;j<m;++j){ if(a[i][j]&&a[i+1][j]&&a[i][j+1]&&a[i+1][j+1]){ b[i][j]=b[i+1][j]=b[i][j+1]=b[i+1][j+1]=1; ans.push_back({i,j}); } } } for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ if(a[i][j]!=b[i][j]){ cout<<"-1\n"; return ; } } } cout<<ans.size()<<'\n'; for(auto v:ans)cout<<v.first<<' '<<v.second<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //init(); //cin>>t; while(t--){ solve(); } return 0; }View Code
题意:1的高度一定为2,0的高度可以为1/2,问管道和柱子的最小总cost
思路:
- dp
dp[i][j]表示前i段高度为j的最小cost;
首尾都是0,所以dp[0][1]=a+b,若s[1]='1',则dp[0][2]=2*a+b;
从1开始遍历所有s,若s[i]=1,dp[i][2]=dp[i-1][2]+2*b+a;
若s[i]=0,1. s[i-1]=='1'且s[i+1]=='1' :dp[i][2]=dp[i-1][2]+2*b+a;
2. s[i-1]=='0'且s[i+1]=='1' :dp[i][2]=min(dp[i-1][2]+2*b+a,dp[i-1][1]+2*a+b);
3. s[i-1]=='1' :dp[i][2]=dp[i-1][2]+2*b+a;
dp[i][1]=dp[i-1][2]+2*a+2*b;
4.s[i-1]=='0'且s[i+1]=='0' :dp[i][2]=min(dp[i-1][1]+2*a+b,dp[i-1][2]+2*b+a);
dp[i][1]=min(dp[i-1][2]+2*a+2*b,dp[i-1][1]+a+b);
- 贪心
对于0的地方,可以选两种高度,找到每段连续的0,取两种高度cost少的
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const int inf=0x3f3f3f3f3f3f; const double eps=1e-6; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; int dp[N][3]; void solve(){ int n,a,b;cin>>n>>a>>b; string s;cin>>s; for(int i=0;i<=n;++i)dp[i][1]=dp[i][2]=inf; if(s[1]=='0')dp[0][1]=a+b; else dp[0][2]=2*a+b; for(int i=1;i<n;++i){ if(s[i]=='1')dp[i][2]=dp[i-1][2]+2*b+a; else{ if(s[i-1]=='1'&&s[i+1]=='1')dp[i][2]=dp[i-1][2]+2*b+a; else if(s[i-1]=='1'){ dp[i][2]=dp[i-1][2]+2*b+a; dp[i][1]=dp[i-1][2]+2*a+2*b; }else if(s[i-1]=='0'&&s[i+1]=='1')dp[i][2]=min(dp[i-1][2]+2*b+a,dp[i-1][1]+2*a+b); else{ dp[i][2]=min(dp[i-1][1]+2*a+b,dp[i-1][2]+2*b+a); dp[i][1]=min(dp[i-1][2]+2*a+2*b,dp[i-1][1]+a+b); } } } cout<<dp[n-1][1]+b<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; //init(); cin>>T; while(T--){ solve(); } return 0; }dp
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=50+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; int T=1; void solve(){ int n,a,b;cin>>n>>a>>b; string s; cin>>s; bool ok=false; int ans=n*2*b+(n+2)*a; for(int i=0,l=-1,r;i<n;++i){ if(l==-1&&s[i]=='0'){ l=i;r=i; }else if(s[i]=='0'){ r=i; }else if(l!=-1){ if(l==0){ ans-=(r-l)*b; }else if(r-l>0){ int aa=2; int bb=r-l; int d=aa*a-bb*b; if(d<0) ans+=d; } l=-1; } if(i==n-1){ ans-=(r-l)*b; if(l==0)ans-=2*a; } }//cout<<aa<<' '<<bb<<"\n"; cout<<ans<<'\n';//cout<<'\n'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); //int T=1; //init(); cin>>T; while(T--){ solve(); } return 0; }贪心
题意:问s有多少种排序,使得p的a和b分别是递减的
思路:找出所有递增的,那么递减的即为n!减去递增的。
对于 1 2 2 3 4 4 4 5,可以求出递增的序列有 2!* 3!种,即每种数的个数的阶乘的积。
可以求出a和b的序列分别递增的数目,但还需减去其中重复的(在某种递增的序列中,另一个ai和令一个bi又组成了同样的序列)
将所有(a,b)按a从小到大排序,看是否存在a和b都是递增的情况,若存在则重复的情况就是该种情况的数量,同样的方法求出递增的数量即为重复的数量
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const int inf=0x3f3f3f3f3f3f; const double eps=1e-6; const int dx[4]={-1,0,1,0}; const int dy[4]={0,1,0,-1}; vector<int>fac(N); vector<PII>ve; map<int,int>mp1,mp2; map<PII,int>mp3; void init(){ fac[0]=1ll; for(int i=1;i<N;++i)fac[i]=fac[i-1]*i%mod; } void solve(){ int n;cin>>n; ve=vector<PII>(n); bool ok=true; for(int i=0;i<n;++i){ cin>>ve[i].first>>ve[i].second; mp1[ve[i].first]++,mp2[ve[i].second]++; if(mp1[ve[i].first]==n||mp1[ve[i].second]==n)ok=false; } if(!ok){ cout<<0;return ; } int ans,t=1; for(auto v:mp1)t=(t%mod*fac[v.second]%mod)%mod; ans=t%mod; t=1; for(auto v:mp2)t=(t%mod*fac[v.second]%mod)%mod; ans=(ans%mod+t%mod)%mod; sort(ve.begin(),ve.end()); for(int i=1;i<ve.size();++i){ if(ve[i].second<ve[i-1].second){ok=false;break;} } if(ok){ for(auto v:ve)mp3[v]++; t=1; for(auto v:mp3){ t=(t%mod*fac[v.second]%mod)%mod; } ans-=t; } cout<<((fac[n]%mod-ans)%mod+mod)%mod; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; init(); //cin>>T; while(T--){ solve(); } return 0; }View Code
思路:第一次的数中二进制的第7~14位都为0,第二次的数中二进制的第0~6位都为0,这样两次就可以分别求出x的二进制情况
#include<bits/stdc++.h> using namespace std; #define int long long //#define int __int128 typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const int inf=0x3f3f3f3f3f3f; const double eps=1e-6; const int dx[4]={-1,0,1,0}; const int dy[4]={0,1,0,-1}; void init(){ } void solve(){ cout<<"? "; for(int i=1;i<=100;++i)cout<<" "<<i;cout<<'\n'; int x;cin>>x; int ans=0; for(int i=7;i<14;++i)ans+=((x>>i&1)<<i); cout<<"? "; for(int i=1;i<=100;++i)cout<<" "<<(i<<7);cout<<'\n'; cin>>x; for(int i=0;i<7;++i)ans+=((x>>i&1)<<i); cout<<"! "<<ans<<'\n'; } signed main(){ //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; //init(); //cin>>T; while(T--){ solve(); } return 0; }View Code
思路:分块√5e5=707,对于大于707的可以直接暴力求,小于707的用ans[i][j]存%i等于j的答案
#include<bits/stdc++.h> using namespace std; //#define int long long //#define int __int128 typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353; const int inf=0x3f3f3f3f3f3f; const double eps=1e-6; const int dx[4]={-1,0,1,0}; const int dy[4]={0,1,0,-1}; int ans[705][705],a[N]; void solve(){ int q;cin>>q; while(q--){ int op,x,y;cin>>op>>x>>y; if(op==1){ a[x]+=y; for(int i=1;i<=700;++i)ans[i][x%i]+=y; }else{ if(x<=700)cout<<ans[x][y]<<'\n'; else{ int res=0; for(int i=y;i<N;i+=x)res+=a[i]; cout<<res<<'\n'; } } } } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; //init(); //cin>>T; while(T--){ solve(); } return 0; }View Code
标签:Educational,Rated,const,int,Codeforces,long,typedef,dp,define From: https://www.cnblogs.com/bible-/p/17577442.html