2018年12月2526日
小結：昨天因為整理課件，調代碼耗費了大量時間，所以沒來得及整理作業，這兩天主要做的題目是關于樹鏈剖分和線段樹的，難度大約都是省選難度，畢竟只要涉及到樹鏈剖分難度就肯定不低。
一. 完成的題目：
洛谷P3870，洛谷P2628，洛谷P3384，洛谷P2590，洛谷P3178，洛谷P2014，洛谷P4092，SP1716
二.
1. 完成題目數：8道。
2. 未完成6個題目的原因：
3. 復習的知識點：樹鏈剖分，樹型dp，dfs序，線段樹
4.不會題目：SP6779，洛谷P1823
三：
1.洛谷 P3870 [TJOI2009]開關
題目描述
現有\(N（2 ≤ N ≤ 100000）\)盞燈排成一排，從左到右依次編號為：\(1，2，......，N\)。然后依次執行\(M（1 ≤ M ≤ 100000）\)項操作，操作分為兩種：第一種操作指定一個區間\([a, b]\)，然后改變編號在這個區間內的燈的狀態（把開著的燈關上，關著的燈打開），第二種操作是指定一個區間\([a, b]\)，要求你輸出這個區間內有多少盞燈是打開的。燈在初始時都是關著的。
輸入輸出格式
輸入格式：
第一行有兩個整數\(N\)和\(M\)，分別表示燈的數目和操作的數目。接下來有\(M\)行，每行有三個整數，依次為：\(c, a, b\)。其中\(c\)表示操作的種類，當\(c\)的值為\(0\)時，表示是第一種操作。當\(c\)的值為\(1\)時表示是第二種操作。\(a\)和\(b\)則分別表示了操作區間的左右邊界\(（1 ≤ a ≤ b ≤ N）\)。
輸出格式：
每當遇到第二種操作時，輸出一行，包含一個整數：此時在查詢的區間中打開的燈的數目。
輸入輸出樣例
輸入樣例#1：
4 5 0 1 2 0 2 4 1 2 3 0 2 4 1 1 4輸出樣例#1：
1 2思路：還是一道線段樹區間異或，思路跟之前做的洛谷P2574和洛谷P2846完全一樣。
代碼：
#include<cstdio> #include<cctype> #define maxn 100007 #define ls rt<<1 #define rs rt<<1|1 using namespace std; int n,m,sum[maxn<<2],lazy[maxn<<2]; inline int qread() {char c=getchar();int num=0,f=1;for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) num=num*10+c-'0';return num*f; } inline void pushup(int rt) {sum[rt]=sum[ls]+sum[rs]; } inline void pushdown(int rt, int len) {if(lazy[rt]) {lazy[ls]^=1;lazy[rs]^=1;sum[ls]=(len-(len>>1))-sum[ls];sum[rs]=(len>>1)-sum[rs];lazy[rt]=0;} } void modify(int rt, int l, int r, int L, int R) {if(L>r||R<l) return;if(L<=l&&r<=R) {lazy[rt]^=1;sum[rt]=r-l+1-sum[rt];return;}pushdown(rt,r-l+1);int mid=(l+r)>>1;modify(ls,l,mid,L,R),modify(rs,mid+1,r,L,R);pushup(rt); } int csum(int rt, int l, int r, int L, int R) {if(L>r||R<l) return 0;if(L<=l&&r<=R) return sum[rt];pushdown(rt,r-l+1);int mid=(l+r)>>1;return csum(ls,l,mid,L,R)+csum(rs,mid+1,r,L,R); } int main() {n=qread(),m=qread();for(int i=1,k,l,r;i<=m;++i) {k=qread(),l=qread(),r=qread();if(!k) modify(1,1,n,l,r);else printf("%d\n",csum(1,1,n,l,r));}return 0; }2. 洛谷 P2826 LJJ的數學課
題目背景
題目描述（本題是提高組第二題難度＋）
題目描述
LJJ又要開始上數學課啦！（T1，永恒不變的數學）
LJJ的Teacher對上次的考試很不滿意（其實是出題人對上次的分數那么高不滿意啦），決定在出一道難（water）題。
LJJ的Teacher給了LJJ一個數列，但這由于是LJJ的Teacher發明的，我們不稱呼他為LJJ數列，而稱他為Teacher數列。但是LJJ還停留在數數的階段啊，所以不能太難。
于是LJJ的Teacher隨便給出了一個Teacher數列。
Teacher會對這個數列進行兩個操作：
1：將其中的一個數加上s（s為整數）
2：Teacher會給出left和right，讓你求：
a[left](right-left+1) + a[left+1](right-left)
- ...... + a[right-1]2 + a[right]1 的值。
即
LJJ的指頭掰不過來了呀，就請您來完成啦~
輸入輸出格式
輸入格式：
第一行有2個數n,q，分別表示Teacher數列中數的個數以及操作次數。
接下來的一行有n個數，第i個數表示a[i]。
再接下來q行，每行三個數；第一個數是order。如果order=1，那么接下來兩個數：x, s，即把a[x]加上s；如果order=2，那么接下來兩個數：left, right，即求這一段區間ljj要求的答案。
注意：Teacher數列中的數并不一定都是正數，但一定都是整數。
輸出格式：
對于每一個詢問(order=2)輸出所求答案
輸入輸出樣例
輸入樣例#1：
5 3 2 4 1 3 5 2 2 4 1 2 3 2 2 4輸出樣例#1：
17 26說明
數據范圍
n<=100000, q<=100000，保證答案不超過long long (int64) 范圍，保證數據有梯度
樣例解釋
43+12+3*1=17
73+12+3*1=26
提示 1.如果看不懂題目，那么看這里：給你一段數列，有兩種操作，單點修改和區間查詢。查詢left到right，返回的值是
a[left](right-left+1)+a[left+1](right-left)+...+a[right]*1。
2.從另一個角度去想問題，把區間答案劃分開來，否則你會打得很累。
3.題目中說是單點修改，而不是區間修改，有沒有覺得簡單得不可思議呢？
思路：把題目給的式子化一化，提出后面的right-1，變成\(a_{i}*(right+1)-a_{i}*i\)，整個式子變成\(\sum_{}(a_{i}*(right+1)-a_{i}*i)\)，用樹狀數組所以維護\(a_{i}*i\)和普通的加法和就好了。
代碼：
#include<cstdio> #include<cctype> #define maxn 100007 #define lb(x) x&(-x) #define ll long long using namespace std; ll n,m,a[maxn],b[maxn]; inline ll qread() {char c=getchar();ll num=0,f=1;for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) num=num*10+c-'0';return num*f; } inline void add(ll x, ll w) {ll p=x*w;while(x<=n) {a[x]+=w;b[x]+=p;x+=lb(x);} } inline ll csum1(ll x) {ll ans=0;while(x) {ans+=a[x];x-=lb(x);}return ans; } inline ll csum2(ll x) {ll ans=0;while(x) {ans+=b[x];x-=lb(x);}return ans; } int main() {n=qread(),m=qread();for(ll i=1,x;i<=n;++i) {x=qread();add(i,x);}for(ll i=1,k,l,r;i<=m;++i) {k=qread(),l=qread(),r=qread();if(k==1) add(l,r);else printf("%lld\n",(r+1)*(csum1(r)-csum1(l-1))-csum2(r)+csum2(l-1));}return 0; }3. 洛谷P3384 【模板】樹鏈剖分
題目描述
如題，已知一棵包含N個結點的樹（連通且無環），每個節點上包含一個數值，需要支持以下操作：
操作1： 格式： 1 x y z 表示將樹從x到y結點最短路徑上所有節點的值都加上z
操作2： 格式： 2 x y 表示求樹從x到y結點最短路徑上所有節點的值之和
操作3： 格式： 3 x z 表示將以x為根節點的子樹內所有節點值都加上z
操作4： 格式： 4 x 表示求以x為根節點的子樹內所有節點值之和
輸入輸出格式
輸入格式：
第一行包含4個正整數N、M、R、P，分別表示樹的結點個數、操作個數、根節點序號和取模數（即所有的輸出結果均對此取模）。
接下來一行包含N個非負整數，分別依次表示各個節點上初始的數值。
接下來N-1行每行包含兩個整數x、y，表示點x和點y之間連有一條邊（保證無環且連通）
接下來M行每行包含若干個正整數，每行表示一個操作，格式如下：
操作1： 1 x y z
操作2： 2 x y
操作3： 3 x z
操作4： 4 x
輸出格式：
輸出包含若干行，分別依次表示每個操作2或操作4所得的結果（對P取模）
輸入輸出樣例
輸入樣例#1：
5 5 2 24 7 3 7 8 0 1 2 1 5 3 1 4 1 3 4 2 3 2 2 4 5 1 5 1 3 2 1 3輸出樣例#1：
2 21說明
時空限制：1s，128M
數據規模：
對于30%的數據： N \leq 10, M \leq 10N≤10,M≤10
對于70%的數據： N \leq {10}^3, M \leq {10}^3N≤103,M≤103
對于100%的數據： N \leq {10}^5, M \leq {10}^5N≤105,M≤105
（ 其實，純隨機生成的樹LCA+暴力是能過的，可是，你覺得可能是純隨機的么233 ）
樣例說明：
樹的結構如下：
各個操作如下：
故輸出應依次為2、21(重要的事情說三遍：記得取模)
思路：思路在課件里面寫過了，不想再寫一遍了……就是一個樹鏈剖分加線段樹的板子題。
代碼：
#include<cstdio> #include<algorithm> #include<cctype> #define maxn 100007 #define ll long long #define ls rt<<1 #define rs rt<<1|1 using namespace std; int mod,head[maxn],d[maxn],sum[maxn<<2],a[maxn]; int num,cnt,n,m,lazy[maxn<<2],fa[maxn],id[maxn]; int rt,w[maxn],top[maxn],size[maxn],son[maxn]; inline int qread() {char c=getchar();int num=0,f=1;for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) num=num*10+c-'0';return num*f; } struct node {int v,nxt; }e[maxn<<1]; inline void ct(int u, int v) {e[++num].v=v;e[num].nxt=head[u];head[u]=num; } inline void pushup(int rt) {sum[rt]=(sum[ls]+sum[rs])%mod; } void build(int rt, int l, int r) {if(l==r) {sum[rt]=a[l];return;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(rt); } inline void pushdown(int rt, int len) {if(lazy[rt]) {lazy[ls]+=lazy[rt],lazy[ls]%=mod;lazy[rs]+=lazy[rt],lazy[rs]%=mod;sum[ls]+=(len-(len>>1))*lazy[rt],sum[ls]%=mod;sum[rs]+=(len>>1)*lazy[rt],sum[rs]%=mod;lazy[rt]=0;} } void modify(int rt, int l, int r, int L, int R, int val) {if(L>r||R<l) return;if(L<=l&&r<=R) {sum[rt]+=val*(r-l+1),sum[rt]%=mod;lazy[rt]+=val,lazy[rt]%=mod;return;}int mid=(l+r)>>1;pushdown(rt,r-l+1);modify(ls,l,mid,L,R,val),modify(rs,mid+1,r,L,R,val);pushup(rt); } int csum(int rt, int l, int r, int L, int R) {if(L>r||R<l) return 0;if(L<=l&&r<=R) return sum[rt];int mid=(l+r)>>1;pushdown(rt,r-l+1);return csum(ls,l,mid,L,R)+csum(rs,mid+1,r,L,R); } void dfs1(int u, int f) {size[u]=1;for(int i=head[u];i;i=e[i].nxt) {int v=e[i].v;if(v!=f) {d[v]=d[u]+1;fa[v]=u;dfs1(v,u);size[u]+=size[v];if(size[v]>size[son[u]]) son[u]=v;}} } void dfs2(int u, int t) {id[u]=++cnt;a[cnt]=w[u];top[u]=t;if(son[u]) dfs2(son[u],t);for(int i=head[u];i;i=e[i].nxt) {int v=e[i].v;if(v!=fa[u]&&v!=son[u]) dfs2(v,v);} } int calc(int x, int y) {int ans=0;int fx=top[x],fy=top[y];while(fx!=fy) {if(d[fx]<d[fy]) swap(x,y),swap(fx,fy);ans+=csum(1,1,cnt,id[fx],id[x]);x=fa[fx],fx=top[x];}if(id[x]>id[y]) swap(x,y);ans+=csum(1,1,cnt,id[x],id[y]);return ans; } void cal(int x, int y, int val) {int fx=top[x],fy=top[y];while(fx!=fy) {if(d[fx]<d[fy]) swap(x,y),swap(fx,fy);modify(1,1,cnt,id[fx],id[x],val);x=fa[fx],fx=top[x];}if(id[x]>id[y]) swap(x,y);modify(1,1,cnt,id[x],id[y],val); } int main() {n=qread(),m=qread(),rt=qread(),mod=qread();for(int i=1;i<=n;++i) w[i]=qread(),w[i]%=mod;for(int i=1,u,v;i<n;++i) {u=qread(),v=qread();ct(u,v);ct(v,u);}d[rt]=1,fa[rt]=1;dfs1(rt,0);dfs2(rt,rt);build(1,1,n);for(int i=1,k,x,y,z;i<=m;++i) {k=qread();if(k==1) {x=qread(),y=qread(),z=qread();cal(x,y,z%mod);}if(k==2) {x=qread(),y=qread();printf("%d\n",calc(x,y)%mod);}if(k==3) {x=qread(),y=qread();modify(1,1,n,id[x],id[x]+size[x]-1,y%mod);}if(k==4) {x=qread();printf("%d\n",csum(1,1,n,id[x],id[x]+size[x]-1)%mod);}}return 0; }4. 洛谷P2590 [ZJOI2008]樹的統計
題目描述
一棵樹上有n個節點，編號分別為1到n，每個節點都有一個權值w。
我們將以下面的形式來要求你對這棵樹完成一些操作：
I. CHANGE u t : 把結點u的權值改為t
II. QMAX u v: 詢問從點u到點v的路徑上的節點的最大權值
III. QSUM u v: 詢問從點u到點v的路徑上的節點的權值和
注意：從點u到點v的路徑上的節點包括u和v本身
輸入輸出格式
輸入格式：
輸入文件的第一行為一個整數n，表示節點的個數。
接下來n – 1行，每行2個整數a和b，表示節點a和節點b之間有一條邊相連。
接下來一行n個整數，第i個整數wi表示節點i的權值。
接下來1行，為一個整數q，表示操作的總數。
接下來q行，每行一個操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式給出。
輸出格式：
對于每個“QMAX”或者“QSUM”的操作，每行輸出一個整數表示要求輸出的結果。
輸入輸出樣例
輸入樣例#1：
4 1 2 2 3 4 1 4 2 1 3 12 QMAX 3 4 QMAX 3 3 QMAX 3 2 QMAX 2 3 QSUM 3 4 QSUM 2 1 CHANGE 1 5 QMAX 3 4 CHANGE 3 6 QMAX 3 4 QMAX 2 4 QSUM 3 4輸出樣例#1：
4 1 2 2 10 6 5 6 5 16說明
對于100％的數據，保證1<=n<=30000，0<=q<=200000；中途操作中保證每個節點的權值w在-30000到30000之間。
思路：這道題目跟洛谷P3384那到題的區別在于那道題是區間修改，這道題是單點修改，這道題還多了查詢任意兩點最短路徑上的最大點權，實際上區間修改包括單點修改，所以這道題只多用樹剖維護一個路徑最大點權即可。
代碼：
#include<cstdio> #include<algorithm> #include<cctype> #define maxn 30007 #define ls rt<<1 #define rs rt<<1|1 using namespace std; int head[maxn],d[maxn],lazy[maxn<<2],sum[maxn<<2]; int maxx[maxn<<2],a[maxn],num,cnt,n,m,fa[maxn],id[maxn]; int w[maxn],top[maxn],size[maxn],son[maxn]; char s[8]; struct node {int v,nxt; }e[maxn<<1]; inline void ct(int u, int v) {e[++num].v=v;e[num].nxt=head[u];head[u]=num; } inline void pushup(int rt) {sum[rt]=sum[ls]+sum[rs];maxx[rt]=max(maxx[ls],maxx[rs]); } void build(int rt, int l, int r) {if(l==r) {sum[rt]=a[l];maxx[rt]=a[l];return;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(rt); } void add(int rt, int l, int r, int L, int val) {if(l==r) {sum[rt]=maxx[rt]=val;return;}int mid=(l+r)>>1;if(L>mid) add(rs,mid+1,r,L,val);else add(ls,l,mid,L,val);pushup(rt); } int csum(int rt, int l, int r, int L, int R) {if(L>r||R<l) return 0;if(L<=l&&r<=R) return sum[rt];int mid=(l+r)>>1;return csum(ls,l,mid,L,R)+csum(rs,mid+1,r,L,R); } int cmax(int rt, int l, int r, int L, int R) {int ans=-1020040222;if(L>r||R<l) return 0;if(L<=l&&r<=R) return maxx[rt];int mid=(l+r)>>1;if(L<=mid) ans=max(ans,cmax(ls,l,mid,L,R));if(R>mid) ans=max(ans,cmax(rs,mid+1,r,L,R));return ans; } void dfs1(int u, int f) {size[u]=1;for(int i=head[u];i;i=e[i].nxt) {int v=e[i].v;if(v!=f) {d[v]=d[u]+1;fa[v]=u;dfs1(v,u);size[u]+=size[v];if(size[v]>size[son[u]]) son[u]=v; }} } void dfs2(int u, int t) {id[u]=++cnt;a[cnt]=w[u];top[u]=t;if(son[u]) dfs2(son[u],t);for(int i=head[u];i;i=e[i].nxt) {int v=e[i].v;if(v!=fa[u]&&v!=son[u]) dfs2(v,v);} } int calc1(int x, int y) {int maxx=-1020040222;int fx=top[x],fy=top[y];while(fx!=fy) {if(d[fx]<d[fy]) swap(x,y),swap(fx,fy);maxx=max(maxx,cmax(1,1,cnt,id[fx],id[x]));x=fa[fx],fx=top[x];}if(id[x]>id[y]) swap(x,y);maxx=max(maxx,cmax(1,1,cnt,id[x],id[y]));return maxx; } int calc2(int x, int y) {int ans=0;int fx=top[x],fy=top[y];while(fx!=fy) {if(d[fx]<d[fy]) swap(x,y),swap(fx,fy);ans+=csum(1,1,cnt,id[fx],id[x]);x=fa[fx],fx=top[x];}if(id[x]>id[y]) swap(x,y);ans+=csum(1,1,cnt,id[x],id[y]);return ans; } int main() {scanf("%d",&n);for(int i=1,u,v;i<n;++i) {scanf("%d%d",&u,&v);ct(u,v);ct(v,u);}for(int i=1;i<=n;++i) scanf("%d",&w[i]);d[1]=1,fa[1]=1;dfs1(1,0);dfs2(1,1);build(1,1,n);scanf("%d",&m);for(int i=1,x,y;i<=m;++i) {scanf("%s%d%d",s,&x,&y);if(s[1]=='H') add(1,1,n,id[x],y);if(s[1]=='M') printf("%d\n",calc1(x,y));if(s[1]=='S') printf("%d\n",calc2(x,y));}return 0; }5. 洛谷P3178 [HAOI2015]樹上操作
題目描述
有一棵點數為 N 的樹，以點 1 為根，且樹點有邊權。然后有 M 個操作，分為三種：
- 操作 1 ：把某個節點 x 的點權增加 a 。
- 操作 2 ：把某個節點 x 為根的子樹中所有點的點權都增加 a 。
- 操作 3 ：詢問某個節點 x 到根的路徑中所有點的點權和。
輸入輸出格式
輸入格式：
第一行包含兩個整數 N, M 。表示點數和操作數。
接下來一行 N 個整數，表示樹中節點的初始權值。
接下來 N-1 行每行兩個正整數 from, to ， 表示該樹中存在一條邊 (from, to) 。
再接下來 M 行，每行分別表示一次操作。其中第一個數表示該操作的種類（ 1-3 ） ，之后接這個操作的參數（ x 或者 x a ） 。
輸出格式：
對于每個詢問操作，輸出該詢問的答案。答案之間用換行隔開。
輸入輸出樣例
輸入樣例#1：
5 5 1 2 3 4 5 1 2 1 4 2 3 2 5 3 3 1 2 1 3 5 2 1 2 3 3輸出樣例#1：
6 9 13說明
對于 100% 的數據， N,M<=100000 ，且所有輸入數據的絕對值都不會超過 10^6 。
思路：這道題跟洛谷P3384的唯一區別在于這里是單點修改，上面說過，區間修改包括單點修改，所以，可是說是一點區別都沒有，就是打一遍加深一下對樹剖的印象。
代碼：
#include<cstdio> #include<algorithm> #include<cctype> #define maxn 100007 #define ll long long #define ls rt<<1 #define rs rt<<1|1 using namespace std; int head[maxn],d[maxn],a[maxn]; int num,cnt,n,m,fa[maxn],id[maxn]; int w[maxn],top[maxn],size[maxn],son[maxn]; ll lazy[maxn<<2],sum[maxn<<2],y; inline ll qread() {char c=getchar();ll num=0,f=1;for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) num=num*10+c-'0';return num*f; } struct node {int v,nxt; }e[maxn<<1]; inline void ct(int u, int v) {e[++num].v=v;e[num].nxt=head[u];head[u]=num; } inline void pushup(int rt) {sum[rt]=sum[ls]+sum[rs]; } void build(int rt, int l, int r) {if(l==r) {sum[rt]=a[l];return;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(rt); } inline void pushdown(int rt, int len) {if(lazy[rt]) {lazy[ls]+=lazy[rt];lazy[rs]+=lazy[rt];sum[ls]+=(len-(len>>1))*lazy[rt];sum[rs]+=(len>>1)*lazy[rt];lazy[rt]=0;} } void modify(int rt, int l, int r, int L, int R, ll val) {if(L>r||R<l) return;if(L<=l&&r<=R) {sum[rt]+=val*(r-l+1);lazy[rt]+=val;return;}int mid=(l+r)>>1;pushdown(rt,r-l+1);modify(ls,l,mid,L,R,val),modify(rs,mid+1,r,L,R,val);pushup(rt); } ll csum(int rt, int l, int r, int L, int R) {if(L>r||R<l) return 0;if(L<=l&&r<=R) return sum[rt];int mid=(l+r)>>1;pushdown(rt,r-l+1);return csum(ls,l,mid,L,R)+csum(rs,mid+1,r,L,R); } void dfs1(int u, int f) {size[u]=1;for(int i=head[u];i;i=e[i].nxt) {int v=e[i].v;if(v!=f) {d[v]=d[u]+1;fa[v]=u;dfs1(v,u);size[u]+=size[v];if(size[v]>size[son[u]]) son[u]=v;}} } void dfs2(int u, int t) {id[u]=++cnt;a[cnt]=w[u];top[u]=t;if(son[u]) dfs2(son[u],t);for(int i=head[u];i;i=e[i].nxt) {int v=e[i].v;if(v!=fa[u]&&v!=son[u]) dfs2(v,v);} } ll calc(int x, int y) {ll ans=0;int fx=top[x],fy=top[y];while(fx!=fy) {if(d[fx]<d[fy]) swap(x,y),swap(fx,fy);ans+=csum(1,1,cnt,id[fx],id[x]);x=fa[fx],fx=top[x];}if(id[x]>id[y]) swap(x,y);ans+=csum(1,1,cnt,id[x],id[y]);return ans; } int main() {n=qread(),m=qread();for(int i=1;i<=n;++i) w[i]=qread();for(int i=1,u,v;i<n;++i) {u=qread(),v=qread();ct(u,v);ct(v,u);}d[1]=1,fa[1]=1;dfs1(1,0);dfs2(1,1);build(1,1,n);for(int i=1,k,x;i<=m;++i) {k=qread();if(k==1) {x=qread(),y=qread();modify(1,1,n,id[x],id[x],y);}if(k==2) {x=qread(),y=qread();modify(1,1,n,id[x],id[x]+size[x]-1,y);}if(k==3) {x=qread();printf("%lld\n",calc(1,x));}}return 0; }6. 洛谷 P2014 選課
題目描述
在大學里每個學生，為了達到一定的學分，必須從很多課程里選擇一些課程來學習，在課程里有些課程必須在某些課程之前學習，如高等數學總是在其它課程之前學習。現在有N門功課，每門課有個學分，每門課有一門或沒有直接先修課（若課程a是課程b的先修課即只有學完了課程a，才能學習課程b）。一個學生要從這些課程里選擇M門課程學習，問他能獲得的最大學分是多少？
輸入輸出格式
輸入格式：
第一行有兩個整數N,M用空格隔開。(1<=N<=300,1<=M<=300)
接下來的N行,第I+1行包含兩個整數ki和si, ki表示第I門課的直接先修課，si表示第I門課的學分。若ki=0表示沒有直接先修課（1<=ki<=N, 1<=si<=20）。
輸出格式：
只有一行，選M門課程的最大得分。
輸入輸出樣例
輸入樣例#1：
7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2輸出樣例#1：
13思路：數據范圍也不是特別大，可以考慮樹型dp，首先，建圖就是按照題目所給的信息建有向邊，之后我們用f[i][j]表示以i為頂點，選了j門課程的最大得分，然后dfs時枚舉每條與一個點相連的邊，用這個結點去更新它的子節點為頂點時的初始值，然后遍歷完它所有的子節點之后，再回過頭來更新這個結點為頂點時的最大值。
代碼：
#include<cstdio> #include<algorithm> #define maxn 307 using namespace std; int n,m,head[maxn],f[maxn][maxn],w[maxn],num; struct node {int v,nxt; }e[maxn]; inline void ct(int u, int v) {e[++num].v=v;e[num].nxt=head[u];head[u]=num; } void dfs(int u, int k) {for(int i=head[u];i;i=e[i].nxt) {int v=e[i].v;for(int j=k+1;j<=m+1;++j) f[v][j]=f[u][j-1]+w[v];dfs(v,k+1);for(int j=k+1;j<=m+1;++j) f[u][j]=max(f[u][j],f[v][j]);} } int main() {scanf("%d%d",&n,&m);for(int i=1,u;i<=n;++i) {scanf("%d%d",&u,&w[i]);ct(u,i);}dfs(0,1);printf("%d\n",f[0][m+1]);return 0; }7. 洛谷P4092 [HEOI2016/TJOI2016]樹
題目描述
在2016年，佳媛姐姐剛剛學習了樹，非常開心。現在他想解決這樣一個問題：給定一顆有根樹（根為1），有以下兩種操作：
標記操作：對某個結點打上標記（在最開始，只有結點1有標記，其他結點均無標記，而且對于某個結點，可以打多次標記。）
詢問操作：詢問某個結點最近的一個打了標記的祖先（這個結點本身也算自己的祖先）
你能幫幫他嗎?
輸入輸出格式
輸入格式：
輸入第一行兩個正整數N和Q分別表示節點個數和操作次數
接下來N-1行，每行兩個正整數u,v(1≤u,v≤n)表示u到v有一條有向邊
接下來Q行，形如“opernum”oper為“C”時表示這是一個標記操作,oper為“Q”時表示這是一個詢問操作對于每次詢問操作。
輸出格式：
輸出一個正整數，表示結果
輸入輸出樣例
輸入樣例#1：
5 5 1 2 1 3 2 4 2 5 Q 2 C 2 Q 2 Q 5 Q 3輸出樣例#1：
1 2 2 1說明
30%的數據，1 ≤ N, Q ≤ 1000
70%的數據，1 ≤ N, Q ≤ 10000
100%的數據，1 ≤ N, Q ≤ 100000
思路：題意就是讓你設計一個數據結構，支持：
單點修改就不用說了吧，對于操作2，我們發現離某個結點最近的一個打了標記的祖先就是樹剖時第二遍dfs的id值大的那個祖先(前提是打過標記)，然后樹鏈剖分，用線段樹維護最大值。
代碼：
#include<cstdio> #include<algorithm> #define maxn 100007 #define ls rt<<1 #define rs rt<<1|1 using namespace std; int cnt,n,m,head[maxn],num,size[maxn],d[maxn]; int id[maxn],maxx[maxn<<2],son[maxn],fa[maxn]; int a[maxn],top[maxn]; char c[3]; struct node {int v,nxt; }e[maxn<<2]; inline void ct(int u, int v) {e[++num].v=v;e[num].nxt=head[u];head[u]=num; } void dfs1(int u, int f) {size[u]=1;for(int i=head[u];i;i=e[i].nxt) {int v=e[i].v;if(v!=f) {d[v]=d[u]+1;fa[v]=u;dfs1(v,u);size[u]+=size[v];if(size[v]>size[son[u]]) son[u]=v; }} } void dfs2(int u, int t) {id[u]=++cnt;top[u]=t;a[cnt]=u;if(son[u]) dfs2(son[u],t);for(int i=head[u];i;i=e[i].nxt) {int v=e[i].v;if(v!=fa[u]&&v!=son[u]) dfs2(v,v);} } void pushup(int rt) {maxx[rt]=max(maxx[ls],maxx[rs]); } void add(int rt, int l, int r, int val) {if(l==r) {maxx[rt]=val;return;}int mid=(l+r)>>1;if(val>mid) add(rs,mid+1,r,val);else add(ls,l,mid,val);pushup(rt); } int cmax(int rt, int l, int r, int L, int R) {if(L>r||R<l) return 0;if(L<=l&&r<=R) return maxx[rt];int ans=0;int mid=(l+r)>>1;if(L<=mid) ans=max(ans,cmax(ls,l,mid,L,R));if(R>mid) ans=max(ans,cmax(rs,mid+1,r,L,R));return ans; } int query(int x, int y) {int maxx=0;int fx=top[x],fy=top[y];while(fx!=fy) {if(d[fx]<d[fy]) swap(x,y),swap(fx,fy);maxx=max(maxx,cmax(1,1,cnt,id[fx],id[x]));x=fa[fx],fx=top[x];}if(id[x]>id[y]) swap(x,y);maxx=max(maxx,cmax(1,1,cnt,id[x],id[y]));return a[maxx]; } int main() {scanf("%d%d",&n,&m);for(int i=1,u,v;i<n;++i) {scanf("%d%d",&u,&v);ct(u,v);ct(v,u);}d[1]=1;dfs1(1,0);dfs2(1,1);add(1,1,n,id[1]);for(int i=1,x;i<=m;++i) {scanf("%s%d",c,&x);if(c[0]=='C') add(1,1,n,id[x]);else printf("%d\n",query(x,1));}return 0; }8. SP1716 GSS3
題意翻譯
n 個數，q 次操作
操作0 x y把\(A_x\) 修改為y
操作1 l r詢問區間[l, r][l,r] 的最大子段和
輸入輸出格式
輸入格式：
The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations in following form:
0 x y: modify Ax into y (|y|<=10000).
1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
輸出格式：
For each query, print an integer as the problem required.
輸入輸出樣例
輸入樣例#1：
4 1 2 3 4 4 1 1 3 0 3 -3 1 2 4 1 3 3輸出樣例#1：
6 4 -3思路：首先分析詢問的本質：求出區間最大子段和！很顯然我們可以使用線段樹維護序列，本題的難點主要在如何進行上傳操作，將子樹l和r的節點信息上傳到子樹rt時，對于rt維護的序列中，和最大的子段有兩種情況：
然后我們用結構體板線段樹來分情況維護一下最大字段和即可，結構體傳址快。
代碼：
#include<cstdio> #include<algorithm> #include<cctype> #define maxn 50007 #define ls rt<<1 #define rs rt<<1|1 using namespace std; inline int qread() {char c=getchar();int num=0,f=1;for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) num=num*10+c-'0';return num*f; } int n,m; struct Tree {int lmax,rmax,sum,maxx; }tree[maxn<<2]; inline void pushup(int rt) {tree[rt].lmax=max(tree[ls].lmax,tree[ls].sum+tree[rs].lmax);tree[rt].rmax=max(tree[rs].rmax,tree[rs].sum+tree[ls].rmax);tree[rt].maxx=max(tree[ls].rmax+tree[rs].lmax,max(tree[ls].maxx,tree[rs].maxx));tree[rt].sum=tree[ls].sum+tree[rs].sum; } void build(int rt, int l, int r) {if(l==r) {tree[rt].lmax=tree[rt].rmax=tree[rt].sum=tree[rt].maxx=qread();return;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(rt); } void add(int rt, int l, int r, int L, int val) {if(l==r) {tree[rt].lmax=tree[rt].rmax=tree[rt].sum=tree[rt].maxx=val;return;}int mid=(l+r)>>1;if(L<=mid) add(ls,l,mid,L,val);else add(rs,mid+1,r,L,val);pushup(rt); } Tree query(int rt, int l, int r, int L, int R) {if(L==l&&r==R) return tree[rt];int mid=(l+r)>>1;if(L>mid) return query(rs,mid+1,r,L,R);else if(R<=mid) return query(ls,l,mid,L,R);else {Tree a=query(ls,l,mid,L,mid),b=query(rs,mid+1,r,mid+1,R),c;c.lmax=max(a.lmax,a.sum+b.lmax);c.rmax=max(b.rmax,b.sum+a.rmax);c.sum=a.sum+b.sum;c.maxx=max(a.rmax+b.lmax,max(a.maxx,b.maxx));return c;} } int main() {n=qread();build(1,1,n);m=qread();for(int i=1,k,x,y;i<=m;++i) {k=qread(),x=qread(),y=qread();if(!k) add(1,1,n,x,y);else printf("%d\n",query(1,1,n,x,y).maxx);}return 0; }轉載于:https://www.cnblogs.com/grcyh/p/10187647.html
總結
以上是生活随笔為你收集整理的2018年12月2526日的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： shell基本运算符
- 下一篇： Linux常用命令: zip、unzip