无聊瞎补简单套路题。
B.Aho-Corasick Automaton
感觉这题有点太水了，场上为什么没人过呢？？？
显然我们只需要对 Trie 树进行计数。尝试一层一层的加节点，我们容易设计出状态 $f(i,j,k)$ 表示选了 $i$ 层（即目前最大长度），此时有 $j$ 个节点，而最下面一层节点有 $k$ 个。转移就变得非常简单，枚举新加的点数 $l$ 进行转移：$f(i,j,k)\to f(i+1,j+l,l)\times g(k,l)$，其中 $g(k,l)$ 表示将 $l$ 个节点加在原先 $k$ 个上面的转移系数，我们容易预处理出来：$g(i,j)\to g(i+1,j+k)\times \binom{m}{k}$。总的时间复杂度为 $\mathcal O(n^3d)$。
你妈的还要特判 $n=1$ 吃屎去吧。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
using ll=long long;
const int N=2e5+10,K=70;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int T,n;
ll k,a[N],f[K][2];
int q[K];
void init()
{
memset(q,-1,sizeof(q));
memset(f,-1,sizeof(f));
}
int get(ll x)
{
int cnt=-1;
for(;x;x>>=1)cnt++;
return cnt;
}
int cmp(ll x,ll y)
{
for(int i=61;i>=0;i--)if((x>>i&1)^(y>>i&1))return i;
return -1;
}
ll dfs(int pos,bool lim)
{
bool bit=k>>pos&1;
if(pos<0)return 1;
ll &ans=f[pos][lim];
if(ans!=-1)return ans;
if(q[pos]==-1)
{
if(bit)return ans=dfs(pos-1,lim)+dfs(pos-1,0);
if(lim)return ans=dfs(pos-1,lim);
return ans=dfs(pos-1,0)<<1;
}
if(q[pos])
{
if(!bit&&lim)return ans=0;
return ans=dfs(pos-1,lim);
}
return ans=dfs(pos-1,lim&(bit==0));
}
void solve()
{
init();
read(n,k);
for(int i=1;i<=n;i++)read(a[i]);
int lim=-1;
for(int i=1;i<n;i++)
{
if(a[i]==a[i+1])continue;
int x=cmp(a[i],a[i+1]);
if(a[i]<a[i+1])
{
if(q[x]==1)return puts("0"),void();
q[x]=0;
}
else
{
if(q[x]==0)return puts("0"),void();
q[x]=1,lim=max(lim,x);
}
}
int st=get(k);
if(lim>st)return puts("0"),void();
printf("%lld\n",dfs(st,1));
}
int main()
{
read(T);
while(T--)solve();
return 0;
}
|
E.Centroid Tree
我太蠢了。
第一眼看是一个神秘智慧题，实际上真的他妈暗藏玄机。首先你会发现重心这个条件很难用（然后就卡住了）。但其实最关键的条件是 $p_i<i$（注意到这一点是最关键也是我感觉最阴的），由此我们可以倒序枚举每个点，以此从下往上构造整棵树。然后你会发现重心这个条件其实是没有用的，我们只需要知道哪些点在儿子的子树里面即可。具体的我们用并查集维护当前连通块的根，然后不断向上合并就行了。时间复杂度 $\mathcal O(n)$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=2e5+10;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int T,n;
int fa[N];
vector<int>e[N];
int get(int x)
{
if(fa[x]==x)return x;
return fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
x=get(x),y=get(y);
fa[y]=x;
}
void init()
{
for(int i=1;i<=n;i++)fa[i]=i,e[i].clear();
}
void solve()
{
read(n);
init();
for(int x=1,m,y;x<=n;x++)
{
read(m);
while(m--)
{
read(y);
e[x].push_back(y);
}
}
for(int i=n;i;i--)
{
for(auto x:e[i])
{
int j=get(x);
printf("%d %d\n",i,j);
merge(i,j);
}
}
}
int main()
{
read(T);
while(T--)solve();
return 0;
}
|
F.Perfect Square
简单题目。
一个简单的想法是将每个数分解成质因数进行考虑。容易发现每个质因子的贡献是可以独立计算的，于是我们把对每个质因子分别计算，其实这就是说一个类背包过程，只不过我们只关心奇偶。时间复杂度瓶颈应该是分解质因数的的 $\mathcal O(n\sqrt{m})$，但显然完全跑不满。实测跑的很快。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1e6+10,mod=1e9+7;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m;
int a[N];
bool vis[N];
int cnt,prime[N],pos[N];
int f[N][2],g[2];
inline void adj(int &x){x+=x>>31&mod;}
inline int qpow(int x,int k)
{
int res=1;
while(k)
{
if(k&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;
k>>=1;
}
return res;
}
void get_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(!vis[i])prime[++cnt]=i,pos[i]=cnt;
for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(!(i%prime[j]))break;
}
}
}
inline void divide(int x)
{
if(x==1)return ;
for(int i=1;prime[i]*prime[i]<=x;i++)
{
int t=0;
int p=prime[i];
while(x%p==0)t++,x/=p;
g[0]=f[i][0];
g[1]=f[i][1];
for(int j=1;j<=t;j++)
{
if(j&1)
{
adj(f[i][0]+=1ll*qpow(p,(j+1)>>1)*g[1]%mod-mod);
adj(f[i][1]+=1ll*qpow(p,j>>1)*g[0]%mod-mod);
}
else
{
adj(f[i][0]+=1ll*qpow(p,j>>1)*g[0]%mod-mod);
adj(f[i][1]+=1ll*qpow(p,j>>1)*g[1]%mod-mod);
}
}
}
if(x==1)return ;
int i=pos[x];
g[0]=f[i][0];
g[1]=f[i][1];
adj(f[i][0]+=1ll*x*g[1]%mod-mod);
adj(f[i][1]+=g[0]-mod);
}
int main()
{
read(n);
for(int i=1;i<=n;i++)read(a[i]),m=max(a[i],m);
get_prime(m);
for(int i=1;i<=cnt;i++)f[i][0]=1;
for(int i=1;i<=n;i++)divide(a[i]);
int ans=1;
for(int i=1;i<=cnt;i++)ans=1ll*ans*f[i][0]%mod;
printf("%d\n",ans);
return 0;
}
|
G.Increasing Sequence
$k$ 的限制一眼数位 DP。刚开始在往 01-Tire 上面想，但发现不好做并且根本每必要（。注意到我们只需要考虑相邻的两个数之间满足 $a_i \oplus x \leq a_{i+1} \oplus x$ 即可。显然我们只需要考虑 $a_i$ 和 $a_{i+1}$ 最高的不同的一位即可（并且这样的条件是充分的）。那么现在问题转换为我们需要强制 $x$ 的某些位必须为 $0/1$，然后进行计数。直接数位 DP 即可，时间复杂度为 $\mathcal O(n\log V)$，其中 $V$ 为值域。
注意可能存在 $k=0$，卡了半天无语了。。。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
using ll=long long;
const int N=2e5+10,K=70;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int T,n;
ll k,a[N],f[K][2];
int q[K];
void init()
{
memset(q,-1,sizeof(q));
memset(f,-1,sizeof(f));
}
int get(ll x)
{
int cnt=-1;
for(;x;x>>=1)cnt++;
return cnt;
}
int cmp(ll x,ll y)
{
for(int i=61;i>=0;i--)if((x>>i&1)^(y>>i&1))return i;
return -1;
}
ll dfs(int pos,bool lim)
{
bool bit=k>>pos&1;
if(pos<0)return 1;
ll &ans=f[pos][lim];
if(ans!=-1)return ans;
if(q[pos]==-1)
{
if(bit)return ans=dfs(pos-1,lim)+dfs(pos-1,0);
if(lim)return ans=dfs(pos-1,lim);
return ans=dfs(pos-1,0)<<1;
}
if(q[pos])
{
if(!bit&&lim)return ans=0;
return ans=dfs(pos-1,lim);
}
return ans=dfs(pos-1,lim&(bit==0));
}
void solve()
{
init();
read(n,k);
for(int i=1;i<=n;i++)read(a[i]);
int lim=-1;
for(int i=1;i<n;i++)
{
if(a[i]==a[i+1])continue;
int x=cmp(a[i],a[i+1]);
if(a[i]<a[i+1])
{
if(q[x]==1)return puts("0"),void();
q[x]=0;
}
else
{
if(q[x]==0)return puts("0"),void();
q[x]=1,lim=max(lim,x);
}
}
int st=get(k);
if(lim>st)return puts("0"),void();
printf("%lld\n",dfs(st,1));
}
int main()
{
read(T);
while(T--)solve();
return 0;
}
|
J.Sum of Squares of GCDs
本场最难感觉也是最有趣的一道题。但我不是数据结构大蛇。
看到 $\gcd$ 确实容易想到进行一些数论转化。考虑莫比乌斯变换，构造 $\sum_{d|n}f(d)=n^2$。完整一点的过程是：
构造 $f(n)$ 使用莫比乌斯反演即可得到：$f(n)=\sum_{d|n}\mu(d)d^2 $。通过积性函数性质通过线性筛我们容易在 $\mathcal O(n)$ 内预处理出来 $f(n)$（但这个显然不是瓶颈）。
我们显然是不可能对于每次询问都枚举一遍 $d$，所以尝试将询问离线，问题的关键就变成了求 $d$ 对每个询问 $\sum_{i=l}^r\sum_{j=L}^R [d|a_i][d|b_j]$ 的贡献。
注意到题目给出的很重要条件：即 $a$ 为一个排列。我们考虑平衡规划（即根号分治），考虑分界为 $B$：
- 对于 $d\le B$，将答案变换为 $(\sum_{i=l}^r[d|a_i])(\sum_{j=L}^R [d|b_j])$，那么我们只需要求 $\sum_{i=1}^n[d|a_i],\sum_{i=1}^n[d|b_j]$（即前缀和）。我们直接暴力枚举后计算前缀和然后查询，这一部分的时间复杂度为 $\mathcal O((n+q)B)$。
- 对于 $d>B$。注意到我们不能对于每个 $d$ 查询一遍了，但是，我们直接暴力枚举所有 $d$ 的倍数 $k$，这样的点数为 $\mathcal O(\frac{n^2}{B})$，然后我们找到 $k$ 在 $a,b$ 中对应位置 $pa_k,pb_k$，那么 $k$ 会对 $l\le pa_k\le r,L\le pb_k\le R$ 的询问产生 $f(d)$ 的贡献。这显然就是一个经典的二维数点，扫描线即可做到 $\mathcal O(\frac{n^2}{B}\log \frac{n^2}{B} +q\log \frac{n^2}{B})$。但是由于是单点修改，并且为了将平衡的思想贯彻到底，我们使用分块进行维护，使修改为 $\mathcal O(1)$，查询为 $\mathcal O(\sqrt{n})$，所以复杂度为 $\mathcal O(\frac{n^2}{B} +q\sqrt{n})$。
结合两种算法运用平衡规划，取 $B=\sqrt{n}$，所以时间复杂度为 $\mathcal O((n+q)\sqrt{n})$。
感觉确实还比较有意思，可能因为好久没做平衡规划的题目了:)。
I.String Duplication
SAM / SA 版题，太傻逼了，不说了。
M.Covering a Tree
显然我们尽可能选最浅的叶子就行了。一种方式是直接 DP，时间复杂度为 $\mathcal O(n)$；另一种做法是按照从浅到深给叶子排序后，从浅的叶子开始依次往上覆盖，瓶颈是排序的 $\mathcal O(n\log n)$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=2e5+10;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int T,n;
int fa[N],d[N];
bool son[N],p[N];
vector<int>leaf;
bool cmp(int x,int y)
{
return d[x]<d[y];
}
void init()
{
for(int i=0;i<=n;i++)son[i]=p[i]=0;
leaf.clear();
}
void solve()
{
read(n);
d[1]=1;
for(int i=2;i<=n;i++)
{
read(fa[i]);
d[i]=d[fa[i]]+1;
son[fa[i]]=1;
}
for(int i=1;i<=n;i++)if(!son[i])leaf.push_back(i);
sort(leaf.begin(),leaf.end(),cmp);
int ans=0;
p[1]=1;
for(auto x:leaf)
{
int res=0;
for(int i=x;!p[i];i=fa[i])res++,p[i]=1;
ans=max(ans,res);
}
printf("%d\n",ans);
init();
}
int main()
{
read(T);
while(T--)solve();
return 0;
}
|