T1:
2000的数据显然不能矩阵乘法。
考场上忘了矩阵乘法怎么写了，手推了一下，结果突然发现有公因式Orz
提取一下公因式，就可以有O(nm)的解法了。。。（忘了矩乘海星）
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
const int N=2005;
int n,m,a[N][N],b[N][N];
long long s1[N][N],s2[N][N];
int xa,xb,ya,yb;
long long ans;
int rd() {
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main() {
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
n=rd(),m=rd();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=rd();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=rd();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
s1[i][j]=s1[i-1][j]+a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
s2[i][j]=s2[i][j-1]+b[i][j];
while(m--) {
ans=0ll;
xa=rd(),ya=rd(),xb=rd(),yb=rd();
if(xa>xb) swap(xa,xb);
if(ya>yb) swap(ya,yb);
for(int i=1;i<=n;i++) {
ans+=(s1[xb][i]-s1[xa-1][i])*(s2[i][yb]-s2[i][ya-1]);
}
cout<<ans<<endl;
}
return 0;
}
T2:
有个结论：选的点的x，y坐标一定出现过。（富贵险中求，和暴力拍一下发现对的。。。）
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
vector<long long>x,y;
long long rd() {
long long x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int N=55;
long long n,dis[N],ans[N],sum[N];
struct Points {long long x,y;} p[N];
int main() {
freopen("tower.in","r",stdin);
freopen("tower.out","w",stdout);
n=rd();
memset(ans,0x3f,sizeof ans);
for(int i=1; i<=n; i++) p[i].x=rd(),p[i].y=rd(),x.push_back(p[i].x),y.push_back(p[i].y);
for(int i=0; i<x.size(); i++)
for(int j=0; j<y.size(); j++) {
memset(dis,0x3f,sizeof dis);
for(int k=1; k<=n; k++) dis[k]=min(dis[k],abs(p[k].x-x[i])+abs(p[k].y-y[j]));
sort(dis+1,dis+1+n);
for(int k=1;k<=n;k++) sum[k]=sum[k-1]+dis[k];
for(int k=1;k<=n;k++) ans[k]=min(ans[k],sum[k]);
}
for(int i=1;i<=n;i++) printf("%lld
",ans[i]);
return 0;
}
T3
树形dp，f[x][0]表示不选这个点作为起点的最大匹配，对应一个g[x][0]表示方案数，f[x][1]表示取这个点为起点。
转移的时候取最大匹配及对应的方案即可。需要注意的是如果f[x][0]==f[x][1]，g需要加法原理求和。（需要写高精）
日常想骂出高精的出题人...
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#define int long long
#define f(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1005;
int n,m,head[N],ecnt;
int f[N][2],mxf[N],g[N][2],mxg[N];
struct Edge {
int nxt,to;
} e[N<<1];
void add(int bg,int ed) {
e[++ecnt].nxt=head[bg];
e[ecnt].to=ed;
head[bg]=ecnt;
}
void dfs(int x,int fa) {
g[x][0]=1;
for(int i=head[x]; i; i=e[i].nxt) {
int v=e[i].to;
if(v==fa) continue;
dfs(v,x);
f[x][0]+=mxf[v];
g[x][0]=g[x][0]*mxg[v];
}
int t=0;int p=0;
for(int i=head[x]; i; i=e[i].nxt) {
int v=e[i].to;
if(v==fa) continue;
t=f[x][0]-mxf[v]+f[v][0]+1;
p=g[x][0]/mxg[v]*g[v][0];
if(f[x][1]==t) g[x][1]+=p;
else if(f[x][1]<t) g[x][1]=p,f[x][1]=t;
}
if(f[x][0]>f[x][1]) mxf[x]=f[x][0],mxg[x]=g[x][0];
else if(f[x][1]>f[x][0]) mxf[x]=f[x][1],mxg[x]=g[x][1];
else mxf[x]=f[x][1],mxg[x]=g[x][1]+g[x][0];
}
signed main() {
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%lld",&n);
for(int i=1,p,c,a; i<=n; i++) {
scanf("%lld%lld",&p,&c);
for(int j=1; j<=c; j++) {
scanf("%lld",&a);
add(p,a);
add(a,p);
}
}
dfs(1,0);
cout<<mxf[1]<<endl<<mxg[1];
}