T1
模拟
#include <cstring> #include <cstdio> #define N 105000 int L,R; char s[N]; int main() { freopen("bracket.in","r",stdin); freopen("bracket.out","w",stdout); scanf("%s",s); int len=strlen(s); for(int i=0;i<len;++i) { if(s[i]=='(') L++; else if(s[i]==')'&&L) L--; else R++; } printf("%d",(L+1)/2+(R+1)/2); return 0; }
T2
线段树维护乘车区间的最小值
#include <algorithm> #include <cstdio> #define N 55000 struct node { int x,y,c; bool operator<(node a)const { return y<a.y; } }af[N]; int k,n,m,ans; namespace Segment { struct segment { int l,r,mid,val,flag; segment * ch[2]; segment() { ch[0]=ch[1]=NULL; flag=val=0; } }*root=new segment; inline int min(int a,int b){return a>b?b:a;} void build(segment *&k,int l,int r) { k=new segment; k->l=l;k->r=r; if(l==r) { k->val=m; return; } k->mid=(l+r)>>1; build(k->ch[0],l,k->mid); build(k->ch[1],k->mid+1,r); k->val=min(k->ch[0]->val,k->ch[1]->val); } void pushdown(segment *&k) { k->ch[0]->flag+=k->flag; k->ch[1]->flag+=k->flag; k->ch[0]->val+=k->flag; k->ch[1]->val+=k->flag; k->flag=0; } int query(segment *&k,int l,int r) { if(k->l==l&&k->r==r) return k->val>=0?k->val:0; if(k->flag) pushdown(k); if(l>k->mid) return query(k->ch[1],l,r); else if(r<=k->mid) return query(k->ch[0],l,r); else return min(query(k->ch[0],l,k->mid),query(k->ch[1],k->mid+1,r)); k->val=min(k->ch[0]->val,k->ch[1]->val); } void modify(segment *&k,int l,int r,int v) { if(k->l==l&&k->r==r) { k->val+=v; k->flag+=v; return; } if(l>k->mid) modify(k->ch[1],l,r,v); else if(r<=k->mid) modify(k->ch[0],l,r,v); else modify(k->ch[0],l,k->mid,v),modify(k->ch[1],k->mid+1,r,v); k->val=min(k->ch[1]->val,k->ch[0]->val); } void init() {build(root,1,n);} int make(int l,int r) {return query(root,l,r);} void change(int l,int r,int x) {modify(root,l,r,x);} } using namespace Segment; using namespace std; int main(int argc,char *argv[]) { scanf("%d%d%d",&k,&n,&m); for(int i=1;i<=k;++i) { scanf("%d%d%d",&af[i].x,&af[i].y,&af[i].c); af[i].y--; } std::sort(af+1,af+1+k); init(); for(int i=1;i<=k;++i) { int minx=make(af[i].x,af[i].y); if(minx>=af[i].c) ans+=af[i].c,change(af[i].x,af[i].y,-af[i].c); else ans+=minx,change(af[i].x,af[i].y,-minx); } printf("%d",ans); return 0; }
T3
枚举左上角 n^2 枚举右下角n^2 枚举修改的数 n^2 求和 n^2 -> n^8 求一个矩阵和，可以通过矩阵前缀和做到O(1) 枚举左上角 n^2 枚举右下角n^2 枚举修改的数 n^2 -> n^6 预处理出每个矩阵的最小值是多少。 n^4 枚举左上角 n^2 枚举右下角n^2 修改的数已知(修改最小的或者不修改) ->n^4
n,m<=300 假如我们不要求修改数，查询最大子矩阵 有n个数，查询最大子段和 O(n) for (i=1; i<=n; i++) f[i]=max(f[i-1]+a[i],a[i]); max{f[i]} = 最大子段和 要求我们修改数 修改的数一定是最小的那个数。 f[i][0]以i结尾并且没有数被修改过的最大和 f[i][1]以i结尾并且有数被修改过的最大和 //a[i] 第i列的和 for (int i=1; i<=n; i++) { f[i][0]=max(f[i-1][0]+a[i],a[i]); f[i][1]=max(f[i-1][1]+a[i],f[i-1][0]+a[i]-MIN[i]+P,a[i]-MIN[i]+P); } max{f[?][0/1]} 是答案
#include <cmath> #include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> #include <assert.h> using namespace std; int n,m,a[305][305],MIN[305],b[305],dp[305][2],i,j,s[305][305],ans,P,k; int main() { freopen("puzzle.in","r",stdin); freopen("puzzle.out","w",stdout); while (cin>>n) { ans=-1000000000; scanf("%d%d",&m,&P); assert(1<=n && n<=300 && 1<=m && m<=300 && -1000<=P && P<=1000); for (i=1; i<=n; i++) for (j=1; j<=m; j++) {scanf("%d",&a[i][j]); assert(-1000<=a[i][j] && a[i][j]<=1000); } for (i=1; i<=n; i++) for (j=1; j<=m; j++) s[i][j]=s[i-1][j]+a[i][j]; for (i=1; i<=n; i++) { for (j=1; j<=m; j++) MIN[j]=a[i][j]; for (j=i; j<=n; j++) { for (k=1; k<=m; k++) MIN[k]=min(MIN[k],a[j][k]); for (k=1; k<=m; k++) b[k]=s[j][k]-s[i-1][k]; dp[0][1]=-1000000000; for (k=1; k<=m; k++) dp[k][0]=max(dp[k-1][0]+b[k],b[k]),dp[k][1]=max(max(dp[k-1][1]+b[k],dp[k-1][0]+b[k]-MIN[k]+P),b[k]-MIN[k]+P); for (k=1; k<m; k++) ans=max(ans,max(dp[k][0],dp[k][1])); if (i==1 && j==n) { ans=max(ans,dp[m][1]); int sum=0; for (k=m; k>1; k--) {sum+=b[k]; ans=max(ans,sum);} } else ans=max(ans,max(dp[m][1],dp[m][0])); } } cout<<ans<<endl; } return 0; }