开学毒瘤赛题解

****T1 ``` #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<string> #include<algorithm> #include<climits> #include<string> using namespace std; const int maxn=100005; int n,m,sum,a[maxn]; int bin(int lim) { int s=0,cnt=1; for(int i=1;i<=n;i++) { if(a[i]>lim) return n; if(s+a[i]<=lim) s+=a[i]; else { s=a[i]; ++cnt; } } return cnt; } int main() { // freopen("x.in","r",stdin); // freopen("x.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum+=a[i]; } int l = 0,r = sum,tmp,mid; while(l<r) { mid=l+r>>1; tmp=bin(mid); if(tmp>m) l=mid+1; else r=mid; } printf("%d\n",l); return 0; } ``` T2 ``` #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<string> #include<algorithm> #include<climits> #include<string> using namespace std; struct node { int st; int en; } a[1000005]; int n; bool pa[100005]; bool cmp(node x,node y) { return x.en<y.en; } int main() { // freopen("6.in","r",stdin); // freopen("x.out","w",stdout); cin>>n; for(int i = 1; i <= n; i++) { scanf("%d%d",&a[i].st,&a[i].en); } sort(a+1,a+n+1,cmp); int ans=0,t; for(int i = 1,t = -1; i <= n; i++) { if(a[i].st > t) { ans++; t=a[i].en; } //cout<<a[i].st<<' '<<a[i].en<<endl; } cout<<ans; return 0; } ``` T3 ``` #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<string> #include<algorithm> #include<climits> #include<cfloat> #include<queue> #include<cstddef> using namespace std; int n,m; char as[10]= {" .in"}; char bs[15]= {" .out"}; char x,a[1005][1005]; int bmp[1005][1005]; int dx[4]= {0,0,-1,1}; int dy[4]= {1,-1,0,0}; int xs[105],ys[105],f[105][105][10],cnts,stx,sty,enx,eny,ans=INT_MAX; queue<int>xx,yy,num; queue<int>null; void bfs() { memset(f,-1,sizeof f); xx=yy=null; f[stx][sty][0]=0; xx.push(stx),yy.push(sty),num.push(0); while(!xx.empty()) { int nox=xx.front(),noy=yy.front(),nnu=num.front(); xx.pop(),yy.pop(),num.pop(); for(int i = 0; i < 4; i++) { int tox=nox+dx[i],toy=noy+dy[i],ton=nnu; if(tox<1||toy<1||tox>n||toy>n) continue; if(a[tox][toy]=='-'||f[tox][toy][ton]!=-1) continue; if(ton+1==a[tox][toy]-'0') ton++; f[tox][toy][ton]=f[nox][noy][nnu]+1; xx.push(tox),yy.push(toy),num.push(ton); } } } void dfs(int k,int ks) { if(k == cnts+1) { bfs(); if(f[enx][eny][m]!=-1) { ans=min(ans,f[enx][eny][m]+ks); } return; } a[xs[k]][ys[k]]='.'; dfs(k+1,ks+1); a[xs[k]][ys[k]]='-'; dfs(k+1,ks); } int main() { memset(bmp,0,sizeof bmp); memset(f,0,sizeof f); memset(xs,0,sizeof f); memset(ys,0,sizeof f); cnts=0,ans=INT_MAX; cin>>n>>m; cin>>stx>>sty>>enx>>eny; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { cin>>a[i][j]; if(a[i][j]=='*') { cnts++,xs[cnts]=i,ys[cnts]=j; } } } dfs(1,0); if(ans>=INT_MAX-10) cout<<"N0!MY GC CHESS"; else cout<<ans; return 0; } ```