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=;i<len;++i)
{
if(s[i]=='(') L++;
else if(s[i]==')'&&L) L--;
else R++;
}
printf("%d",(L+)/+(R+)/);
return ;
}
T2
线段树维护乘车区间的最小值
#include <algorithm>
#include <cstdio>
#define N 55000struct 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[];
segment()
{
ch[]=ch[]=NULL;
flag=val=;
}
}*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)>>;
build(k->ch[],l,k->mid);
build(k->ch[],k->mid+,r);
k->val=min(k->ch[]->val,k->ch[]->val);
}
void pushdown(segment *&k)
{
k->ch[]->flag+=k->flag;
k->ch[]->flag+=k->flag;
k->ch[]->val+=k->flag;
k->ch[]->val+=k->flag;
k->flag=;
}
int query(segment *&k,int l,int r)
{
if(k->l==l&&k->r==r) return k->val>=?k->val:;
if(k->flag) pushdown(k);
if(l>k->mid) return query(k->ch[],l,r);
else if(r<=k->mid) return query(k->ch[],l,r);
else return min(query(k->ch[],l,k->mid),query(k->ch[],k->mid+,r));
k->val=min(k->ch[]->val,k->ch[]->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[],l,r,v);
else if(r<=k->mid) modify(k->ch[],l,r,v);
else modify(k->ch[],l,k->mid,v),modify(k->ch[],k->mid+,r,v);
k->val=min(k->ch[]->val,k->ch[]->val);
}
void init() {build(root,,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=;i<=k;++i)
{
scanf("%d%d%d",&af[i].x,&af[i].y,&af[i].c);
af[i].y--;
}
std::sort(af+,af++k);
init();
for(int i=;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 ;
}
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[][],MIN[],b[],dp[][],i,j,s[][],ans,P,k;
int main()
{
freopen("puzzle.in","r",stdin);
freopen("puzzle.out","w",stdout);
while (cin>>n)
{
ans=-;
scanf("%d%d",&m,&P); assert(<=n && n<= && <=m && m<= && -<=P && P<=);
for (i=; i<=n; i++)
for (j=; j<=m; j++) {scanf("%d",&a[i][j]); assert(-<=a[i][j] && a[i][j]<=); }
for (i=; i<=n; i++)
for (j=; j<=m; j++)
s[i][j]=s[i-][j]+a[i][j];
for (i=; i<=n; i++)
{
for (j=; j<=m; j++) MIN[j]=a[i][j];
for (j=i; j<=n; j++)
{
for (k=; k<=m; k++) MIN[k]=min(MIN[k],a[j][k]);
for (k=; k<=m; k++) b[k]=s[j][k]-s[i-][k]; dp[][]=-;
for (k=; k<=m; k++) dp[k][]=max(dp[k-][]+b[k],b[k]),dp[k][]=max(max(dp[k-][]+b[k],dp[k-][]+b[k]-MIN[k]+P),b[k]-MIN[k]+P);
for (k=; k<m; k++) ans=max(ans,max(dp[k][],dp[k][]));
if (i== && j==n)
{
ans=max(ans,dp[m][]); int sum=;
for (k=m; k>; k--) {sum+=b[k]; ans=max(ans,sum);}
} else
ans=max(ans,max(dp[m][],dp[m][]));
}
}
cout<<ans<<endl;
}
return ;
}
