网站排名英文,西安最新消息,网站手机app开发,室内设计工作室排名引
对老师布置的题目稍微记录一下吧 也算对树形 D P DP DP 的巩固
T1 Ostap and Tree
题目传送门 由于有 距离 k 距离k 距离k 的限制#xff0c;设计二维 d p dp dp
设计状态#xff1a; f i , j : i 的子树内#xff0c;离 i 最近的染色点与 i 距离为 j 且若 j 设计二维 d p dp dp
设计状态 f i , j : i 的子树内离 i 最近的染色点与 i 距离为 j 且若 j k , 那么 i 的子树满足题目限制的方案数 f_{i,j}:i的子树内 离i最近的染色点与i距离为j\\ 且若jk,那么i的子树满足题目限制的方案数 fi,j:i的子树内离i最近的染色点与i距离为j且若jk,那么i的子树满足题目限制的方案数
状态转移
考虑父节点 u u u 与 子节点 v v v 的合并 若枚举 i , j i,j i,j ,那么考虑 f u , i f_{u,i} fu,i 与 f v , j f_{v,j} fv,j 可以转移到哪里 我们有 1.当 i j ≤ k ∗ 2 ij\leq k*2 ij≤k∗2 时 \quad f u , min ( i , j ) ← f u , i ∗ f v , j f_{u,\min(i,j)} \gets f_{u,i} *f_{v,j} fu,min(i,j)←fu,i∗fv,j 2.当 i j k ∗ 2 ij k*2 ijk∗2 时 \quad f u , max ( i , j ) ← f u , i ∗ f v , j f_{u,\max(i,j)} \gets f_{u,i} *f_{v,j} fu,max(i,j)←fu,i∗fv,j 只能说都是状态设计的功劳
#include algorithm
#include iostream
#include vector
#include cmath
using namespace std;
typedef long long ll;
const int N2e27,K55 , INF1e9;
const ll mod1e97;
int n,k;
ll f[N][K],ans;
vectorint G[N];
void dfs(int u,int fa) {f[u][0]f[u][k1]1;for(int v:G[u]) {if(v fa) continue; dfs(v,u);vectorll tmp(k*25) ;for(int i0;ik1;i) for(int j0;jk1;j) {if(ij(k1))tmp[min(i,j1)](tmp[min(i,j1)]f[u][i]*f[v][j]%mod)%mod;else tmp[max(i,j1)](tmp[max(i,j1)]f[u][i]*f[v][j]%mod) %mod;}for(int i0;ik1;i) f[u][i]tmp[i];}
}
int main() {scanf(%d%d,n,k);for(int i1,u,v;in;i) {scanf(%d%d,u,v);G[u].push_back(v),G[v].push_back(u);}dfs(1,0);for(int i0;ik;i) ans(ansf[1][i])%mod;printf(%lld\n,ans);
}T2 实验比较
题目传送门
显然 根据 关系建边 缩点 若没有 ,那么这将是一道十分友好的题稍微运用一下组合数学即可状态也会十分简单 多设一维限制 等号即可注意判环的无解情况
#include cmath
#include cstdio
#include cstring
#include iostream
#include algorithm
using namespace std;
inline int read() {int res 0; bool bo 0; char c;while (((c getchar()) 0 || c 9) c ! -);if (c -) bo 1; else res c - 48;while ((c getchar()) 0 c 9)res (res 3) (res 1) (c - 48);return bo ? ~res 1 : res;
}
inline char get() {char c; while ((c getchar()) ! c ! ); return c;
}
const int N 135, M 265, ZZQ 1e9 7;
int n, m, X[N], Y[N], fa[N], ecnt, nxt[M], adj[N], go[M], in[N], cnt[N],
f[N][N], sze[N], C[N][N], g[N];
bool eq[N], its[N];
void init() {int i, j; for (i 0; i 120; i) C[i][0] 1;for (i 1; i 120; i) for (j 1; j i; j)C[i][j] (C[i - 1][j] C[i - 1][j - 1]) % ZZQ;
}
void add_edge(int u, int v) {nxt[ecnt] adj[u]; adj[u] ecnt; go[ecnt] v;nxt[ecnt] adj[v]; adj[v] ecnt; go[ecnt] u;
}
int cx(int x) {if (fa[x] ! x) fa[x] cx(fa[x]);return fa[x];
}
bool zm(int x, int y) {int ix cx(x), iy cx(y);if (ix ! iy) fa[iy] ix;else return 1;return 0;
}
void dfs(int u, int fu) {int i, j, k; sze[u] f[u][1] 1;for (int e adj[u], v; e; e nxt[e]) {if ((v go[e]) fu) continue; dfs(v, u);for (i 1; i n; i) g[i] 0;for (i 1; i sze[u] sze[v]; i) for (j 1; j sze[u]; j)for (k 1; k sze[v]; k) {int x k - i j; if (x 0) continue;(g[i] 1ll * f[u][j] * f[v][k] % ZZQ *C[i - 1][j - 1] % ZZQ * C[j - 1][x] % ZZQ) % ZZQ;}for (i 1; i sze[u] sze[v]; i) f[u][i] g[i];sze[u] sze[v]; }
}
int main() {int i; n read(); m read(); init();for (i 1; i n; i) fa[i] i;for (i 1; i m; i) X[i] read(),eq[i] get() , Y[i] read();for (i 1; i m; i) if (eq[i]) zm(X[i], Y[i]);for (i 1; i n; i) its[in[i] cx(i)] 1;for (i 1; i n; i) fa[i] i;for (i 1; i m; i)if (!eq[i]) {add_edge(in[X[i]], in[Y[i]]); cnt[in[Y[i]]];if (zm(in[X[i]], in[Y[i]])) return printf(0\n), 0;}for (i 1; i n; i) if (its[i] !cnt[i]) add_edge(n 1, i);int ans 0; dfs(n 1, 0); for (i 1; i sze[n 1]; i)ans (ans f[n 1][i]) % ZZQ; cout ans endl;return 0;
}T3 podjela
题目传送门 对题目中的限制第二维开不下… 观察到答案的数量级应该是与 n n n 同阶 严谨的证明一下就是 a n s ≤ n − 1 ans\le n-1 ans≤n−1 因为 n − 1 n-1 n−1 次后我们一定可以将每一条边遍历到合理规划方案即可满足条件 那么就有了状态将答案放进状态中最后统计合法的最值即可
设计状态 f i , j : i 的子树中操作 j 次后除 i 的节点都合法 i 最多能获得的钱 f_{i,j} :i的子树中操作j次后除i的节点都合法i最多能获得的钱 fi,j:i的子树中操作j次后除i的节点都合法i最多能获得的钱 注意可能会欠款也就是 f i , j 0 f_{i,j}0 fi,j0
状态转移
转移是个树上背包 f u , i j 1 ← f u , i f v , j ( v 的钱转移到 i 上 ) 若 v 不欠款即 f v , j ≥ 0 , 就有 f u , i j ← f u , i f_{u,ij1}\gets f_{u,i}f_{v,j}(v的钱转移到i上)\\ 若v不欠款即f_{v,j}\ge0,就有f_{u,ij}\gets f_{u,i} fu,ij1←fu,ifv,j(v的钱转移到i上)若v不欠款即fv,j≥0,就有fu,ij←fu,i a n s ans ans就是第一个 f 1 , i ≥ 0 f_{1,i}\ge0 f1,i≥0时取i即可
#include algorithm
#include iostream
#include vector
#include cstring
using namespace std;
typedef long long ll;
const int N2e37,INF1e9;
int n,X;
int v[N],f[N][N],sz[N],g[N];
vectorintG[N];
void dfs(int u,int fa) {for(int i0;in;i) f[u][i]-INF;f[u][0]X-v[u],sz[u]1;for(int v:G[u]) {if(vfa) continue;dfs(v,u); sz[u]sz[v];for(int i0;isz[u]1;i) g[i]-INF;for(int i0;isz[u]-sz[v];i) {for(int j0;jsz[v];j) {g[ij1]max(g[ij1],f[u][i]f[v][j]);if(f[v][j]0) g[ij]max(g[ij],f[u][i]);}}for(int i0;isz[u]1;i) f[u][i]g[i];}
}
int main(){scanf(%d%d,n,X);for(int i1;in;i) scanf(%d,v[i]);for(int i1,u,v;in;i) {scanf(%d%d,u,v);G[u].push_back(v),G[v].push_back(u);}dfs(1,0);for(int i0;in;i) if(f[1][i]0) return printf(%d\n,i),0;
}T4 赛道修建
题目传送门 二分答案 贪心 二分答案贪心 二分答案贪心 即可贪心时用好 s e t set set 即可 据说可以用 v e c t o r vector vector 维护不过又不卡 s e t set set 不用白不用 代码虚长
#include algorithm
#include iostream
#include set
using namespace std;
const int N5e47;
int n,m,head[N],tot,ans,up;
struct node{ int to,next,w; }e[N1];multisetint s[N];
multisetint::iterator it;inline int read(){register int x0,f1;char chgetchar();while(!isdigit(ch)){if(ch-)f-1;chgetchar();}while(isdigit(ch)){x(x3)(x1)ch-0;chgetchar();}return (f1)?x:-x;
}void Add(int x,int y,int w){e[tot](node) {y,head[x],w};head[x]tot;
}int Dfs(int x,int fa,int k){s[x].clear();for(int ihead[x],y,val;i;ie[i].next){ye[i].to; if(yfa) continue;valDfs(y,x,k)e[i].w;if(valk) ans;else s[x].insert(val);}int Max0;while(!s[x].empty()){if(s[x].size()1) return max(Max,*s[x].begin());its[x].lower_bound(k-*s[x].begin());if(its[x].begin()s[x].count(*it)1) it;if(its[x].end()){Maxmax(Max,*s[x].begin());s[x].erase(s[x].begin());}else {ans;s[x].erase(s[x].find(*it));s[x].erase(s[x].find(*s[x].begin()));}}return Max;
}int Check(int k){ans0;Dfs(1,0,k);return (ansm);
}int Dfs1(int x,int fa){int sum10,sum20;for(int ihead[x],y;i;ie[i].next){ye[i].to; if(yfa) continue;sum2max(sum2,Dfs1(y,x)e[i].w);if(sum1sum2) swap(sum1,sum2);//最大与次大}upmax(up,sum1sum2);return sum1;
}int main(){nread(),mread();for(int i1,x,y,w;in;i){xread(),yread(),wread();Add(x,y,w);Add(y,x,w);}Dfs1(1,0);int l1,rup,mid;while(lr){mid(lr1)1;if(Check(mid)) lmid;else rmid-1;}printf(%d\n,l);
}T5 Aerial Tramway
题目传送门
很有意思的一题直入主题 引用别人的话 我们首先发觉每个可以连的区间都是不相交的只有相邻和包含关系所以是 O ( n ) O(n) O(n) 个其实最多只有 n 2 \frac{n}{2} 2n 个。然后这段区间跟相邻的是没有关系的。跟这段区间有关的只有包含的区间。所以我们可以递归的考虑这个问题。 一段区间与其包含的区间之间建边
设计状态 f i , j , k : i 的子树分配了 j 个缆车子树内被覆盖最多的点被覆盖了 k 次 f_{i,j,k}:i的子树分配了j个缆车子树内被覆盖最多的点被覆盖了k次 fi,j,k:i的子树分配了j个缆车子树内被覆盖最多的点被覆盖了k次
状态转移
是一个经典的树上背包注意 前缀 max 前缀\max 前缀max 优化,单次求解为 O ( n 2 ) O(n^2) O(n2) 总的复杂度为 O ( T n 2 ) O(Tn^2) O(Tn2)
#include algorithm
#include iostream
using namespace std;
const int N2e27,INF1e9;
int n,m,k,ca,cb,ans;
int x[N],y[N],b[N],g[N],nxt[N],sz[N],f[N][N][10],t[N][10];
struct st {int l,r,w;} a[N];
inline void up(inta,int b){if(ab)ab;}
void dfs(int x){for(int a0;am;a) for(int b0;bk;b) f[x][a][b]-INF;f[x][0][0]0;for(int ig[x];i;inxt[i]){dfs(i);for(int amin(sz[x]sz[i],m);im;i--) for(int b0;bk;b) t[a][b]f[x][a][b];for(int amin(sz[x],m);~a;a--) for(int cmin(sz[i],m-a);~c;c--) {int t1-INF,t2-INF;for(int b0;bk;b) {up(t1,f[i][c][b]); up(t2,f[x][a][b]);up(t[ac][b],max(f[x][a][b]t1,f[i][c][b]t2));}}sz[x]sz[i];for(int amin(sz[x],m);am;a--) for(int b0;bk;b) f[x][a][b]t[a][b];}if(!x)return;sz[x];for(int amin(sz[x],m-1);~a;a--) for(int bk-1;~b;b--) up(f[x][a1][b1],f[x][a][b]::a[x].w);
}
int main(){int T;while(~scanf(%d%d%d,n,m,k)){k--;for(int i1;in;i) scanf(%d%d,x[i],y[i]);for(int i1;in;i) for(int ji1;jn;j) if(y[i]y[j]){bool flag1;for(int ki1;kj;k) if(y[k]y[i]) {flag0; break;}if(flag){if(i1j) b[cb]x[j]-x[i];else a[ca](st){i1,j-1,x[j]-x[i]};}}sort(b1,bcb1,greaterint());for(int i2;icb;i) b[i]b[i-1];for(int i1,j0;ica;i){for(int k1;kca;k)if(a[k].la[i].la[k].ra[i].r (!j||a[k].wa[j].w))jk;nxt[i]g[j],g[j]i;}dfs(0);ans-1;for(int im-cb;im;i) for(int j0;jk;j)up(ans,f[0][i][j]b[m-i]);printf(Case %d: %d\n,T,ans);for(int i0;ica;i) g[i]sz[i]0;cacb0;}
}T6 Mousetrap
题目传送门 选好根就是老鼠所在的位置 t t t 。 观察好性质老鼠一进入某个子树就一定会无路可走。 考虑完情况老鼠往根的情况二分答案 详细的题解 贴个链接别人的Blog 再贴个自己的代码
#include algorithm
#include iostream
#include vector
using namespace std;
const int N1e67,INF1e9;
int n,t,m,l,r,ans;
int sum[N],f[N],fa[N];
vectorint G[N];
void dfs(int u,int ff) {int MAX0,_MAX0,cntG[u].size()-1; fa[u]ff;if(u!t) sum[u]sum[ff]cnt-1(um);for(int v:G[u]) if(v!ff) {dfs(v,u); if(f[v]MAX) _MAXMAX,MAXf[v];else if(f[v]_MAX) _MAXf[v];}f[u]_MAXcnt;
}
bool check(int k) {int cnt1;for(int um,tuu;u!t;ufa[u],cnt) {int x0;for(int v:G[u]) if(v!fa[u] v!tu f[v]sum[u]k) {if(!cnt) return 0;x,cnt--;}k-x,tuu;}return k0;
}
int main(){scanf(%d%d%d,n,t,m); rn1;for(int i1,u,v;in;i) {scanf(%d%d,u,v);G[u].push_back(v),G[v].push_back(u);}dfs(t,0);f[t]0;// for(int i1;in;i) printf(%d: %d\n,i,f[i]); puts();// for(int i1;in;i) printf(%d: %d\n,i,sum[i]);puts();while (lr) {int midlr1;if(check(mid)) ansmid,rmid-1;else lmid1;}printf(%d\n,ans);
}结
其实还有三道题但我太懒了就不写了贴一题目链接 [PA2015] Rozstaw szyn [POI2017] Sabotaż [CEOI2017] Chase
