目录
写在前面
比赛地址：https://codeforces.com/gym/104090。
以下按个人难度向排序。
最上强度的一集，然而金牌题过了铜牌题没过，唐！
去年杭州似在一道树上痛失 Au 呃呃，vp 2022 树题过了然而铜牌题没过呃呃
F
签到。
大力模拟。
code by dztle：
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1; char s;
while((s=getchar())<'0'||s>'9') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+(s^'0'),s=getchar();
return x*f;
}
#define ull unsigned long long
const int N=100005;
int n,m;
string s;
map<string,int>ma;
int main(){
n=read();
for(int i=1;i<=n;++i){
m=read();
bool ok=0;
for(int j=1;j<=m;++j){
bool fl=0;
cin>>s;
int len=s.length();
for(int k=0;k<len;++k){
if(k+2==len) break;
if(s[k]=='b'&&s[k+1]=='i'&&s[k+2]=='e') fl=1;
}
if(fl==1){
if(ma.count(s)==0){
ok=1;
ma[s]=1;
cout<<s<<'\n';
}
}
}
if(!ok){
cout<<"Time to play Genshin Impact, Teacher Rice!\n";
}
}
return 0;
}
/*
6
1
biebie
1
adwlknafdoaihfawofd
3
ap
ql
biebie
2
pbpbpbpbpbpbpbpb
bbbbbbbbbbie
0
3
abie
bbie
cbie
*/
D
结论。
写了个暴力模拟打表，发现最终数列形态一定为 \(2:1:1:\cdots : 1\)。
The proof is left as exercise for the readers.
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
const int kN = 1e6 + 10;
double a[kN], sum;
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int n; std::cin >> n;
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
sum += a[i];
}
sum /= (n + 1);
std::cout << std::fixed << std::setprecision(10) << 2 * sum << " ";
for (int i = 1; i < n; ++ i) std::cout << std::fixed << std::setprecision(10) << sum << " ";
// for (int T = 1; T <= 1000; ++ T) {
// for (int i = 0; i < n; ++ i) {
// a[(i + 1) % n] += a[i] / 2.0;
// a[i] /= 2.0;
// }
// // for (int i = 0; i < n; ++ i) std::cout << std::fixed << std::setprecision(10) << a[i] << " ";
// // std::cout << "\n";
// }
// for (int i = 0; i < n; ++ i) std::cout << std::fixed << std::setprecision(10) << a[i] << " ";
return 0;
}
C
DP。
对于给出的三种取物品的贡献，发现第三种情况至多贡献一次。
设 \(f_{i, j, 0/1}\) 表示使用物品 \(1\sim i\)，且其中某个物品是/否以第三种情况产生贡献。初始化 \(f_{0, 0, 0} = 0\)，转移时考虑当前物品的贡献形式，则有：
\[\forall p_i\le j\le k,\ f_{i, j, 0} \leftarrow \begin{cases} f_{i - 1, j, 0}\\ f_{i - 1, j - p_i, 0} + w_{i, p_i} \end{cases}\]\[\forall 1\le j\le k,\ f_{i, j, 1} \leftarrow \begin{cases} f_{i, j, 1}\\ \max\limits_{1\le l\le \min(j, p_i-1)} f_{i, j - l, 0} + w_{i, l} \end{cases}\]发现这个转移方程是一个显然的背包形式，套路地滚掉第一维按 01 背包实现即可。
特别地，需要考虑无第三种情况的影响。若 \(\sum p_i \le k\) 则答案为 \(f_{\sum p_i, 0}\)，否则答案为 \(\max\left( f_{k, 0}, f_{k, 1}\right)\)。
总时间复杂度 \(O(nk)\) 级别加一个 10 的常数。
code by dztle：
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1; char s;
while((s=getchar())<'0'||s>'9') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+(s^'0'),s=getchar();
return x*f;
}
const int N=30005;
int n,k,p[N],w[N][15];
int f[N][2];
signed main(){
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
n=read(),k=read();
int sum=0;
for(int i=1;i<=n;++i){
p[i]=read();
sum+=p[i];
for(int j=1;j<=p[i];++j){
w[i][j]=read();
}
}
// cout<<sum<<endl;
memset(f,-0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;++i){
for(int j=k;j>=1;--j){
if(j>=p[i]){
f[j][0]=max(f[j][0],f[j-p[i]][0]+w[i][p[i]]);
f[j][1]=max(f[j][1],f[j-p[i]][1]+w[i][p[i]]);
}
for(int o=p[i]-1;o>=1;--o){
if(j>=o) f[j][1]=max(f[j][1],f[j-o][0]+w[i][o]);
}
}
// for(int j=1;j<=k;++j){
// cout<<j<<' '<<f[j][0]<<' '<<f[j][1]<<endl;
// }
}
if(sum>=k)cout<<max(f[k][0],f[k][1]);
else cout<<f[sum][0];
return 0;
}
/*
4 20
3 1 1 3
3 1 1 3
3 3 1 1
3 3 1 3
*/
K
字符串，枚举。
读完题看看数据范围感觉像一个很怪的复杂度，发现 \(O(26^2)\) 地询问一次大概是能过的。
考虑字符串比较字典序的本质——两个字符串的字典序仅与它们第一个不同的字符有关。
则当字符优先级调整时，实际上并不需要重新求得所有字符串的字典序：当某字符串为另一字符串的真前缀时字典序恒定更小不受影响，否则仅需重新比较它们两两之间的第一个不同的字符即可。
于是考虑预处理 \(s\) 表示满足下列条件的二元组 \((i, j)\) 的数量：
- \(1\le i < j\le n\)。
- \(s_j\) 为 \(s_i\) 的真前缀。
预处理数组 \(f_{c_1, c_2}\) 表示满足下列条件的二元组 \((i, j)\) 的数量：
- \(1\le i < j\le n\)。
- \(s_i \not= s_j\)，且第一个不相同的位置 \(k\) 满足 \(c_1 = s_{i, k}, c_2 = s_{j, k}\)。
上述两者可在顺序枚举字符串，插入 Trie 时顺便求得。具体地：
- 当插入字符串 \(s_j\) 时，每次对当前节点 \(u\) 按当前枚举到的字符 \(s_{j, k}\) 进行转移时，则对于其他转移 \(\operatorname{trans}(u, c) (c\not= s_{j, k})\) 子树中所有字符串 \(s_i\)，它们第一个不相同的位置即为 \(k\) 且满足 \(c_1 = c, c_2 = s_{j, k}\)，对 \(f_{s_{i, k}, c}\) 的贡献为 \(\operatorname{size}(\operatorname{trans}(u, c))\)；
- 当插入结束到达终止状态 \(u'\) 时，其子树中所有字符串即为所有以 \(s_i\) 为真前缀的字符串，令 \(s:=s+\sum \operatorname{size}(\operatorname{trans}(u', c))\) 即可。
预处理后每次询问即可枚举有序的字符二元组 \(c_1, c_2 (c_1 > c_2)\) 遍历数组 \(f\)，答案即为：
\[s + \sum_{c_1<c_2} f_{c_1, c_2} \]总时间复杂度 \(O(\sum |s| + 26^2q)\)。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kM = 30;
const int kN = 1e6 + 10;
//=============================================================
int n, q;
std::string s;
LL cnt[kM][kM], sum;
//=============================================================
namespace Trie {
const int kNode = kN << 3;
int nodenum = 1, tr[kNode][30], sz[kNode];
void Insert() {
int now = 1;
for (int i = 0, len = s.length(); i < len; ++ i) {
int ch = s[i] - 'a';
if (!tr[now][ch]) tr[now][ch] = ++ nodenum;
for (int j = 0; j < 26; ++ j) {
if (j == ch) continue;
cnt[ch][j] += sz[tr[now][j]];
}
now = tr[now][ch];
++ sz[now];
}
for (int j = 0; j < 26; ++ j) {
sum += sz[tr[now][j]];
}
}
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> n >> q;
for (int i = 1; i <= n; ++ i) {
std::cin >> s;
Trie::Insert();
}
while (q --) {
std::string t; std::cin >> t;
LL ans = 0;
for (int i = 0; i < 26; ++ i) {
for (int j = i + 1; j < 26; ++ j) {
ans += cnt[t[i] - 'a'][t[j] - 'a'];
}
}
std::cout << ans + sum << "\n";
}
return 0;
}
/*
4 1
a
ab
abc
a
abcdefghijklmnopqrstuvwxyz
*/
A
数论。
咕咕~
G
手玩，树哈希。
大力手玩题。
首先发现若图中有多于一个环则必定为不合法，此时断开环上不同的边必然导致不同构。
于是仅需考虑基环树的情况。考虑以环上 \(k\) 个节点为根的子树分别为 \(t_0, t_1, \cdots, t_{k-1}\)，记 \(t_i = t_j\) 表示 \(t_i, t_j\) 同构。
手玩下发现若环为奇环，当且仅当 \(t_0 = t_1 = \cdots = t_{k-1}\) 时合法；若为偶环，记环上节点 \(i\) 在环上对称节点为 \(f_j\)（两条路径 \(i\rightarrow j\) 长度相同，均为 \(\frac{k}{2}\)），则当且仅当基环树以任意 \((i, f_j)\) 为轴均呈现轴对称时合法，再手玩下发现此时一定有 \(t_i = t_{(i + 2)\bmod k}\)。
为什么想到轴对称？因为想到需要令不同的边断开均是等价的，根据基环树的形态想到断开对称的边一定需要是等价的，于是想到对于任意对称轴对称的边均应等价。
按照上述结论，按顺序枚举环上所有节点的子树，并判断对应位置是否同构，树哈希实现即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
inline int read(){
int x=0,f=1; char s;
while((s=getchar())<'0'||s>'9') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+(s^'0'),s=getchar();
return x*f;
}
const int N=1e5+5;
ull pri[N];
int T,n,m,tot,head[N];
struct node{
int to,nxt;
}e[N*10*2];
int uu[N],vv[N];
void add(int u,int v){
e[++tot].nxt=head[u],head[u]=tot;
e[tot].to=v;
}
int fa[N],top;
int q[N];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
if(x!=y) fa[x]=y;
}
bool ok[N];
int que[N],cnt;
void dfsh(int u,int fap,int g){
if(ok[g]) return;
q[++top]=u;
if(u==g){
cnt=0;
for(int i=1;i<=top;++i){
ok[q[i]]=1;
que[++cnt]=q[i];
}
return;
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fap) continue;
if(fap==0&&v==g) continue;
dfsh(v,u,g);
}
--top;
}
int siz[N];
ull get(int u,int fap){
ull ans=1;
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fap) continue;
if(ok[v]) continue;
ans+=get(v,u)*pri[siz[v]];
siz[u]+=siz[v];
}
return ans;
}
signed main(){
srand(time(0));
for(int i=1;i<=100000;++i){
pri[i]=i*i+rand();
if(!(pri[i]&1)) pri[i]++;
}
T=read();
while(T--){
cnt=0;
n=read(),m=read();
tot=0;
for(int i=1;i<=n;++i){
head[i]=0;
}
for(int i=1,u,v;i<=m;++i){
u=read(),v=read();
add(u,v),add(v,u);
uu[i]=u,vv[i]=v;
}
if(m==n-1){
puts("YES"); continue;
}
if(m>n) {
puts("NO"); continue;
}
for(int i=1;i<=n;++i){
fa[i]=i;ok[i]=0;
}
top=0;
for(int i=1;i<=m;++i){
int u=find(uu[i]),v=find(vv[i]);
if(u!=v){
merge(u,v);
}else{
// uu[i] vv[i]
dfsh(uu[i],0,vv[i]);
}
}
ull now=0;
bool fl=0;
if(cnt%2==1){
now=get(que[1],0);
for(int i=2;i<=cnt;++i){
if(get(que[i],0)!=now){
fl=1;
}
}
}else{
now=get(que[1],0);
for(int i=3;i<=cnt;i+=2){
if(get(que[i],0)!=now){
fl=1;
}
}
now=get(que[2],0);
for(int i=4;i<=cnt;i+=2){
if(get(que[i],0)!=now){
fl=1;
}
}
}
if(fl){
puts("NO");
}else puts("YES");
}
return 0;
}
/*
3
3 3
1 2
2 3
3 1
4 4
1 2
2 3
3 1
3 4
7 7
1 2
2 3
3 1
1 4
2 5
5 6
3 7
*/
M
换根 DP，线段树，数论。
考虑枚举起点将其作为根节点 \(R\)，确定根节点后显然最优的 \(d\) 应为 \(\gcd\left(\operatorname{dep}_{c_1}, \operatorname{dep}_{c_2}, \cdots, \operatorname{dep}_{c_k}\right)\)，此时的总花费即为：
\[2\times \dfrac{\sum\limits_{1\le i\le k} \operatorname{dep}_{c_i}}{\gcd\limits_{1\le i\le k}\operatorname{dep}_{c_1}} \]上式的分子是经典的换根 DP 问题，考虑能否在换根的同时维护分母，即维护所有关键点的深度。显然每次换根向子节点沿距离为 \(w\) 的边移动时，会令子树中的节点 \(\operatorname{dep} - w\)，其他所有节点 \(\operatorname{dep} + w\)。考虑将所有关键点按 dfs 序排序使子树内关键点构成一段连续区间，移动后维护 \(\operatorname{dep}\) 可转化为区间修改问题。
那么在此基础上能否求得全局 \(\gcd\) 呢？答案是可以的。由数论性质可知：
\[\gcd(a_1, a_2, \cdots, a_k) = \gcd(a_1, a_2 - a_1, \cdots, a_k - a_{k - 1}) \]则仅需维护差分数组的 \(\gcd\)，此时区间修改转化为了差分数组的单点修改，线段树单点修改+维护区间 \(\gcd\) 实现即可，单次修改时间复杂度为 \(O(\log n\log w)\) 级别。
每次换根时按上述算法分别维护分子分母的值即可，取最小值即为答案。换根时需要进行常数次线段树修改，则总时间复杂度为 \(O(n\log n\log w)\) 级别。
注意：在求节点 dfs 序、维护每个节点子树范围、以及维护线段树时应仅考虑关键点，若出现非关键点，则它们也会被区间修改影响从而影响求得的 \(\gcd\)。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, k;
int edgenum, head[kN], v[kN << 1], w[kN << 1], ne[kN << 1];
int dfnnum, dfn[kN], node[kN], subtree[kN][2];
LL ans = kInf, dep[kN], f[kN], g[kN];
bool colored[kN];
//=============================================================
namespace Seg {
#define ls ((now_<<1))
#define rs ((now_<<1|1))
#define mid ((L_+R_)>>1)
const int kNode = kN << 2;
LL d[kNode];
void Pushup(int now_) {
d[now_] = std::__gcd(d[ls], d[rs]);
}
void Build(int now_, int L_, int R_) {
if (L_ == R_) {
d[now_] = dep[node[L_]] - dep[node[L_ - 1]];
return ;
}
Build(ls, L_, mid), Build(rs, mid + 1, R_);
Pushup(now_);
}
void Insert(int now_, int L_, int R_, int pos_, LL val_) {
if (pos_ < L_ || pos_ > R_) return ;
if (L_ == R_) {
d[now_] += val_;
return ;
}
if (pos_ <= mid) Insert(ls, L_, mid, pos_, val_);
else Insert(rs, mid + 1, R_, pos_, val_);
Pushup(now_);
}
LL Query() {
return abs(d[1]);
}
#undef ls
#undef rs
#undef mid
}
void Add(int u_, int v_, int w_) {
v[++ edgenum] = v_;
w[edgenum] = w_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
int Dfs1(int u_, int fa_, LL dep_) {
if (colored[u_]) {
node[++ dfnnum] = u_;
dfn[u_] = dfnnum;
dep[u_] = dep_;
g[u_] = 1;
subtree[u_][0] = dfnnum;
} else {
subtree[u_][0] = kN;
}
int min_dfnnum = kN;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i], w_ = w[i];
if (v_ == fa_) continue;
min_dfnnum = std::min(min_dfnnum, Dfs1(v_, u_, dep_ + w_));
f[u_] += f[v_] + 1ll * w_ * g[v_];
g[u_] += g[v_];
}
subtree[u_][0] = std::min(subtree[u_][0], min_dfnnum);
subtree[u_][1] = dfnnum;
return subtree[u_][0];
}
void Dfs2(int u_, int fa_, LL f_, LL g_) {
LL d = Seg::Query();
if (d == 0) ans = 0;
else ans = std::min(ans, 1ll * (f[u_] + f_) / d);
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i], w_ = w[i];
if (v_ == fa_) continue;
LL newg = g_ + g[u_] - g[v_];
LL newf = f_ + (f[u_] - (f[v_] + 1ll * g[v_] * w_)) + 1ll * w_ * newg ;
// LL newf = f_ + 1ll * w_ * newg;
Seg::Insert(1, 1, k, 1, w_);
if (subtree[v_][0] <= subtree[v_][1]) {
Seg::Insert(1, 1, k, subtree[v_][0], -2ll * w_);
Seg::Insert(1, 1, k, subtree[v_][1] + 1, 2ll * w_);
}
Dfs2(v_, u_, newf, newg);
Seg::Insert(1, 1, k, 1, -w_);
if (subtree[v_][0] <= subtree[v_][1]) {
Seg::Insert(1, 1, k, subtree[v_][0], 2ll * w_);
Seg::Insert(1, 1, k, subtree[v_][1] + 1, -2ll * w_);
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> n >> k;
for (int i = 1; i <= k; ++ i) {
int c; std::cin >> c;
colored[c] = 1;
}
for (int i = 1; i < n; ++ i) {
int u_, v_, w_; std::cin >> u_ >> v_ >> w_;
Add(u_, v_, w_), Add(v_, u_, w_);
}
Dfs1(1, 0, 0);
Seg::Build(1, 1, k);
Dfs2(1, 0, 0, 0);
std::cout << 2ll * ans << "\n";
return 0;
}
/*
7 1
2
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
5 3
2 3 4
1 2 4
2 3 2
3 4 1
4 5 4
*/
写在最后
学到了什么：
- A：裴蜀定理可扩展到任意个变量。
- G：相等关系的推导。
- M：区间修改区间 \(\gcd\) 有 \(O(\log^2 n)\) 做法。