10.18
就不能有任何一场同时切掉t1和t2是吧,t1过就t2爆,t2过就t1爆,还有将差结果取并的情况 \(\ldots\)
t1
想假了。
若不翻转,则答案可分为两段,前一段为 1 ,后一段为 2 。
考虑至多翻转一次后答案可拆为四段(中间的第二段和第三段不一定连续,赛时假做法让其连续了),第一、三段均为 1 ,二、四段均为 2 。(将二、三翻转后即可满足条件)。
直接dp即可。
转移过程类似 CSP-S31 中 t3 的转移,都是记录对于每个段的最大值。
看代码
code
噔噔!
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int a[N], dp[4]; // 第i段的值(滚动后)signed main()
{freopen("sequence.in", "r", stdin);freopen("sequence.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n;for (int i = 1; i <= n; ++i)cin >> a[i];for (int i = 1; i <= n; ++i){if (a[i] == 1)++dp[0], ++dp[2];else++dp[1], ++dp[3];dp[1] = max(dp[1], dp[0]);dp[2] = max(dp[2], dp[1]);dp[3] = max(dp[3], dp[2]);}cout << dp[3] << "\n";return 0;
}
t2
签到题。
思路简单,判无解后贪心即可,正确性显然。
上线段树维护就行了。
(其实可以不用维护次小值的,赛时脑子里回荡着“吉司机”的声音,反正赛时写出什么东西都不稀奇是不是)
直接代码就行了,这题代码难度大于思维难度(虽然代码也不难就是了)。
code
锵锵🎉
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
const int inf = 1e9 + 7;
int n;
int a[N], cnt[N];
queue<int> q[N];
struct tree
{int l, r;int nowmin, sizmax, semn;int minid, maxid, seid;
} t[N << 2];
#define lid (id << 1)
#define rid (id << 1 | 1)inline void pushup(int id)
{if (t[lid].sizmax > t[rid].sizmax)t[id].sizmax = t[lid].sizmax, t[id].maxid = t[lid].maxid;elset[id].sizmax = t[rid].sizmax, t[id].maxid = t[rid].maxid;if (t[lid].nowmin < t[rid].nowmin){t[id].nowmin = t[lid].nowmin, t[id].minid = t[lid].minid;if (t[lid].semn < t[rid].nowmin)t[id].semn = t[lid].semn, t[id].seid = t[lid].seid;elset[id].semn = t[rid].nowmin, t[id].seid = t[rid].minid;}else{t[id].nowmin = t[rid].nowmin, t[id].minid = t[rid].minid;if (t[rid].semn < t[lid].nowmin)t[id].semn = t[rid].semn, t[id].seid = t[rid].seid;elset[id].semn = t[lid].nowmin, t[id].seid = t[lid].minid;}
}void build(int id, int l, int r)
{t[id].l = l, t[id].r = r;if (l == r){t[id].sizmax = q[l].size();t[id].nowmin = (t[id].sizmax ? q[l].front() : inf);t[id].minid = t[id].maxid = l;t[id].semn = inf;t[id].seid = 0;return;}int mid = (l + r) >> 1;build(lid, l, mid);build(rid, mid + 1, r);pushup(id);
}void update(int id, int pos, int sizmax, int nowmin)
{if (t[id].l == t[id].r && t[id].l == pos){t[id].nowmin = nowmin;t[id].sizmax = sizmax;return;}int mid = (t[id].l + t[id].r) >> 1;if (mid >= pos)update(lid, pos, sizmax, nowmin);elseupdate(rid, pos, sizmax, nowmin);pushup(id);
}signed main()
{freopen("food.in", "r", stdin);freopen("food.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n;for (int i = 1; i <= n; ++i){cin >> a[i];q[a[i]].push(i);cnt[a[i]]++;if (n & 1){if (cnt[a[i]] > n / 2 + 1){cout << -1;return 0;}}else{if (cnt[a[i]] > n / 2){cout << -1;return 0;}}}build(1, 1, n);int las = 0;for (int i = n; i; --i){int now;if (i & 1){if (t[1].sizmax == i / 2 + 1){now = t[1].maxid;cout << q[now].front() << ' ';q[now].pop();int siz = q[now].size();update(1, now, siz, siz ? q[now].front() : inf);}else{now = t[1].minid;if (now == las)now = t[1].seid;cout << q[now].front() << ' ';q[now].pop();int siz = q[now].size();update(1, now, siz, siz ? q[now].front() : inf);}}else{now = t[1].minid;if (now == las)now = t[1].seid;cout << q[now].front() << ' ';q[now].pop();int siz = q[now].size();update(1, now, siz, siz ? q[now].front() : inf);}las = now;}return 0;
}
t3
很好的题,成功提醒我该去看字符串了。
首先显然对于拼好串的贡献是可以拆解的,将其分为原串内的贡献和跨越串的贡献。
对于原串内的贡献,跑二分哈希或manacher即可。
考虑跨串贡献如何处理:
发现跨串有贡献当且仅当在原串内扩展达到边界,所以只考虑这部分即可。
我们先令回文中心在 t 中,在 s 中重复下列操作即可。
发现跨串扩展实质上就是匹配t与s的反串,所以我们将所有 s 翻转令其变正,此时变为前缀问题,将 s 插入 trie 树中进行匹配即可。
但此时时间复杂度是\(O(nm)\)的,不可接受,考虑优化。
发现对于每个串,其在 trie 上的可匹配长度是可以二分的(具体的,某一长度可被匹配到,则更短长度一定存在,反之毅然),我们二分找长度即可。
到这里思路已经清晰了,所以看代码吧。
(蒟蒻感觉代码不是很好写)
code
gugugaga
#include <bits/stdc++.h>
#define ull unsigned long long
#define int long long
using namespace std;
const int N = 2e6 + 10;
const int M = 1e5 + 10;
const ull p = 131;
unordered_map<ull, int> posid;
int n, m, ans;
string s[M], t[M], a[M];
ull hx1[N], hx2[N], P[N];inline ull get_hx1(int l, int r) { return hx1[r] - hx1[l - 1] * P[r - l + 1]; }
inline ull get_hx2(int l, int r) { return hx2[l] - hx2[r + 1] * P[r - l + 1]; }struct trie
{int ch[1 << 20][26];int val[N], tot; // trie 的根链前缀和inline void insert(const string &s){int u = 0;ull hx = 0; // 记录当前链的哈希for (int i = 0; i < (int)s.size(); ++i){hx = hx * p + s[i] - 'a' + 1;int &v = ch[u][s[i] - 'a'];if (!v)v = ++tot, posid[hx] = tot;++val[v];u = v;}}inline void Sum(int id, int sum) // 根链前缀和{val[id] += sum;for (int i = 0; i < 26; ++i)if (ch[id][i])Sum(ch[id][i], val[id]);}inline void clear(){for (int i = 0; i <= tot; ++i)memset(ch[i], 0, sizeof(ch[i])), val[i] = 0;tot = 0;}
} T;inline void clear()
{T.clear();posid.clear();
}inline void solve()
{clear();for (int i = 1; i <= n; ++i)T.insert(s[i]);T.Sum(0, 0);// cerr << "!\n";for (int i = 1; i <= m; ++i){int len = t[i].size();hx1[0] = hx2[len + 1] = 0;for (int j = 1; j <= len; ++j)hx1[j] = hx1[j - 1] * p + t[i][j - 1] - 'a' + 1;for (int j = len; j; --j)hx2[j] = hx2[j + 1] * p + t[i][j - 1] - 'a' + 1;// cerr << "i=" << i << "\n";for (int j = 1; j <= len; ++j){int l = 1, r = min(len - j + 1ll, j), pos = 1;while (l <= r){int mid = (l + r) >> 1;if (get_hx1(j - mid + 1, j) == get_hx2(j, j + mid - 1))l = mid + 1, pos = mid;elser = mid - 1;}// cerr << "j=" << j << " pos=" << pos << "\n";ans += n * pos;if (j - pos + 1 != 1)continue;int nowmid = j + pos;l = nowmid, r = len, pos = 0;while (l <= r){int mid = (l + r) >> 1;if (posid[get_hx1(nowmid, mid)])l = mid + 1, pos = posid[get_hx1(nowmid, mid)];elser = mid - 1;}ans += T.val[pos];// cerr << "j=" << j << " ans=" << ans << "\n";}}
}signed main()
{freopen("str.in", "r", stdin);freopen("str.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);int T;P[0] = 1;for (int i = 1; i < N; ++i)P[i] = P[i - 1] * p;cin >> T;while (T--){ans = 0;cin >> n >> m;// cerr << "n=" << n << " m=" << m << "\n";for (int i = 1; i <= n; ++i)cin >> s[i], reverse(s[i].begin(), s[i].end());for (int i = 1; i <= m; ++i)cin >> t[i];solve();// cerr << "ans=" << ans << "\n";swap(s, t); // 这里应reverse t 字符集,但没有把上面的 s 反回来,不reverse t ,两操作叠加等效于reverse tswap(n, m);solve();cout << ans << "\n";}return 0;
}
t4
打表打了一辈子\(\ldots\)
首先发现前n个数大于后n个数的概率是一样的,因此找出前n个数和等于后n个数的概率即可(显然这个条件限制更强,更可做)。
我们令后n个数都乘 -1 ,再加 m ,则转化为求在 \([0,m]\) 内 \(2n\) 个数的和为 \(nm\) 的方案数。
若没有 \(\le m\) 的限制,则直接插板法组合数即可。(详见OI-wiki)
有限制则考虑容斥,斥掉不合法的部分。
设这 \(2n\) 个数组成的集合为 \(A\) 。
则答案:
其中的每一步都较好理解,除了第四行到第五行的转化(蒟蒻认为较难),所以着重讲那一步转化。
其中注意是 \(i(m+1)\) ,只有提出 \(m+1\) 才能使那 \(i\) 个数的范围变为 \([0,m]\) ,与另外 \(2n-i\) 个数的范围相同,做到合并。所以这个 \(1\) 是重要的且是易错的。
于是我们就得出了前n个数和等于后n个数的次数,除以总次数 \((m+1)^{2n}\) 即可得到概率,用 \(1\) 减去这个概率再除以 \(2\) 即可得到最终答案。
code
啦~啦啦啦啦~啦啦啦啦~啦~啦~~
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e6 + 4e3 + 10;
int T, n, m, mod;
int jc[N], inv[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;
}signed main()
{freopen("pr.in", "r", stdin);freopen("pr.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> mod >> T;jc[0] = 1, inv[0] = 1;for (int i = 1; i <= N - 10; ++i)jc[i] = jc[i - 1] * i % mod;inv[N - 10] = km(jc[N - 10], mod - 2);for (int i = N - 11; i; --i)inv[i] = inv[i + 1] * (i + 1) % mod;while (T--){cin >> n >> m;int ans = 0;for (int i = 0; i <= (n << 1); ++i){if (n * m - (m + 1) * i + (n << 1) - 1 < 0)break;ans += ((i & 1) ? -1 : 1) * C(n << 1, i) % mod * C(n * m - (m + 1) * i + (n << 1) - 1, (n << 1) - 1) % mod;ans = (ans + mod) % mod;}ans = ans * km(km(m + 1, n << 1), mod - 2) % mod;ans = (1 - ans + mod) % mod * km(2, mod - 2) % mod;cout << ans << "\n";}return 0;
}