#include<bits/stdc++.h> using namespace std; int n,a[10][10],vis[10],ans,b[10][10]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') ff=-1; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*ff; } inline void put(int x) { if(x<0) putchar('-'),x=-x; if(x>9) put(x/10); putchar(x%10+'0'); } void work() { int cnt=0; for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) a[i][j]=b[i][j]; for(int i=1;i<=5;i++) { if(vis[i]) { cnt++; a[1][i]=-a[1][i]; a[2][i]=-a[2][i]; if(i-1>0) a[1][i-1]=-a[1][i-1]; if(i+1<6) a[1][i+1]=-a[1][i+1]; } } for(int i=1;i<=4;i++) for(int j=1;j<=5;j++) { if(a[i][j]==-1) { cnt++; a[i][j]=-a[i][j]; a[i+1][j]=-a[i+1][j]; if(j-1>0) a[i+1][j-1]=-a[i+1][j-1]; if(j+1<6) a[i+1][j+1]=-a[i+1][j+1]; if(i+2<6) a[i+2][j]=-a[i+2][j]; } } for(int j=1;j<=5;j++) { if(a[5][j]==-1) {cnt=-1;break;} } if(cnt!=-1) ans=min(ans,cnt); } inline void dfs(int x) { if(x==5) {work();return;} dfs(x+1); vis[x+1]=1; dfs(x+1); vis[x+1]=0; } int main() { freopen("1.in","r",stdin); n=read(); for(int k=1;k<=n;k++) { char ch;ans=INT_MAX; for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) { cin>>ch; if(ch=='0') b[i][j]=-1; else b[i][j]=1; } dfs(0); if(ans>6) put(-1),cout<<endl; else put(ans),cout<<endl; } return 0; }
PS:无序变有序...
2：激光炸弹：
#include<bits/stdc++.h> using namespace std; int n,r,f[5100][5100],nx,mx,ans; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') ff=-1; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*ff; } inline void put(int x) { if(x<0) putchar('-'),x=-x; if(x>9) put(x/10); putchar(x%10+'0'); } int main() { freopen("1.in","r",stdin); n=read();r=read(); nx=mx=r; for(int i=1;i<=n;i++) { int x=read()+1,y=read()+1,v=read(); nx=max(nx,x);mx=max(mx,y); f[x][y]=v; } for(int i=1;i<=nx;i++) { for(int j=1;j<=mx;j++) f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j]; } for(int x1=1;x1<=nx-r+1;x1++) { for(int y1=1;y1<=mx-r+1;y1++) { int x2=x1+r-1; int y2=y1+r-1; ans=max(ans,f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1]); } } put(ans); return 0; }
前缀和，但注意细节：
1：此题以（0,0）为起始坐标，输入时直接加一.
2：空间限制，省掉a数组，记录是直接用f数组记录，再预处理值（不会有问题，因为推时是从小到大推的（i，j）这个点只有在f[i][j]是才会用到，不会对前面或后面造成影响）.
Tallest Cow：
#include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define _ 0 using namespace std; const int maxn=11000; int c[maxn],d[maxn],n,p,h,r,x,y; map<int,map<int,int> >f; int main() { cin>>n>>p>>h>>r; for(int i=1;i<=r;i++) { cin>>x>>y; if(x>y) swap(x,y); if(f[x][y]) continue; f[x][y]=1; d[x+1]--; d[y]++; } for(int i=1;i<=n;i++) { c[i]=c[i-1]+d[i]; cout<<h+c[i]<<endl; } return (0^_^0); }
细节：
1：直接贪心的思考问题，要求每一个奶牛尽可能的高，限制的条件A，B之间的奶牛都减1即可，A，B不变.
2：一维数组加前缀和实现区间修改.