目录
写在前面
比赛地址：https://codeforces.com/gym/103427。
以下按个人向难度排序。
唉唉国庆 vp 三场唯一打的还像人的一场，最后手里还有两道题在写可惜都没出来呃呃。
被树上背包沙勒呃呃呃要苦学树上背包！
E 签到
我看都没看。
code by wenqizhi：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 2e5 + 5;
char s[N];
int main()
{
scanf("%s", s + 1);
int cnt = 0, len = strlen(s + 1);
for(int i = 1; i <= len - 4; ++i)
{
if(s[i] == 'e' && s[i + 1] == 'd' && s[i + 2] == 'g' && s[i + 3] == 'n' && s[i + 4] == 'b') ++cnt;
}
printf("%d\n", cnt);
return 0;
}
F 签到
直接大力枚举后缀暴力做然后大力排序即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1010;
//=============================================================
int n, cnt[21], map[21];
std::string s, ans[kN];
//=============================================================
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> n;
std::cin >> s; s = "$" + s;
for (int i = 1; i <= n; ++ i) {
int num = 0;
for (int j = 0; j < 20; ++ j) cnt[j] = 0, map[j] = 0;
for (int j = i; j; -- j) {
if (cnt[s[j] - 'a'] == 0) map[s[j] - 'a'] = num, ++ num;
++ cnt[s[j] - 'a'];
}
for (int j = 1; j <= i; ++ j) ans[i].push_back(map[s[j] - 'a'] + 'a');
}
std::sort(ans + 1, ans + n + 1);
std::cout << ans[n] << "\n";
return 0;
}
J BFS
dztlb 大爹觉得一眼秒了但是唐了 1h 吃了三发都没出我 tama 受不了了直接重新开了一遍这题发现纯傻逼题 10min 过了呃呃
显然仅需考虑起点和终点每位在环上的相对差值即可，即对于询问 \((s, t)\) 等价于询问 \((0, t - s)\)。
于是仅需预处理起点为 \(0\) 时，到所有状态的最短路长度，边权值均为 1，考虑 BFS 实现即可。
状态数量仅有 \(10^4\) 个，每个状态转移时仅需大力枚举操作的区间和方向即可，转移仅有 32 种，则总转移次数不超过 \(10^6\) 次。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const int kInf = 1e9 + 2077;
//=============================================================
int dis[kN];
bool vis[kN];
//=============================================================
int trans(int u_, int l_, int r_, int v_) {
int v = 0;
for (int i = 0, pw10 = 1; i < 4; ++ i, pw10 *= 10) {
if (i < l_ || r_ < i) {
v += (u_ % 10) * pw10;
} else {
v += (u_ % 10 + v_ + 10) % 10 * pw10;
}
u_ /= 10;
}
return v;
}
void init() {
for (int i = 0; i < 10000; ++ i) dis[i] = kInf;
std::queue<int> q;
q.push(0);
dis[0] = 0;
vis[0] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int l = 0; l < 4; ++ l) {
for (int r = l; r < 4; ++ r) {
int v = trans(u, l, r, 1);
if (!vis[v]) vis[v] = 1, dis[v] = dis[u] + 1, q.push(v);
v = trans(u, l, r, -1);
if (!vis[v]) vis[v] = 1, dis[v] = dis[u] + 1, q.push(v);
}
}
}
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
init();
int T; std::cin >> T;
while (T --) {
std::string a, b; std::cin >> a >> b;
int t = 0;
for (int i = 0; i < 4; ++ i) t = 10 * t + (b[i] - a[i] + 10) % 10;
// std::cout << t << "\n";
std::cout << dis[t] << "\n";
}
return 0;
}
B 带权并查集
wenqizhi 大爹秒了。
考虑将每个数看做一个点，发现给定的限制关系实际上构成了若干连通块，不同连通块内互不影响，仅需考虑每个连通块内如何构造即可。
一开始的想法是考虑类似 2-SAT 的拆位，但是发现并不需要。发现对于某个连通块内，只需要确定某一个数的取值，其他所有数的取值即可唯一确定，于是考虑带权并查集维护联通块内每个数到根节点的异或和即可，手玩下容易得到合并联通块时对权值的影响。
然后再枚举每个联通块，拆位统计贡献，根据带权并查集的信息，贪心确定该联通块的根节点这一位的取何值时，这一位贡献和最小即可。
code by wenqizhi：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 1e5 + 5;
int f[N], xo[N], n, m;
int find(int x)
{
if(x == f[x]) return x;
int fa = f[x];
f[x] = find(f[x]);
xo[x] ^= xo[fa];
return f[x];
}
vector<int> num[N];
int cnt[100];
int main()
{
n = read(), m = read();
for(int i = 1; i <= n; ++i) f[i] = i;
for(int i = 1; i <= m; ++i)
{
int u = read(), v = read(), w = read();
int fu = find(u), fv = find(v);
if(fv != fu)
{
xo[fv] ^= xo[v] ^ xo[u] ^ w, f[fv] = fu;
}else
{
if((xo[u] ^ xo[v]) != w)
{
printf("-1\n");
return 0;
}
}
}
for(int i = 1; i <= n; ++i)
{
find(i);
if(i != f[i]) num[f[i]].emplace_back(xo[i]);
}
ll ans = 0;
for(int t = 1; t <= n; ++t)
if(num[t].size())
{
ll tot = num[t].size();
for(int i = 0; i <= 29; ++i) cnt[i] = 0;
for(int i = 0; i < tot; ++i)
{
int x = num[t][i];
for(int j = 0; j <= 29; ++j)
if((1 << j) & x) ++cnt[j];
}
for(int i = 29; i >= 0; --i) ans += min((1ll << i) * cnt[i], (1ll << i) * (tot - cnt[i] + 1));
}
printf("%lld\n", ans);
return 0;
}
H 图论
dztlb 大爹看了眼秒了但是鉴于他太唐了不敢让他上机于是我写的。
这是什么？这是线图。容易发现线图的匹配就是原图的边匹配，当原图两条边有公共点时即可匹配，贡献即两条边权之和。手玩下发现当原图边的数量为偶数时，总能全部匹配完并取得全部贡献。
当原图边数量为奇数时，则最优方案一定是一定仅有一条边无法匹配。若存在仅有某条边无法匹配的方案，则删掉这条边后一定是得到一张边数为偶数的连通图，或是边数为偶数的两个联通块。则一条边不合法的情况仅为：
- 是割边；
- 该边连接的两个联通块内的边数均为奇数。
考虑边双缩点，求得割边并维护边双内边的数量。显然边双缩点后得到的是一棵树，树边均为割边，在这棵树上 dfs 考虑断边后子树内边的数量是否为奇数即可。
稍微有点难写呃呃。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kN = 5e5 + 10;
const int kM = 2e6 + 10;
//=============================================================
int n, m;
int edgenum = 1, head[kN], v[kM], w[kM], ne[kM];
int dfnnum, dfn[kN], low[kN];
bool bridge[kM];
int dccnum, indcc[kN], sz[kN];
std::vector<pr <int, int> > edge[kN];
LL ans, edgesum;
bool tag[kM];
//=============================================================
void addedge(int u_, int v_, int w_) {
v[++ edgenum] = v_;
w[edgenum] = w_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void tarjan(int u_, int from_) {
dfn[u_] = low[u_] = ++ dfnnum;
for (int i = head[u_]; i > 1; i = ne[i]) {
int v_ = v[i];
if (!dfn[v_]) {
tarjan(v_, i);
if (low[v_] > dfn[u_]) bridge[i] = bridge[i ^ 1] = 1;
low[u_] = std::min(low[u_], low[v_]);
} else if (i != (from_ ^ 1)) {
low[u_] = std::min(low[u_], dfn[v_]);
}
}
}
void dfs(int u_, int id_) {
indcc[u_] = id_;
for (int i = head[u_]; i > 1; i = ne[i]) {
int v_ = v[i];
if (indcc[v_] || bridge[i]) continue;
dfs(v_, id_);
}
}
void dfs1(int u_, int fa_) {
for (auto [v_, i]: edge[u_]) {
if (v_ == fa_) continue;
dfs1(v_, u_);
if (sz[v_] % 2 == 1 && (m - sz[v_] - 1) % 2 == 1) {
tag[i] = 1;
}
sz[u_] += sz[v_] + 1;
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> n >> m;
for (int i = 1; i <= m; ++ i) {
int u_, v_, w_; std::cin >> u_ >> v_ >> w_;
edgesum += w_;
addedge(u_, v_, w_), addedge(v_, u_, w_);
}
if (m % 2 == 0) {
std::cout << edgesum << "\n";
return 0;
}
for (int i = 1; i <= n; ++ i) if (!dfn[i]) tarjan(i, 0);
for (int i = 1; i <= n; ++ i) if (!indcc[i]) dfs(i, ++ dccnum);
for (int u_ = 1; u_ <= n; ++ u_) {
for (int i = head[u_]; i > 1; i = ne[i]) {
if (i % 2 == 1) continue;
int v_ = v[i];
if (indcc[u_] == indcc[v_]) {
++ sz[indcc[u_]];
continue;
}
edge[indcc[u_]].push_back(mp(indcc[v_], i));
edge[indcc[v_]].push_back(mp(indcc[u_], i));
}
}
dfs1(1, 0);
for (int i = 2; i <= 2 * m; i += 2) {
if (!tag[i]) ans = std::max(ans, edgesum - w[i]);
}
std::cout << ans << "\n";
return 0;
}
I 数学
wenqizhi 大爹真是大爹啊我草，大力解方程过了。
code by wenqizhi：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int read()
{
int x = 0; bool f = false; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const double eps = 1e-10;
struct node
{
double A, B;
node(){ A = 0, B = 0; }
node friend operator + (node a, node b)
{
node c;
c.A = a.A + b.A;
c.B = a.B + b.B;
return c;
}
node friend operator - (node a, node b)
{
node c;
c.A = a.A - b.A;
c.B = a.B - b.B;
return c;
}
node friend operator * (node a, node b)
{
node c;
c.A = a.A * b.A - a.B * b.B;
c.B = a.A * b.B + a.B * b.A;
return c;
}
node friend operator / (node a, node b)
{
node c, d;
d.A = b.A, d.B = -b.B;
double x = b.A * b.A + b.B * b.B;
d.A /= x, d.B /= x;
return a * d;
}
}z1, z2, z3, z0, w1, w2, w3, w0, X, Y, K, ans, I;
bool check(node a)
{
double x = sqrt(a.A * a.A + a.B * a.B );
if(fabs(x) < eps) return false;
return true;
}
void solve()
{
I.A = 1, I.B = 0;
scanf(" %lf %lf %lf %lf", &z1.A , &z1.B , &w1.A , &w1.B );
scanf(" %lf %lf %lf %lf", &z2.A , &z2.B , &w2.A , &w2.B );
scanf(" %lf %lf %lf %lf", &z3.A , &z3.B , &w3.A , &w3.B );
scanf(" %lf %lf", &z0.A , &z0.B );
if(check(((z2 - z1) * (w3 * z3 - w1 * z1) - (z3 - z1) * (w2 * z2 - w1 * z1))) && check(z3 - z1))
{
// printf("DDD\n");
X = ((z3 - z1) * (w2 - w1) - (z2 - z1) * (w3 - w1)) / ((z2 - z1) * (w3 * z3 - w1 * z1) - (z3 - z1) * (w2 * z2 - w1 * z1));
Y = ((w3 * z3 - w1 * z1) * X + w3 - w1) / (z3 - z1);
K = w1 * z1 * X + w1 - z1 * Y;
ans = (Y * z0 + K) / (X * z0 + I);
printf("%.10lf %.10lf\n", ans.A , ans.B );
return ;
}
if(check(((z3 - z1) * (w2 - w1) - (z2 - z1) * (w3 - w1))) && check(z3 - z1))
{
// printf("CCC\n");
X = ((z2 - z1) * (w3 * z3 - w1 * z1) - (z3 - z1) * (w2 * z2 - w1 * z1)) / ((z3 - z1) * (w2 - w1) - (z2 - z1) * (w3 - w1));
Y = (w3 * z3 - w1 * z1 + (w3 - w1) * X) / (z3 - z1);
K = w1 * z1 + w1 * X - z1 * Y;
ans = (Y * z0 + K) / (z0 + X);
printf("%.10lf %.10lf\n", ans.A , ans.B );
return ;
}
if(check(((w2 - w1) * (w3 * z3 - w1 * z1) - (w3 - w1) * (w2 * z2 - w1 * z1))) && check(w2 - w1))
{
// printf("AAA\n");
X = ((w2 - w1) * (z3 - z1) - (w3 - w1) * (z2 - z1)) / ((w2 - w1) * (w3 * z3 - w1 * z1) - (w3 - w1) * (w2 * z2 - w1 * z1));
Y = ((z2 - z1) - (w2 * z2 - w1 * z1) * X) / (w2 - w1);
K = w1 * z1 * X + w1 * Y - z1;
ans = (z0 + K) / (X * z0 + Y);
printf("%.10lf %.10lf\n", ans.A , ans.B );
return ;
}
if(check(((z1 * z3 * w1 - z1 * z3 * w3) * (z1 * w2 - z2 * w1) - (z1 * z2 * w1 - z1 * z2 * w2) * (z1 * w3 - z3 * w1))) && check((z1 * z2 * w3 - z1 * z3 * w1)) && check(z1))
{
// printf("BBB\n");
X = ((z1 * z2 * w1 - z1 * z2 * w2) * (z3 - z1) - (z1 * z3 * w1 - z1 * z3 * w3) * (z2 - z1)) / ((z1 * z3 * w1 - z1 * z3 * w3) * (z1 * w2 - z2 * w1) - (z1 * z2 * w1 - z1 * z2 * w2) * (z1 * w3 - z3 * w1));
Y = (z3 * w1 * X - z1 * w3 * X + z1 - z3) / (z1 * z2 * w3 - z1 * z3 * w1);
K = (w1 * z1 * Y + w1 * X - I) / (z1);
ans = (K * z0 + I) / (Y * z0 + X);
printf("%.10lf %.10lf\n", ans.A , ans.B );
return ;
}
}
int main()
{
int T = read();
while(T--) solve();
return 0;
}
L 树形DP，容斥
赛时想到树形DP但是状态假了呃呃。
M 字符串，离线，单调性
草这题做过询问区间任意的版本而且打算出到新生赛上，于是直接拿过来秒了。
题解也搬一下：
一个显然的性质是子串 \(s[l:r]\) 中字典序最大的子串的右端点一定是 \(r\)。
考虑将所有询问 \((l, r)\) 离线，按右端点 \(r\) 升序排序后顺序枚举右端点 \(r\)，则此时所有询问的答案一定以 \(r\) 结尾。在此过程中维护以 \(r\) 结尾的所有子串 \(s[1:r] \sim s[r:r]\) 的字典序大小关系并回答询问。
发现对于某个确定的右端点 \(r\)，当询问左端点 \(l\) 增加时，作为答案的子串 \(s[p:r]\) 的左端点一定是单调不降的，字典序一定是单调不增的。则考虑在枚举 \(r\) 的同时，对有贡献的左端点，维护一个按照答案的左端点 \(p\) 递增，字典序递减的序列，回答询问时二分即得到答案。
对于两个子串 \(s[p_1: r], s[p_2: r](p_1 < p_2)\)，若有 \(s[p_1: r]<s[p_2: r]\) 则当 \(r\) 增加时恒有 \(s[p_1: r']<s[p_2: r']\) 成立，又 \([p_2, r]\in [p_1, r]\) 则 \(s[p_1: r']\) 对之后的任何询问均无贡献，可以将其删去。
更一般地，记 \(\operatorname{lcp}(s_1, s_2)\) 表示两个字符串 \(s_1, s_2\) 的最长公共前缀的长度，对于两个原字符串的后缀 \(s[p_1, n], s[p_2, n](p_1 < p_2)\)，记 \(\operatorname{lcp} = \operatorname{lcp}(s[p_1:n], s[p_2:n])\)：
- 若 \(s_{p_1 + \operatorname{lcp}}>s_{p_2 + \operatorname{lcp}}\)，则恒有 \(s[p_1:r] > s[p_2:r]\)。
- 若 \(s_{p_1 + \operatorname{lcp}}<s_{p_2 + \operatorname{lcp}}\)，则当 \(r<p_2 + \operatorname{lcp}\) 时有 \(s[p_1:r] > s[p_2:r]\)；当 \(r\ge p_2 + \operatorname{lcp}\) 时有 \(s[p_1:r] < s[p_2:r]\)。则在枚举到 \(r=p_2 + \operatorname{lcp}\) 后 \(s[p_1:r]\) 对之后的任何询问都无贡献，可以将其删去。
- 对于上述情况，我们称左端点 \(p_2\) 支配了左端点 \(p_1\)。发现支配关系实际上构成了一个 DAG 的结构，当左端点 \(p_1\) 被删除时，显然被 \(p_1\) 支配的所有左端点之后也不会有贡献，应当递归地把它们全部删除。
考虑在上述过程中，额外维护此时没有被支配的左端点序列，用来辅助有贡献的左端点的维护。显然该序列也是有上述按照答案的左端点 \(p\) 递增，字典序递减的单调性的。为了方便删除均使用 set 实现即可。
在枚举右端点时维护 \(\operatorname{D}_r\) 表示枚举到 \(r\) 时应删除哪些左端点，\(\operatorname{G}_p\) 表示左端点 \(p\) 直接支配哪些左端点。每次右端点 \(r\) 增加时，不断比较序列尾部元素 \(p_1\) 与当前入栈元素 \(r\) 的 \(s_{p_1 + \operatorname{lcp}}, s_{r+ \operatorname{lcp}}\)，若有 \(s_{p_1 + l}< s_{r + l}\) 说明 \(p_1\) 被 \(i\) 支配而应当将 \(p_1\) 弹出并更新 \(\operatorname{D}_{r+\operatorname{lcp}}\) 与 \(\operatorname{G}_{r}\)；若有 \(s_{p_1 + l}> s_{r + l}\) 由单调性可知此时序列内任何左端点均不会被 \(r\) 支配，可以结束枚举。
然后根据此时的 \(\operatorname{D}_r\) 与 \(\operatorname{G}\) 递归删除无贡献的左端点，再枚举询问二分即可。
那么如何求两个串的 \(\operatorname{lcp}\)？同样考虑二分两个子串长度相同的前缀的长度并哈希检查，即可在 \(O(\log n)\) 时间复杂度内解决。当然如果你是字符串大神直接掏出后缀数组+ST表就秒了哈哈。
考虑到大家应该都不会后缀数组所以本题 std 使用了哈希二分实现。总复杂度 \(O((|s|+m)\log^2 |s|)\) 级别。
参考：https://blog.csdn.net/C20181220_xiang_m_y/article/details/95516076
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 10;
const LL c1 = 29;
const LL c2 = 1145141;
const LL p1 = 1e9 + 7;
const LL p2 = 998244353;
//=============================================================
int n;
LL pw1[kN], pw2[kN], h1[kN], h2[kN];
std::string s;
std::vector<int> st, del[kN], g[kN];
std::set<int> suf;
//=============================================================
LL hash1(int l_, int r_) {
return (h1[r_] - h1[l_ - 1] * pw1[r_ - l_ + 1] % p1 + p1) % p1;
}
LL hash2(int l_, int r_) {
return (h2[r_] - h2[l_ - 1] * pw2[r_ - l_ + 1] % p2 + p2) % p2;
}
bool equal(int l1_, int r1_, int l2_, int r2_) {
return hash1(l1_, r1_) == hash1(l2_, r2_) &&
hash2(l1_, r1_) == hash2(l2_, r2_);
}
int lcp(int i_, int j_) {
int ret = 0;
for (int l = 1, r = std::min(n - i_, n - j_) + 1; l <= r; ) {
int mid = (l + r) >> 1;
if (equal(i_, i_ + mid - 1, j_, j_ + mid - 1)) {
ret = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ret;
}
void dfs(int u_) {
if (suf.find(u_) == suf.end()) return ;
suf.erase(u_);
for (auto v_: g[u_]) dfs(v_);
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> s; n = s.length(); s = "$" + s;
pw1[0] = pw2[0] = 1;
for (int i = 1; i <= n; ++ i) {
pw1[i] = c1 * pw1[i - 1] % p1;
pw2[i] = c2 * pw2[i - 1] % p2;
h1[i] = (c1 * h1[i - 1] + s[i]) % p1;
h2[i] = (c2 * h2[i - 1] + s[i]) % p2;
}
for (int i = 1; i <= n; ++ i) {
while (!st.empty()) {
int j = st.back(), len = lcp(i, j);
if (s[j + len] > s[i + len]) break;
del[i + len].push_back(j);
g[i].push_back(j);
st.pop_back();
}
st.push_back(i), suf.insert(i);
for (auto j: del[i]) dfs(j);
int p = *suf.lower_bound(1);
std::cout << p << " " << i << '\n';
}
return 0;
}
G 贪心
写在最后
学到了什么：
- L：