首页 > 代码库 > Shoi2017试题泛做
Shoi2017试题泛做
一口气做完六个省的省选（误）
Day1
[Shoi2017]期末考试
枚举最大的天数，然后代价贪心地O(1)计算。
1 #include <cstdio> 2 #include <algorithm> 3 4 #define R register 5 typedef long long ll; 6 #define maxn 100010 7 #define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0) 8 #define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0) 9 #define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))10 int a[maxn], b[maxn];11 int main()12 {13 R ll A, B, C, sum = 0, suma = 0; scanf("%lld%lld%lld", &A, &B, &C);14 R int n, m, maxx = 0; scanf("%d%d", &n, &m);15 for (R int i = 1; i <= n; ++i) scanf("%d", &a[i]), suma += a[i];16 for (R int i = 1; i <= m; ++i) scanf("%d", &b[i]), sum += b[i];17 std::sort(a + 1, a + n + 1);18 std::sort(b + 1, b + m + 1);19 maxx = b[m];20 R int p = m + 1, pp = n + 1;21 R ll pre = sum, suf = 0, ans = 1e18;22 for (R int i = maxx; i; --i)23 {24 while (p && b[p - 1] >= i) --p, suf += b[p], pre -= b[p];25 while (pp && a[pp - 1] >= i) suma -= a[--pp];26 R ll need = suf - 1ll * i * (m - p + 1);27 if (A >= B)28 {29 R ll cost = (1ll * i * (pp - 1) - suma) * C + need * B;30 cost > 0 ? cmin(ans, cost) : 0;31 }32 else33 {34 R ll v = 1ll * i * (p - 1) - pre;35 // printf("v = %lld %lld %d\n", v, need, i);36 // printf("pp %d suma %lld\n", pp, suma);37 cmin(v, need);38 R ll cost = (1ll * i * (pp - 1) - suma) * C + v * A;39 need -= v;40 cost += need * B;41 cost > 0 ? cmin(ans, cost) : 0;42 // printf("%lld\n", ans);43 }44 }45 printf("%lld\n", ans);46 return 0;47 }
[Shoi2017]相逢是问候
恶心题。广义欧拉定理+线段树。
不懂什么是广义欧拉定理的同学（比如我）自行Baidu吧。大意和普通的欧拉定理是差不多的。
我们想象一下，指数第一次是模phi(p)，第二次就是模phi(phi(p))，如此迭代下去直到模数变成1，那么就和原先的数无关了，并且因为后面都是模1，到最后的时候每次操作相当于最上面的那个c拿去模1，结果还是c^c^c...的多少次方，所以它的值没有变。
一直迭代phi的这个操作我们联想到了 2749: [HAOI2012]外星人 ，可以证明这个操作次数是log级别的（详见那题题解）。
根据以上预备知识我们可以得到以下算法：
用线段树维护区间没有变成自环的点的位置，然后每次找到这个点暴力重新计算数值。
复杂度是每个点最多算log次*每次要算log次*快速幂的log，所以是3个log的。（很爆炸的复杂度）
1 #include <cstdio> 2 3 #define R register 4 #define maxn 50010 5 #define maxh 25 6 #define maxx 500000 7 typedef long long ll; 8 bool flag, fl[maxh][maxx + 10], vis[maxh][maxx + 10]; 9 int dp[maxh][maxx + 10]; 10 int ph[2333], phcnt, fc, p, c; 11 int counter; 12 inline int qpow(R int base, R int power, R int mh) 13 { 14 flag = 0; 15 R bool memo = power <= maxx && phcnt - mh < maxh; 16 if (memo && vis[phcnt - mh][power]) {flag = fl[phcnt - mh][power]; ++counter; return dp[phcnt - mh][power];} 17 R int mod = ph[mh], tp = power; 18 // fprintf(stderr, "base %d %d\n", mh, power); 19 R int ret = 1; ret >= mod ? flag = 1, ret %= mod : 0; 20 for (R ll t; power; power >>= 1, base = 1ll * base * base % mod) 21 power & 1 ? (t = 1ll * ret * base) >= mod ? flag = 1, ret = t % mod : ret = t : 0; 22 // printf("flag %d\n", flag); 23 memo ? vis[phcnt - mh][tp] = 1, fl[phcnt - mh][tp] = flag, dp[phcnt - mh][tp] = ret : 0; 24 return ret; 25 } 26 inline int phi(R int x) 27 { 28 R int t = x, ret = 1; 29 // printf("%d\n", x); 30 for (R int i = 2; 1ll * i * i <= x; ++i) 31 if (t % i == 0) 32 { 33 t /= i; ret *= i - 1; 34 while (t > 1 && t % i == 0) 35 t /= i, ret *= i; 36 } 37 t != 1 ? ret *= t - 1 : 0; 38 return ret; 39 } 40 ll sum[maxn << 2]; 41 bool tr[maxn << 2]; 42 int cov[maxn], a[maxn], ql, qr, qv; 43 inline void update(R int o) 44 { 45 sum[o] = (sum[o << 1] + sum[o << 1 | 1]) % p; 46 tr[o] = tr[o << 1] && tr[o << 1 | 1]; 47 } 48 void build(R int o, R int l, R int r) 49 { 50 if (l == r) 51 { 52 sum[o] = a[l]; 53 tr[o] = phcnt == 0; 54 return ; 55 } 56 R int mid = l + r >> 1; 57 build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r); 58 update(o); 59 } 60 int query(R int o, R int l, R int r) 61 { 62 if (ql <= l && r <= qr) return sum[o]; 63 R int mid = l + r >> 1, ret = 0; 64 if (ql <= mid) (ret += query(o << 1, l, mid)) %= p; 65 if (mid < qr) (ret += query(o << 1 | 1, mid + 1, r)) %= p; 66 return ret; 67 } 68 void modify(R int o, R int l, R int r) 69 { 70 if (l == r) 71 { 72 if (tr[o]) return ; 73 ++cov[l]; 74 a[l] >= ph[cov[l]] ? flag = 1 : flag = 0; 75 R int ff = a[l] % ph[cov[l]]; 76 // printf("apos %d flag %d\n", a[l], flag); 77 for (R int i = cov[l]; i; --i) ff = qpow(c, ff + (flag ? ph[i] : 0), i - 1); 78 79 // printf("l %d ff %d\n", l, ff); 80 tr[o] = cov[l] == phcnt; 81 sum[o] = ff; 82 return ; 83 } 84 R int mid = l + r >> 1; 85 if (ql <= l && r <= qr) 86 { 87 if (!tr[o << 1]) modify(o << 1, l, mid); 88 if (!tr[o << 1 | 1]) modify(o << 1 | 1, mid + 1, r); 89 } 90 else 91 { 92 if (ql <= mid) modify(o << 1, l, mid); 93 if (mid < qr) modify(o << 1 | 1, mid + 1, r); 94 } 95 update(o); 96 } 97 int main() 98 { 99 R int n, m; scanf("%d%d%d%d", &n, &m, &p, &c);100 ph[0] = p; for (; ph[phcnt] != 1;) ph[++phcnt] = phi(ph[phcnt - 1]);101 ph[++phcnt] = 1;102 // fprintf(stderr, "phcnt %d\n", phcnt);103 // for (R int i = phcnt - 1; i; --i) fc = qpow(c, fc + ph[i], ph[i - 1]);104 // printf("%d\n", fc);105 for (R int i = 1; i <= n; ++i) scanf("%d", &a[i]);106 build(1, 1, n);107 for (; m; --m)108 {109 R int opt, l, r; scanf("%d%d%d", &opt, &l, &r);110 if (opt == 0)111 {112 ql = l; qr = r;113 modify(1, 1, n);114 }115 else116 {117 ql = l; qr = r;118 printf("%d\n", query(1, 1, n));119 }120 }121 // fprintf(stderr, "%d\n", counter);122 return 0;123 }
[Shoi2017]组合数问题
循环矩阵快速幂，做法和 4818: [Sdoi2017]序列计数 有点像。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 5 #define R register 6 typedef long long ll; 7 int k, p; 8 typedef int Vector[60]; 9 Vector base, ans;10 void mul(R Vector A, R Vector B)11 {12 R Vector C; memset(C, 0, k << 2);13 for (R int i = 0; i < k; ++i)14 for (R int j = 0; j < k; ++j)15 C[(i + j) % k] = (C[(i + j) % k] + 1ll * A[i] * B[j]) % p;16 memcpy(A, C, k << 2);17 }18 int main()19 {20 R int n, r; scanf("%d%d%d%d", &n, &p, &k, &r);21 base[0] = 1; ++base[k - 1];22 ans[0] = 1;23 for (R ll power = 1ll * n * k; power; power >>= 1, mul(base, base))24 power & 1 ? mul(ans, base), 1 : 0;25 // for (R int i = 0; i < k; ++i) printf("%d ", ans[i]);26 printf("%d\n", ans[r]);27 return 0;28 }
Day2
[Shoi2017]摧毁“树状图”
恶心题*2。树形DP
这题本来写了一个换根的做法结果因为太乱太复杂就推掉重新写了。（论想清楚再写的重要性）
最后参考了 SD_le 做法的题解。这位神犇的状态设计有理有据令人信服，所以我就参考了他的DP状态设计，然后自己推了一遍转移。然而推完以后还是不能1A，对拍以后才发现自己漏掉了好几种情况。。。（我好菜啊.jpg）
1 #include <cstdio> 2 #include <cstring> 3 4 #define R register 5 #define maxn 500010 6 struct Edge { 7 Edge *next; 8 int to; 9 } *last[maxn], e[maxn << 1], *ecnt = e; 10 inline void link(R int a, R int b) 11 { 12 *++ecnt = (Edge) {last[a], b}; last[a] = ecnt; 13 *++ecnt = (Edge) {last[b], a}; last[b] = ecnt; 14 } 15 int f1[maxn], f2[maxn], f3[maxn], f4[maxn], g1[maxn], g2[maxn], ans; 16 #define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0) 17 void dfs(R int x, R int fa) 18 { 19 R int tf1, tf2, tf3, tf4, tg1, tg2, deg = 0, mx = 0; 20 R bool debug = x == 1; 21 for (R Edge *iter = last[x]; iter; iter = iter -> next) 22 if (iter -> to != fa) 23 { 24 dfs(iter -> to, x); ++deg; 25 tf1 = f1[x]; tf2 = f2[x]; tf3 = f3[x]; tf4 = f4[x]; tg1 = g1[x]; tg2 = g2[x]; 26 27 cmax(tg1, f2[iter -> to]); 28 cmax(tg1, g1[iter -> to] - 1); 29 30 cmax(tg2, g1[x] + g1[iter -> to] - 1); 31 cmax(tg2, g1[x] + f2[iter -> to]); 32 cmax(tg2, f4[iter -> to]); 33 cmax(tg2, g2[iter -> to] - 1); 34 35 36 cmax(tf1, f1[iter -> to] - 1); 37 38 cmax(tf2, f1[x] + f1[iter -> to] - 1); 39 40 cmax(tf3, f1[x] + f2[iter -> to] - 1);// && debug ? printf("t1 %d %d\n", iter -> to, tf3) : 0; 41 cmax(tf3, f1[x] + g1[iter -> to] - 1);// && debug ? printf("t2 %d %d\n", iter -> to, tf3) : 0; 42 cmax(tf3, f2[x] + f1[iter -> to] - 1);// && debug ? printf("t3 %d %d\n", iter -> to, tf3) : 0; 43 cmax(tf3, mx + f1[iter -> to] - 2);// && debug ? printf("t4 %d %d %d\n", iter -> to, tf3) : 0; 44 cmax(tf3, f3[iter -> to] - 1);// && debug ? printf("t5 %d %d\n", iter -> to, tf3) : 0; 45 46 cmax(tf4, f1[x] + f3[iter -> to] - 1); 47 cmax(tf4, f3[x] + f1[iter -> to] - 1); 48 cmax(tf4, f2[x] + g1[iter -> to] - 1); 49 cmax(tf4, f2[x] + f2[iter -> to] - 1); 50 51 cmax(mx, f2[iter -> to]); 52 cmax(mx, g1[iter -> to]); 53 f1[x] = tf1; f2[x] = tf2; f3[x] = tf3; f4[x] = tf4; g1[x] = tg1; g2[x] = tg2; 54 // printf("f %d %d %d %d iter -> to %d %d\n", tf1, tf2, tf3, tf4, iter -> to, x); 55 } 56 ++g1[x]; ++g2[x]; 57 f1[x] += deg; f2[x] += deg; f3[x] += deg; f4[x] += deg; 58 /*cmax(g1[x], 1);*/ cmax(g2[x], g1[x]); 59 cmax(f2[x], f1[x]); cmax(f3[x], f2[x]); cmax(f4[x], f3[x]); 60 cmax(ans, g2[x]); cmax(ans, f4[x]); 61 // printf("ans %d x %d\n", ans, x); 62 // x == 2 ? printf("f %d %d %d %d\ng %d %d\n", f1[x], f2[x], f3[x], f4[x], g1[x], g2[x]) : 0; 63 } 64 int main() 65 { 66 R int T, type; scanf("%d%d", &T, &type); 67 for (; T; --T) 68 { 69 R int n; scanf("%d", &n); ans = 0; 70 for (R int i = 1; i <= type; ++i) scanf("%*d%*d"); 71 for (R int i = 1; i < n; ++i) 72 { 73 R int a, b; scanf("%d%d", &a, &b); link(a, b); 74 } 75 if (n == 1) {puts("0"); continue;} 76 dfs(1, 0); 77 printf("%d\n", ans); 78 79 memset(last, 0, (n + 1) << 2); ecnt = e; 80 memset(f1, 0, (n + 1) << 2); 81 memset(f2, 0, (n + 1) << 2); 82 memset(f3, 0, (n + 1) << 2); 83 memset(f4, 0, (n + 1) << 2); 84 memset(g1, 0, (n + 1) << 2); 85 memset(g2, 0, (n + 1) << 2); 86 } 87 return 0; 88 } 89 /* 90 1 0 91 15 92 1 2 93 2 3 94 1 4 95 2 5 96 1 6 97 3 7 98 4 8 99 3 9100 4 10101 6 11102 5 12103 4 13104 6 14105 5 15106 9107 108 1 0109 10110 1 2111 2 3112 1 4113 3 5114 3 6115 2 7116 1 8117 7 9118 9 10119 6120 121 1 0122 10123 1 2124 1 3125 2 4126 1 5127 3 6128 3 7129 5 8130 5 9131 4 10132 */
[Shoi2017]分手是祝愿
高斯消元有95分。
先把倍数关系通过一次高斯消元转化为单个灯是否要改变。
计c[i]表示还剩下i个1时的期望步数。根据题意，对于i<=k,有c[i] = i。然后这个转移有环，所以得高斯消元。
推出来每一行只有3个变量，所以消元是线性的。因为n和模数很接近，而消元的时候又有+1，然后系数很容易就+到0了，然后就boom（爆炸熊.jpg）。
既然出题人卡了高斯消元那么我们就来考虑推推式子。（因为没有用markdown所以式子略丑请原谅。。。）
考虑我们之前推出来的递推式：c[i] = (i/n) * c[i-1] + ((n - i) / n) * c[i + 1] + 1
然后对于i=n的时候，有c[n] = c[n - 1] + 1 (1)
对于i=n-1时，有c[n-1] = 1 + ((n - 1) / n) * c[n - 2] + (1 / n) * c[n] (2)
把(1)式代入(2)式：c[n - 1] = 1 + ((n - 1) / n) * c[n - 2] + 1 / n + 1 / n * c[n - 1]
移项：((n - 1) / n) * c[n - 1] = ((n - 1) / n) * c[n - 2] + (n + 1) / n
除过去：c[n - 1] = c[n - 2] + (n + 1) / (n - 1)
只剩两项啦~于是我们猜想c[i]这个序列是一个一阶递推式，并且上一项的系数是1（这个可以用数学归纳法证）。
于是我们就只要知道递推的常数项即可。我们来强行分析一波：
设第i项的系数为x[i]，而且我们已知了x[n] = 1。递推式可以写成c[i] = c[i - 1] + x[i]
我们从一开始的式子入手：c[i] = (i / n) * c[i - 1] + ((n - i) / n) * c[i + 1] + 1
代入：c[i] = (i / n) * c[i - 1] + ((n - i) / n) * (c[i] + x[i + 1]) + 1
两边乘个n然后再移项：i * c[i] = i * c[i - 1] + (n - i) * x[i + 1] + n
除个i：c[i] = c[i - 1] + ((n - i) * x[i + 1] + n) / i
这样的话连上面系数等于1的顺便也给证了。。。
所以求得x[i] = ((n - i) * x[i + 1] + n) / i。
然后递推一下就能求出c每一项的值来啦。
附代码：（95分的高斯消元在注释里面）
1 #include <cstdio> 2 #define R register 3 #define maxn 100010 4 const int mod = 1e5 + 3; 5 int a[maxn], b[maxn], c[maxn][3], f[maxn], x[maxn], inv[maxn]; 6 inline int qpow(R int base, R int power) 7 { 8 R int ret = 1; 9 for (; power; power >>= 1, base = 1ll * base * base % mod)10 power & 1 ? ret = 1ll * ret * base % mod : 0;11 return ret;12 }13 int main()14 {15 R int n, k, fact = 1; scanf("%d%d", &n, &k);16 for (R int i = 1; i <= n; ++i) scanf("%d", &a[i]);17 inv[1] = 1;18 for (R int i = 2; i <= n; ++i)19 {20 fact = 1ll * fact * i % mod, inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;21 // printf("%d %d\n", inv[i], qpow(i, mod - 2));22 }23 R int tmp = k, kk = 0;24 for (R int i = n; i; --i)25 {26 b[i] = a[i];27 for (R int j = i << 1; j <= n; j += i) b[i] ^= b[j];28 kk += b[i];29 }30 if (kk <= k) return !printf("%d\n", 1ll * kk * fact % mod);31 /* c[k][0] = 1; c[k][1] = 0; c[k][2] = k;32 for (R int i = k + 1; i <= n; ++i)33 {34 R int tmp = 1ll * qpow(c[i - 1][0], mod - 2) * i % mod * qpow(n, mod - 2) % mod;35 c[i][0] = (1 + 1ll * c[i - 1][1] * tmp) % mod;36 c[i][1] = 1ll * (mod + i - n) * qpow(n, mod - 2) % mod;37 c[i][2] = (1 + 1ll * c[i - 1][2] * tmp) % mod;38 }39 for (R int i = n; i > k; --i)40 {41 f[i] = 1ll * (c[i][2] - 1ll * f[i + 1] * c[i][1] % mod + mod) * qpow(c[i][0], mod - 2) % mod;42 }43 printf("%d\n", 1ll * f[kk] * fact % mod);*/44 x[n] = 1;45 R int ans = k;46 for (R int i = n - 1; i > k; --i)47 {48 x[i] = (1ll * x[i + 1] * (n - i) % mod * inv[n] % mod + 1) * n % mod * inv[i] % mod;49 }50 for (R int i = k + 1; i <= kk; ++i) (ans += x[i]) %= mod;51 printf("%d\n", 1ll * ans * fact % mod);52 return 0;53 }
[Shoi2017]寿司餐厅
最大权闭合子图。最小割。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 #define R register 6 #define maxn 100010 7 #define inf 0x7fffffff 8 #define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b)) 9 struct Edge {10 Edge *next, *rev;11 int to, cap;12 } *last[maxn], *cur[maxn], e[maxn << 2], *ecnt = e;13 inline void link(R int a, R int b, R int w)14 {15 // printf("%d %d %d\n", a, b, w);16 *++ecnt = (Edge) {last[a], ecnt + 1, b, w}; last[a] = ecnt;17 *++ecnt = (Edge) {last[b], ecnt - 1, a, 0}; last[b] = ecnt;18 }19 int a[110], d[110][110], id1[1010], id2[1010], id[110][110];20 int ans, s, t, q[maxn], dep[maxn];21 inline bool bfs()22 {23 memset(dep, -1, (t + 1) << 2);24 dep[q[1] = t] = 0; R int head = 0, tail = 1;25 while (head < tail)26 {27 R int now = q[++head];28 for (R Edge *iter = last[now]; iter; iter = iter -> next)29 if (dep[iter -> to] == -1 && iter -> rev -> cap)30 dep[q[++tail] = iter -> to] = dep[now] + 1;31 }32 return dep[s] != -1;33 }34 int dfs(R int x, R int f)35 {36 if (x == t) return f;37 R int used = 0;38 for (R Edge* &iter = cur[x]; iter; iter = iter -> next)39 if (iter -> cap && dep[iter -> to] + 1 == dep[x])40 {41 R int v = dfs(iter -> to, dmin(f - used, iter -> cap));42 iter -> cap -= v;43 iter -> rev -> cap += v;44 used += v;45 if (used == f) return f;46 }47 return used;48 }49 inline void dinic()50 {51 while (bfs())52 {53 memcpy(cur, last, sizeof cur);54 ans += dfs(s, inf);55 }56 }57 int main()58 {59 R int n, m, sum = 0; scanf("%d%d", &n, &m);60 for (R int i = 1; i <= n; ++i) scanf("%d", &a[i]);61 for (R int i = 1; i <= n; ++i) for (R int j = i; j <= n; ++j) scanf("%d", &d[i][j]);62 R int tot = 0;63 for (R int i = 1; i <= n; ++i)64 {65 for (R int j = i; j <= n; ++j)66 id[i][j] = ++tot;67 link(id[i][i], id1[a[i]] ? id1[a[i]] : id1[a[i]] = ++tot, a[i]);68 m ? link(id[i][i], id2[a[i]] ? id2[a[i]] : id2[a[i]] = ++tot, inf), 1 : 0;69 }70 t = ++tot;71 for (R int i = 1; i <= n; ++i)72 {73 for (R int j = i; j <= n; ++j)74 {75 d[i][j] > 0 ? link(s, id[i][j], d[i][j]), sum += d[i][j] : (link(id[i][j], t, -d[i][j]), 0);76 i != j ? link(id[i][j], id[i + 1][j], inf), link(id[i][j], id[i][j - 1], inf), 1 : 0;77 }78 }79 for (R int i = 0; i <= 1000; ++i)80 {81 id1[i] ? link(id1[i], t, inf), 1 : 0;82 id2[i] ? link(id2[i], t, i * i), 1 : 0;83 }84 dinic();85 // printf("ans = %d %d\n", ans, t);86 printf("%d\n", sum - ans);87 return 0;88 }
Shoi2017试题泛做
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。