2020-2021:teams:wangzai_milk:weekly8
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly8 [2020/07/04 14:02] wzx27 |
2020-2021:teams:wangzai_milk:weekly8 [2020/07/16 17:59] (当前版本) zars19 [比赛] |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| ==== 容斥原理 ==== | ==== 容斥原理 ==== | ||
| + | [[https://ac.nowcoder.com/acm/problem/16513|牛客16513]] | ||
| + | |||
| + | 给一个集合 $A$，问 $[1,N]$ 有多少个数满足 $A$ 中的元素都不是它的因数。 | ||
| + | |||
| + | 比较模板的一个题目，二进制枚举 $A$ 的子集，根据集合大小的奇偶性容斥。 | ||
| + | |||
| + | <hidden code> | ||
| + | <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #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<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 2e5+5; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | |||
| + | ll L,R; int n,a[25]; | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | fastio(); | ||
| + | cin>>L>>R>>n; | ||
| + | rep(i,0,n-1){ | ||
| + | cin>>a[i]; | ||
| + | } | ||
| + | ll ans = 0; | ||
| + | rep(i,0,((1<<n)-1)){ | ||
| + | ll now = 1; int cnt = 0,flag = 0; | ||
| + | rep(j,0,n-1){ | ||
| + | if((i>>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<<ans<<endl; | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | \\ | ||
| [[https://www.luogu.com.cn/problem/P5628|P5628]] | [[https://www.luogu.com.cn/problem/P5628|P5628]] | ||
| + | |||
| 给一颗树，每条边的边权为它分割出的两个子树大小的乘积。对去掉某个点以及和这个点距离不超过k的其他点之后，损失的最大边权。 | 给一颗树，每条边的边权为它分割出的两个子树大小的乘积。对去掉某个点以及和这个点距离不超过k的其他点之后，损失的最大边权。 | ||
| 行 17: | 行 74: | ||
| 然后考虑树形 $\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]$ | 然后考虑树形 $\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]$ | ||
| - | <hidden> | + | <hidden code> |
| <code cpp> | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| 行 77: | 行 134: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | \\ | ||
| [[https://www.luogu.com.cn/problem/P1450|P1450]] | [[https://www.luogu.com.cn/problem/P1450|P1450]] | ||
| + | |||
| 有四种币值的硬币 $c_i$，有 $t$ 组询问，每组有 $5$ 个整数 $d_i$ 和 $s$，要求有 $d_i$ 个 $c_i$ 的硬币的情况下，恰好组合出 $s$ 的方案数。 | 有四种币值的硬币 $c_i$，有 $t$ 组询问，每组有 $5$ 个整数 $d_i$ 和 $s$，要求有 $d_i$ 个 $c_i$ 的硬币的情况下，恰好组合出 $s$ 的方案数。 | ||
| 行 85: | 行 143: | ||
| 求解的时候先 $\text{dp}$ 求出在完全背包的情况下组合出 $i$ 的方案数 $f[i]$ ，然后用 $\text{dfs}$ 模拟容斥的过程。 | 求解的时候先 $\text{dp}$ 求出在完全背包的情况下组合出 $i$ 的方案数 $f[i]$ ，然后用 $\text{dfs}$ 模拟容斥的过程。 | ||
| - | <hidden> | + | <hidden code> |
| <code cpp> | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| 行 139: | 行 197: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | \\ | ||
| ===== Infinity37 ===== | ===== Infinity37 ===== | ||
| 行 163: | 行 221: | ||
| [[Codeforces Round 651 Div. 2 Zars19]] **DONE** | [[Codeforces Round 651 Div. 2 Zars19]] **DONE** | ||
| - | [[Codeforces Round 652 Div. 2 Zars19]] | + | [[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]]// | ||
2020-2021/teams/wangzai_milk/weekly8.1593842537.txt.gz · 最后更改: 2020/07/04 14:02 由 wzx27
