AtCoder Beginner Contest 287 解题报告
\(\text{By DaiRuiChen007}\)
A. Majority
用 map 分别统计两种字符串出现的次数并与 \(\left\lfloor\dfrac n2\right\rfloor\) 比较即可
时间复杂度 \(\Theta(n\log n)\)
#include<bits/stdc++.h>
using namespace std;
map <string,int> cnt;
signed main() {
int n;
cin>>n;
for(int i=1;i<=n;++i) {
string s;
cin>>s;
++cnt[s];
}
puts(cnt["For"]>(n/2)?"Yes":"No");
return 0;
}
B. Postal Card
用 map 先标记所有的 \(T_i\)，然后依次处理每个 \(S_i\) 的后 \(3\) 位，检查其是否被标记过，若被标记过则说明存在某个 \(T_j\) 与 \(S_i\) 的后 \(3\) 位匹配
时间复杂度 \(\Theta((n+m)\log m)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1001;
string s[MAXN];
map <string,bool> cnt;
signed main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>s[i];
int ans=0;
for(int i=1;i<=m;++i) {
string t;
cin>>t;
cnt[t]=true;
}
for(int i=1;i<=n;++i) if(cnt[s[i].substr(3,3)]) ++ans;
cout<<ans<<"\n";
return 0;
}
C. Path Graph?
判断一个图是否是链：要求图联通，且度数为 \(1\) 的点恰好 \(2\) 个，剩下的点度数都为 \(2\)
可以证明这些条件是充要的
第一个问题用并查集维护，第二问题直接算度数即可
时间复杂度 \(\Theta(n\alpha(n))\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
int deg[MAXN],dsu[MAXN];
inline int find(int x) {
if(dsu[x]==x) return x;
return dsu[x]=find(dsu[x]);
}
signed main() {
int n,m,tot=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) dsu[i]=i;
for(int i=1;i<=m;++i) {
int u,v;
scanf("%d%d",&u,&v);
++deg[u],++deg[v];
int x=find(u),y=find(v);
if(x!=y) ++tot,dsu[x]=y;
}
if(tot<n-1) {
puts("No");
return 0;
}
int cnt=0;
for(int i=1;i<=n;++i) {
if(deg[i]>2) {
puts("No");
return 0;
} else if(deg[i]==1) ++cnt;
}
puts(cnt==2?"Yes":"No");
return 0;
}
D. Match or Not
考虑将原问题拆分为：\(S\) 的前 \(i\) 个和 \(T\) 的前 \(i\) 个可以匹配，且 \(S\) 的后 \(|T|-i\) 个可以和 \(T\) 的后 \(|T|-i\) 个匹配
而注意到对 \(S[1\cdots i]\) 和 \(T[1\cdots i]\) 匹配可以拆成：先对 \(S[1\cdots i-1]\) 和 \(T[1\cdots i-1]\) 匹配，然后对 \(S_i,T_i\) 进行匹配
因此第一个问题可以先前缀扫一遍算出所有 \(i\) 的答案，第二根问题类似扫一遍后缀即可
预处理之后每个问题把前后缀拼起来即可
时间复杂度 \(\Theta(|S|+|T|)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+1;
char s[MAXN],t[MAXN];
bool pre[MAXN],suf[MAXN];
signed main() {
scanf("%s%s",s+1,t+1);
int m=strlen(s+1),n=strlen(t+1);
pre[0]=suf[0]=true;
for(int i=1;i<=n;++i) {
if(s[i]==t[i]||s[i]=='?'||t[i]=='?') pre[i]=true;
pre[i]&=pre[i-1];
}
for(int i=1;i<=n;++i) {
if(s[m-i+1]==t[n-i+1]||s[m-i+1]=='?'||t[n-i+1]=='?') suf[i]=true;
suf[i]&=suf[i-1];
}
for(int i=0;i<=n;++i) {
puts((pre[i]&&suf[n-i])?"Yes":"No");
}
return 0;
}
E. Karuta
多次求 \(\operatorname{lcp}\)，直接建立 Trie，统计每个位置被访问的次数
对于每个 \(S_i\) 求出：从 \(\operatorname{start}\to \operatorname{end}_i\) 的路径中被访问次数 \(\ge 2\)（\(S_i\) 访问一次 \(S_j\) 访问一次）的所有节点中深度最大的一个即可
时间复杂度 \(\Theta(\sum|S_i|)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1;
struct node {
int son[26],cnt,dep;
inline int& operator [](const int &i) { return son[i]; }
inline int& operator [](const char &ch) { return son[ch-'a']; }
} tr[MAXN];
int siz=0;
inline void insert(string s) {
int pos=0;
for(auto ch:s) {
if(!tr[pos][ch]) {
tr[pos][ch]=++siz;
tr[tr[pos][ch]].dep=tr[pos].dep+1;
}
pos=tr[pos][ch];
++tr[pos].cnt;
}
}
string s[MAXN];
signed main() {
int n;
cin>>n;
for(int i=1;i<=n;++i) {
cin>>s[i];
insert(s[i]);
}
for(int i=1;i<=n;++i) {
int pos=0,ans=0;
for(auto ch:s[i]) {
pos=tr[pos][ch];
if(tr[pos].cnt>1) ans=tr[pos].dep;
}
cout<<ans<<"\n";
}
return 0;
}
F. Components
首先有一个简单的 dp，\(dp_{i,0/1,j}\) 表示以 \(i\) 为根的子树，\(i\) 不选或选的情况下构成 \(j\) 个联通块的方案数，对于一条边 \(u\to v\)，转移的时候按如下的方式卷积：
\[\begin{aligned} dp'_{u,0,j+k}&\gets dp_{u,0,j}\times dp_{v,0,k}\\ dp'_{u,0,j+k}&\gets dp_{u,0,j}\times dp_{v,1,k}\\ dp'_{u,1,j+k}&\gets dp_{u,1,j}\times dp_{v,0,k}\\ dp'_{u,1,j+k-1}&\gets dp_{u,1,j}\times dp_{v,1,k}\\ \end{aligned} \]最后卷积完令 \(dp_{u}\gets dp'_{u}\)，继续和下一个 \(v\) 卷积
这样的复杂度是 \(\Theta(n^3)\) 的
但注意到我们每次卷积的上界其实不需要到 \(n\)，而是当前的 \(siz_u\) 和 \(siz_v\) 即可
这样优化之后可以证明时间复杂度是 \(\Theta(n^2)\) 的
因此维护 \(dp_{i,0/1,j}\)，每次以 \(siz_u,siz_v\) 为两维的上界暴力卷积转移即可
时间复杂度 \(\Theta(n^2)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5001,MOD=998244353;
vector <int> G[MAXN],dp[MAXN][2];
int siz[MAXN];
inline void dfs(int p,int f) {
siz[p]=1;
dp[p][0]=vector<int>{1,0};
dp[p][1]=vector<int>{0,1};
for(int v:G[p]) {
if(v==f) continue;
dfs(v,p);
vector <int> ret[2];
ret[0].resize(siz[v]+siz[p]+1,0);
ret[1].resize(siz[v]+siz[p]+1,0);
for(int j=0;j<=siz[p];++j) {
for(int k=0;k<=siz[v];++k) {
ret[0][j+k]=(ret[0][j+k]+dp[v][0][k]*dp[p][0][j]%MOD)%MOD;
ret[0][j+k]=(ret[0][j+k]+dp[v][1][k]*dp[p][0][j]%MOD)%MOD;
ret[1][j+k]=(ret[1][j+k]+dp[v][0][k]*dp[p][1][j]%MOD)%MOD;
if(j!=0||k!=0) ret[1][j+k-1]=(ret[1][j+k-1]+dp[v][1][k]*dp[p][1][j]%MOD)%MOD;
}
}
siz[p]+=siz[v];
dp[p][0]=ret[0],dp[p][1]=ret[1];
}
}
signed main() {
int n;
scanf("%lld",&n);
for(int i=1;i<n;++i) {
int u,v;
scanf("%lld%lld",&u,&v);
G[u].push_back(v),G[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;++i) printf("%lld\n",(dp[1][0][i]+dp[1][1][i])%MOD);
return 0;
}
G. Balance Update Query
以所有 \(a_i\) 作为下标，建立动态开点权值线段树
维护区间内 \(\sum b_i\) 和 \(\sum a_i\times b_i\) 的值，修改 \(b_i\) 就是普通的单点修操作，修改 \(a_i\) 相当于在原本的 \(a_i\) 上减去 \(b_i\) 并且在新的 \(a_i\) 的上加上 \(b_i\)，因此两种修改操作都可以转化成权值线段树上的单点修改
查询答案的时候在线段树上二分即可，过程类似主席树：
- 如果 \(k\) 小于等于右子树的 \(\sum b_i\)，那么直接优先走右子树
- 否则走左子树，递归 \(k\gets k-\sum b_i\)，并且加上全取右子树的 \(\sum a_i\times b_i\) 即可
时间复杂度 \(\Theta((n+q)\log V)\)，\(V\) 为 \(\{a_i\}\) 的值域
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+1,V=1e9;
struct SegmentTree {
struct node {
int sum,cnt,lson,rson;
node() { sum=0,cnt=0,lson=rson=0; }
} tree[MAXN*40];
int siz;
inline void pushup(int pos) {
tree[pos].sum=tree[tree[pos].lson].sum+tree[tree[pos].rson].sum;
tree[pos].cnt=tree[tree[pos].lson].cnt+tree[tree[pos].rson].cnt;
}
SegmentTree() { siz=0; }
inline void Modify(int u,int k,int l,int r,int &pos) {
if(!pos) pos=++siz;
if(l==r) {
tree[pos].cnt+=k;
tree[pos].sum+=u*k;
return ;
}
int mid=(l+r)>>1;
if(u<=mid) Modify(u,k,l,mid,tree[pos].lson);
else Modify(u,k,mid+1,r,tree[pos].rson);
pushup(pos);
}
inline int Query(int k,int l,int r,int pos) {
if(!pos) return 0;
if(tree[pos].cnt==k) return tree[pos].sum;
if(l==r) return l*k;
int mid=(l+r)>>1,val=tree[tree[pos].rson].cnt;
if(val>=k) return Query(k,mid+1,r,tree[pos].rson);
return Query(k-val,l,mid,tree[pos].lson)+tree[tree[pos].rson].sum;
}
} S;
int a[MAXN],b[MAXN];
signed main() {
int n,rt=0;
scanf("%lld",&n);
for(int i=1;i<=n;++i) {
scanf("%lld%lld",&a[i],&b[i]);
S.Modify(a[i],b[i],0,V,rt);
}
int q;
scanf("%lld",&q);
while(q--) {
int opt;
scanf("%lld",&opt);
if(opt==1) {
int x,y;
scanf("%lld%lld",&x,&y);
S.Modify(a[x],-b[x],0,V,rt);
a[x]=y;
S.Modify(a[x],b[x],0,V,rt);
}
if(opt==2) {
int x,y;
scanf("%lld%lld",&x,&y);
S.Modify(a[x],y-b[x],0,V,rt);
b[x]+=y-b[x];
}
if(opt==3) {
int x;
scanf("%lld",&x);
if(S.tree[rt].cnt<x) puts("-1");
else printf("%lld\n",S.Query(x,0,V,rt));
}
}
return 0;
}
Ex. Directed Graph and Query
首先看到这个问题先想离线询问，对于 \(t\) 从 \(1\) 枚举到 \(n\)，考虑标号 \(\le t\) 的图中 \(s_i\to t_i\) 是否联通，如果联通就用 \(t\) 更新
注意到这个过程实际上和 Floyd 传递闭包的过程是一致的，因此我们在 Floyd 传递闭包每次枚举完某个中转点 \(k\) 时，更新联通的 \(s_i\to t_i\) 的答案，注意 Floyd 传递闭包只能保证路径中转点 \(\le k\)，还需要判断 \(s_i,t_i\le k\)
时间复杂度 \(\Theta\left(nq+\dfrac{n^3}\omega\right)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2001,MAXQ=1e4+1;
bitset <MAXN> f[MAXN];
int s[MAXQ],t[MAXQ],ans[MAXQ];
signed main() {
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) f[i].set(i);
for(int i=1;i<=m;++i) {
int u,v;
scanf("%d%d",&u,&v);
f[u].set(v);
}
int q;
scanf("%d",&q);
for(int i=1;i<=q;++i) scanf("%d%d",&s[i],&t[i]);
for(int k=1;k<=n;++k) {
for(int i=1;i<=n;++i) {
if(f[i][k]) f[i]|=f[k];
}
for(int i=1;i<=q;++i) {
if(ans[i]==0&&(s[i]<=k&&t[i]<=k)&&(f[s[i]][t[i]])) ans[i]=k;
}
}
for(int i=1;i<=q;++i) printf("%d\n",ans[i]>0?ans[i]:-1);
return 0;
}