(AtCoder Beginner Contest 310)
思路:比较下打折和不打折的情况
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; void solve(){ int n,p,q;cin>>n>>p>>q; int ans=p; for(int i=1;i<=n;++i){ int x;cin>>x; ans=min(ans,x+q); } cout<<ans; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //init(); //cin>>t; while(t--){ solve(); } return 0; }
思路:找出满足条件的任务(i,j)即YES,满足:
p[j]<=p[i],j任务的功能需包含i所有的功能,若p[j]=p[i],j任务还需比i任务多至少1个功能
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; void solve(){ int n,m;cin>>n>>m; set<int>se[n]; vector<int>p(n),c(n); for(int i=0;i<n;++i){ cin>>p[i]>>c[i]; for(int j=0,x;j<c[i];++j){ cin>>x; se[i].insert(x); } } bool ok=false; for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ if(i!=j&&p[j]<=p[i]){ int same=0; for(auto v:se[i]){ if(se[j].count(v)){ same++; } } if(p[j]<p[i]&&same==se[i].size()){ ok=true;break; }else if(p[j]==p[i]&&same==se[i].size()&&se[j].size()>same){ ok=true;break; } } } if(ok)break; } if(ok)cout<<"Yes"; else cout<<"No"; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //init(); //cin>>t; while(t--){ solve(); } return 0; }
思路:用map标记原始有的所有字符串,询问字符串s是否含有时,看s和s的倒序后的字符串是否被标记即可
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; void solve(){ int n,ans=0;cin>>n; string s; map<string,int>mp; for(int i=0;i<n;++i){ cin>>s; string a=s; reverse(s.begin(), s.end()); if(!mp[s]&&!mp[a])ans++; mp[a]++; } cout<<ans; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //init(); //cin>>t; while(t--){ solve(); } return 0; }
思路:搜索所有分队可能,求所有满足条件的情况
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<char,int>PCI; typedef pair<string,string>PSS; const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; typedef long long ll; vector<vector<int>>ve; int g[11][11],res; int n,t,m; void dfs(int u,int cnt){ if(cnt>t)return ; if(u>n){ if(cnt==t){ for(auto i:ve) for(auto a:i) for(auto b:i) if(g[a][b])return ; res++; } return ; } for(int i=1;i<=cnt+1;++i){ ve[i].push_back(u); dfs(u+1,max(i,cnt)); ve[i].pop_back(); } } void solve(){ cin>>n>>t>>m; ve=vector<vector<int>>(n+1,vector<int>(n+1)); for(int i=0,a,b;i<m;++i){ cin>>a>>b;g[a][b]=g[b][a]=1; } dfs(1,0); cout<<res; return ; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; //cin>>T; while(T--){ solve(); } return 0; }
思路:求所有区间的价值和。可以看出 a⊼b =!(a&b)。
用f(i)表示以i结尾的所有区间的价值和,将所有f(i)加起来即可
f(i)的状态转移:
若a[i]为0,f(i)=f(i-1)+(i-1);
若a[i]为1,f(i)=(i-1)-f(i-1);
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef pair<string,string>PSS; const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7; const double eps=1e-6; void solve(){ int n;cin>>n; string s;cin>>s; s.insert(s.begin(),' '); vector<int>f(s.size(),0); int ans=0; //f[1]=!(s[1]&&s[1]); for(int i=1;i<=n;++i){ if(s[i]=='0'){ f[i]+=(i-1); }else{ f[i]+=(i-1-f[i-1]); } f[i]+=(s[i]-'0');//cout<<f[i]<<' '; ans+=f[i]; } cout<<ans; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t=1; //init(); //cin>>t; while(t--){ solve(); } return 0; }
- Beginner AtCoder Contest 310beginner atcoder contest 310 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 315