视频讲解：BV1ya411S7KF
给定长度为 n n n 的数组 a a a ，可以进行任意次操作，每次操作选择一个整数 i ∈ [ 2 , n ] i\in[2,n] i∈[2,n] 将 a i a_i ai 修改为 a i − a i − 1 a_i-a_{i-1} ai−ai−1
问能否对所有 i ∈ [ 2 , n ] i\in[2,n] i∈[2,n] ，使得 a i = 0 a_i=0 ai=0 。
从左到右考虑。
若使得
a
1
=
0
a_1=0
a1=0 ，则必须
a
0
∣
a
1
a_0|a_1
a0∣a1 。
若使得
a
2
=
0
a_2=0
a2=0 ，则必须存在
k
∈
[
0
,
a
1
a
0
]
k\in[0,\frac{a_1}{a_0}]
k∈[0,a0a1] ，使得
(
a
1
−
k
∗
a
i
)
∣
a
2
(a_1-k*a_i)|a_2
(a1−k∗ai)∣a2 ，即
a
0
∣
a
2
a_0|a_2
a0∣a2 。
以此类推，必须对于所有
i
∈
[
2
,
n
]
i\in[2,n]
i∈[2,n] ，满足
a
0
∣
a
i
a_0|a_i
a0∣ai ，才存在合法方案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=110;
int a[MAXN];
int main()
{
int T,n,i,flag;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
flag=1;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]%a[1])
flag=0;
}
if(flag)
puts("YES");
else
puts("NO");
}
}
给定 n ( 1 ≤ n ≤ 1 0 5 ) ， l , r ( 1 ≤ l ≤ r ≤ 1 0 9 ) n(1 \leq n \leq 10^5)，l,r(1 \leq l \leq r \leq 10^9) n(1≤n≤105)，l,r(1≤l≤r≤109) ，构造长为 n n n 的数组 a 1 , a 2 , . . . , a n ( l ≤ a i ≤ r ) a_1,a_2,...,a_n(l \leq a_i \leq r) a1,a2,...,an(l≤ai≤r) ，使得 g c d ( i , a i ) gcd(i,a_i) gcd(i,ai) 均不同。
注意到 g c d ( i , a i ) ∈ [ 1 , i ] gcd(i,a_i)\in[1,i] gcd(i,ai)∈[1,i] ，因此若使得 g c d ( i , a i ) gcd(i,a_i) gcd(i,ai) 均不同，则必须 g c d ( i , a i ) = i gcd(i,a_i)=i gcd(i,ai)=i ，即 i ∣ a i i|a_i i∣ai 。
因此对于每个 i i i ，在 [ l , r ] [l,r] [l,r] 区间内寻找是否存在 i i i 的倍数即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100100;
int a[MAXN];
int main()
{
int T,n,l,r,i,flag;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&l,&r);
flag=1;
for(i=1;i<=n;i++)
{
a[i]=r/i*i;
if(a[i]<l)
{
flag=0;
break;
}
}
if(!flag)
puts("NO");
else
{
puts("YES");
for(i=1;i<=n;i++)
printf("%d ",a[i]);
puts("");
}
}
}
Doremy有 n n n 场考试，第 i i i 场考试只能在第 i i i 天进行，难度为 a i a_i ai 。初始IQ为 q ( 1 ≤ q ≤ 1 0 9 ) q(1 \leq q \leq 10^9) q(1≤q≤109) ，每场考试可以选择参加或不参加。 q > 0 q>0 q>0 时才能参加考试，若参加，则会产生以下影响：
求最多可以参加的考试数。
由于不论 a i a_i ai 多少，只要 a i > q a_i>q ai>q 都会使得 q q q 减少 1 1 1 ，因此贪心考虑，将降智考试全部排在最后即可。
可以简单证明，将一个降智考试从早调整到晚后，必定会产生不更差的结果。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100100;
int a[MAXN],ans[MAXN];
int main()
{
int T,n,q,i,now;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(ans,0,sizeof(int)*(n+5));
now=0;
for(i=n;i>=1&&now<q;i--)
{
ans[i]=1;
if(now<a[i])
now++;
}
for(i;i>=1;i--)
{
if(a[i]<=q)
ans[i]=1;
}
for(i=1;i<=n;i++)
printf("%d",ans[i]);
puts("");
}
}
初始给定包含 n n n 个非负整数的数组 a a a ，保证从小到大排列。
每次操作生成一个新的数组 b i = a i + 1 − a i b_i=a_{i+1}-a_i bi=ai+1−ai ，并从小到大排列，然后替换掉原有的 a a a 。
求 n − 1 n-1 n−1 次操作后，最终剩下的一个数是多少。
如果没有排列操作，那么是一个组合数问题。
有排列操作的情况下，会发现很容易生成 0 0 0 。在排列后，这些 0 0 0 都会移动到首部，可以想办法对其快速处理。
考虑序列
{
0
,
0
,
.
.
.
,
0
⏟
m
,
x
1
,
x
2
,
x
3
,
.
.
.
}
\{\begin{matrix}\underbrace{0,0,...,0}\\m\end{matrix},x_1,x_2,x_3,...\}
{
0,0,...,0m,x1,x2,x3,...}
进行一次差分操作后，在排列前，得到
{ 0 , 0 , . . . , 0 ⏟ m − 1 , x 1 , x 2 − x 1 , x 3 − x 2 , . . . } \{\begin{matrix}\underbrace{0,0,...,0}\\m-1\end{matrix},x_1,x_2-x_1,x_3-x_2,...\} { 0,0,...,0m−1,x1,x2−x1,x3−x2,...}
因此这些
0
0
0 采用一个计数器维护即可，不直接参与计算。
当序列中存在
0
0
0 时，在一次操作后，
0
0
0 的数量减
1
1
1 ，并且加入一个
x
1
x_1
x1 。
需要注意的是，在之后得到的
x
i
+
1
−
x
i
x_{i+1}-x_i
xi+1−xi 中，可能也会出现
0
0
0 ，统计这些新生成的
0
0
0 ，在最后加入到新序列中。
新旧序列可以采用滚动的优先队列维护。
由于
a
i
≤
M
=
5
⋅
1
0
5
a_i\leq M=5 \cdot 10^5
ai≤M=5⋅105 ，在一次操作后，最多得到
M
\sqrt{M}
M
个不同的数。
如果有相同的数，则在下次操作时，会得到
0
0
0 。
以此类推，每轮不同的数之和不超过
M
1
2
+
M
1
4
+
M
1
8
+
.
.
.
+
1
M^\frac{1}{2}+M^\frac{1}{4}+M^\frac{1}{8}+...+1
M21+M41+M81+...+1 ，总复杂度不超过
O
(
N
+
M
log
(
log
(
M
)
)
)
O(N+\sqrt{M} \log(\log(M)))
O(N+M
log(log(M))) 。
更严谨的复杂度证明，可以看thematdev的评论。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100100;
priority_queue<int> q[2];
int main()
{
int T,n,i,x,now,bef,zero,tmp,tmpzero;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
while(!q[0].empty())
q[0].pop();
zero=0;
for(i=1;i<=n;i++)
{
scanf("%d",&x);
if(x)
q[0].push(x);
else
zero++;
}
now=0;
while(q[now].size()>1)
{
while(!q[now^1].empty())
q[now^1].pop();
bef=q[now].top();
q[now].pop();
tmpzero=0;
while(q[now].size())
{
tmp=q[now].top();
q[now].pop();
if(bef-tmp)
q[now^1].push(bef-tmp);
else
tmpzero++;
bef=tmp;
}
now^=1;
if(zero)
{
zero--;
q[now].push(bef);
}
zero+=tmpzero;
}
if(q[now].size())
printf("%d\n",q[now].top());
else
printf("0\n");
}
}
有一个错误的最小生成树算法，伪代码为
vis := an array of length n
s := a set of edges
function dfs(u):
vis[u] := true
iterate through each edge (u, v) in the order from smallest to largest edge weight
if vis[v] = false
add edge (u, v) into the set (s)
dfs(v)
function findMST(u):
reset all elements of (vis) to false
reset the edge set (s) to empty
dfs(u)
return the edge set (s)
分别判断调用 f i n d M S T ( 1 ) , f i n d M S T ( 2 ) , . . . , f i n d M S T ( n ) findMST(1),findMST(2),...,findMST(n) findMST(1),findMST(2),...,findMST(n) 后，能否得到正确的最小生成树。
首先由于每条边权值不同，因此最小生成树是唯一的。
以最小生成树为基础，若边 ( u , v ) (u,v) (u,v) 不在最小生成树上，则 u u u 到 v v v 的链（不包含 u , v u,v u,v），及链上节点的分支子树上的点作为起点，会得到一个选择了边 ( u , v ) (u,v) (u,v) 的错误最小生成树。
只有当起点在 u , v u,v u,v 及其子树内，才会得到不选择边 ( u , v ) (u,v) (u,v) 的生成树（但也不一定是正确的）。
对于每条不在MST中的边，筛选掉非法的节点即可。
采用LCA+树上差分可以在
O
(
n
log
(
n
)
)
O(n\log(n))
O(nlog(n)) 复杂度内实现。
或者某些神奇的dfs写法，可以在
O
(
n
)
O(n)
O(n) 复杂度内实现。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=200200;
const int MAXM=20;
int fa[MAXN],dep[MAXN],pa[MAXN][MAXM],a[MAXN];
char ans[MAXN];
vector<int> e[MAXN];
pair<int,int> err[MAXN];
int findfa(int x)
{
if(fa[x]==x)
return x;
return fa[x]=findfa(fa[x]);
}
void dfs(int x,int p)
{
pa[x][0]=p;
for(int j=1;(1<<j)<=dep[x];j++)
pa[x][j]=pa[pa[x][j-1]][j-1];
for(int i=0;i<e[x].size();i++)
{
int son=e[x][i];
if(son==p)
continue;
dep[son]=dep[x]+1;
dfs(son,x);
}
}
int jump(int x,int step)
{
for(int j=MAXM-1;j>=0;j--)
{
if((1<<j)&step)
x=pa[x][j];
}
return x;
}
int lca(int x,int y)
{
if(dep[x]<dep[y])
swap(x,y);
x=jump(x,dep[x]-dep[y]);
if(x==y)
return x;
for(int j=MAXM-1;j>=0;j--)
{
if(pa[x][j]!=pa[y][j])
{
x=pa[x][j];
y=pa[y][j];
}
}
return pa[x][0];
}
void pushDown(int x,int p)
{
if(a[x])
ans[x]='0';
else
ans[x]='1';
for(int i=0;i<e[x].size();i++)
{
int son=e[x][i];
if(son==p)
continue;
a[son]+=a[x];
pushDown(son,x);
}
}
int main()
{
int n,m,i,cnt=0,u,v,root,lc;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
fa[i]=i;
while(m--)
{
scanf("%d%d",&u,&v);
if(findfa(u)==findfa(v))
{
err[cnt++]=make_pair(u,v);
}
else
{
fa[findfa(u)]=findfa(v);
e[u].push_back(v);
e[v].push_back(u);
}
}
dfs(root=1,0);
for(i=0;i<cnt;i++)
{
u=err[i].first;
v=err[i].second;
if(dep[u]<dep[v])
swap(u,v);
lc=lca(u,v);
if(lc==v)
{
a[jump(u,dep[u]-dep[v]-1)]++;
a[u]--;
}
else
{
a[root]++;
a[u]--;
a[v]--;
}
}
pushDown(root,0);
ans[n+1]=0;
printf("%s\n",ans+1);
}
给定包含
n
(
2
≤
n
≤
2000
)
n(2 \leq n \leq 2000)
n(2≤n≤2000) 个点的树，根节点为
1
1
1 。
树上的顶点构成集合
U
=
{
1
,
2
,
3
,
.
.
.
,
n
}
U=\{1,2,3,...,n\}
U={1,2,3,...,n} 。
每次操作，选择 U U U 的一个“部分虚树” T T T ，然后替换掉原有的 U U U 。
求对于 [ 1 , n − 1 ] [1,n-1] [1,n−1] 范围内每个整数 k k k ，恰好 k k k 次操作后，有多少种不同的方法使得 U = { 1 } U=\{1\} U={1} 。
答案对 p ( 1 0 8 ≤ p ≤ 1 0 9 + 9 ) p(10^8 \leq p \leq 10^9+9) p(108≤p≤109+9) 取模。
参考官方题解的做法
假设忽略 T ≠ U T\neq U T=U 的条件，即 T ⊆ U T\subseteq U T⊆U ，每次操作可以不删除任何点，以便进行DP转移。
设 d p x , i dp_{x,i} dpx,i 表示将 x x x 节点为根的子树在恰好 i i i 步后全部被删除的方案数。注意最后删除的节点不一定是 x x x 节点。
设
S
u
m
x
,
i
Sum_{x,i}
Sumx,i 表示将
x
x
x 节点为根的子树在
i
i
i 步之内全部被删除的方案数。有
S
u
m
x
,
i
=
∑
j
=
1
i
d
p
x
,
i
Sum_{x,i}=\sum_{j=1}^{i}{dp_{x,i}}
Sumx,i=j=1∑idpx,i
如果
x
x
x 最后在第
i
i
i 步才被删除，则方案数为
D
x
,
i
=
∏
u
∈
S
o
n
x
S
u
m
u
,
i
D_{x,i}=\prod_{u\in Son_x}{Sum_{u,i}}
Dx,i=u∈Sonx∏Sumu,i
如果 x x x 在之前就被删除，考虑枚举最后个被删除的点在 u ∈ S o n x u\in Son_x u∈Sonx 为根的子树中，此时其他儿子为根的子树中的点，必定在 x x x 之前被删除，枚举 x x x 在第 j j j 次操作后被删除。方案数为
∑ u ∈ S o n x d p u , i ∑ j = 1 i − 1 ∏ v ∈ S o n x , v ≠ x S u m v , j = ∑ u ∈ S o n x d p u , i ∑ j = 1 i − 1 D x , j S u m u , j \begin{align*} &\sum_{u\in Son_x}{dp_{u,i}\sum_{j=1}^{i-1}{\prod_{v\in Son_x,v \neq x}{Sum_{v,j}}}}\\ &=\sum_{u\in Son_x}{dp_{u,i}\sum_{j=1}^{i-1}{\frac{D_{x,j}}{Sum_{u,j}}}} \end{align*} u∈Sonx∑dpu,ij=1∑i−1v∈Sonx,v=x∏Sumv,j=u∈Sonx∑dpu,ij=1∑i−1Sumu,jDx,j
综上，得到DP转移式
d p x , i = D x , i + ∑ u ∈ S o n x d p u , i ∑ j = 1 i − 1 D x , j S u m u , j dp_{x,i}=D_{x,i}+\sum_{u\in Son_x}{dp_{u,i}\sum_{j=1}^{i-1}{\frac{D_{x,j}}{Sum_{u,j}}}} dpx,i=Dx,i+u∈Sonx∑dpu,ij=1∑i−1Sumu,jDx,j
特别的，对于根节点 1 1 1 ，由于必须 1 1 1 号点最后删除，因此转移式为 d p 1 , i = D 1 , i dp_{1,i}=D_{1,i} dp1,i=D1,i 。
以上可以用树形DP在 O ( n 2 ) O(n^2) O(n2) 复杂度内求解。
但是 d p 1 , k dp_{1,k} dp1,k 并不是最终解法，因为一开始忽略了 T ≠ U T\neq U T=U 的条件，即每次操作可以不删除任何点。
设
a
n
s
i
ans_i
ansi 表示真正的答案，考虑枚举
d
p
1
,
i
dp_{1,i}
dp1,i 中，共有
j
j
j 步是合法的，
i
−
j
i-j
i−j 步是不删除任何点的方案。
d
p
1
,
i
=
∑
j
=
0
i
C
i
j
a
n
s
j
dp_{1,i}=\sum_{j=0}^i{C_i^j}ans_j
dp1,i=j=0∑iCijansj
变换下，则有
a
n
s
i
=
d
p
1
,
i
−
∑
j
=
0
i
−
1
C
i
j
a
n
s
j
ans_i=dp_{1,i}-\sum_{j=0}^{i-1}C_i^j ans_j
ansi=dp1,i−j=0∑i−1Cijansj
可以在 O ( n 2 ) O(n^2) O(n2) 复杂度内求解出所有的 a n s i ans_i ansi 。
参考代码来自官方题解。
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)\
freopen(#x".in" ,"r" ,stdin);\
freopen(#x".out" ,"w" ,stdout)
#define LL long long
const int MX = 2000 + 23;
LL MOD;
using namespace std;
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
int head[MX] ,tot = 1;
struct edge{
int node ,next;
}h[MX << 1];
void addedge(int u ,int v ,int flg = 1){
// if(flg) debug("%d %d\n" ,u ,v);
h[++tot] = (edge){v ,head[u]} ,head[u] = tot;
if(flg) addedge(v ,u ,false);
}
int n ,dp[MX][MX] ,S[MX][MX] ,suf[MX][MX] ,pre[MX][MX];
void dapai(int x ,int f){
int ch = 0;
for(int i = head[x] ,d ; i ; i = h[i].next){
if((d = h[i].node) == f) continue;
dapai(d ,x);
}
for(int i = head[x] ,d ; i ; i = h[i].next){
if((d = h[i].node) == f) continue;
++ch;
for(int j = 0 ; j <= n ; ++j){
suf[ch][j] = pre[ch][j] = S[d][j];
}
}
if(!ch){
for(int i = 1 ; i <= n ; ++i){
dp[x][i] = 1 % MOD;
S[x][i] = (S[x][i - 1] + dp[x][i]) % MOD;
}
return ;
}
for(int j = 0 ; j <= n ; ++j){
for(int i = 1 ; i <= ch ; ++i)
pre[i][j] = 1LL * pre[i][j] * pre[i - 1][j] % MOD;
for(int i = ch ; i >= 1 ; --i)
suf[i][j] = 1LL * suf[i][j] * suf[i + 1][j] % MOD;
}
for(int i = 1 ; i <= n ; ++i) dp[x][i] = pre[ch][i];
if(x != 1) for(int i = head[x] ,d ,c = 0 ; i ; i = h[i].next){
if((d = h[i].node) == f) continue;
++c;
LL sum = 0;
for(int mx = 1 ; mx <= n ; ++mx){
dp[x][mx] = (dp[x][mx] + sum * dp[d][mx]) % MOD;
sum = (sum + 1LL * pre[c - 1][mx] * suf[c + 1][mx]) % MOD;
}
}
for(int i = 1 ; i <= ch ; ++i)
for(int j = 0 ; j <= n ; ++j)
suf[i][j] = pre[i][j] = 1 % MOD;
for(int i = 1 ; i <= n ; ++i)
S[x][i] = (S[x][i - 1] + dp[x][i]) % MOD;
}
int C[MX][MX];
void init(){
for(int i = 0 ; i < MX ; ++i) C[i][0] = 1 % MOD;
for(int i = 1 ; i < MX ; ++i)
for(int j = 1 ; j < MX ; ++j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
int main(){
n = read() ,MOD = read();
init();
for(int i = 0 ; i < MX ; ++i)
for(int j = 0 ; j < MX ; ++j)
suf[i][j] = pre[i][j] = 1 % MOD;
for(int i = 2 ; i <= n ; ++i){
addedge(read() ,read());
// addedge(rand() % (i - 1) + 1 ,i);
}
dapai(1 ,0);
for(int i = 1 ; i < n ; ++i){
LL ans = 0;
for(int j = 1 ; j <= i ; ++j){
ans += ((i - j) & 1 ? -1LL : 1LL) * C[i][j] * dp[1][j] % MOD;
}
ans = (ans % MOD + MOD) % MOD;
printf("%lld%c" ,ans ," \n"[i == n]);
}
return 0;
}
咕了
咕了