upd on 2023.11.02 初稿
upd on 2023.11.04 修正部分表达
感觉这一套题质量都很不错，有比较好的思维难度，又不是特别难（当然，对于我来说很难），而且有一些比较好的思路和套路。
题目链接均为洛谷链接。
CF1474D Cleaning
摘要：
-
性质：考虑端点，发现一定可以从左右两侧开始消除。
-
分别维护单独从一侧消除的相关信息。
-
枚举交界处，检查是否有解。
分析性质：
因为“使用交换”后会变成“不使用交换”的情况，所以先分析不使用/交换后的情况。因为在两端的数至多有一种消除方法，所以若有解，一定存在消除方案，满足每次消除最外侧，从左右两端向中间交界消除，形如 \(a_1 \rightarrow a_i,a_{i+1} \leftarrow a_n\)。
进一步考虑交换。若交换的位置单独包含于某一侧，则相当于没有产生影响，所以交换的位置应当是从左右两边开始消除的交界。如果能枚举交换位置并直接判断是否可行，问题就解决了。
实现：
于是，考虑对于两个方向分别维护：如果强行消除这个数之前的所有数，这个数剩了多少，记为 \(resl_i,resr_i\)（如果是负的说明已经不可行），以及两方向最多消除到哪里。
接着枚举两方向的交界，检查是否有解，设为 \(a_i,a_{i+1}\)。有两种合法情况：若不使用能力，则应有 \(a_i-res_{i-1} = a_{i+1}-res_{i+2} \ge 0\)；若使用，则应有 \(a_{i+1}-res_{i-1} = a_{i}-res_{i+2}\ge 0\)。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,a[N],l,r;
int ansl[N],ansr[N];
void work()
{
#define YES return puts("YES"),void()
#define NO return puts("NO"),void()
scanf("%d",&n);l=0,r=n+1;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
ansl[i]=ansr[i]=a[i];
ansl[0]=ansr[n+1]=0;
for(int i=1;i<=n;i++)
{
ansl[i+1]-=ansl[i];l=i;
if(ansl[i+1]<0)break;
}
for(int i=n;i>=1;i--)
{
ansr[i-1]-=ansr[i];r=i;
if(ansr[i-1]<0)break;
}
if(ansl[n]==0||ansr[1]==0)YES;
// printf("l=%d,r=%d\n",l,r);
// for(int i=1;i<=n;i++)
// printf("%d ",ansl[i]);puts("");
// for(int i=1;i<=n;i++)
// printf("%d ",ansr[i]);puts("");
for(int i=1;i<n;i++)//swap_it ; 1~n-1
{
if (i-1>l || i+2<r)continue;
if
(
(
( (a[i]-ansl[i-1]) >= 0 )
&& ( (a[i]-ansl[i-1]) == (a[i+1]-ansr[i+2]) )
)
||
(
( (a[i+1]-ansl[i-1]) >= 0 )
&& ( (a[i+1]-ansl[i-1]) == (a[i]-ansr[i+2]) )
)
)YES;
}
NO;
}
int main()
{
int T;scanf("%d",&T);
while(T--)work();
}
CF1468A LaIS
摘要：
-
DP。
-
性质：选出上升子序列，并加入（若有）不会成为 \(min\) 的数。
-
由性质设计 DP 状态，并用贪心优化转移策略。
-
单调栈维护最近更大值，树状数组维护最大最远转移点。
首先分析合法序列的性质：
对于 \(b_1,b_2,b_3\)，最小值在 \(b_1\) 或 \(b_2\)。
分别考虑两种情况并拓展，发现每次向\(b_1,...,b_{i-1},b_i\) 中加入 \(b_{i+1}\) 时，\(b_{i+1} \ge \min(b_{i-1},b_i)\)，序列整体似乎呈上升趋势。
进一步地，发现合法序列可以拆分成两部分。第一部分为某个不降序列，第二部分中，每个元素两侧的元素均属于第一部分（此元素处于序列首时例外）。
接下来推导 DP 状态及转移：
设 \(f_i\) 表示不降序列以 \(i\) 结尾时，合法序列的最长长度。于是有转移
发现由于 \(k\) 至多带来 \(1\) 的贡献，那么为了 \(k\) 而选择更小的 \(j\) 是不优的，应优先保证 \(f_j\) 最大。在此基础上，为了使更可能存在合法的 \(k\)，需要使下标 \(j\) 最小，并检查这一段区间的最大值是否大于 \(a_i\)。
最后是转移的实现：
发现加入 \(k\) 只有一次，所以可以转化为：（在 \(i\) 之前）最近的大于 \(a_i\) 的数的下标是否大于 \(j\)，可以采用单调栈维护。
发现 \(j<i,a_j<a_i\) 是一个二维偏序问题，考虑在意义上将 \(j,f_j\) 打包，放在下标为 \(a_j\) 的位置，每次树状数组查询 \(a_i\) 的前缀最优（即 \(f_j\) 更大或 \(f_j\) 相同时 \(j\) 更小）。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,a[N],dp[N];
struct node{int val,pos;};
node w[N];
#define lowbit(x) (x)&(-(x))
void trans(node &x,node &y)
{
if ( (x.val<y.val) || (x.val==y.val&&x.pos>y.pos) )x=y;
}
void update(int x,node k)
{
while(x<=n)
trans(w[x],k),x+=lowbit(x);
}
node query(int x)
{
node res={0,0};
while(x)
trans(res,w[x]),x-=lowbit(x);
return res;
}
int sta[N],tp,lst[N];
void work()
{
int ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
while(tp&&a[i]>=a[sta[tp]])tp--;
lst[i]=sta[tp],sta[++tp]=i;
}
for(int i=1;i<=n;i++)
{
node tmp=query(a[i]);
dp[i]=tmp.val+1;
if(lst[i]>tmp.pos)dp[i]++;
ans=max(ans,dp[i]);
node now={dp[i],i};
update(a[i],now);
}
printf("%d\n",ans);
}
void clear()
{
for(int i=1;i<=n;i++)
w[i]={0,0},lst[i]=dp[i]=0;
tp=0;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
work(),clear();
return 0;
}
CF1476E Pattern Matching
摘要：
-
性质：给出要求等价于顺序限制。
-
性质：\(k \le 4\)，枚举通配符，得到所有可匹配模式串。
-
建边，拓扑排序。
每个要求实际上限制了指定串的位置先于其它可匹配模式串。
由于 \(k \le 4\)，可以对于每个匹配串 \(m_i\) 枚举所有通配符出现情况，并查看是否有相同模式串。当然，也可以对模式串枚举，这样会有常数级优化，但相对不好写。
然后对于每一个匹配串 \(m\)，设指定模式串为 \(t\)，未指定但可匹配的串的集合为 \(S\)，\(pos_x\) 表示模式串 \(x\) 的排序后位置，则有 $\forall pos_{t} < pos_{S_i} $，于是 \(t\) 向 \(S_i\) 连边，表示 \(S_i\) 应排在 \(t\) 之后，拓扑排序求解。
碎碎念：
其实一开始想写成 \(pos_t < \min_{x\in S} pos_x\)，然而发现不利于思路通顺改掉了。回头一想，发现这一类 min/max 关系似乎也可能转拓扑，可能是个没什么用的 Trick。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int V=N,E=N*16;
struct edge{int to,nxt;};
edge e[E*2];int head[V],tot;
void add(int u,int v)
{
e[++tot]={v,head[u]};head[u]=tot;
}
int n,m,k,limk,mt[N],id[531441+100];
char p[N][6],s[N][6];
int Hash(char *s)
{
int res=0;
for(int i=1;i<=k;i++)
res*=27,res+=(s[i]=='_')?0:s[i]-'a'+1;
return res;
}
int ans[N],cnt,indeg[N];queue<int>q;
void Push(int x){q.push(x),ans[++cnt]=x;}
bool topo()
{
int vis=0;
for(int i=1;i<=n;i++)
if(!indeg[i])Push(i);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(!(--indeg[v]))Push(v);
}
}
return cnt==n;
}
bool check(char *pp,char *ss)
{
for(int i=1;i<=k;i++)
if(pp[i]!='_'&&ss[i]!=pp[i])return false;
return true;
}
void debug()
{
return ;
for(int i=1;i<=n;i++)
{
cout<<Hash(p[i])<<" ";
}cout<<endl;
for(int i=1;i<=m;i++)
{
cout<<Hash(s[i])<<" ";
}cout<<endl;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);limk=(1<<k)-1;
for(int i=1;i<=n;i++)
{
scanf("%s",p[i]+1);
id[Hash(p[i])]=i;
}
char tmp[6];
for(int i=1;i<=m;i++)
{
scanf("%s",s[i]+1);
scanf("%d",&mt[i]);
if(!check(p[mt[i]],s[i]))return puts("NO"),0;
int u=Hash(p[mt[i]]),w=Hash(s[i]);
for(int j=0;j<=limk;j++)
{
bitset<4>b=j;
for(int l=1;l<=k;l++)
{
if(j&(1<<(l-1)))
tmp[l]='_';
else
tmp[l]=s[i][l];
}
int v=Hash(tmp);
if(u==v||id[v]==0)continue;
add(id[u],id[v]);indeg[id[v]]++;
}
}
if(topo())
{
puts("YES");
for(int i=1;i<=cnt;i++)
printf("%d ",ans[i]);puts("");
}
else
{
puts("NO");
}
return 0;
}
CF1467D Sum of Paths
摘要：
-
单点点权修改，答案变化量取决于该点被到达的次数。
-
由只走 \(i\) 步到 \(j\) 的方案数算出在第 \(i\) 步到 \(j\) 的方案数，加和即所求。
如果我们可以求出每个点被走了多少次，那么就可以 \(O(1)\) 地修改了。
每次走一步题、求方案数题、\(n^2\) 可过题，那大概率会有个很典的东西：设 \(f_{i,j}\) 表示走了 \(i\) 步，当前走到 \(j\) 的方案数。转移显然：
然而打表出来发现不太对，因为 \(f_{i,j}\) 只计算到 第 \(i\) 步，后面的没有算。
怎么办呢？发现其实走后面的 \(n-i\) 步可以看成从某个点为终点，倒着走 \(n-i\) 步到 \(j\)，与正着走 \(n-i\) 步 到 \(j\) 没有任何不同，于是可以“拼接”。
所以考虑设 \(g_{i,j}\) 表示走满步数，在第 \(i\) 步走到 \(j\) 的方案数，转移：
对于每个点 \(j\)，累加所有的 \(g_{i,j}\)，得到所有方案中被走到的次数 \(sum_j\)，那么每次答案的改变量就是 \(sum_j \times (val^{'}_j-valj)\)。
也许有的同学怀疑前后“拼接”的方式会算重，比如从 \(a\) 到 \(b\) 再到 \(a\) 被算了两次或多次。实际上不会，因为从逻辑上讲，\(b\) 到 \(a\) 时间上在 \(a\) 到 \(b\) 之后，两者是完全分开，互不影响的。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5010,mod=1e9+7;
int n,k,q,a[N];
int f[N][N],g[N][N],sum[N];
void init()
{
for(int j=1;j<=n;j++)
f[0][j]=1;
for(int i=1;i<=k;i++)
for(int j=1;j<=n;j++)
f[i][j]=(f[i-1][j-1]+f[i-1][j+1])%mod;
for(int j=1;j<=n;j++)
for(int i=0;i<=k;i++)
g[i][j]=1ll*f[i][j]*f[k-i][j]%mod;
for(int j=1;j<=n;j++)
for(int i=0;i<=k;i++)
sum[j]=(sum[j]+g[i][j])%mod;
}
LL ans[N];int cnt;
signed main()
{
scanf("%d%d%d",&n,&k,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
init();
LL now=0;
for(int i=1;i<=n;i++)
{
now=(now+1ll*sum[i]*a[i]%mod)%mod;
}
for(int i=1;i<=q;i++)
{
int x,y;scanf("%d%d",&x,&y);
now = (now+(1ll*(y-a[x])*sum[x]%mod))%mod;
now = (now+mod)%mod;
a[x]=y;
ans[++cnt]=now;
}
for(int i=1;i<=q;i++)
printf("%lld\n",ans[i]);
return 0;
}
CF1468M Similar Sets
摘要：
-
根号分治
-
对每个大集合遍历所有集合，桶处理。
-
对所有小集合枚举所有元素对，按较小值放入容器，每个容器桶处理。
-
注意算空间调块长，注意离散化，注意清空。
-
存在二分图做法，但个人觉得没必要。
根号分治的根本在于总大小有保障。对于本题，发现从元素入手不一定好处理，于是从集合入手。以下设块长为 \(B\),大小大于 \(B\) 的称作大集合，其余为小集合。
大集合数量不超过 \(B\) 级别，所以支持对每个大集合进行全局遍历。对于每个大集合，同其它所有集合比对，用桶维护大集合每个元素是否出现，如果比对时有不少于两次发现存在相同元素则得解。
小集合大小不超过 \(B\)。设小集合数量为 \(k\)，则 \(kB \le n\)，而 \(kB^2 \le Bn\)，所以支持对每个小集合进行平方级别处理。考虑枚举所有元素对，类似 stl map 的思路，按小值为键，大值、编号为值，放入对应容器中。遍历每个容器，如果遇到新元素将桶中放入集合编号，遇到第二次得解。
tag 里有一个“graphs”的标签，是说将集合与元素的关系视作二分图，然后在两集合中存在相同元素对转化为找四元环，但是个人感觉没有什么本质区别，反而绕来绕去显得麻烦。
Code
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp(x,y) make_pair((x),(y))
#define fir first
#define sec second
const int N=1e5+10;
int n,B;
vector<int>s[N];
int buc[N*2];
vector<pii>p[N*2];
int brr[N*2],len;
void work()
{
scanf("%d",&n);B=0;len=0;
for(int i=1;i<=n;i++)
{
int j;scanf("%d",&j);
B+=j;
while(j--)
{
int x;scanf("%d",&x);
s[i].push_back(x);brr[++len]=x;
}
}
B=sqrt(B)/2;
sort(brr+1,brr+len+1);len=unique(brr+1,brr+len+1)-brr-1;
for(int i=1;i<=n;i++)
{
for(auto &x:s[i])
x=lower_bound(brr+1,brr+len+1,x)-brr;
}
pii ans=mkp(0,0);
for(int i=1;i<=n;i++)
{
if((int)s[i].size()<=B)continue;
for(auto x:s[i])buc[x]=1;
for(int j=1;j<=n;j++)
{
if(j==i)continue;
bool cnt=0;
for(auto y:s[j])
{
if(buc[y])
cnt?ans=mkp(i,j),1:cnt=1;
}
}
for(auto x:s[i])buc[x]=0;
if(ans.fir)return printf("%d %d\n",ans.fir,ans.sec),void();
}
for(int i=1;i<=n;i++)
{
if((int)s[i].size()>B)continue;
for(int j=0;j<s[i].size();j++)
{
for(int k=j+1;k<s[i].size();k++)
{
p[min(s[i][j],s[i][k])].push_back(mkp(max(s[i][k],s[i][j]),i));
}
}
}
for(int i=1;i<=len;i++)
{
for(auto x:p[i])
buc[x.fir]?ans=mkp(buc[x.fir],x.sec),1:buc[x.fir]=x.second;
for(auto x:p[i])
buc[x.fir]=0;
if(ans.fir)return printf("%d %d\n",ans.fir,ans.sec),void();
}
return puts("-1"),void();
}
void clear()
{
for(int i=1;i<=n;i++)
s[i].clear();
for(int i=1;i<=len;i++)
p[i].clear();
}
int main()
{
int T;scanf("%d",&T);
while(T--)work(),clear();
return 0;
}
CF1528C Trees of Tranquillity
摘要：
-
性质：第一棵树上选一条从上到下的链上的结点。
-
转化：第二棵树不存在祖先关系等价于入栈出栈时间无交（无嵌套）。
-
贪心：若存在嵌套，取小区间不劣。
-
实现：在第一棵中 dfs，依据贪心策略加入、弹出；记录操作，回溯时撤销。
-
实现：用 set 存储点，依据入栈出栈序性质判断区间关系。
本题的两个核心分别是：入栈出栈序性质的使用、使用 set 维护两两不交或嵌套区间。以下所有“入栈出栈”相关均指第二棵树，并用 \(in,out\) 分别表示入栈出栈时间，也即两者构成的区间的端点。
首先，两两存在祖先关系一定对应了一条链。于是我们可以在第一棵树上 dfs 了，接下来要处理第二棵树。
由于 dfs 入栈出栈序的性质，如果存在祖先关系，则祖先的入栈出栈区间包含后代的区间。考虑贪心，如果两个区间出现冲突，选小的区间一定是不劣的。
如何维护区间呢？请使用 stl set。有大佬手写红黑树我没有任何意见。
在 set 中，我们将点按 \(in\) 排序。判断区间 \(u\) 内是否有区间的方式是，lower_bound 找到第一个 \(v\) 使得 \(in_v\) 大于 \(in_u\) ，查看 \(out_v\) 是否在 \(out_u\) 之前；而判断是否被包括的方式是，lower_bound \(u\) 后将指针 it--，查看前一个元素的信息并依样判断。
需要注意，如果不存在想找的元素，指针会返回 set.begin 和 set.end，注意特判。另外，由于我们时刻保证区间无交，两种判断一次即可，但对于更加一般的问题可能包含多个或被多个包含，具体问题具体分析。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
struct edge{int to,nxt;};
edge e[N];int head[N],tot;
int in[N],out[N],cnt;
vector<int>ee[N];
int n,ans;
set< pair<int,int> >s;
vector< pair<int,char> >opt[N];
#define Pair(_) (make_pair(in[(_)],(_)))
void add(int u,int v)
{
e[++tot]={v,head[u]};head[u]=tot;
}
void dfs0(int u,int pa)
{
in[u]=++cnt;
for(auto v:ee[u])
dfs0(v,u);
out[u]=++cnt;
}
int check(int u)// 0 -> 可以加入；-1 -> 不可加入；x -> 需要删去 x
{
auto it=s.lower_bound(Pair(u));
if(it!=s.end()&&out[it->second]<out[u])
return -1;
if(it==s.begin())
return 0;
it--;
if(out[it->second]<in[u])return 0;
if(out[it->second]>out[u])return it->second;
return -2;
}
void dfs1(int u,int pa)
{
int flag=check(u);
if(flag>=0)
{
s.insert(Pair(u)),
opt[u].push_back(make_pair(u,'A'));
if(flag>0)
s.erase(Pair(flag)),
opt[u].push_back(make_pair(flag,'D'));
}
ans=max(ans,(int)s.size());
for(int i=head[u];i;i=e[i].nxt)
{
dfs1(e[i].to,u);
}
for(auto v:opt[u])
{
if(v.second=='A')//之前 Add
s.erase(Pair(v.first));
else if(v.second=='D')//之前 Delete
s.insert(Pair(v.first));
}
opt[u].clear();
}
void clear()
{
for(int i=1;i<=n;i++)
in[i]=out[i]=head[i]=0,ee[i].clear();
tot=cnt=0;
s.clear();
ans=0;
}
void work()
{
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
int u;scanf("%d",&u);
add(u,i);
}
for(int i=2;i<=n;i++)
{
int u;scanf("%d",&u);
ee[u].push_back(i);
}
dfs0(1,0);
for(int i=head[1];i;i=e[i].nxt)
{
dfs1(e[i].to,0);
}
printf("%d\n",ans);
}
int main()
{
int T;scanf("%d",&T);
while(T--)
work(),clear();
return 0;
}
CF1485F Copy or Prefix Sum
摘要：
-
从值域入手设计 DP 状态。
-
分析 DP 的性质，采用数据结构维护并转移。
-
本题卡哈希，请使用 map 保证复杂度。
这题似乎不太能从第几个、选什么来 DP，依据 \(b\) 数组的相互关系也不太可做，不得不从值域入手，然而值域 \(10^9\)。先试试吧，万一有惊喜呢？DP 题只想出暴力肯定要挖掘一下啊。
设 \(f_{i,j}\) 表示符合了 \(b_1\) 到 \(b_i\) 的限制，\(\sum a_x = j\) 的方案数，转移如下：
发现我们似乎不需要真的遍历值域，同时存储 \(i\) 这一维是无用的。状态改为\(f_j\)。第一个转移相当于全局平移，只需要记录 \(\Delta j\)，表示已经平移了多少，每次将 \(\Delta j\) 加上 \(b_i\)，访问时由 \(j\) 变为 \(j-\Delta j\)。对于第二个转移，记录全局 \(sum\) 可以解决。
那么如何存储 \(f\) 呢？使用 map 即可。本题中，unordered_map、gp_hash_table、cc_hash_table 均超时。因为所有哈希表是可以被卡的，然而 map 的复杂度固定。衷心建议，在复杂度允许的情况下尽量使用 map，哈希实在有些玄学。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10,mod=1e9+7;
int T,n,b[N];map<LL,int>dp;
void work()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
dp[b[1]]=1;int sum=1;LL offset=0;
for(int i=2;i<=n;i++)
{
offset+=-b[i];
long long tmp=dp[b[i]+offset];
dp[b[i]+offset]=sum;
(sum+= ((sum-tmp+mod)%mod))%=mod;
}
printf("%d\n",sum);
}
int main(){cin>>T;while(T--)work(),dp.clear();return 0;}
CF1499E Chaotic Merge
摘要：
- 暴力转移题中式子，发现答案只与 \(r_1,r_2\) 有关。
- 去掉状态中 \(l_1,l_2\)，加入其它状态：上一个选了什么，总共选过什么。
首先尝试暴力转移题里给出的式子，容易发现，每次新加入一个字符时，需要讨论的只有结尾的状态，因为无论最初从哪里开始，只要不相邻，都不需要管。
因为需要记录上一个选了什么，所以加入一维 \(0/1\) 表示末尾的字符来自 \(x/y\) ；因为只有 \(x,y\) 都选过才合法，所以加入一维 \(0/1/2/3\)，用二进制表示 \(x/y\) 是否选过。
综上，设 \(f[i][j][0/1][k]\) 表示： “ 当前 \(x\) 串选到了第 \(i\) 个，\(y\) 串选到了第 \(j\) 个，\(z\) 串的末尾字符来自 \(x(0)/y(1)\)，已经选过了什么 ” 的方案数。
此处采用了由当前的状态向以后的状态转移，考虑是否能将 \(x/y\) 的下一字符加入，若能则考虑影响。具体地，转移时枚举 \(k\)，若当前 \(i/j\) 不是字符串结尾，并且与上一位不同，即可加入，由当前状态确认转移给谁。转移如下：
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
{
if(i<n)
(dp[i+1][j][0][1]+=1)%=mod;
if(j<m)
(dp[i][j+1][1][2]+=1)%=mod;
for(int k=0;k<4;k++)
{
if(i<n&&s[i]!=s[i+1])
(dp[i+1][j][0][k|1]+=dp[i][j][0][k])%=mod;
if(i<n&&t[j]!=s[i+1])
(dp[i+1][j][0][k|1]+=dp[i][j][1][k])%=mod;
if(j<m&&s[i]!=t[j+1])
(dp[i][j+1][1][k|2]+=dp[i][j][0][k])%=mod;
if(j<m&&t[j]!=t[j+1])
(dp[i][j+1][1][k|2]+=dp[i][j][1][k])%=mod;
}
}
这里提供一种比较简洁的加法取模写法：
a=(a+b)%mod 可以写成 (a+=b)%=mod，可以避免大量重复导致的眼花甚至错误。
Code
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=1010;
int n,m;
char s[N],t[N];
int dp[N][N][2][4];
// s 串计算到 i；t 串计算到 j；z 的上一位来自 s/t；已经选了 s/t（00，01，10，11）；
int main()
{
scanf("%s%s",s+1,t+1);
n=strlen(s+1),m=strlen(t+1);
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
{
if(i<n)
(dp[i+1][j][0][1]+=1)%=mod;
if(j<m)
(dp[i][j+1][1][2]+=1)%=mod;
for(int k=0;k<4;k++)
{
if(i<n&&s[i]!=s[i+1])
(dp[i+1][j][0][k|1]+=dp[i][j][0][k])%=mod;
if(i<n&&t[j]!=s[i+1])
(dp[i+1][j][0][k|1]+=dp[i][j][1][k])%=mod;
if(j<m&&s[i]!=t[j+1])
(dp[i][j+1][1][k|2]+=dp[i][j][0][k])%=mod;
if(j<m&&t[j]!=t[j+1])
(dp[i][j+1][1][k|2]+=dp[i][j][1][k])%=mod;
}
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
ans+=dp[i][j][0][3];ans%=mod;
ans+=dp[i][j][1][3];ans%=mod;
}
printf("%d\n",ans);
return 0;
}
CF1536E Omkar and forest
摘要：
-
性质：所有填 \(0\) 的位置确定之后，一定只有一种情况或无解，无解当且仅当零个 \(0\)。
-
\(cnt\) 个‘\(\#\)’，每个有两种安排，所以 \(2^{cnt}\)，并特判全为\('\#'\)。
神奇的思路。
如果性质成立，那么只需计算一次快速幂，并特判全是 \(\#\) 的情况（只有这种情况无解），设 \(cnt\) 为 ‘\(\#\)’ 的个数，答案为 $ 2^{cnt} - [cnt=nm] $。
以下是性质的证明。
事实上这就是 bfs 的描述证明啥。
类比边权为 \(1\) 的多源 bfs。从 填完 \(0\) 开始， 每次将周围的一圈更新最短路，由于 bfs 的性质，最后一定得到唯一的合法解。
唯一性来源于最短路；合法来源于边权为 \(1\)，即每一个 \(dis\) 不为 \(0\) 的点必由相邻的 \(dis\) 更小的点转移来，且不存在相邻两点 \(dis\) 之差超过 \(1\)。
Code
#include<bits/stdc++.h>
using namespace std;
const int &mod=1e9+7;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T,n,m,mp;char c;
int cnt=0,ans=0,flag=0;
cin>>T;while(T--)
{
cin>>n>>m;mp=n*m;
while(mp--)
cin>>c,cnt+=(c=='#');
if(cnt==n*m)flag=1;
ans=1;
while(cnt--)(ans<<=1)%=mod;
ans-=flag;
printf("%d\n",ans);
cnt=ans=flag=0;
}
return 0;
}
CF1523D Love-Hate
摘要：
-
对于某个合法答案，选 \(T\) 个人枚举子集，最终没访问到的概率是 \(2^{-T}\)，所以可以随机化。
-
每次随机，计算所有人与此人的交集，求超集个数不少于 \(\lceil \frac{n}{2} \rceil\) 的最大集合。
-
枚举子集 \(3^p\)，改为高维前缀和优化至 \(n \times 2^n\)。
tips：超集是指包含当前集合的集合。
抽象题。当时在 tag 里看到 probabilities 的时候还疑惑怎么会有概率，结果是随机化。
一个合法答案定义为，被至少 \(\lceil \frac{n}{2} \rceil\) 个人的集合包含。那么若本次没有选中，下次仍然没有选中的概率就是本次的一半，而 \(2^{-50} \approx 8.88 \times 10^{-16}\)…………所以随机化可过。不如说只要没写挂就很难错。
每次选中一个人，然后检查 \(n\) 个人，每个人算出他与选中的人的集合交集。
更快速地计算超集要用到高维前缀和。
首先考虑二维前缀和，可以把两维拆开分别做；进一步地，如果要求子集个数，设 集合对应着长度为 \(p\) 的 01 串，则可以视作 求一个 \(p\) 维的，每一维长度为 \(1\) 的 高维前缀和。
对于求子集个数，显然可以转为前缀和形式。对于求超集个数，如果倒着处理，即求前缀和的方向从 \(0 \rightarrow 1\) 变成 \(0 \leftarrow 1\)，同样可以利用前缀和处理。这样复杂度是 \(p\times 2^p\)。
求超集代码：
for(int j=0;j<vrr.size();j++)
{
for(int i=1;i<=lim;i++)
{
if( (i & (1<<j)) == 0 )
f[i] += f[i ^ (1<<j)];
}
}
细节挺多，建议慢点写，但一定要准。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
int n,m,p;char ss[N];
LL a[N];int f[1<<15];
bool vis[N];
vector<int>vrr;
#define __count __builtin_popcount
#define __countLL __builtin_popcountll
mt19937 rnd(time(0));
int get()
{
LL y=rnd()%n+1;return y;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>p;
for(int i=1;i<=n;i++)
{
cin>>ss+1;
for(int j=1;j<=m;j++)
if(ss[j]=='1')a[i]^=1LL<<(j-1);
}
LL ans=0;
int it,T=min(50,n);
int cnt=0;
while(T--&&cnt<n)
{
it=get();++cnt;
if(a[it]==0)continue;
vrr.clear();
for(int j=1;j<=m;j++)
{
if(a[it]& (1LL<<(j-1)) )
vrr.push_back(j);
}
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
{
int s=0;
for(int j=0;j<vrr.size();j++)
{
if( a[i] & (1LL<<(vrr[j]-1)) )
s^=1<<j;
}
f[s]++;
}
int lim=1<<vrr.size();lim--;
for(int j=0;j<vrr.size();j++)
{
for(int i=1;i<=lim;i++)
{
if( (i & (1<<j))==0 )
f[i] += f[i ^ (1<<j)];
}
}
int now=0;
for(int i=1;i<=lim;i++)
{
if(f[i]*2>=n && __count(i) > __count(now) )
now = i;
}
if( __count(now) > __countLL(ans) )
{
ans=0;
for(int i=0;i<vrr.size();i++)
{
if(now&(1<<i))ans|=(1LL<<(vrr[i]-1));
}
}
}
for(int i=1;i<=m;i++)
{
if(ans&(1LL<<(i-1)))cout<<"1";
else cout<<"0";
}cout<<endl;
return 0;
}
CF1419E Fib-tree
摘要：
-
转化：如果一个树合法，那么一定能经合法过程全拆成单点。
-
性质：每次拆大小 \(Fib_i\) 的，一定拆成 \(Fib_{i-1},Fib_{i-2}\)。
-
每次拆只有两种拆法且等价。所以暴力即可，复杂度 \(nlog_\phi n\)。
抽象结论题。说它抽象是因为证明很多比较抽象，感觉不严谨又说不明白看不懂。
我们考虑一个树合法，则会一直在合法状态下断成 \(n\) 个点，所以如果能有一种方式，使得可以在最优策略下模拟，即如果做出来了自然有解，而做不出来也一定无解，那么这题就做完了，因为 Fib 增长很快，是 \(\phi^n\) 的，所以每次割之前重新跑一遍 dfs 维护真子树，复杂度是 \(nlog_\phi n\)。此处 \(\phi\) 是黄金分割比，详情请百度 Fibonacci Sequence 相关知识。
性质一，\(F_{n}\) 一定只能拆成 \(F_{n-1}\) 和 \(F_{n-2}\)
考虑斐波那契数列（以下简称 Fib）的性质。如果要拆 \(F_{n}\) 一定只能拆成 \(F_{n-1}\) 和 \(F_{n-2}\)，比较显然，可以通过解方程的方式证明（官方题解），也可以简单考虑：如果不在这两个里选，那无论选什么，减完的数都会大于这两个，没得选了。
性质二：如果存在两条边，先切哪条都是等价的
接着考虑怎么拆，每次随便找一个 \(Fib_{n-1}\) 或者 \(Fib_{n-2}\) 拆行不行？行，然而找到的大部分不是非常严谨（主要是我看不懂）的证明，包括官方题解，但还有一个算挺靠谱的：
这个是用归纳法证的。首先对于 \(Fib_3\) 是满足的，这是真显然。
假设直到 \(Fib_{n-1}\) 都满足性质二，且对于\(Fib_n\) 有 \(a,b\) 两条可以切出 \(Fib_{n-2}\) 的边。
如果先切 \(a\)，之后 \(b\) 在 \(Fib_{n-1}\) 里面，由于性质二，可以立马切 \(b\)；如果先切 \(b\) 那么可以立马切 \(a\)。
综上，在前提条件下无论先切哪条都可以紧接着把另一条切了，于是两种切法等价了。
如果只有一个合法方案，直接切就可以了。
有的同学可能会想，随便找一个点当根，不会存在由于选的根在应切掉的子树内而找不到的情况吗？事实上我们相当于枚举了每一条边，所以不会有漏掉的情况。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int Fib[]={0,1,1,2,3,5,8,13,21,34,55,89,
144,233,377,610,987,1597,2584,4181,6765,
10946,17711,28657,46368,75025,121393,196418};
bool mp[N];
void init_Fibonacci()
{
for(int i=1;i<=27;i++)
mp[Fib[i]]=1;
}
int n;
struct edge{int to,nxt;};
edge e[2*N];int head[N],tot;
void add(int u,int v)
{
e[++tot]={v,head[u]};head[u]=tot;
}
int fa[N],sz[N],dfn[N],rk[N],dc;bool cut[N];
void dfs0(int u,int pa)
{
fa[u]=pa;sz[u]=1;rk[dfn[u]=++dc]=u;
for(int i=head[u];i;i=e[i].nxt)
if ( (e[i].to^pa) and (!cut[e[i].to]) )
dfs0(e[i].to,u),sz[u]+=sz[e[i].to];
}
bool dfs1(int u)
{
if(sz[u]==1)
{
return true;
}
if(mp[sz[u]]==0)
{
return false;
}
for(int i=dfn[u]+1;;)
{
int v=rk[i];
if(cut[v])
{
i+=sz[v];
}
else if(mp[sz[v]] and mp[sz[u]-sz[v]])
{
cut[v]=1;dc=0;dfs0(u,fa[u]);dfs0(v,fa[v]);
bool res1=dfs1(u),
res2=dfs1(v);
return res1 && res2;
}
else
{
i++;
}
if(i>=dfn[u]+sz[u])break;
}
// printf(" at %d %d,false\n",u,sz[u]);
return false;
}
void debug()
{
return ;
for(int i=1;i<=n;i++)printf("%d ",fa[i]);puts("");
for(int i=1;i<=n;i++)printf("%d ",sz[i]);puts("");
for(int i=1;i<=n;i++)printf("%d ",dfn[i]);puts("");
for(int i=1;i<=n;i++)printf("%d ",rk[i]);puts("");
}
int main()
{
init_Fibonacci();
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs0(1,0);
bool ans = dfs1(1);
puts(ans?"YES":"NO");
debug();
return 0;
}
CF1527D Mex Tree
摘要：
-
T转化 ：\(mex\) 为 \(x\) 的等于 包含到 \(x-1\) 的减去包含到 \(x\) 的。
-
以 \(0\) 为根模拟路径，并用 \(size\) 计算方案数。
-
注意细节。
套路好题。
首先考虑，如果使 \(mex\) 为 \(0\)，只需不经过 \(0\) 即可，简单 DP 维护子树内路径可解。
接下来考虑继续推，如果 \(mex_{path}=x\) 那么需要包含 \([1,x-1]\) 所有点，并不包含 \(x\)，其余点任意。因此，我们考虑维护 \(f_i\) 表示包含 \([1,i]\) 所有点的路径数。
接下来是比较重要的地方，设 \(mex_x\) 为 \(mex=x\) 的方案数，那么有转化：
于是做完了。
一些实现：
\(f_{i-1} \rightarrow f_{i}\) 时，路径一定会变得更长或无解，因此我们只需每次判断 \(i\) 与 之前的路径端点的祖先关系，并用两端点外侧的 \(size\) 相乘计算答案。
具体地，如果已经在路径中就继承，如果是端点的后代就将端点拽下来，如果 \(LCA\) 在路径中间就说明从这里开始都无解。注意特判一端在 \(0\) 的情况。细节略多但不多。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+10;
struct edge {int to,nxt;};
edge e[N*2];int head[N],tot;
void add(int u,int v)
{
e[++tot]={v,head[u]};head[u]=tot;
}
int n,fa[N],dep[N],sz[N];
int dfn[N],dc,st[N][25];
LL sum[N],f[N];int L,R;
void dfs0(int u,int pa)
{
dfn[u]=++dc;st[dc][0]=pa;
fa[u]=pa;dep[u]=dep[pa]+1;sz[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;if(v==pa)continue;
dfs0(v,u);
sum[u]+=1ll*(sz[u]-1)*sz[v];
sz[u]+=sz[v];
}
}
int get(int u,int v)
{
return (dfn[u]<dfn[v])?u:v;
}
void init()
{
for(int i=1;i<=__lg(n);i++)
for(int j=1;j+(1<<i)-1<=n;j++)
st[j][i]=get(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
int LCA(int u,int v)
{
if(u==v)return u;
if( (u=dfn[u]) > (v=dfn[v]) )swap(u,v);
int d=__lg(v-u);
return get(st[u+1][d],st[v-(1<<d)+1][d]);
}
bool flag=1;
void work()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs0(0,0);
init();
L=R=0;
LL all=0;
for(int i=0;i<n;i++)
all += sum[i]+sz[i]-1;
f[0]=sum[0]+sz[0]-1;
int it=0;
for(int i=1;i<n;i++)
{
int cal=LCA(i,L),car=LCA(i,R);
if(cal==L&&car==R)
{
int tmp=0;
if(!it)
for(int j=head[L];j;j=e[j].nxt)
{
int v=e[j].to;
if (dep[v]>dep[L]&&LCA(v,i)==v)
{
it=v;break;
}
}
tmp= (sz[0]-sz[L]+sz[L]-sz[it]);
f[i] = 1ll * tmp * sz[i];
R=i;
}
else
{
if(cal==L&&car==0)
{
f[i] = 1ll * sz[R] * sz[i];
L=i;
}
else if(car==R&&cal==0)
{
f[i] = 1ll * sz[L] * sz[i];
R=i;
}
else if(cal==i||car==i)
{
f[i]=f[i-1];
}
else
{
break;
}
}
}
printf("%lld ",all-f[0]);
for(int i=1;i<=n;i++)
{
printf("%lld ",f[i-1]-f[i]);
}puts("");
}
void clear()
{
for(int i=0;i<n;i++)
dep[i]=sz[i]=fa[i]=head[i]
=sum[i]=f[i]=0;
L=R=0;dc=0;tot=0;
}
signed main()
{
int T;scanf("%d",&T);
while(T--)
{
work(),clear();
}
return 0;
}
CF1499F Diameter Cuts
摘要：
-
暴力 DP，将子树内最大深度放入状态，看上去 \(O(n^2 m)\)。
-
任选优化，或者暴力。
-
转移时用临时数组存储避免算重。
DP 优化好题，有各式各样的优化方法，其实暴力就可过。
朴素 DP：
先考虑 DP 状态，由于关系到直径，所以考虑维护子树内最大深度。
至于子树直径或者说次长不需要考虑，因为可以由转移新的子节点时确定合法性。
具体地，设 \(f_{u,i}\) 表示 \(u\) 子树内最深（距离 \(u\)）为 \(i\) 的方案数。
我们考虑动态地向子树中加入子节点，并计算它割断与否的影响。
如果断开，互不影响，则有 ：
不断开，那么原先最长链加新的最长链不能超过 \(m\)。
注意，由于 \(f_{u,j}'\) 与 \(f_{u,j}\) 要分开，所以每次合并子节点时要开个 \(tmp\) 记录一下。
那么我们考虑优化……吗？我直接：
dfs(v,u);
for(int j=0;j<=min(mxd[u]-dep[u]);j++)
for(int k=0;k<=min(mxd[v]-dep[u]);k++)
复杂度分析：
好，在优化之前，我们想想复杂度。它真是 \(O(n^2 m)\) 吗？如是。它真 TLE 吗？如 T。
实际上复杂度是 \(O(n^2)\) 的：
如果这个点只有一个子节点就是 \(O(1)\)，这部分加起来 \(O(n)\)；如果有多个，那么相当于每次合并两个子树（可以看成两条链），代价为最大深度相乘。最坏情况显然是从大到小合并，是 \(\sum len \times \max - \max \le n \times \max\)，所以复杂度不超过 \(O(n^2)\)，所以做完了。
碎碎念：
这个问题可以看成是一些物品，每次合并两个，代价是两值相乘，结果是两值取最大。
接下来的部分已经与本题无关。
容易用调整法证明，代价最大是从大到小合并，代价最小是从小到大合并。
具体地，先排序，然后钦定合并为由小的指向大的，对于 \(a<b<c<d\)，讨论交换产生的影响。更具体地，\(ab,cd\) 相对于其余任意形式，代价方面和最大值方面都是更优的。 证明代价最大也可以直接取 \(max\)。
对于这道题，不止有这一种方式，也可以推推式子用前缀和、前后缀积等方法优化。
另外，由于本题 \(n,m\) 同级， \(O(n^2)\) 的转移是被允许的，然而如果 \(n\) 更大， \(m\) 更小，也许就需要一些别的方法变为 \(O(nm)\) 的做法。
长链剖分优化 DP：
首先说一下长链剖分。
和重链剖分差不多，以后代深度最深的点为重儿子，按长度剖分。相比重剖，长剖跳链是 $\sqrt n $ 的。可以支持 \(O(n\log n)-O(1)\) 求树上 \(k\) 级祖先，也可以优化与深度有关（包含深度维）的树上 DP。
假设 \(u\) 只有一个儿子 \(v\)，\(f[i][j]\) 为一个数组，其中 \(i,j\) 分别表示点和深度，比如：“\(i\) 子树内与 \(i\) 距离为 \(j\) 的点的数量”。
我们发现，\(f[u]\) 与 \(f[v]\) 长得差不多，把 \(f[v]\) 整体挪一位即可得到 \(f[u]\)。
具体地，\(f[u][0]=1,f[u][i]=f[v][i-1]\)。
那要不你俩用一个数组得了。
众所周知，指针有时候是个好东西。我们可以直接把 \(f[v]\) 指在 \(f[u]+1\) 的位置，这样到时候访问就不用重新算了。当然，也可以手动模拟指针，甚至有 vector 的 swap 写法。
于是，对于重儿子的信息，我们 \(O(1)\) 继承；对于轻儿子，也就是单独的一条长链，我们暴力转移。假设每转移一对点是 \(O(s)\) 的，那转移一条长链是 \(O(len\times s)\) 的，相当于每个点只在链顶并入链顶父亲时被转移一次，即 \(\sum len \times s = n \times s\)。
于是我们得到了时间 \(O(nm)\)、空间\(O(n)\) 的做法。注意，这种做法不支持在计算结束后任意访问某一节点的 \(f\) 数组，因为重儿子的数组会被父亲更新。
指针部分的代码：
int *f[N],*now,dp[N],tmp[N];
main()
dfs1(1,0);
now = dp;f[1]=now;now+=lev[1];//lev表示链长度（点数）
dfs2(1,0);
dfs2(int u,int v)
if(son[u])
{
f[son[u]] = f[u] + 1;
dfs2(son[u],u);
}
f[v] = now;now += lev[v];
for(int j=0;j<=min(lev[u]-1,m);j++)
for(int k=0;k<=min(lev[v]-1,m);k++)
细节：
一定注意子树内到根最长距离是链长（点数）减一，而不是链长。
如果是其他写法不会错，因为那里是空的。但如果使用了指针实现的长剖，就会把别的东西拿进来，症状为答案更大。
有一篇题解开了二倍空间，是因为两条长链之间空了一个，以弥补枚举时越界的问题。
Code
// LUOGU_RID: 132975308
#include<bits/stdc++.h>
using namespace std;
const int N=5010,M=5010;
const int mod=998244353;
int n,m;
int dep[N],mxd[N],lev[N],son[N];
int *f[N],*now,dp[N],tmp[N];
struct edge{int to,nxt;};
edge e[2*N];int head[N],tot;
void add(int u,int v)
{
e[++tot]={v,head[u]};head[u]=tot;
}
void dfs1(int u,int pa)
{
dep[u]=dep[pa]+1;
// lev[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;if(v==pa)continue;
dfs1(v,u);
if(lev[v]>lev[son[u]])son[u]=v;
}
lev[u]=lev[son[u]]+1;
}
void dfs2(int u,int pa)
{
f[u][0]=1;
//注意枚举时到 （节点数-1） lev-1
if(son[u])
{
f[son[u]] = f[u] + 1;
dfs2(son[u],u);
tmp[0]=0;
for(int i=0;i<=min(lev[son[u]]-1,m);i++)
{
(tmp[0]+=f[son[u]][i])%=mod;//f[u][0] <- sum
}
f[u][0]=tmp[0];
}
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;if(v==pa||v==son[u])continue;
f[v] = now;now += lev[v];
dfs2(v,u);
for(int j=0;j<=min(lev[u]-1,m);j++)
tmp[j]=0;
for(int j=0;j<=min(lev[u]-1,m);j++)
{
for(int k=0;k<=min(lev[v]-1,m);k++)
{
(tmp[j]+=1ll*f[u][j]*f[v][k]%mod)%=mod;
if(j+k+1<=m)
(tmp[max(j,k+1)]+=1ll*f[u][j]*f[v][k]%mod)%=mod;
}
}
for(int j=0;j<=min(lev[u]-1,m);j++)
(f[u][j]=tmp[j])%=mod;
//f[u][j] = tmp[j]，而非 += 因为状态逻辑上应包含已合并的全部子结点
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs1(1,0);
now = dp;f[1]=now;now+=lev[1];//加上节点数
dfs2(1,0);
int ans=0;
for(int i=0;i<=min(lev[1]-1,m);i++)
(ans+=f[1][i])%=mod;
printf("%d\n",ans);
return 0;
}