NOIP模拟19/07/20

NOIP模拟19/07/20

​​WOJ4615 最大公约数​​

考虑答案 x 可以在多少个子集存在，我们可以先求出x的倍数的个数cnt

显然 2 ^ cnt - 1 就是所有子集的个数，但是我们同时算上了 2x, 3x ... 的答案，所以要减掉

注意指数要对 Mod-1 取模

#include#define N 100050using namespace std;typedef long long ll;const ll Mod = 1000000007;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f;}ll add(ll a, ll b, ll p){ return (a+b) % p;}ll dec(ll a, ll b, ll p){ return (a-b+p) % p;}ll mul(ll a, ll b, ll p){ return (a*b) % p;}ll power(ll a, ll b, ll p){ ll ans = 1; for(;b;b>>=1){ if(b&1) ans = mul(ans, a, p); a = mul(a, a, p); } return ans;}int n, a[N], cnt[N], mx;ll ans = 1, sum[N];int gcd(int a, int b){ return !b ? a : gcd(b, a % b);}int main(){ n = read(); for(int i=1; i<=n; i++) a[i] = read(), cnt[a[i]]++, mx = max(mx, a[i]); if(n <= 10){ for(int S = 0; S < (1<=2; i--){ int tmp = 0; for(int j=1; i*j <= mx; j++){ tmp += cnt[i * j]; if(j > 1) sum[i] = dec(sum[i], sum[i * j], Mod - 1); } sum[i] = add(sum[i], power(2, tmp, Mod-1) - 1, Mod - 1); ans = mul(ans, power(i, sum[i], Mod), Mod); } printf("%lld", ans); return 0;}

​​WOJ4616 切题​​

比较水的概率 DP , 因为一场比赛的总题数不超过 3，并且顺序没有影响，所以状态设为 i，j，k表示剩1/2/3道题的个数

然后观察空间，发现需要滚动数组一下

到这里一切正常，然后我就被卡常了，直接卡成 65

后来找原因，发现需要压一下 for 的上界

k 枚举到 cnt3，j 枚举到 cnt3 + cnt2 - k, 然后就过了！以后要学会卡常啊！

#include#define N 105#define M 505using namespace std;typedef long long ll;const int Mod = 17680321;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f;}inline int add(int a, int b){ return (a+b > Mod) ? a+b-Mod : a+b;}inline int mul(int a, int b){ return 1ll * a * b % Mod;}inline int power(int a, int b){ int ans = 1; for(;b;b>>=1){ if(b&1) ans = mul(ans, a); a = mul(a, a); } return ans;}int n, cnt1, cnt2, cnt3;int f[N][N][N], inv[M];int dp[2][M][M];int DP(int i, int j, int k){ if(i == 0 && j == 0 && k == 0) return 0; if(f[i][j][k]) return f[i][j][k]; int ans = 0; if(i) ans = add(ans, mul(DP(i-1, j, k), mul(i, inv[(i + j + k)]))); if(j) ans = add(ans, mul(DP(i+1, j-1, k), mul(j, inv[(i + j + k)]))); if(k) ans = add(ans, mul(DP(i, j+1, k-1), mul(k, inv[(i + j + k)]))); ans = add(ans, mul(n, inv[(i + j + k)])); return f[i][j][k] = ans;}int main(){ n = read(); inv[0] = inv[1] = 1; for(int i=2; i<=n; i++) inv[i] = power(i, Mod - 2); for(int i=1; i<=n; i++){ int x = read(); cnt1 += (x == 1); cnt2 += (x == 2); cnt3 += (x == 3); } if(n <= 100){ printf("%d", DP(cnt1, cnt2, cnt3)); return 0;} for(int k=0; k<=cnt3; k++){ int l = k & 1; memset(dp[l], 0, sizeof(dp[l])); for(int j=0; j<=cnt2+cnt3-k; j++){ for(int i=0; i<=n-j-k; i++){ if(i==0 && j==0 && k==0) continue; int ans = 0; if(i) ans = add(ans, mul(dp[l][i-1][j], mul(i, inv[(i + j + k)]))); if(j) ans = add(ans, mul(dp[l][i+1][j-1], mul(j, inv[(i + j + k)]))); if(k) ans = add(ans, mul(dp[l^1][i][j+1], mul(k, inv[(i + j + k)]))); ans = add(ans, mul(n, inv[(i + j + k)])); dp[l][i][j] = ans; } } } printf("%d", dp[cnt3&1][cnt1][cnt2]); return 0;}

​​WOJ4617 最短路​​

比较直观的做法就是每个点建一棵最短路树，两个点 LCA 到 根的距离就是一种答案

由于把每棵树存下来空间可能会爆炸，所以我们把询问离线，然后每棵树做一次

比较麻烦的是字典序，我们可以先求出最短路，然后把边按对面点的编号排序，按顺序深搜

如果dis[to] = dis[x] + w[i]，那么就在最短路树上加上这条边，因为它是字典序最小的

然后打上vis标记，这样后来的也更新不了它

看看复杂度，由于有负环，所以 spfa O(n*m), 然后做 n 次，O(n*m*n)

然后倍增 LCA, O(n * n * log), 然后查询 lca, O(q * n * log), 复杂度可以上天了

考虑先优化 spfa, 有一个玄学做法

就是建一个虚点 0，向每一个点连长度为0的边，然后跑最短路

dis[u] 要么为0，要么为负，然后 边权重新定义为 w[i] + dis[u] - dis[v]

可以证明一定为正. 考虑如何还原原来的最短路，发现中间的会抵消掉，然后多了一个dis[st]，少了一个 dis[v]

于是复杂度变成优美的 O(n*m + n^2 logn)

兴致勃勃写完过后发现还是被卡，因为 q = 6000，n = 2000，log 只能套在n上不能套在q上

于是只好 st 表，于是最后的复杂度O(n*m + n^2logn + n*q)

#include#define N 2050using namespace std;const int inf = 0x3fffffff;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f;}#define mp make_pairstruct Edge{ int u, to, w;};bool cmp(Edge a, Edge b){ return a.to < b.to;}vector v[N];int n, m, q;int dis[N], delta[N]; bool vis[N];struct Qu{ int u, v;} Q[N*4];void spfa(int st){ queue q; q.push(st); memset(delta, 63, sizeof(delta)); memset(vis, 0, sizeof(vis)); delta[st] = 0; while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0; for(int i = 0; i < v[x].size(); i++){ int t = v[x][i].to; if(delta[t] > delta[x] + v[x][i].w){ delta[t] = delta[x] + v[x][i].w; if(!vis[t]) vis[t] = true, q.push(t); } } } }void dijsktra(int st){ priority_queue >q; q.push(mp(0, st)); memset(dis, 63, sizeof(dis)); dis[st] = 0; memset(vis, 0, sizeof(vis)); while(!q.empty()){ int x = q-().second; q.pop(); if(vis[x]) continue; vis[x] = true; for(int i=0; i dis[x] + v[x][i].w + del){ dis[t] = dis[x] + v[x][i].w + del; q.push(mp(-dis[t], t)); } } } for(int i=1; i<=n; i++) dis[i] = dis[i] - delta[st] + delta[i];} int first[N], nxt[N], to[N], w[N], tot;void add(int x, int y, int z){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y, w[tot] = z;}int ans[N*4]; bool in[N];void Build(int x){ for(int i = 0; i < v[x].size(); i++){ int t = v[x][i].to; if(!in[t] && dis[t] == dis[x] + v[x][i].w){ add(x, t, v[x][i].w); in[t] = true; Build(t); } }}int st[N*2][16], dep[N], d[N], sign, pos[N], lg[N*2];int Min(int x, int y){ return dep[x] < dep[y] ? x : y; }void dfs(int u){ st[++sign][0] = u; pos[u] = sign; for(int i=first[u];i;i=nxt[i]){ int t = to[i]; dep[t] = dep[u] + 1; d[t] = d[u] + w[i]; dfs(t); st[++sign][0] = u; }}void Init(){ for(int j = 1; (1 << j) <= sign; j++) for(int i = 1; i + (1 << j) - 1 <= sign; i++) st[i][j] = Min(st[i][j-1], st[i+(1<<(j-1))][j-1]);}int lca(int u, int v){ int l = pos[u], r = pos[v]; if(l > r) swap(l, r); int x = lg[r - l + 1]; return Min(st[l][x], st[r-(1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。