只会切水题,表示很菜,压力很大。。。
B题树状数组:
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<algorithm> #include<vector> using namespace std; #define MAXN 1000005 int c[MAXN]; void init() { memset(c,0,sizeof(c)); } int Lowbit(int t){ return t&(-t); } void add(int pos,int val) { for( ;pos<=MAXN;c[pos]+=val,pos+=Lowbit(pos)); } int getsum(int end) { int sum=0; for( ;end>0;sum+=c[end],end-=Lowbit(end)); return sum; } int main() { int a,b; char str[5]; init(); while(scanf("%s%d%d",str,&a,&b)!=EOF) { if(str[0]=='p') add(a,b); else if(str[0]=='c') add(a,-b); else { if(a>b) swap(a,b); printf("%d\n",getsum(b)-getsum(a-1)); } } return 0; }
E题简单DP:
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<algorithm> #include<map> #include<string> #include<iomanip> #include<vector> using namespace std; #define MAX 1005 int a[MAX][MAX],leftUp[MAX][MAX],rightUp[MAX][MAX],n,m,i,j; void init() { for(j=1;j<=m;j++) leftUp[1][j]=rightUp[1][j]=a[1][j]; for(i=1;i<=n;i++) leftUp[i][1]=rightUp[i][1]=a[i][1]; } int dp() { int ans=0; for(i=2;i<=n;i++) for(j=2;j<=m;j++) { if(a[i][j]) { leftUp[i][j]=leftUp[i-1][j-1]+1; if(j<m) rightUp[i][j]=rightUp[i-1][j+1]+1; else rightUp[i][j]=a[i][j]; } else leftUp[i][j]=rightUp[i][j]=0; if(leftUp[i][j]>1 && rightUp[i][j]>1) ans=max(ans,leftUp[i][j]+rightUp[i][j]-1); } return ans; } int main() { int t,ans; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&a[i][j]); init(); ans=dp(); printf("%d\n",ans>=3?ans:-1); } return 0; }