====== 2020.06.22-2020.06.28 周报 ======
===== 团队训练 =====
2020.06.24 [[https://vjudge.net/contest/379605|2017-2018 ACM-ICPC, NEERC, Northern Subregional Contest]] ''prob:8:8:14'' ''rnk:11/?''
[[20200624比赛记录]]
===== _wzx27 =====
==== 容斥原理 ====
[[https://ac.nowcoder.com/acm/problem/16513|牛客16513]]
给一个集合 $A$,问 $[1,N]$ 有多少个数满足 $A$ 中的元素都不是它的因数。
比较模板的一个题目,二进制枚举 $A$ 的子集,根据集合大小的奇偶性容斥。
#include
#define ll long long
#define pii_ pair
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<>L>>R>>n;
rep(i,0,n-1){
cin>>a[i];
}
ll ans = 0;
rep(i,0,((1<>j)&1){
cnt++;
if(now<=R/a[j]) now = now*a[j];
else flag=1;
}
}
ll tmp;
if(flag) tmp = R-L+1;
else tmp = R-L+1 - (R/now - (L-1)/now);
if(cnt&1) ans += tmp;
else ans -= tmp;
}
cout<
\\
[[https://www.luogu.com.cn/problem/P5628|P5628]]
给一颗树,每条边的边权为它分割出的两个子树大小的乘积。对去掉某个点以及和这个点距离不超过k的其他点之后,损失的最大边权。
任取根,边权可以一次 $\text{dfs}$ 求出每个点的子树大小,也就可以求出他的父亲边的边权。
然后考虑树形 $\text{dp}$ (树上容斥),$f[u][j]$ 表示去掉点 $u$ 以及和它距离不超过 $j$ 的其他点之后损失的边权。那么有 $f[u][j] = \sum _{v\in son(u)}f[v][j-1] - (deg[u]-1)\times f[u][j-2]$
#include
#define ll long long
#define pii_ pair
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "< g[maxn];
ll f[maxn][205];
void dfs(int u,int fa)
{
sz[u] = 1; father[u] = fa;
for(int v:g[u])if(v!=fa){
dfs(v,u);
sz[u] += sz[v];
f[u][0] += (ll)sz[v] * (n-sz[v]);
f[v][0] += (ll)sz[v] * (n-sz[v]);
}
}
int main()
{
fastio();
cin>>n>>k;
rep(i,1,n-1){
int u,v; cin>>u>>v;
g[u].pb(v),g[v].pb(u);
deg[u]++,deg[v]++;
}
dfs(1,0);
ll ans = 0;
rep(j,1,k){
rep(i,1,n){
if(j>1) f[i][j] = f[i][j-2];
for(int v:g[i]){
f[i][j] += f[v][j-1];
if(j>1) f[i][j] -= f[i][j-2];
}
}
}
rep(i,1,n){
ans = max(ans,f[i][k]);
}
cout<
\\
[[https://www.luogu.com.cn/problem/P1450|P1450]]
有四种币值的硬币 $c_i$,有 $t$ 组询问,每组有 $5$ 个整数 $d_i$ 和 $s$,要求有 $d_i$ 个 $c_i$ 的硬币的情况下,恰好组合出 $s$ 的方案数。
如果没有个数的限制就是完全背包,有个数的限制则考虑容斥,减掉一种硬币不满足的个数,加上两种硬币不满足的个数....
求解的时候先 $\text{dp}$ 求出在完全背包的情况下组合出 $i$ 的方案数 $f[i]$ ,然后用 $\text{dfs}$ 模拟容斥的过程。
#include
#define ll long long
#define pii_ pair
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<>a[i];
int t ;cin>>t;
f[0] = 1;
rep(i,1,4){
rep(j,1,100000) if(j>=a[i]) f[j]+=f[j-a[i]];
}
while(t--){
rep(i,1,4) cin>>b[i]; int s;cin>>s;
ans = 0;
dfs(1,0,s);
cout<
\\
===== Infinity37 =====
==== 专题 ====
==== 题目 ====
[[20200624比赛记录#b_boolean_satisfiability|B.Boolean Satisfiability]]
[[20200624比赛记录#c_consonant_fencity|C.Consonant Fencity]]
[[20200624比赛记录#i_intelligence_in_perpendicularia|I.Intelligence in Perpendicularia]]
==== 比赛 ====
[[Codeforces Round 652 (Div. 2) Infinity37比赛记录]]
[[Educational Codeforces Round 90 Infinity37比赛记录]]
===== Zars19 =====
\摸= =摸/
==== 比赛 ====
[[Codeforces Round 651 Div. 2 Zars19]] **DONE**
[[Codeforces Round 652 Div. 2 Zars19]] **DONE**
===== 本周推荐 =====
[[https://atcoder.jp/contests/abc173/tasks/abc173_f|abc173: F - Intervals on Tree]] 代码不到20行,运用森林的性质,简单而不失难想。 --- //[[1036473307@qq.com|Zars19]]//