csp-s模拟19[木棍，环，传令，序列]
木棍
- 就是个分讨，注意先\(3, 4\)配就行
here
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; ++ x)
#define fp(x, y, z)for(Re x = y; x >= z; -- x)
#define delfr(x, y, z)for(Re x = y; x < z; ++ x)
#define delfp(x, y, z)for(Re x = y; x > z; -- x)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define sec second
#define fst first
using namespace std;
namespace kiritokazuto{
fuc(char, getc)() {
static char buf[1 << 18], *p1, *p2;
if(p1 == p2){p1 = buf, p2 = buf + fread(buf, 1, 1 << 18, stdin);if(p1 == p2)return EOF;}
return *p1 ++;
}
fuc(LL, read)() {
LL x = 0, f = 1; char c = getc();
while(!isdigit(c)){if(c == '-')f = -1;c = getc();}
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getc();
return x * f;
}
template <typename T> fuc(void, write) (T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);putchar(x % 10 | '0');
}
}
using namespace kiritokazuto;
const int maxn = 5e5 + 10, Inf = 2147483647, Mod = 1e9 + 7;
int t;
LL num2, num3, num4;
LL res, ans = 0;
/*
100 4 1
用二冲都没有3,4先拼优秀(20 vs 21)
100 2 1
虽然不知道为啥，那就3，4先冲把
嗷嗷嗷知道了，那样的话冲两个3是4，冲一个4是6，抵消了一个....
*/
fuc(void, work)();
signed main(){
t = read();
while(t --) {
num2 = read(), num3 = read(), num4 = read();
work();
}
}
fuc(void, work)(){
res = ans = 0;
if(num3 >= 2 && num4) {//3 * 2 = 6 + 4 = 10
res = min(num3 / 2, num4);
ans += res;
num3 -= res * 2;
num4 -= res;
}
if(num2 >= 2 && num3 >= 2) {//二用的少 2 * 2 = 4 + 3 * 3 = 6 = 10
res = min(num2 / 2, num3 / 2);
ans += res;
num2 -= res * 2;
num3 -= res * 2;
}
if(num2 && num4 >= 2) {//2 + 4 * 2 = 8 = 10
res = min(num2, num4 / 2);
ans += res;
num2 -= res;
num4 -= res * 2;
}
if(num2 >= 3 && num4) {//2 * 3 = 6 + 4 = 10
res = min(num2 / 3, num4);
ans += res;
num2 -= res * 3;
num4 -= res;
}
if(num2 >= 5)ans += num2 / 5;// 2 * 5 = 10
write(ans), ki;
}
环
-
先将 \(a_{i}\) 从小到大排序。(相当于重新编号，这个题没有什么捆绑关系)
容易想到一个朴素的\(dp\) \(dp[i][j][k]\) 表示考虑左侧的前 \(i\) 个点和右侧的
前 \(a_{i}\) 个点，右侧的点中有 \(j\) 个单点和 \(k\) 条链。转移时考虑是单点和单点、单点和链还是链和链相连即可。
发现需要记录两维 \(j、k\) 的原因在于单点和单点相连的方案数是 \(1\)，但是
单点和链的方案数是 \(2\)，链和链相连的方案数是 \(4\) 。那么不妨记录 \(dp[i][j +k]\)表示单点和链的总和是 \(j + k\)，所有方案数 $ \times 2^{k}$ 之和（也可以理解成把链看成有向的），就可以直接转移了。
复杂度 \(O(n^{2})\)。 -
人话一点就是，如果你是无向图，它方案的系数是不同的，所以我都改成有向，那么我的方案就都是\(2\)了，因为两个单点显然左链有或者右链左两种,点和链以及链和链都是两种,但是这样显然会算重，所以最后除个二就是(注意时候逆元)
-
还有就是我的\(dp\)是\(dp\)的方案，通过它来算答案，不是直接搞答案
-
我们考虑每次增量一个左边的点，然后考虑它连出去的两条边，最终达到的效果就是合并两条路径。再次强调定义$ dp[i][j] $表示考虑前 \(i\) 个左边的点，形成的有向链数量是 \(j\) 个的方案数。
-
首先考虑新加进来的右边的单点, 个数为\(a_{i} - a_{i - 1}\)个
- 意思就是从新来的点里选出\(k\)个和我原来的组成链，\(k\)枚举就行。
- 其次任取两条有向链合并：
- 因为我们选出了两个合并，所以链数少了一个(两个合一个)，方案数就是\({j + 1 \choose 2}\)也就是\(j * (j + 1) / 2\)又因为是有向边，所以是两种，乘以一个二把分母消了。
- 最后统计答案就们在第一步转移之后将 \(dp[i][1] - a[i]\) 计入答案因为除了来的新点无法构成环以外，都可以。
here
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; ++ x)
#define fp(x, y, z)for(Re x = y; x >= z; -- x)
#define delfr(x, y, z)for(Re x = y; x < z; ++ x)
#define delfp(x, y, z)for(Re x = y; x > z; -- x)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define re(x) return x
#define sec second
#define fst first
using namespace std;
namespace kiritokazuto{
fuc(char, getc)() {
static char buf[1 << 18], *p1, *p2;
if(p1 == p2){p1 = buf, p2 = buf + fread(buf, 1, 1 << 18, stdin);if(p1 == p2)return EOF;}
return *p1 ++;
}
fuc(LL, read)() {
LL x = 0, f = 1; char c = getc();
while(!isdigit(c)){if(c == '-')f = -1;c = getc();}
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getc();
return x * f;
}
template <typename T> fuc(void, write) (T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);putchar(x % 10 | '0');
}
}
using namespace kiritokazuto;
const int maxn = 5e3 + 10, Inf = 0x3f3f3f3f, Mod = 998244353;
#define int long long
int C[maxn][maxn];
int dp[maxn][maxn];
int a[maxn];
int n;
int ans;
signed main(){
n = read();
fr(i, 1, n)a[i] = read(), C[i][0] = 1;
sort(a + 1, a + n + 1);
C[0][0] = 1;
fr(i, 1, n){
fr(j, 1, i) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Mod;
}
}
// fr(i, 1, n)fr(j, 1, i)cout << C[i][j] << "\n";
dp[0][0] = 1;
fr(i, 1, n) {
int dis = a[i] - a[i - 1];
fr(j, 0, a[i]) {
fr(k, max(0ll, 1ll * j - dis), j) {
dp[i][j] = (dp[i][j] + dp[i - 1][k] * C[dis][j - k]) % Mod;
}
}
ans = ((ans + (dp[i][1] - a[i] + Mod) % Mod) % Mod) % Mod;
fr(j, 0, a[i]) {
dp[i][j] = (dp[i][j] + dp[i][j + 1] * j % Mod * (j + 1) % Mod) % Mod;
}
}
write(ans * ((Mod + 1) / 2) % Mod);
return 0;
}
传令
- 首先很显然的二分答案，考虑怎么\(check\),首先应该的就是从叶子向上贪心地去选，而不是从上到下贪心地去选，因为下边是更不容易被满足的。
- 考虑如何实现，我这里是暴力去跳\(k\)级祖先，然后从它开始\(dfs\)把\(mid\)以内的点都扫进去。。。然后就没了，贪心的话排个序就行。其实这样会有很多次重复扫的操作，所以可以优化，维护一个\(f[i]\)和\(g[i]\)，一个表示\(i\)的子树里未覆盖的点距离\(i\)的最远距离是多少，另一个表示\(i\)的子树里已经有的信使中距离\(i\)最近的距离是多少，如过\(f[i] + g[i] \le mid\)显然就不用扫了，直接继续跳就行。具体的可以看洛谷将军令，我这里就不挂了。
here
#include <bits/stdc++.h>
#define LL long long
#define Re register int
#define LD double
#define mes(x, y) memset(x, y, sizeof(x))
#define cpt(x, y) memcpy(x, y, sizeof(x))
#define fuc(x, y) inline x y
#define fr(x, y, z)for(Re x = y; x <= z; ++ x)
#define fp(x, y, z)for(Re x = y; x >= z; -- x)
#define delfr(x, y, z)for(Re x = y; x < z; ++ x)
#define delfp(x, y, z)for(Re x = y; x > z; -- x)
#define frein(x) freopen(#x ".in", "r", stdin)
#define freout(x) freopen(#x ".out", "w", stdout)
#define ki putchar('\n')
#define fk putchar(' ')
#define WMX aiaiaiai~~
#define mk(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define re(x) return x
#define sec second
#define fst first
using namespace std;
namespace kiritokazuto{
fuc(char, getc)() {
static char buf[1 << 18], *p1, *p2;
if(p1 == p2){p1 = buf, p2 = buf + fread(buf, 1, 1 << 18, stdin);if(p1 == p2)return EOF;}
return *p1 ++;
}
fuc(LL, read)() {
LL x = 0, f = 1; char c = getc();
while(!isdigit(c)){if(c == '-')f = -1;c = getc();}
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getc();
return x * f;
}
template <typename T> fuc(void, write) (T x){
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);putchar(x % 10 | '0');
}
}
using namespace kiritokazuto;
const int maxn = 2e5 + 1000, Inf = 0x3f3f3f3f, Mod = 5000007;
struct Node{int to, next;}wmx[maxn << 1];
int len = 0, head[maxn], lid, rid, Mdep, tmp, x, y;
fuc(void, Qian)(int from, int to){wmx[++len] = {to, head[from]};head[from] = len;}
int n, k;
int dep[maxn], fa[maxn], id[maxn];
int vis[maxn];
int l, r;
int ans;
fuc(bool, cmp)(int x, int y){return dep[x] > dep[y];}
fuc(void, dfs)(int x, int pre) {
dep[x] = dep[pre] + 1;
fa[x] = pre;
id[x] = x;
for(Re i = head[x]; i; i = wmx[i].next){
int to = wmx[i].to;
if(to == pre)continue;
dfs(to, x);
}
}
fuc(void, draw)(int x, int tag, int depth, int fa) {
if(depth > tag)return;
vis[x] = 1;
for(Re i = head[x]; i; i = wmx[i].next) {
int to = wmx[i].to;
if(to == fa)continue;
draw(to, tag, depth + 1, x);
}
}
fuc(bool, check)(int mid){
fr(i, 1, n)vis[i] = 0;
int cnt = 0;
fr(i, 1, n) {
if(!vis[id[i]]) {
int from = id[i], dis = mid;
cnt++;
if(cnt > k)return 0;
while(dis && fa[from])from = fa[from], dis--;
draw(from, mid, 0, 0);
}
}
return 1;
}
signed main(){
n = read(), k = read();
delfr(i, 1, n) {x = read(), y = read(), Qian(x, y), Qian(y, x);}
// cerr << "RE";
dfs(1, 0);
// cerr << "RE";
sort(id + 1, id + n + 1, cmp);
l = 1, r = dep[id[1]];
// cerr << "l = " << l << " r = " << r << "\n";
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) {
ans = mid;
r = mid - 1;
}else l = mid + 1;
}
write(ans);
}
序列
- 还在码