FZU 2079 最大获利(dp)
自己很难想到，囧
dp[i]表示处理完前i 个点的最大收益。
有两种情况：
（1）第i 个点不投资，那么dp[i] = dp[i - 1]
（2）第i 个点投资，那么dp[i] = max(dp[k] + get(k + 1,i) - sigma(c[j]) (k + 1 <= j <= i))(0 < k <
i)
这个的意思是，[k + 1,i]点选择全部投资，所以sigma(c[j])表示每个点都投资了，get(k +
1,i)的意思是，[k + 1,i]完全包含了的给出区间的总价值
第二步需要优化，我们发现，任意一个dp[i]的转移dp[k]，sigma(c[j])，即dp[k] 减去了从k
+ 1,i 的每个数c[i]，所以每做到一个数i，给1..i - 1 中的每个dp 值减去c[i]（因为以后要用
某个dp 转移的话，后面的每个数都被减了一次)。第二个是收益[Li,Ri,Pi]，同样的方法，
选择了dp[k],k < Li 的话，意味着get(k + 1,i)增加了Pi，所以给1...Li - 1 的每个dp 值加上Pi
赛后代码：
view code#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int N = 22222;int n, m, a[N], dp[N], col[N<<2], Max[N<<2];struct seg{ int l, r, w; seg() {} seg(int l, int r, int w):l(l),r(r),w(w) {} bool operator < (const seg &o) const { return r<o.r||(o.r==r&&l>o.l); }}e[N];void Down(int rt){ if(col[rt]) { Max[rt<<1] += col[rt]; Max[rt<<1|1] += col[rt]; col[rt<<1] += col[rt]; col[rt<<1|1] += col[rt]; col[rt] = 0; }}void update(int L, int R, int c, int l, int r, int rt){ if(L<=l && R>=r) { Max[rt] += c; col[rt] += c; return ; } Down(rt); int m=(l+r)>>1; if(L<=m) update(L, R, c, lson); if(R>m) update(L, R, c, rson); Max[rt] = max(Max[rt<<1], Max[rt<<1|1]);}int query(int L, int R, int l, int r, int rt){ if(L<=l && R>=r) return Max[rt]; int m = (l+r)>>1, ans = 0; if(L<=m) ans = max(query(L,R,lson), ans); if(R>m) ans = max(query(L,R,rson), ans); return ans;}void solve(){ memset(col, 0, sizeof(col)); memset(Max, 0, sizeof(Max)); for(int i=1; i<=n; i++) scanf("%d", a+i); for(int i=0; i<m; i++) scanf("%d%d%d", &e[i].l, &e[i].r, &e[i].w); sort(e, e+m); int i=1, j=0; for(; i<=n; i++) { update(0, i-1, -a[i], 0, n, 1); while(j<m && e[j].r<=i) { update(0, e[j].l-1, e[j].w, 0, n, 1); j++; } dp[i] = max(dp[i-1], query(0, i-1, 0, n, 1)); update(i, i, dp[i], 0, n, 1); } printf("%d\n", dp[n]);}int main(){// freopen("in.txt", "r", stdin); while(scanf("%d%d", &n, &m)>0 ) solve(); return 0;}
FZU 2056 最大正方形（二分，水题）
刚开始看题目还以为是长方形，最近老是看错题目
view code#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <cmath>#include <algorithm>#include <map>#include <vector>#include <string>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int N = 1010;int mat[N][N], sum[N][N];int _, n, m, lim, ansn, ansm;bool is_ok(int len){ for(int i=len; i<=n; i++) { for(int j=len; j<=m; j++) { if(sum[i][j]+sum[i-len][j-len]-sum[i-len][j]-sum[i][j-len]<=lim) return 1; } } return 0;}void solve(){ scanf("%d%d%d", &n, &m, &lim); for(int i=1 ;i<=n ;i++) { for(int j=1; j<=m; j++) { scanf("%d", &mat[i][j]); sum[i][j] = sum[i-1][j]+sum[i][j-1] - sum[i-1][j-1] +mat[i][j]; } } int l=1, r=min(n, m), ans=0; while(l<=r) { int mid = (l+r)>>1; if(is_ok(mid)) ans = mid, l = mid+1; else r = mid-1; } printf("%d\n", ans*ans);}int main(){// freopen("in", "r", stdin); cin>>_; while(_--) solve(); return 0;}
FZU 2082
方法一：树链剖分最入门的题目，复杂度nlognlogn(第一次听说树链剖分)
方法二：随便选一个点作为root，dfs 一次求出root 到某个点的距离，并且得到dfs 序。
一个显然的事实：dis(u,v) = dis(root,u) + dis(root,v) - 2 * dis(root,lca(u,v))，因此任意两个点的
距离可以直接用到root 的距离算出来。dis(root,i)表示从根到i 的距离，dis(u,v)是u 到v 的距
离
修改操作是，如果给(fa(u),u)这条边增加了一个值x，那么dis(root,u)增加x，且其后代每个
点的dis(root,i)都增加了x，这个操作，直接用得到的dfs 序维护即可
（把dfs序列得到的dis弄到线段树上，对于root所有子节点增加x,相当于成段更新，因为root的所有子节点是连续的线段）！！
view code#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long ll;const int N = 50010;int n, m, c, pre[N], id[N], now;int E[N<<1], pos, R[N], d[N<<1][21];//E得到的dfs序列用来求Lcaint LL[N], RR[N], EE[N], ppos;//EE得到的序列是用于线段树，EE[i]的字结点位于区间LL[i]+1,RR[i]-1.bool vis[N];ll dp[N], sum[N<<2];struct edge{ int u, v;ll w; int p; edge() {} edge(int u, int v,ll w, int p):u(u), v(v), w(w), p(p) {}}e[N<<1];int ecnt, tot;void init_RMQ(){ for(int i=0; i<pos; i++) d[i][0] = E[i]; for(int j=1; (1<<j)<pos; j++) for(int i=0; i+(1<<j)-1<pos; i++) d[i][j] = min(d[i][j-1], d[i+(1<<(j-1))][j-1]);}ll RMQ(int L, int R){ int k=0; while((1<<(k+1)) <= R-L+1) k++; return min(d[L][k], d[R-(1<<k)+1][k]);}void dfs(int u, int h){ vis[u] = 1; id[u] = now++; R[id[u]] = pos; E[pos++] = id[u]; LL[id[u]] = tot; EE[tot++] = id[u]; dp[id[u]] = h; for(int i=pre[u]; ~i; i=e[i].p) { int v = e[i].v; if(vis[v]) continue; dfs(v, h+e[i].w); E[pos++] = id[u]; } RR[id[u]]=tot;}void build(int l, int r, int rt){ if(l==r) { sum[rt] = dp[EE[pos++]]; return ; } int m = (l+r)>>1; build(lson); build(rson); sum[rt] = 0;}void Down(int rt){ if(sum[rt]) { sum[rt<<1|1]+=sum[rt]; sum[rt<<1] += sum[rt]; sum[rt] = 0; }}ll query(int p, int l, int r, int rt){ if(l==r) return sum[rt]; Down(rt); int m = (l+r)>>1; ll ans = 0; if(p<=m) ans = query(p, lson); else ans = query(p, rson); return ans;}void update(int L, int R, int c,int l, int r, int rt){ if(L<=l && R>=r) { sum[rt] += c; return ; } Down(rt); int m = (l+r)>>1; if(L<=m) update(L, R, c, lson); if(R>m) update(L, R, c, rson);}void addedge(int u, int v, int w){ e[ecnt] = edge(u, v, w, pre[u]); pre[u] = ecnt++; e[ecnt] = edge(v, u, w, pre[v]); pre[v] = ecnt++;}void solve(){ memset(pre, -1, sizeof(pre)); ecnt = 0, tot=1; int u, v, w, flag; for(int i=1; i<n; i++) { scanf("%d%d%d", &u, &v, &w); addedge(u,v,w); } now = 1; pos = 0, ppos = 1; memset(vis, 0, sizeof(vis)); dfs(1, 0); init_RMQ(); pos = 1; build(1, n, 1); while(m--) { scanf("%d%d%d", &flag, &u, &v); if(flag) { u = id[u], v = id[v]; int lca = RMQ(min(R[u], R[v]), max(R[u],R[v])); ll ans = query(LL[u], 1, n, 1) + query(LL[v], 1, n, 1) - 2*query(LL[lca], 1, n, 1); printf("%I64d\n", ans); } else { int ndis = v, c = 2*u-1; u = id[e[c].u], v = id[e[c].v]; if(query(LL[u], 1, n, 1)>query(LL[v], 1, n, 1)) update(LL[u], RR[u]-1, ndis-e[c].w, 1, n, 1); else update(LL[v], RR[v]-1, ndis-e[c].w, 1, n, 1); e[c].w = e[c-1].w = ndis; } }}int main(){// freopen("in.txt","r",stdin); while(scanf("%d%d", &n, &m)>0) solve(); return 0;}
FZU 2057 家谱（简单的遍历）
view code#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <cmath>#include <algorithm>#include <map>#include <vector>#include <string>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int N = 10010;int _, n, m, p[N];struct edge{ int fa, ma, flag; edge() {} edge(int fa, int ma, int flag):fa(fa),ma(ma),flag(flag) {}}e[N];bool dfs(int u, int t){ if(u==0) return 0; if(u==t) return 1; if(dfs(e[u].fa, t)) { p[u] = e[u].fa; return 1;// printf("") } else if(dfs(e[u].ma, t)) { p[u] = e[u].ma; return 1; } return 0;}void visit(int u, int t){ if(u==t) { printf(e[u].flag?"F":"M"); return; } printf(e[u].flag?"F":"M"); visit(p[u], t);}void solve(){ scanf("%d", &n); int k = n/2, t, u, v; for(int i=0; i<=n; i++) e[i] = edge(0, 0, 0); for(int i=0; i<k; i++) { scanf("%d%d%d", &t, &u, &v); e[t].fa = u; e[t].ma = v; e[u].flag = 1; } scanf("%d", &m); for(int i=0; i<m; i++) { scanf("%d%d", &u, &v); if(dfs(u,v)) { printf("1 "); visit(p[u],v); puts(""); } else if(dfs(v, u)) { printf("0 "); visit(p[v],u); puts(""); } else puts("Relative"); }}int main(){// freopen("in", "r", stdin); cin>>_; while(_--) solve(); return 0;}
FZU 2059 MM(暴力)
因为最多只有10次修改，就把当作最多有10个子case就好了
view code#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std;const int INF = 0x3f3f3f3f;const int N = 100010;int _, n, m;int a[N], L[N], R[N], ma[N], mcnt, Max[N];int find(int ser){ int l = 0, r = mcnt-1, ans = -1; while(l<=r) { int m = (l+r)>>1; if(ma[m]==ser) return m; if(ser<ma[m]) ans = m, r = m-1; else l = m+1; } return ans;}void init(){ a[0] = a[n+1] = -INF; mcnt = 1; for(int i=1; i<=n; i++) ma[i-1] = a[i]; sort(ma, ma+n); for(int i=1; i<n; i++) if(ma[i]!=ma[i-1]) ma[mcnt++] = ma[i]; int pos, id; for(int i=1; i<=n; i++) { L[i] = i; pos = i-1; while(a[i]<=a[pos]) L[i]=L[pos], pos=L[pos]-1; } memset(Max, 0, sizeof(Max)); for(int i=n; i>0; i--) { R[i] = i; pos = i+1; while(a[i]<=a[pos]) R[i]=R[pos], pos=R[pos]+1; id = find(a[i]); Max[id] = max(Max[id], R[i]-L[i]+1); } for(int i=mcnt-1; i>0; i--) { Max[i-1] = max(Max[i], Max[i-1]); }// for(int i=1; i<=n; i++) printf("%d , %d\n", L[i], R[i]);}int main(){// freopen("in.txt", "r", stdin); while(scanf("%d%d", &n, &m)>0) { for(int i=1; i<=n; i++) scanf("%d", a+i); int f, x, y; init(); for(int i=0; i<m; i++) { scanf("%d%d", &f, &x); if(f==1) { int id = find(x); if(id>=0) printf("%d\n", Max[id]); else printf("0\n"); } else { scanf("%d", &y); a[x] = y; init(); } } } return 0;}
FZU 2060 The Sum of Sub-matrices（状态压缩dp，不会）
FZU 2030 括号问题（dfs/dp）
view code#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <cmath>#include <algorithm>#include <map>#include <vector>#include <string>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;int n, m, sum[50], a[50];char s[50];int dfs(int now, int num){ if(num<0) return 0; if(now>=n) { if(num==0) return 1; else return 0; } int ans = 0; if(s[now]==‘(‘) ans= dfs(now+1, num+1); else if(s[now]==‘)‘ ) { ans = dfs(now+1, num-1); } else { ans += dfs(now+1, num+1); ans += dfs(now+1, num-1); }// printf("%d , %d\n", now, ans); return ans;}void solve(){ n = strlen(s); printf("%d\n", dfs(0, 0));}int main(){// freopen("in", "r", stdin); while(scanf("%s", s)>0) solve(); return 0;}
