这一次又崩了，最后只a了一题（还是被hack后才发现的错误）
第一题水题，多用一个数保存2-1后的数，注意先用2的桌子，再用这个
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 10007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-9; const int N=1000+10,maxn=45000+10,inf=0x3f3f3f3f; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,a,b,c=0; cin>>n>>a>>b; ll ans=0; for(int i=0;i<n;i++) { int s; cin>>s; if(s==1) { if(a>0)a--; else if(b>0)c++,b--; else if(c>0)c--; else ans++; } else { if(b>0)b--; else ans+=2; } } cout<<ans<<endl; return 0; }
第二题，找最小的能覆盖所有B的正方形，输出最小不是B的值，暴力搜索比较一边，m写成n导致蹦了
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-9; const int N=100+10,maxn=5000+10,inf=0x3f3f3f3f; char ma[N][N]; bool vis[N][N]; int n,m; bool ok() { for(int k=1;k<=n;k++) { for(int l=1;l<=n;l++) { if(!vis[k][l]&&ma[k][l]=='B') return 0; } } return 1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; int l=101,r=-1,u=101,d=-1; bool f=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>ma[i][j]; if(ma[i][j]=='B') { f=1; l=min(l,j); r=max(r,j); u=min(u,i); d=max(d,i); } } } if(!f) { cout<<1<<endl; return 0; } int p=max(r-l,d-u),ans=1000000; // cout<<p<<endl; for(int i=1;i+p<=n;i++) { for(int j=1;j+p<=m;j++) { int te=0; memset(vis,0,sizeof vis); for(int k=i;k<=i+p;k++) { for(int l=j;l<=j+p;l++) { if(ma[k][l]!='B') te++; vis[k][l]=1; } } if(ok())ans=min(ans,te); } } if(ans==1000000)cout<<-1<<endl; else cout<<ans<<endl; return 0; }
第三题字符串模拟，先标记，输出的时候判断谁的到达距离更远来决定要不要更新，还有数组记得开1e7
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-9; const int N=1000000+10,maxn=5000+10,inf=0x3f3f3f3f; string s[N]; int bj[N*10]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,k; cin>>n; memset(bj,-1,sizeof bj); int maxx=0; for(int i=0;i<n;i++) { cin>>s[i]>>k; while(k--){ int a; cin>>a; int p=a+s[i].size(); maxx=max(maxx,p-1); if(bj[a]==-1)bj[a]=i; else { if(s[bj[a]].size()<s[i].size()) bj[a]=i; } } } for(int i=1;i<=maxx;) { if(bj[i]==-1)i++,cout<<'a'; else { int p=bj[i],te=s[p].size(); for(int j=0;j<s[p].size();j++) { if(j!=0&&bj[i+j]!=-1&&s[bj[i+j]].size()>s[p].size()-j) { te=j; break; } } // cout<<te<<endl; cout<<s[p].substr(0,te); i+=te; } } cout<<endl; return 0; }
第四题连通图，通过找规律可以发现，把1当作定点，第二层有k个点与1相连，然后依次链接到上一层，这样一定是有k个点为出口点
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-9; const int N=1000000+10,maxn=5000+10,inf=0x3f3f3f3f; vector<pair<int,int> >v; int le[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,k; cin>>n>>k; for(int i=2;i<=k+1;i++) { v.push_back(make_pair(1,i)); le[i]=2; } int t=k+2,ans=3; while(t<=n){ v.push_back(make_pair(t-k,t)); le[t]=ans; if((t-k-1)%k==0)ans++; t++; } sort(le+1,le+1+n); cout<<le[n]+le[n-1]-2<<endl; for(int i=0;i<v.size();i++) cout<<v[i].first<<" "<<v[i].second<<endl; return 0; }