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|1
const 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|1
typedef 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序列用来求Lca
int 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;
}
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;
}
2014 8.7 第8场个人 排位,布布扣,bubuko.com
2014 8.7 第8场个人 排位
原文：http://www.cnblogs.com/zyx1314/p/3898425.html
