| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 7/12 | Ø | O | . | O | Ø | O | . | . | . | O | . | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A Lightning Routing I
题目描述
给一棵树，有$Q$次操作，每次改变某个边权或者询问距离某点最远的点的距离。
解题思路
发现树的直径这个知识点没有点亮…!
先学习一下树的直径好了。树的直径有几个性质：
- 直径两端点必为叶子节点。（显然）
- 距离任一点最远的点必为直径的一个端点。（下面会证）
- 对于两棵树，如果两棵树分别以$(u,v)(a,b)$作为直径，将他们用一条边连起来后，新的树直径必为这四点中的某两点。
- 若一棵树存在多条直径，那么这些直径交于一点，且交点为这些直径的中点。（显然）
现在来证明第二条性质：
假设树的直径为$AB$，当前点为$P$，距离$P$最远点为$Q$。
讨论：
- $PQ,AB$交于点$R$：$PR+RQ>PR+RB$，故$RQ>RB$，$dis_{AB}<dis_{AQ}$，与$AB$为直径矛盾
- $PQ,AB$不相交：设$PQ,AB$通过$CR$相连，则$PR+RQ>PR+CR+BC$，故$RQ>CR+BC,AQ=AC+CR+RQ>AC+CR+CR+BC=AB+2CR$，同样矛盾
故$P$的最远点必为$AB$两点中的某一点。同样地，如果有多条直径，任意一条直径中必包含一个距离$P$最远的点。
利用这条性质，本题就可转化为：可修改边权，维护树直径及其端点。
首先将树用全$dfs$序表示，即遍历树所经过的路径。
如：样例输入中，以$1$为根的全$dfs$序为：$131252421$或$124252131$。
全$dfs$序有一个性质：任意两位置代表的顶点的$lca$必定包含在这两位置之间（如$5,4:$131252421，$LCA$为$2$）。很容易通过遍历方法证明这一点。
利用这个性质以及边权为正，设$dis_p$为$p$到根的距离，容易得出$min_{p=l}^{r}(dis_p)$为$LCA$到根的距离。故有树的直径$d=max_{1\leq L\leq LCA\leq R\leq 2n-1}(dis[L]+dis[R]-2dis[LCA])$。用一棵线段树维护$L,LCA,R$即可。
具体维护步骤：$ML,MR$分别表示区间之中$L\leq LCA,LCA\leq R$的$dis[L]-2dis[LCA],dis[R]-2dis[LCA]$的值，$val$表示区间$dis$最大的值，$dia$表示区间直径，合并区间时使用这些值，再加入点维护直径端点即可。
同时，需要维护每一点到根节点距离，这里可以用$dfs$序上$BIT$，每次改变边权时，在$st[p],ed[p]$区间更改，在区间左端点查询即可。
AC代码
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
typedef long long ll;
using namespace std;
int u[N],v[N],w[N],n;
struct Edge{
int e,n,l;
}e[N<<1];
int cnt,hd[N];
void add(int a,int b,int l){e[++cnt].e=b;e[cnt].n=hd[a];e[cnt].l=l;hd[a]=cnt;}
ll dis[N];
int d[N],st[N],ed[N],tot,id[N<<1];
ll bit[N<<2];
void add(int p,ll x){
while(p&&p<(N<<2))bit[p]+=x,p+=p&(-p);
}
ll getdis(int p){
ll ans=0;
while(p)ans+=bit[p],p-=p&(-p);
return ans;
}
int fa[22][N],lg[N];
void dfs(int p,int f){
d[p]=d[f]+1;
id[st[p]=++tot]=p;
fa[0][p]=f;
int i;
for(i=1;(1<<i)<=d[p];i++)fa[i][p]=fa[i-1][fa[i-1][p]];
for(;i<22;i++)fa[i][p]=0;//!!!
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(q==f)continue;
dis[q]=dis[p]+e[i].l;
dfs(q,p);
id[++tot]=p;
}
ed[p]=tot;
}
int LCA(int x,int y){
int i;
if(d[x]<d[y]){int t=x;x=y;y=t;}
while(d[x]>d[y])
x=fa[lg[d[x]-d[y]]][x];
if(x==y)return x;
for(i=lg[d[x]];~i;i--)
if(fa[i][x]!=fa[i][y])
x=fa[i][x],y=fa[i][y];
return fa[0][x];
}
int L[N<<2],R[N<<2],A[N<<2],B[N<<2];
int Lx[N<<2],Rx[N<<2],Dx[N<<2];
ll ML[N<<2],MR[N<<2],lca[N<<2],dia[N<<2];
ll lazy[N<<2],val[N<<2];
ll getdis2(int x,int y){
int fa=LCA(x,y);
ll ans=dis[x]+dis[y]-2*dis[fa]+getdis(st[x])+getdis(st[y])-2*getdis(st[fa]);
return ans;
}
void pushup(int p){
lca[p]=max(lca[p<<1],lca[p<<1|1]);
val[p]=max(val[p<<1],val[p<<1|1]);
if(val[p]==val[p<<1])Dx[p]=Dx[p<<1];
else Dx[p]=Dx[p<<1|1];
ML[p]=max(max(ML[p<<1],ML[p<<1|1]),val[p<<1]+lca[p<<1|1]);
if(ML[p]==ML[p<<1])Lx[p]=Lx[p<<1];
else if(ML[p]==ML[p<<1|1])Lx[p]=Lx[p<<1|1];
else Lx[p]=Dx[p<<1];
MR[p]=max(max(MR[p<<1],MR[p<<1|1]),val[p<<1|1]+lca[p<<1]);
if(MR[p]==MR[p<<1])Rx[p]=Rx[p<<1];
else if(MR[p]==MR[p<<1|1])Rx[p]=Rx[p<<1|1];
else Rx[p]=Dx[p<<1|1];
dia[p]=max(max(dia[p<<1],dia[p<<1|1]),max(val[p<<1]+MR[p<<1|1],val[p<<1|1]+ML[p<<1]));
if(dia[p]==dia[p<<1])A[p]=A[p<<1],B[p]=B[p<<1];
else if(dia[p]==dia[p<<1|1])A[p]=A[p<<1|1],B[p]=B[p<<1|1];
else if(dia[p]==val[p<<1]+MR[p<<1|1])A[p]=Dx[p<<1],B[p]=Rx[p<<1|1];
else A[p]=Dx[p<<1|1],B[p]=Lx[p<<1];
}
void pushdown(int p){
if(lazy[p]){
ll t=lazy[p];
if(L[p]!=R[p]){
val[p<<1]+=t,val[p<<1|1]+=t;
lazy[p<<1]+=t,lazy[p<<1|1]+=t;
ML[p<<1]-=t,ML[p<<1|1]-=t;
MR[p<<1]-=t,MR[p<<1|1]-=t;
lca[p<<1]-=2*t,lca[p<<1|1]-=2*t;
}
lazy[p]=0;
}
}
void build(int p,int l,int r){
L[p]=l;R[p]=r;
lazy[p]=0;
if(l==r){
Lx[p]=Rx[p]=Dx[p]=id[l];
A[p]=B[p]=id[l];
ML[p]=MR[p]=-dis[id[l]];
lca[p]=-2*dis[id[l]];
val[p]=dis[id[l]];
dia[p]=0;
return;
}
build(p<<1,l,(l+r)>>1);
build(p<<1|1,((l+r)>>1)+1,r);
pushup(p);
}
void modify(int p,int l,int r,ll delta){
if(L[p]>r||R[p]<l)return;
if(l<=L[p]&&R[p]<=r){
lazy[p]+=delta;
lca[p]-=2*delta;
ML[p]-=delta;
MR[p]-=delta;
val[p]+=delta;
pushdown(p);
getAB(p);
return;
}
pushdown(p);
modify(p<<1,l,r,delta);
modify(p<<1|1,l,r,delta);
pushup(p);
}
int main(){
int i,q;
scanf("%d",&n);
for(i=1;i<n;i++){
int x,y,l;
scanf("%d%d%d",&x,&y,&l);
add(x,y,l);add(y,x,l);
u[i]=x;v[i]=y;w[i]=l;
}
dfs(1,0);
build(1,1,tot);
for(i=2;i<=n;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
scanf("%d",&q);
while(q--){
char s[10]={0};int x,y;
scanf("%s%d",s,&x);
if(s[0]=='Q'){
ll ans=getdis2(A[1],x);
ans=max(ans,getdis2(B[1],x));
printf("%lld\n",ans);
}else{
scanf("%d",&y);
int p=d[u[x]]>d[v[x]]?u[x]:v[x];
add(st[p],y-w[x]);
add(ed[p]+1,w[x]-y);
modify(1,st[p],ed[p],y-w[x]);
w[x]=y;
}
}
return 0;
}
B Light bulbs
题目描述
初始时所有灯都是灭的，有$m$次翻转操作，每次一个区间$L[i],R[i]$，问最终灯有多少是亮的。
解题思路
对询问排序做一下就好了。
AC代码
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
typedef long long ll;
using namespace std;
struct Seg{
int pos;char sign;
bool operator<(const Seg&a)const{return pos<a.pos||(pos==a.pos&&sign>a.sign);}
}a[2010];
int main(){
int i,T,n,m,Cas=0;
scanf("%d",&T);
while(T--){
int tot=0;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++){
int l,r;
scanf("%d%d",&l,&r);
a[++tot]={l,1};
a[++tot]={r+1,0};
}
sort(a+1,a+1+tot);
int now=0,last=0,ans=0;
for(i=1;i<=tot;i++){
if(now&&now%2)ans+=a[i].pos-last;
if(a[i].sign)now++;
else now--;
last=a[i].pos;
}
printf("Case #%d: %d\n",++Cas,ans);
}
return 0;
}
C Triple
题目描述
解题思路
AC代码
2
D Counting Sequences I
题目描述
定义一个长度为$n$的序列为好序列，当且仅当$\sum_{i=1}^{n}a_i=\prod_{i=1}^{n}a_i$。给定$2\leq n\leq 3000$，求好序列个数。
解题思路
爆搜剪枝打表。
打表代码 - by nikkukun
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
using namespace std;
typedef long long ll;
const int N = 6000 + 5;
const int MOD = 1e9 + 7;
int n;
ll fac[N], inv[N], ifac[N];
int ans = 0;
ll QPow(ll bas, int t){
ll ret = 1;
while(t){
if(t & 1) ret = ret * bas % MOD;
bas = bas * bas % MOD;
t >>= 1;
}
return ret;
}
ll Inv(ll x){
return QPow(x, MOD-2);
}
void Cnt(int p, int v, int sum, int prod, int cnt, ll _ans){
if(sum > 2*n || prod > 2*n) return;
if(sum + v * (n-p) > 2*n) return;
if(prod * pow(v, n-p) > 2*n) return;
if(p == n){
if(prod != sum) return;
ans = (ans +_ans) % MOD;
return;
}
Cnt(p+1, v, sum+v, prod*v, cnt+1, _ans * inv[cnt+1] % MOD);
for(int i=v+1; i<=n; i++)
Cnt(p+1, i, sum+i, prod*i, 1, _ans);
}
int main(){
// freopen("data2.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
fac[0] = 1;
for(int i=1; i<N; i++)
fac[i] = fac[i-1] * i % MOD;
ifac[N-1] = Inv(fac[N-1]);
for(int i=N-1; i>0; i--)
ifac[i-1] = ifac[i] * i % MOD;
for(int i=1; i<N; i++)
inv[i] = fac[i-1] * ifac[i] % MOD;
int t; cin >> t;
while(t--){
cin >> n;
ans = 0;
Cnt(0, 1, 0, 1, 0, fac[n]);
cout << ans << endl;
}
return 0;
}
$AC$代码就不放了。
E Counting Sequences II
题目描述
问有多少个长为$n$的数列满足$1\leq a_i\leq m$，且每个偶数在数列中都出现偶数次。
$1\leq n\leq 10^{18},1\leq m\leq 200000$
解题思路
枚举偶数对数，奇数可任选，记$f(n)$为用$\lfloor\frac m2\rfloor$种偶数填$n$个元素，且每个元素均出现偶数次的方案个数，则$ans=\sum_{k=0}^{\lfloor\frac n2\rfloor}C_n^{2k}\lceil\frac m2\rceil^{n-2k}f(2k)$
考虑如何求$f(n)$：构造生成函数$g(x)$表示每一种偶数值的选择个数与总方案数之间的关系，则$g(x)^{\lfloor\frac m2\rfloor}$在$x^n$处的取值即为所求。于是$g(x)=n!(1+\frac {x^2}{2!}+\frac{x^4}{4!}+…)=n!\frac{e^x+e^{-x}}2$。求幂次，牛顿二项式展开得：
$f(n)=g(x)^{\lfloor\frac m2\rfloor}[x^n]=\frac {\sum_{i=0}^{\lfloor\frac m2\rfloor}C_{\lfloor\frac m2\rfloor}^i(\lfloor\frac m2\rfloor-2i)^{n}}{2^{\lfloor\frac m2\rfloor}}$
方便起见，设$p=\lfloor\frac m2\rfloor$，则$f(n)=\frac {\sum_{i=0}^{p}C_{p}^i(p-2i)^n}{2^{p}}$
$ans=\sum_{k=0}^{\frac n2}C_{n}^{2k}\lceil\frac m2\rceil^{n-2k}\cdot \frac{\sum_{i=0}^pC_p^i(p-2i)^{2k}}{2^p}$
交换求和符号，提出与变量无关量：
$=\frac{\lceil\frac m2\rceil^n}{2^p}\sum_{i=0}^{p}C_p^i\sum_{k=0}^{\lfloor\frac n2\rfloor}C_n^{2k}\frac{(p-2i)^{2k}}{\lceil\frac m2\rceil^{2k}}$
对于$s=\sum_{i=0}^{n}C_{2n}^{2i}x^{2i}$，有$s=\frac{(1+x)^{2n}+(1-x)^{2n}}2$（牛顿二项式展开）
于是$ans=\frac{\lceil\frac m2\rceil^n}{2^{p+1}}\sum_{i=0}^{p}C_p^i((1+\frac{p-2i}{\lceil\frac m2\rceil})^n+(1-\frac{p-2i}{\lceil\frac m2\rceil})^n)$
$=\frac{1}{2^{p+1}}\sum_{i=0}^{p}C_p^i((\lceil\frac m2\rceil+p-2i)^n+(\lceil\frac m2\rceil-p+2i)^n)$
这就可以$O(m\log n)$地计算了。
AC代码
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
typedef long long ll;
using namespace std;
int mod=1000000007;
ll qp(ll a,int p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
ll fac[N],inv[N];
ll c(int n,int m){
if(n<0||n<m||m<0)return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
ll n,m;
int main(){
int i,T;
fac[0]=inv[0]=1;
for(i=1;i<N;i++)fac[i]=fac[i-1]*i%mod,inv[i]=qp(fac[i],mod-2);
scanf("%d",&T);
while(T--){
ll ans=0;
scanf("%lld%lld",&n,&m);n%=(mod-1);
for(i=0;i<=m/2;i++)(ans+=c(m/2,i)*(qp(m-2*i,n)+qp(2*i+(m%2),n)))%=mod;
ans=ans*qp(qp(2,m/2+1),mod-2)%mod;
printf("%lld\n",ans);
}
return 0;
}
F Rhyme scheme
题目描述
求长度为$n$的韵律序列第$k$项。
解题思路
可以看做在字典树上选择，可以递推求出$f[i][j][k]$表示长度为$i$的第$j$层第$k$个前面共有多少种选择。
AC代码 - by Mogg
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
f = [[0 for i in range(30)] for j in range(30)]
def init():
stir[1][1] = 1
for i in range(2,27):
for j in range(1,i+1):
stir[i][j] = stir[i - 1][j - 1] + j * stir[i - 1][j]
for i in range(2,27):
for j in range(1,i+1):
stir[i][j] += stir[i][j - 1]
for i in range(1,27):
f[i][0] = 1
f[i][1] = min(26, i + 1)
for j in range(2,27):
for i in range(1,27):
f[i][j] = i * f[i][j - 1] + f[min(i + 1, 26)][j - 1]
def work(n,m):
if n == 1:
return "A"
if m <= stir[n-1][n-1]:
res = work(n-1,m)
return "A" + res
res = "AB"
mc = 2
m -= stir[n-1][n-1]
for i in range(3,n):
r = mc + 2
for j in range(1,r):
mc = max(mc,j)
if m > f[mc][n-i]:
m -= f[mc][n-i]
continue
else:
res+=chr(64+j)
break
if (n > 2):
res+=chr(64+m)
return res
init()
#print(stir[3][3])
t = int(input())
for i in range(t):
s = input().split()
#print(s)
print("Case #"+str(i+1)+": "+work(int(s[0]),int(s[1])))
G Substring
题目描述
解题思路
AC代码
2
H Luhhy’s Matrix
题目描述
解题思路
AC代码
2
I Debug
题目描述
解题思路
AC代码
2
J Stone game
题目描述
从长度为$n$的数列$a$里找出一个子集$S$满足$sum(S)\geq sum(a-S)$且$\forall s\in S,sum(S-s)\leq sum(a-S)$
求方案数。
解题思路
将数列由大到小排序，$f[i][j]$表示选到$i$且最后一个元素为$i$，当前总和为$j$的方案数，$g[i][j]$表示选到$i$且最后一个元素不为$i$，当前总和为$j$的方案数，可以递推求出这两个序列，对每一个$f$判断加入答案即可。
智障题卡取模的常数AC代码
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
typedef long long ll;
using namespace std;
int mod=1000000007,g[150010],f[2][150010],a[305];
void add(int &a,int b){
a+=b;
if(a>=mod)a-=mod;
}
int main(){
int i,j,T,n;
scanf("%d",&T);
while(T--){
int s=0,cur=0,res=0;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
s+=a[i];
}
a[n]=0;
sort(a,a+n);reverse(a,a+n+1);
for(j=0;j<=s;j++)f[0][j]=f[1][j]=g[j]=0;
f[0][0]=1;
for(i=1;i<=n;i++){
cur^=1;
for(j=0;j<a[i];j++)f[cur][j]=0;
for(j=a[i];j<=s;j++){
f[cur][j]=(f[cur^1][j-a[i]]+g[j-a[i]]);
if(f[cur][j]>=mod)f[cur][j]-=mod;
}
for(j=0;j<=s;j++){
add(g[j],f[cur^1][j]);
if(j>=s-j&&j-a[i]<=s-j)add(res,f[cur][j]);
}
}
printf("%d\n",res);
}
return 0;
}
K Peekaboo
题目描述
解题思路
AC代码
2
L Digit sum
题目描述
求$b$进制下$\sum_{i=1}^{n}digitnum(i)$。
解题思路
预处理出来即可。
AC代码 - by nikkukun
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
using namespace std;
typedef long long ll;
const int N = 1e6 + 5, K = 10 + 3;
ll f[N][K];
int cal(int n,int b)
{
int now = 0;
while (n)
{
now += n % b;
n /= b;
}
return now;
}
void Init(){
for(int i=1; i<N; i++)
for(int b=2; b<=10; b++)
f[i][b] = f[i-1][b] + cal(i, b);
}
ll Solve(){
int n, b;
cin >> n >> b;
return f[n][b];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
Init();
int t; cin >> t;
for(int i=1; i<=t; i++){
cout << "Case #" << i << ": ";
cout << Solve() << endl;
}
return 0;
}