11.10
为什么noip模拟赛从5开始？
前面的不想写（懒）。
分了个div1/2
不是你题目难度也不对应啊?
div2版
t1
抽象状压。
赛后帮Gon_Tata hack 他的假状压，获得金牌辅助。
首先\(\ldots\)
然后\(\ldots\)
最后\(\ldots\)
懒。
直接看吧
code
。。。
#include <bits/stdc++.h>
using namespace std;
int n, m;
int dp[110][260];
char c[110][10];signed main()
{freopen("merging.in", "r", stdin);freopen("merging.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)cin >> c[i][j];memset(dp, 0x3f, sizeof(dp));dp[0][0] = 0;int ans = 0x3f3f3f3f;for (int i = 1, tmp, cnt, len; i <= n; ++i){tmp = len = 0;for (int j = 1; j <= m; ++j){if (c[i][j] == '1' && c[i][j - 1] != '1')tmp |= 1 << (j - 1);else if (c[i][j] == '1')++len;}int now;for (int k = 0; k < 1 << len; ++k){now = tmp;cnt = 0;for (int j = 1; j <= m; ++j){if (c[i][j] == '1' && !(1 & (tmp >> (j - 1))))now |= (1 & (k >> (cnt++))) << (j - 1);}cnt = __builtin_popcount(now);for (int o = 0; o < 1 << m; ++o){if (dp[i - 1][o] > 2000)continue;int res = cnt;int flag = 0;for (int p = 1; p <= m; ++p){if ((c[i][p] == '0' || 1 & now >> (p - 1)) && (c[i - 1][p] == '0' || 1 & o >> (p - 1))){res -= flag;if (1 & now >> (p - 1) & 1 & o >> (p - 1))flag = 1;}if (c[i][p] == '0' || c[i - 1][p] == '0' || (1 & now >> (p - 1)) ^ (1 & o >> (p - 1)))flag = 0;}res -= flag;dp[i][now] = min(dp[i][now], dp[i - 1][o] + res);ans = min(ans, dp[n][now]);}}}cout << ans << "\n";return 0;
}
t2
水。
一眼二分答案然后文件名写错？？？
应该上午太困了导致的（中间差点睡着）
代码没必要放
t3
巴巴博弈。
性质比较好想。
所以只看性质吧（
code
巴巴博弈
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 10;
int n, k, sum, cnt;
int a[N];inline void solve1()
{if (sum % 2 == 0){for (int i = 1; i <= n; ++i)if (a[i] >= 2)cout << i << ' ' << 2 << "\n";}else{for (int i = 1; i <= n; ++i){cout << i << ' ' << 1 << "\n";if (a[i] == 3)if ((cnt - 2) & 1)cout << i << ' ' << 3 << "\n";}}exit(0);
}inline void solve2()
{if (sum % 2 == 0){for (int i = 1; i <= n; ++i)if (a[i] >= 2)cout << i << ' ' << 2 << "\n";}else{for (int i = 1; i <= n; ++i){cout << i << ' ' << 1 << "\n";if (a[i] >= 3){if (a[i] % 2 == 0 && (cnt - 2) % 2 == 0)cout << i << ' ' << 3 << "\n";else if ((a[i] & 1) && (cnt - 1) % 2 == 0)cout << i << ' ' << 3 << "\n";}}}exit(0);
}signed main()
{freopen("nim.in", "r", stdin);freopen("nim.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k;bool f = 0;for (int i = 1; i <= n; ++i){cin >> a[i];a[i] > 3 ? f = 1 : 0;sum += a[i];cnt += a[i] >> 1;}if (sum % 2 == 0){if (cnt % 2 == 0){cout << 0;exit(0);}}cout << "1\n";if (!f)solve1();if (k <= 3)solve2();return 0;
}
t4
性质： border的boeder也是border
于是border构成树型关系，建出树即失配树（KMP求nxt以建树）。
树型dp即可。
code
border
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int mod = 998244353;
int n, k;
string s;
int jc[N], inv[N], nxt[N], dep[N], siz[N], dp[N];
vector<int> e[N];inline int km(int a, int b)
{int ans = 1;while (b){if (b & 1)(ans *= a) %= mod;(a *= a) %= mod;b >>= 1;}return ans;
}inline int C(int a, int b)
{if (a < b)return 0;return jc[a] * inv[b] % mod * inv[a - b] % mod;
}inline void get_nxt()
{nxt[1] = 0;for (int i = 2, j = 0; i <= n; ++i){while (j && s[i] != s[j + 1])j = nxt[j];if (s[i] == s[j + 1])++j;nxt[i] = j;e[j].emplace_back(i);}
}inline void dfs(int x, int f)
{siz[x] = 1, dep[x] = dep[f] + 1;for (auto y : e[x]){if (y == f)continue;dfs(y, x);dp[x] -= dep[x] * dep[x] % mod * C(siz[y], k) % mod;// (ans += mod) %= mod;// (ans -=) %= mod;siz[x] += siz[y];}(dp[x] += dep[x] * dep[x] % mod * C(siz[x], k)) %= mod;// cout << "x=" << x << " ans=" << ans << "\n";
}signed main()
{freopen("string.in", "r", stdin);freopen("string.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> k;cin >> s;n = s.size();s = " " + s;jc[0] = 1, inv[0] = 1;for (int i = 1; i <= n + 1; ++i)jc[i] = jc[i - 1] * i % mod;inv[n + 1] = km(jc[n + 1], mod - 2);for (int i = n; i; --i)inv[i] = inv[i + 1] * (i + 1) % mod;get_nxt();e[0].emplace_back(1);dfs(0, n + 2);int ans = 0;for (int i = 0; i <= n; ++i)(ans += dp[i]) %= mod;cout << ans;return 0;
}
/*
多个串的border相关问题:建fail树，树上做（若最长公共border长为lca）
*/
解释的很少，但其实每道题细讲都不少（除了t2）。
大抵是累了。
或许马上就要退役了？
不知道。