CSP-S模拟33
今天是挂分场，总计挂分 132 tps。。。
T1：Divisors
大简单题。
这里粘一个结论，然后直接暴力做就行了。
结论
$ [1,1e5] 内 因子个数max = 128 (83160) $
$ [1,1e6] 内 因子个数max = 240 (720720) $
$ [1,1e7] 内 因子个数max = 448 (8648640) $
$ [1,1e8] 内 因子个数max = 768 (73513440) $
$ [1,1e18] 内 因子个数max = 1e5 $
然后直接做就可以了，有了上边的结论就不用担心时间复杂度有问题了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
using namespace std;
constexpr int N = 2e3 + 3;
constexpr int M = 1e5 + 7;
constexpr int INF = 1e18;
constexpr int mod = 1e9 + 7;
constexpr char me[] = "終末なにしてますか？忙しいですか？救ってもらっていいですか？";int n;
int m;
int cnt;
int top;
int sum;
int t[N];
int a[N];
int pri[M];
int tim[15];
int vec[15];bool st[M];vector<int> yz[N];unordered_map<int,int> mp;inline int read()
{int k = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();} while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + c - '0',c = getchar_unlocked();return k * f;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline void init(int up)
{for(int i = 2;i <= up;i ++){if(!st[i]) pri[++ cnt] = i;for(int j = 1;pri[j] * i <= up && j <= cnt;j ++){st[i * pri[j]] = 1;if(i % pri[j] == 0) break;}}
}inline void dfs(int x,int up,int res)
{if(res > n) return;if(x == up){mp[res] ++;return;}for(int i = 0,op = 1;i <= tim[x];i ++){dfs(x + 1,up,res * op);op *= vec[x];}
}inline void work(int x)
{top = 0;for(int i = 1;pri[i] * pri[i] <= x;i ++){if(x % pri[i] == 0){vec[++ top] = pri[i];tim[top] = 0;while(x % pri[i] == 0) x /= pri[i],tim[top] ++;}}if(x > 1) vec[++ top] = x,tim[top] = 1;dfs(1,top + 1,1);
}signed main()
{freopen("div.in","r",stdin);freopen("div.out","w",stdout);// freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();m = read();init(M - 7);for(int i = 1;i <= m;i ++){a[i] = read();work(a[i]);} for(auto op : mp){if(op.second){t[op.second] ++;sum ++;}}write(n - sum),ent;for(int i = 1;i <= m;i ++) write(t[i]),ent;Blue_Archive;
}
/*
10 3
4 6 70 : 5 8 9 10
1 : 3 4 6 7
2 : 2
3 : 1
*/
T2: Market
因为看错数据范围导致狂挂 60 tps，难蚌！
首先因为加了时间的限制，所以将超市按营业时间从小到大排序是一定的。
因为考虑到价值的和仅仅为 \(9e4\) 而体积是 \(1e9\) 级别的。（注意！这俩玩意而不是同阶的）
所以很容易想到改变传统背包 DP 的定义。
考虑求在一段时间内的价格为定值的最小体积。对于每次查询先二分其合法的时间，再二分最大的价格即可。
\(dp_{i,j}\) 表示在按时间排序后的第 \(i\) 个超市开门前，价值为 \(j\) 的最小体积。
点击查看代码
#include<bits/stdc++.h>
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
using namespace std;
constexpr int N = 3e2 + 3;
constexpr int M = 9e4 + 3;
constexpr int INF = 123456789;
constexpr int mod = 1e9 + 7;
constexpr char me[] = "終末なにしてますか？忙しいですか？救ってもらっていいですか？";int n;
int m;
int VV;
int ans;
int mn[N][M];
int dp[N][M];struct miku
{int c;int v;int t;
}a[N];inline int read()
{int k = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();} while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + c - '0',c = getchar_unlocked();return k * f;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline int find(int val)
{int l = 1,r = n,mid,res = 0;while(l <= r){mid = (l + r) >> 1;if(a[mid].t <= val) l = mid + 1,res = mid;else r = mid - 1;}return res;
}inline int find_val(int pos,int V)
{int l = 1,r = VV,mid,res = 0;while(l <= r){mid = (l + r) >> 1;if(dp[pos][mid] <= V) l = mid + 1,res = mid;else r = mid - 1;}return res;
}signed main()
{freopen("market.in","r",stdin);freopen("market.out","w",stdout);// freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();m = read();for(int i = 1;i <= n;i ++){a[i].c = read(); // ti jia[i].v = read(); // jia zhia[i].t = read(); // shi jianVV += a[i].v;} memset(dp,0x3f,sizeof(dp));sort(a + 1,a + n + 1,[](miku a,miku b){return a.t < b.t;});dp[0][0] = 0;for(int i = 1;i <= n;i ++){dp[i][0] = 0;for(int j = VV;j >= a[i].v;j --){dp[i][j] = min(dp[i - 1][j],dp[i - 1][j - a[i].v] + a[i].c);}for(int j = 0;j < a[i].v;j ++) dp[i][j] = min(dp[i][j],dp[i - 1][j]);}for(int i = 1;i <= n;i ++){for(int j = VV;j >= 0;j --){dp[i][j] = min(dp[i][j],dp[i][j + 1]);}}for(int i = 1,t,V,pos;i <= m;i ++){t = read();V = read();pos = find(t);write(find_val(pos,V));ent;}Blue_Archive;
}
T3:连通性
大困难题，场上因为打表抄错了，导致又挂了 35 tps。唉。
很容易可以将问题转化为：对于 \([n - m + 1,n]\) 区间中的点，不存在其相连的不属于该集合的点集的连通块有连边的情况。
首先考虑一下部分分。
对于 \(n == m\) 的情况，我们要考虑到实际上就是把 \([1,n]\) 分成若干个强联通块，答案就是贝尔数的第 \(n\) 项。（这个神秘贝尔数赛后才知道）
对于 \(m == 1\) 的情况，我们只需要考虑一个点。枚举其所有的连边情况，然后对于每种连边需要保证与其相连的连通块中的 \([1,n - m]\) 中的点是互相相连的。
然后我就不会了。。。
赛时考虑到这儿已经挺逼近正解了，只是实在想不到了。。。
然后对着题解狂贺。
考虑到一种 \(dp_{i,j}\)，为 $ n == i 并且 m == j$ 时的答案。
考虑枚举所有点的连通块来容斥一下。
然后分别考虑 \([1,i - j]\) 的点所处连通块与 \([i - j + 1,i]\) 的点所处的连通块。
然后疯狂推柿子。
首先对于只有后者，柿子还挺显然的:
\(dp_{i,j} = \sum_{k = 1}^m dp_{i - k,j - i} C(j - 1,k - 1)\)。（就是枚举连通块的大小，在取一下组合数）。
然而考虑加上前者就不好搞了。。。
首先定义一个数组 \(h\)。
定义 \(h_i = 2^{i(i - 1) / 2}\)。
然后在钦定一个数组 \(g\)。表示不连通的个数（容斥一下）（不太明白）
\(g_I = h_i - \sum_{j = 1}^{n - 1} g_j h_{i - j} C(i - 1,j - 1)\)。
之后就能推出来添加了 \([1,i - j]\) 后 \([i - j + 1,i]\) 的点所处连通块的贡献了。
然后就有完整柿子了
\(dp_{i,j} = \sum_{k = 1}^j \sum_{s = 1}^{i - j} dp_{i - k - s,j - k} h_k g_s C(j - 1,k - 1) C(i - j,s) (2^s - 1)^k\)
点击查看代码
#include<bits/stdc++.h>
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
using namespace std;
constexpr int N = 1e2 + 1;
constexpr int mod = 1e9 + 7;
constexpr char me[] = "終末なにしてますか？忙しいですか？救ってもらっていいですか？";int T;
int n;
int m;
int g[N];
int h[N];
int fac[N];
int inv[N];
int bel[N];
int dp[N][N];inline int read()
{int k = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();} while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + c - '0',c = getchar_unlocked();return k * f;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline int qpow(int a,int b)
{int res = 1;while(b){if(b & 1) res = (1ll * res * a) % mod;a = (1ll * a * a) % mod;b >>= 1;}return res;
}inline int C(int n,int m)
{if(n < m) return 0;return 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
}inline void init()
{bel[0] = fac[0] = g[0] = h[0] = inv[0] = 1;for(int i = 1;i <= 100;i ++){fac[i] = 1ll * fac[i - 1] * i % mod;inv[i] = qpow(fac[i],mod - 2);g[i] = h[i] = qpow(2,(i - 1) * i / 2);bel[i] = C(i - 1,0);for(int j = 1;j < i;j ++){g[i] = (g[i] - 1ll * g[j] * h[i - j] % mod * C(i - 1,j - 1) % mod + mod) % mod;bel[i] = (bel[i] + 1ll * C(i - 1,j) * bel[j] % mod) % mod;}}dp[0][0] = 1;for(int i = 1;i <= 100;i ++){dp[i][0] = h[i];dp[i][i] = bel[i];for(int j = 1;j < i;j ++){for(int k = 1;k <= j;k ++){dp[i][j] = (dp[i][j] + 1ll * dp[i - k][j - k] * C(j - 1,k - 1) % mod) % mod;for(int s = 1;s <= i - j;s ++){dp[i][j] = (dp[i][j] + 1ll * dp[i - k - s][j - k] * C(j - 1,k - 1) % mod * C(i - j,s) % mod * qpow(qpow(2,s) - 1,k) % mod * h[k] % mod * g[s] % mod) % mod;}}}}
}signed main()
{freopen("connect.in","r",stdin);freopen("connect.out","w",stdout);// freopen("data.in","r",stdin);freopen("data.out","w",stdout);T = read();init();while(T --) {n = read();m = read();write(dp[n][m]),ent;}Blue_Archive;
}
T4:树
严格简单于 T3，直接输出 0 有 37 tps...（什么不可以总司令？）
很容易可以将问题转化成求被覆盖的路径条数，与剩余的边的个数。
2 的这个和次幂即为答案。
考虑如何去维护。
发现对于每条路径来说，可以从 \(lca\) 将其分成两条，且需要保证两条路径的方向不同。
所以可以将每条边下放到深度大的节点，然后将每个节点分成两个点。
如将节点 \(i\) 分成 \(i\) 和 \(i + n\)。
对于一条边 \(u - v\)
如果连向下的边，就连接 \(u\) 和 \(v\) 与 \(u + n\) 和 \(v + n\)。
反之则连 \(u + n\) 和 \(v\) 与 \(u\) 和 \(v + n\)。
至于怎么用维护这个，直接上并查集就行。
但是如果我们直接暴力跳每条路径，时间复杂度是 \(O(n ^ 2 log_2{n})\) 的。
不能接受，所以我们再上一棵线段树去维护区间的连边情况，就可以做到 \(O(n log_2^2{n})\)。可以通过此题。
其实真的很好想，只是赛时都在凹 T3 去了，没打 T4 ，大悲。
点击查看代码
#include<bits/stdc++.h>
// #define int long long
// #define ld double
#define lid (id << 1)
#define rid (id << 1 | 1)
#define Blue_Archive return 0
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define add(x,y) to[++ tot] = y,nxt[tot] = h[x],h[x] = tot
using namespace std;
constexpr int N = 3e5 + 3;
constexpr int M = 5e6 + 7;
constexpr int mod = 1e9 + 7;
constexpr char me[] = "終末なにしてますか？忙しいですか？救ってもらっていいですか？";int T;
int n;
int m;
int cnt;
int tot;
int ans;
int tim;
int a[N];
int b[N];
int h[N];
int f[N << 1];
int fa[N];
int to[M];
int rk[N];
int nxt[M];
int son[N];
int siz[N];
int top[N];
int dfn[N];
int dep[N];bool tr[N << 2];inline int read()
{int k = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();} while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + c - '0',c = getchar_unlocked();return k * f;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline int qpow(int a,int b)
{int res = 1;while(b){if(b & 1) res = (1ll * res * a) % mod;a = (1ll * a * a) % mod;b >>= 1;}return res;
}inline int find(int x){return f[x] == x ? x : f[x] = find(f[x]);}inline void link(int u,int v)
{u = find(u),v = find(v);if(u != v) f[u] = v;
}inline void meg(int u,int v,int op)
{if(op){link(u,v + n);link(u + n,v);}else {link(u,v);link(u + n,v + n);}
}inline void dfs1(int x,int f)
{fa[x] = f;siz[x] = 1;dep[x] = dep[f] + 1;for(int i = h[x];i;i = nxt[i]){if(to[i] == f) continue;dfs1(to[i],x);siz[x] += siz[to[i]];if(siz[to[i]] > siz[son[x]]) son[x] = to[i];}
}inline void dfs2(int x,int tp)
{top[x] = tp;dfn[x] = ++ tim;rk[tim] = x;if(son[x]) dfs2(son[x],tp);for(int i = h[x];i;i = nxt[i]){if(to[i] == fa[x] || to[i] == son[x]) continue;dfs2(to[i],to[i]);}
}inline int LCA(int x,int y)
{while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]]) swap(x,y);x = fa[top[x]];}return dep[x] > dep[y] ? y : x;
}inline void change(int id,int l,int r,int L,int R)
{if(R < L) return;if(tr[id]) return;if(l == r){meg(fa[rk[l]],rk[l],0);tr[id] = 1;return;}int mid = (l + r) >> 1;if(L <= mid) change(lid,l,mid,L,R);if(R > mid) change(rid,mid + 1,r,L,R);tr[id] = tr[lid] & tr[rid];
}signed main()
{freopen("usmjer.in","r",stdin);freopen("usmjer.out","w",stdout);// freopen("data.in","r",stdin);freopen("data.out","w",stdout);n = read();m = read();for(int i = 1,x,y;i < n;i ++){x = read();y = read();add(x,y);add(y,x);f[i] = i;f[i + n] = i + n;}f[n] = n;f[n + n] = n + n;dfs1(1,0);dfs2(1,1);for(int i = 1,a,b,lca;i <= m;i ++){a = read();b = read();lca = LCA(a,b);if(a != lca && b != lca) meg(a,b,1);while(top[a] != top[lca]){change(1,1,n,dfn[top[a]] + (fa[top[a]] == lca),dfn[a]);a = fa[top[a]];}change(1,1,n,dfn[lca] + 2,dfn[a]);while(top[b] != top[lca]){change(1,1,n,dfn[top[b]] + (fa[top[b]] == lca),dfn[b]);b = fa[top[b]];}change(1,1,n,dfn[lca] + 2,dfn[b]);}for(int i = 2,p,q;i <= n;i ++){p = find(i);q = find(i + n);if(p == q){puts("0");Blue_Archive;}cnt += (i != p) + (i + n != q);}write(qpow(2,n - 1 - (cnt >> 1)));ent;Blue_Archive;
}