极限了，感觉还行
Rank
感觉 T3 不是一般人可做的，遂先来写赛记。
A. 图
签。
本来不是很一眼的，但看到给了这个
和这个
然后就很一眼了。用 long long 状压每个点所有操作下是否属于 S/T 集合的状态，那么发现对于一条边 \((i,j)\)，只有某一次操作满足 \(i\in S\) 且 \(j\in T\) 或者 \(i\in T\) 且 \(j\in S\) 才会有影响，而我们只用考虑这样成功操作的次数，所以求总和用位运算简单算出：tot=(s[i]&t[j])|(s[j]&t[i])，然后用给的求 1 的个数的函数直接算即可。复杂度 \(\mathcal{O(nm+n^2)}\)，\(n^2\) 前面有 \(\frac{1}{2}\) 的常数，所以理论上会比 bitset 快。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
char ch = getchar(); lx x = 0, f = 1;
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 10000 + 5;
int n, m;
ll a[N], b[N], ans;
namespace Wisadel
{
short main()
{
freopen("a.in", "r", stdin), freopen("a.out", "w", stdout);
n = qr, m = qr;
fo(i, 1, m)
fo(j, 1, n)
{
int x; scanf("%1d", &x);
if(x >= 2) a[j] = a[j] << 1 | 1;
else a[j] = a[j] << 1;
if(x == 1 || x == 3) b[j] = b[j] << 1 | 1;
else b[j] = b[j] << 1;
}
fo(i, 1, n) fo(j, i + 1, n)
{
ll zc = (a[i] & b[j]) | (b[i] & a[j]);
if(__builtin_popcountll(zc) & 1) ans++;
}
printf("%lld\n", ans);
return Ratio;
}
}
signed main(){return Wisadel::main();}
// All talk and never answer
B. 序列
细节不少但不难的贪心题。疑惑只有 7 个场切，大概都把这题想难了。
一眼贪心，因为 dp 不了一点。但是有乘有加有赋值，怎么贪？算最终贡献还需要处理其他很多东西。但是发现乘不用，因为最终都是乘积的形式，所以都换成乘法完全不用考虑其他的东西。设 \(b_x\) 为当前已经确定加入的数，那么有：
\[k=\begin{cases}y\qquad\qquad\qquad t=1\\\frac{a_x+b_x+y}{a_x+b_x}\qquad\quad\; t=2\\\frac{a_x+b_x+y-a_x}{a_x+b_x}\quad\quad t=3 \end{cases} \]但是发现操作 2、3 都会有后效性，很不好处理。这时候又发现一个细节：一个数同时只会被操作一次。十分显然，那么我们完全可以先将每个数的操作排序，然后逐个加入总体的优先队列中即可。由于赛时思路比较混乱，几乎是到最后才切，所以有很多能简略的步骤复杂写了，酌情观看。复杂度 \(\mathcal{O(n\log n)}\)。
Upd：赛时唐氏在每次取部分加入总体时排了序，导致容易卡成 \(\mathcal{O(n^2\log n)}\) 的复杂度，注释掉就过了。
UUpd：由于某个卡逆元的点导致我的码更不好看了，所以下面放的是能过的赛时的码。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
char ch = getchar(); lx x = 0, f = 1;
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n, m, noned;
ll a[N], b[N], c[N], gx[N];
vector<int> zj[N];
ll ans = 1;
struct rmm
{
ll op, k, x;
bool operator < (const rmm &A) const
{
ld zcA = 0, zcB = 0;
if(A.op == 3) zcA = (ld)A.k;
else if(A.op == 2) zcA = ld(a[A.x] + b[A.x] + A.k) / (a[A.x] + b[A.x]);
else zcA = ld(b[A.x] + A.k) / (a[A.x] + b[A.x]);
if(op == 3) zcB = (ld)k;
else if(op == 2) zcB = ld(a[x] + b[x] + k) / (a[x] + b[x]);
else zcB = ld(b[x] + k) / (a[x] + b[x]);
return zcA > zcB;
}
};
priority_queue<rmm> q;
vector<rmm> zcc[N];
namespace Wisadel
{
inline ll Wqp(ll x, int y)
{
ll res = 1;
while(y){if(y & 1) res = res * x % mod; x = x * x % mod; y >>= 1;}
return res;
}
short main()
{
freopen("b.in", "r", stdin), freopen("b.out", "w", stdout);
n = qr, m = qr;
fo(i, 1, n) a[i] = qr, ans = ans * a[i] % mod, c[i] = 1, gx[i] = a[i];
fo(i, 1, m)
{
int op = qr, x = qr, k = qr;
if(op == 1) zj[x].P_B(k);
else if(op == 2) zcc[x].push_back(rmm{op, k, x});
else zcc[x].push_back(rmm{op, k, x});
}
fo(i, 1, n) if(zj[i].size())
{
sort(zj[i].begin(), zj[i].end());
ld zc = ld(zj[i].back()) / a[i];
if(zc < 1.0) ;
else zcc[i].push_back(rmm{1, zj[i].back(), i});
}
fo(i, 1, n) if(zcc[i].size())
{
sort(zcc[i].begin(), zcc[i].end());
q.push(zcc[i].back()), zcc[i].pop_back();
}
printf("%lld ", ans);
int now = 1;
while(q.size())
{
if(q.top().op == 1)
{
ans = ans * Wqp(gx[q.top().x], mod - 2) % mod;
a[q.top().x] = q.top().k;
gx[q.top().x] = (q.top().k + b[q.top().x]) % mod * c[q.top().x] % mod;
ans = ans * gx[q.top().x] % mod;
}
else if(q.top().op == 2)
{
ans = ans * Wqp(gx[q.top().x], mod - 2) % mod;
b[q.top().x] = (b[q.top().x] + q.top().k) % mod;
gx[q.top().x] = (a[q.top().x] + b[q.top().x]) % mod * c[q.top().x] % mod;
ans = ans * gx[q.top().x] % mod;
}
else c[q.top().x] = c[q.top().x] * q.top().k % mod, ans = ans * q.top().k % mod, gx[q.top().x] = gx[q.top().x] * q.top().k % mod;
printf("%lld ", ans);
int nono = q.top().x;
now++, q.pop();
if(zcc[nono].size()) q.push(zcc[nono].back()), zcc[nono].pop_back();
}
fo(i, now, m) printf("%lld ", ans);
return Ratio;
}
}
signed main(){return Wisadel::main();}
// All talk and never answer
C. 树
幽默换根 dp 博弈论。赛时开的时候就剩 5min 了，随便思考发现很容易出现全部都是解的情况，敲了 \(n^{2D}\) 拿了 70pts。后来不出意外被卡了，后后来得知我没开 long long，开了就直接拿 90pts，有点猛。
D. 字符串
放 T4 属实是有些诈骗。
发现 \(k\) 很小，以至于足够我们记录所有可能的字母相邻情况。首先明确题目所求 \(\frac{|s'|}{k}\) 就是分成的段数，而显然段数等于断点处 +1，所以我们直接找断点即可。考虑什么时候必须断：已知 \(t\) 是个排列非常好，不会有重复的字母需要考虑，那么只要某位置上的字符与上一个存在承接关系就不需要断。相反地，如果上一个字母在 \(t\) 中出现位置比当前字母靠后或相等，那么这就是一个断点。
我们线段树维护所有相邻两字母的情况，然后 \(\mathcal{O(k^2)}\) 枚举不合法的连接方式找断点即可。比较好实现的方法是将字母转为整形从 0 开始存储，这样取模求下标很方便，然后对于相邻对开桶记录数量，桶可以存在结构体里，查询直接返回结构体即可。时间复杂度 \(\mathcal{O(nk^2+mk^2\log n)}\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
char ch = getchar(); lx x = 0, f = 1;
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e5 + 5, K = 10;
const int mod = 1e9 + 7;
int n, m, k;
string s;
int zc[K][K], a[N];
struct rmm
{
int t[K][K], lc, rc, lazy;
rmm(){memset(t, 0, sizeof t); lc = rc = lazy = 0;}
} t[N << 2], W;
namespace Wisadel
{
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)
inline rmm Wpushup(rmm A, rmm B)
{
rmm zc;
fo(i, 0, k - 1) fo(j, 0, k - 1)
zc.t[i][j] = A.t[i][j] + B.t[i][j];
zc.t[A.rc][B.lc]++;
zc.lc = A.lc, zc.rc = B.rc;
return zc;
}
inline void Wpushdown(int rt)
{
int c = t[rt].lazy;
fo(i, 0, k - 1) fo(j, 0, k - 1) zc[(i + c) % k][(j + c) % k] = t[ls].t[i][j];
fo(i, 0, k - 1) fo(j, 0, k - 1) t[ls].t[i][j] = zc[i][j];
fo(i, 0, k - 1) fo(j, 0, k - 1) zc[(i + c) % k][(j + c) % k] = t[rs].t[i][j];
fo(i, 0, k - 1) fo(j, 0, k - 1) t[rs].t[i][j] = zc[i][j];
t[ls].lc = (t[ls].lc + c) % k, t[ls].rc = (t[ls].rc + c) % k;
t[rs].lc = (t[rs].lc + c) % k, t[rs].rc = (t[rs].rc + c) % k;
t[ls].lazy = (t[ls].lazy + c) % k, t[rs].lazy = (t[rs].lazy + c) % k;
t[rt].lazy = 0;
}
inline void Wbuild(int rt, int l, int r)
{
if(l == r)
{
t[rt].lc = t[rt].rc = a[l];
return ;
}
Wbuild(ls, l, mid), Wbuild(rs, mid + 1, r);
t[rt] = Wpushup(t[ls], t[rs]);
}
inline void Wupd(int rt, int l, int r, int x, int y, int c)
{
if(x <= l && r <= y)
{
fo(i, 0, k - 1) fo(j, 0, k - 1) zc[(i + c) % k][(j + c) % k] = t[rt].t[i][j];
fo(i, 0, k - 1) fo(j, 0, k - 1) t[rt].t[i][j] = zc[i][j];
t[rt].lc = (t[rt].lc + c) % k, t[rt].rc = (t[rt].rc + c) % k;
t[rt].lazy = (t[rt].lazy + c) % k;
return ;
}
if(t[rt].lazy) Wpushdown(rt);
if(x <= mid) Wupd(ls, l, mid, x, y, c);
if(y > mid) Wupd(rs, mid + 1, r, x, y, c);
t[rt] = Wpushup(t[ls], t[rs]);
}
inline rmm Wq(int rt, int l, int r, int x, int y)
{
if(x <= l && r <= y) return t[rt];
if(t[rt].lazy) Wpushdown(rt);
if(y <= mid) return Wq(ls, l, mid, x, y);
if(x > mid) return Wq(rs, mid + 1, r, x, y);
return Wpushup(Wq(ls, l, mid, x, y), Wq(rs, mid + 1, r, x, y));
}
short main()
{
freopen("d.in", "r", stdin), freopen("d.out", "w", stdout);
n = qr, m = qr, k = qr;
cin >> s; s = " " + s;
fo(i, 1, n) a[i] = s[i] - 'a';
Wbuild(1, 1, n);
fo(i, 1, m)
{
int op = qr, l = qr, r = qr, c;
if(op == 1) c = qr, Wupd(1, 1, n, l, r, c);
else
{
cin >> s; s = " " + s;
fo(i, 1, k) a[i] = s[i] - 'a';
W = Wq(1, 1, n, l, r);
int res = 0;
fo(i, 1, k) fo(j, 1, i) res += W.t[a[i]][a[j]];
printf("%d\n", res + 1);
}
}
return Ratio;
}
}
signed main(){return Wisadel::main();}
// All talk and never answer
末
这场策略风险很高，但结果是好的。
开局依然 10min 切签，然后以防万一果断打拍，拍了 50000 组开始写 T2，然后一直不会处理的好方法。好在循序 渐进来着，通过先暴力用 vector 存每次操作 sort 一遍逐渐找到正确的排序方法，然后优化到不排序直接取，过程花了 30min 左右。危险的原因是敲完 vector 时已经就剩 40min 了。然后最后时刻把两组程序拍上看 T3，一眼大众数据性质是全部合法，预估的 40pts 左右，换做正式考场也会这么打，而且不会绑包。
比较可惜是 T4，涉及的知识点都掌握，如果深看进去了可能也会场切，不过那样估计 T2 就打不出来了，都一样。
真的就剩不到 7 场比赛了，希望能将今天的状态保持下去，到 noip 展现自己真正的实力。
完结撒花~
