A/B
赛时没打。
C
暴力判断是相等 s[i] == t 还是替换了一个字符，或者是添加/删除了一个字符。
最后两个判断只需要交换一下 \(s\) 和 \(t\) 的顺序就可以共用一个函数了。
D
注意到 \(N\le 13\)，所以平方数不会超过 \(v=10^{13}\)，很容易想到暴力枚举 \(\sqrt v\) 以内的数，判断是否能够被表示出来。
时间复杂度 \(O(N\sqrt v)\)，或者说 \(O(N10^{\frac{N}{2}})\)
E
注意到如果两个字符串 \(S1,S2\) 拼起来可以包含 \(T\) 那么一定可以被前后分割成 \(T=T1+T2\) 使得 \(T1\subset S1, T2\subset S2\)。
预处理出每个 \(S_i\) 包含 \(T\) 的最长前后缀的长度，使用双指针解决。
复杂度 \(O(\sum_i |S_i|)\)
查询时计算前缀后缀和大于 \(|T|\) 的 \((i,j)\) 对数。
最后对计算出的前后缀长度做一个后缀和来优化查询。
时间复杂度 \(O(N+\sum_i |S_i|)\)。
F
分数规划裸题。
二分答案，然后在 DAG 上跑个最长路 dp 就完事了。
G
将排列上的数放在二维平面上，每个数可以表示为 \((i,a_i)\) 的形式，对于每个序列可以写作 \((l,r,u,d)\)，表示包含了 \(l\le i\le r, u\le a_i\le d\) 的所有数。注意到这相当于包含了一个矩形内的所有点，可以使用主席树来维护。
具体的，把点按照第二维排序，依次加入主席树中。
对于两个操作，相当于在矩形 \(s\) 里划一条平行于坐标轴的分界线（自己模拟一下）。
怎么找这条分界线呢？
对于每个 1 操作，在主席树上找到 \(l_s-1\) 的排名 \(rk\)，然后主席树上二分出 \(rk+x\) 的值 \(v\) 就得到了分界线。
将 \((l,r,u,d)\) 变成了 \((l,v,u,d)(v+1,r,u,d)\)
对于每个 2 操作，分界线就是 \(x\)，直接分割就行了。
将 \((l,r,u,d)\) 变成了 \((l,r,u,v)(l,r,v+1,d)\)
查询是容易的。
附 C,D,E,F,G 代码
C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
string s[N], t;
int n;
bool chk1(string s1, string s2)
{
int cnt = 0;
for(int i = 0; i < s1.size(); i ++)
cnt += s1[i] != s2[i];
return cnt <= 1;
}
bool chk2(string s1, string s2)
{
int dt = 0;
for(int i = 0; i < s1.size(); i ++)
{
while(!dt && s1[i] != s2[i + dt]) dt ++;
if(s1[i] != s2[i + dt]) return false;
}
return true;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> t;
vector<int> ans;
for(int i = 1; i <= n; i ++)
{
cin >> s[i];
if(s[i].size() < t.size() - 1 || s[i].size() > t.size() + 1) continue;
if(s[i] == t)
{
ans.push_back(i);
continue;
}
if(s[i].size() == t.size() && chk1(s[i], t))
{
ans.push_back(i);
continue;
}
if(s[i].size() == t.size() - 1 && chk2(s[i], t))
{
ans.push_back(i);
continue;
}
if(s[i].size() == t.size() + 1 && chk2(t, s[i]))
{
ans.push_back(i);
continue;
}
}
cout << ans.size() << "\n";
for(int i : ans) cout << i << " ";
return 0;
}
D
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 15;
int a[N], n, p[N];
string s;
inline bool chk(int x)
{
int b[N];
memcpy(b, a, sizeof a);
while(x)
{
b[x % 10] --;
if(b[x % 10] < 0) return false;
x /= 10;
}
for(int i = 1; i < 10; i ++)
if(b[i] > 0) return false;
return true;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> s;
p[0] = 1;
for(int i = 1; i <= n; i ++) p[i] = p[i - 1] * 10ll;
for(int i = 0; i < n; i ++) a[s[i] - '0'] ++;
int ans = 0;
for(int i = 0; i * i < p[n]; i ++)
ans += chk(i * i);
cout << ans;
return 0;
}
E
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 5e5 + 5;
string s[N], t;
int n, l[N], r[N], sl[N], sr[N];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> t;
for(int i = 1; i <= n; i ++)
{
cin >> s[i];
int k = 0;
for(int j = 0; k < t.size() && j < s[i].size(); j ++)
if(s[i][j] == t[k]) k ++;
l[i] = k;
k = t.size() - 1;
for(int j = s[i].size() - 1; k >= 0 && j >= 0; j --)
if(s[i][j] == t[k]) k --;
r[i] = t.size() - 1 - k;
sl[l[i]] ++;
sr[r[i]] ++;
}
for(int i = N - 5; i >= 0; i --) sl[i] += sl[i + 1];
for(int i = N - 5; i >= 0; i --) sr[i] += sr[i + 1];
int ans = 0;
for(int i = 1; i <= n; i ++)
{
ans += sr[t.size() - l[i]] + sl[t.size() - r[i]];
}
cout << ans / 2;
return 0;
}
F
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double D;
#define int ll
const int N = 2e5 + 5;
struct edge{int v, a, b;};
vector<edge> e[N];
int deg[N], n, m;
D f[N];
bool check(D x)
{
queue<int> q;
int d[N];
memcpy(d, deg, sizeof deg);
memset(f, -0x10, sizeof f);
f[1] = 0;
for(int i = 1; i <= n; i ++)
if(!d[i]) q.push(i);
while(!q.empty())
{
int t = q.front();q.pop();
for(auto i : e[t])
{
if(--d[i.v] == 0) q.push(i.v);
f[i.v] = max(f[i.v], f[t] + (i.a - x * i.b));
}
}
return f[n] >= 0.L;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i ++)
{
int x, y, a, b;
cin >> x >> y >> a >> b;
e[x].push_back({y, a, b});
deg[y] ++;
}
D l = 0, r = 1e4;
while(l + (D)1e-12 < r)
{
D mid = (l + r) / 2.L;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.17Lf", r);
return 0;
}
G
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
struct node{int l, r, sz;};
int n, m, a[N];
struct sgtv
{
node tr[N << 5];
int root[N], idx;
int insert(int lstt, int l, int r, int x)
{
int nowt = ++idx;
tr[nowt] = tr[lstt];
if(l == r)
{
tr[nowt].sz++;
return nowt;
}
int mid = (l + r) >> 1;
if(mid >= x) tr[nowt].l = insert(tr[lstt].l, l, mid, x);
else tr[nowt].r = insert(tr[lstt].r, mid + 1, r, x);
tr[nowt].sz = tr[tr[nowt].l].sz + tr[tr[nowt].r].sz;
return nowt;
}
int query(int lt, int rt, int l, int r, int k)
{
if(l > k || r < k) return 0;
if(l == r) return tr[rt].sz - tr[lt].sz;
int mid = (l + r) >> 1;
if(mid >= k) return query(tr[lt].l, tr[rt].l, l, mid, k);
else return tr[tr[rt].l].sz - tr[tr[lt].l].sz + query(tr[lt].r, tr[rt].r, mid + 1, r, k);
}
int find(int lt, int rt, int l, int r, int k)
{
if(l == r) return r;
int mid = (l + r) >> 1;
int cnt = tr[tr[rt].l].sz - tr[tr[lt].l].sz;
if(cnt >= k) return find(tr[lt].l, tr[rt].l, l, mid, k);
else return find(tr[lt].r, tr[rt].r, mid + 1, r, k - cnt);
}
} tr;
struct M{int l, r, u, d;}b[N];
int h = 0;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n;
vector<pair<int, int>> v;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
v.push_back({a[i], i});
}
sort(v.begin(), v.end());
for(int i = 1; i <= n; i ++)
tr.root[i] = tr.insert(tr.root[i - 1], 0, n + 1, v[i - 1].second);
cin >> m;
b[0] = {1, n, 1, n};
while(m --)
{
int t, s, x;
cin >> t >> s >> x;
if(t == 1)
{
int L = tr.query(tr.root[b[s].u - 1], tr.root[b[s].d], 0, n + 1, b[s].l - 1);
int r = tr.find(tr.root[b[s].u - 1], tr.root[b[s].d], 0, n + 1, L + x);
r = min(r, b[s].r);
r = max(r, b[s].l - 1);
b[++h] = {r + 1, b[s].r, b[s].u, b[s].d};
b[s].r = r;
}
else
{
x = min(x, b[s].d);
x = max(x, b[s].u - 1);
b[++h] = {b[s].l, b[s].r, x + 1, b[s].d};
b[s].d = x;
}
cout << tr.query(tr.root[b[h].u - 1], tr.root[b[h].d], 0, n + 1, b[h].r) -
tr.query(tr.root[b[h].u - 1], tr.root[b[h].d], 0, n + 1, b[h].l - 1) << "\n";
}
return 0;
}