A：暴力枚举第一列加多少次，显然这样能确定一种方案。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 110
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,m,a[N][N],b[N][N],ans[1000000][2],u,v,qwq[1000000][2];
ll qaq;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read(),m=read();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
qaq+=a[i][j]=read();
u=1000000;
for (int i=0;i<=500;i++)
{
bool flag=0;
for (int j=1;j<=n;j++) if (a[j][1]<i) {flag=1;break;}
if (flag) break;
memcpy(b,a,sizeof(b));v=0;
for (int j=1;j<=i;j++) v++,qwq[v][0]=1,qwq[v][1]=1;
for (int j=1;j<=n;j++) b[j][1]-=i;
for (int j=1;j<=n;j++)
{
for (int x=1;x<=b[j][1];x++) v++,qwq[v][0]=0,qwq[v][1]=j;
for (int x=2;x<=m;x++)
b[j][x]-=b[j][1];
b[j][1]=0;
}
flag=0;
for (int j=1;j<=n;j++)
for (int x=1;x<=m;x++)
if (b[j][x]<0) {flag=1;break;}
if (!flag)
{
for (int j=2;j<=m;j++)
{
int y=510;
for (int x=1;x<=n;x++)
y=min(y,b[x][j]);
for (int x=1;x<=y;x++) v++,qwq[v][0]=1,qwq[v][1]=j;
for (int x=1;x<=n;x++)
b[x][j]-=y;
flag=0;
for (int x=1;x<=n;x++)
if (b[x][j]) {flag=1;break;}
if (flag) break;
}
if (!flag&&v<u)
{
u=v;for (int j=1;j<=u;j++) ans[j][0]=qwq[j][0],ans[j][1]=qwq[j][1];
}
}
}
if (u==1000000) {cout<<-1;return 0;}
cout<<u<<endl;
for (int i=1;i<=u;i++)
{
if (ans[i][0]==0) printf("row ");
else printf("col ");
printf("%d
",ans[i][1]);
}
return 0;
//NOTICE LONG LONG!!!!!
}
B：显然每个数的贡献与组合数有关，找找规律发现讨论一下n%4的几种情况就行了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 200010
#define P 1000000007
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,a[N],b[N],fac[N],inv[N],ans;
int C(int n,int m){if (n<0||m<0||m>n) return 0;return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
n=read();
for (int i=1;i<=n;i++) b[i]=a[i]=read();
fac[0]=fac[1]=1;for (int i=2;i<=n;i++)fac[i]=1ll*fac[i-1]*i%P;
inv[0]=inv[1]=1;for (int i=2;i<=n;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;
for (int i=2;i<=n;i++) inv[i]=1ll*inv[i]*inv[i-1]%P;
if (n%4==1)
{
for (int i=1;i<=n;i++)
if (i&1) ans=(ans+1ll*a[i]*C(n/2,i/2))%P;
}
else if (n%4==3)
{
for (int i=1;i<=n;i++)
if (i&1) ans=(ans+1ll*a[i]*(C((n-3)/2,i/2)-C((n-3)/2,i/2-1)+P))%P;
else ans=(ans+2ll*a[i]*C((n-3)/2,i/2-1))%P;
}
else
{
for (int i=1;i<=n;i++)
if ((i&1)||n%4==2) ans=(ans+1ll*a[i]*C(n/2-1,(i-1)/2))%P;
else ans=(ans-1ll*a[i]*C(n/2-1,i/2-1)%P+P)%P;
}
cout<<ans;
return 0;
//NOTICE LONG LONG!!!!!
}
C：显然依赖关系形成一棵树。设f[i][j]为i子树选j个的最小代价，其中根必须使用优惠券；g[i][j]为i子树选j个的最小代价，不能使用优惠券。直接背包即可，众所周知复杂度O(n2)。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 5010
#define inf 1010000000
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,m,p[N],f[N][N],s[N][N],size[N],t,c[N],d[N];
struct data2{int to,nxt;
}edge[N];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
void dfs(int k)
{
size[k]=1;s[k][1]=c[k];f[k][1]=d[k];f[k][0]=inf;
for (int i=p[k];i;i=edge[i].nxt)
{
dfs(edge[i].to);
for (int j=size[k]+1;j<=size[k]+size[edge[i].to];j++) f[k][j]=s[k][j]=inf;
for (int j=size[k];j>=0;j--)
for (int x=size[edge[i].to];x>=0;x--)
s[k][j+x]=min(s[k][j+x],s[k][j]+s[edge[i].to][x]),
f[k][j+x]=min(f[k][j+x],f[k][j]+min(s[edge[i].to][x],f[edge[i].to][x]));
size[k]+=size[edge[i].to];
}
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
n=read(),m=read();
for (int i=1;i<=n;i++)
{
c[i]=read(),d[i]=c[i]-read();
if (i>1) addedge(read(),i);
}
dfs(1);
int ans=0;
for (int i=0;i<=n;i++) if (f[1][i]<=m||s[1][i]<=m) ans=i;
cout<<ans;
return 0;
//NOTICE LONG LONG!!!!!
}
D：枚举第一维，剩下两维看成一个平面，考虑每张牌对答案的限制。容易发现根据第一维是大还是小分成两类，分别将答案所对应的点限制在一块矩形区域（或两个矩形的并），且对于同一张牌，后者对应的区域包含前者。现在要动态维护这些区域的交的面积。
考虑改为求其补集的并。注意到这些矩形底部都在坐标轴上。那么相当于要支持区间取max区间求和。并且可以注意到其矩形并构成下降阶梯状。于是建棵线段树，修改时线段树上二分时找到边界，区间取max改为区间覆盖即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cassert>
using namespace std;
#define ll long long
#define N 500010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,A,B,C,L[N<<2],R[N<<2],lazy[N<<2],mx[N<<2];
ll ans,tree[N<<2];
struct data
{
int x,y,z;
bool operator <(const data&a) const
{
return x<a.x;
}
}a[N];
void up(int k)
{
tree[k]=tree[k<<1]+tree[k<<1|1];
mx[k]=max(mx[k<<1],mx[k<<1|1]);
}
void update(int k,int x)
{
tree[k]=1ll*(R[k]-L[k]+1)*x;
lazy[k]=mx[k]=x;
}
void down(int k)
{
update(k<<1,lazy[k]);
update(k<<1|1,lazy[k]);
lazy[k]=0;
}
void build(int k,int l,int r)
{
L[k]=l,R[k]=r;
if (l==r) return;
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
int find(int k,int x)
{
if (L[k]==R[k]) return L[k]+(mx[k]>=x);
if (lazy[k]) down(k);
if (mx[k<<1|1]>=x) return find(k<<1|1,x);
else return find(k<<1,x);
}//��һ��<x��λ��
void cover(int k,int l,int r,int x)
{
if (L[k]==l&&R[k]==r) {update(k,x);return;}
if (lazy[k]) down(k);
int mid=L[k]+R[k]>>1;
if (r<=mid) cover(k<<1,l,r,x);
else if (l>mid) cover(k<<1|1,l,r,x);
else cover(k<<1,l,mid,x),cover(k<<1|1,mid+1,r,x);
up(k);
}
void modify(int x,int y)
{
int u=find(1,y);
if (u<=x) cover(1,u,x,y);
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read(),A=read(),B=read(),C=read();
for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].z=read();
sort(a+1,a+n+1);
build(1,1,B+1);
for (int i=1;i<=n;i++) modify(a[i].y,a[i].z);
int x=n+1;
for (int i=A;i>=1;i--)
{
while (a[x-1].x>=i)
{
x--;
modify(B,a[x].z);
modify(a[x].y,C);
}
ans+=1ll*B*C-tree[1];
}
cout<<ans;
return 0;
//NOTICE LONG LONG!!!!!
}