第一题：O (n*m) 对于查询矩阵xl, yl, xr, yr;
可以变为 sum（x, i） * (i, y) xl <= x <= xr, yl <= y <= yr, 1 <= i <= n;
用一个乘法分配率+前缀和 变为sum ( a[xl - xr][i] * b[i][yl - yr]);
#include<bits/stdc++.h> using namespace std; #define ll long long const int M = 2005; ll sum1[M][M], sum2[M][M], b[M][M], a[M][M], tot; int main(){ freopen("matrix.in","r",stdin); freopen("matrix.out","w",stdout); int n, m, x; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){ scanf("%lld", &a[i][j]); sum1[i][j] = sum1[i - 1][j] + a[i][j]; } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){ scanf("%lld", &b[i][j]); sum2[i][j] = sum2[i][j - 1] + b[i][j]; } int xl, yl, xr, yr; while(m--){ ll ans = 0; scanf("%d%d%d%d", &xl, &yl, &xr, &yr); if(xl > xr) swap(xl, xr); if(yl > yr) swap(yl, yr); for(int j = 1; j <= n; j++) ans += (sum1[xr][j] - sum1[xl - 1][j]) * (sum2[j][yr] - sum2[j][yl - 1]); printf("%lld ",ans); } }
第二题：X轴，Y轴可以分开处理，就变成了一个中位数问题（证明蓝书上有）；因为肯定有一个中位数即一个点存在，我们就可以枚举这个中位数，X，Y各枚举一个，取距离的前i小；
O（n^4 * logn）
#include<bits/stdc++.h> using namespace std; const int M = 55, inf = 2e9; int dis[M]; struct Point{int x, y;}a[M]; inline int ab(int a){return a >= 0 ? a : -a;} inline int get(int x, int y, int t){ return ab(x - a[t].x) + ab(y - a[t].y); } int main(){ freopen("tower.in","r",stdin); freopen("tower.out","w",stdout); int n; scanf("%d", &n); for(int i = 1; i <= n; i++)scanf("%d%d", &a[i].x, &a[i].y); for(int cnt = 1; cnt <= n; cnt++){ int ans = inf; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ int xx = a[i].x, yy = a[j].y; int tmp = 0; for(int p = 1; p <= n; p++) dis[p] = get(xx, yy, p); sort(dis + 1, dis + 1 + n); for(int p = 1; p <= cnt; p++) tmp += dis[p]; ans = min(ans, tmp); } } printf("%d ", ans); } return 0; }
第三题：树形DP+高精度；
dp[u][0/1]表示u的子树中的最大匹配，g[u][0/1]表示方案数；
更新dp, 对于u和下面连的情况就暴力枚举和哪一个连；
dp是用那种更新的，g就用那种更新，乘法原理， 如果dp值一样，就加法原理
下面是无高精的code
#include<bits/stdc++.h> using namespace std; #define ll long long const int M = 1e3 + 10; ll g[M][2]; int h[M], dp[M][2], tot; struct edge{int v, nxt;}G[M << 1]; void add(int u, int v){G[++tot].v = v; G[tot].nxt = h[u]; h[u] = tot;} void dfs(int u, int f){ int child = 0, ans = 0; ll tmp1 = 1, opt = 0; for(int i = h[u]; i; i = G[i].nxt){ int v = G[i].v; if(v == f)continue; dfs(v, u); child++; if(dp[v][0] > dp[v][1]) tmp1 *= g[v][0]; else if(dp[v][0] == dp[v][1]) tmp1 *= (g[v][0] + g[v][1]); else tmp1 *= g[v][1]; dp[u][0] += max(dp[v][0], dp[v][1]); } g[u][0] = tmp1; for(int i = h[u]; i; i = G[i].nxt){ int v = G[i].v; if(v == f)continue; int d = dp[v][0]; ll tmp2 = g[v][0]; for(int j = h[u]; j; j = G[j].nxt){ int vv = G[j].v; if(vv != f && vv != v){ if(dp[vv][0] > dp[vv][1]) tmp2 *= g[vv][0]; else if(dp[vv][0] == dp[vv][1]) tmp2 *= (g[vv][0] + g[vv][1]); else tmp2 *= g[vv][1]; d += max(dp[vv][0], dp[vv][1]); } } if(d > ans)ans = d, opt = tmp2; else if(d == ans) opt += tmp2; } if(child) dp[u][1] = ans + 1, g[u][1] = opt; //printf("%d %d %d %lld %lld ", u, dp[u][0], dp[u][1], g[u][0], g[u][1]); } int main(){ freopen("tree.in","r", stdin); freopen("tree.out","w",stdout); int n, u, x, v; scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d%d",&u, &x); while(x--) { scanf("%d", &v); add(u, v); } } dfs(1, 0); ll ret = 0; if(dp[1][0] >= dp[1][1]) ret += g[1][0]; if(dp[1][1] >= dp[1][0]) ret += g[1][1]; printf("%d %lld ", max(dp[1][0], dp[1][1]), ret); }