大概是 $2600\sim 3000$ 的 CF 题。
简单写点阴间东西。
看不懂一概不负责。
CF1045D Nauuo and Portals
先不看竖着的限制，如果仅需要满足横着的限制，那么我们每次在同一列放下一个传送门，相当于交换排列的两个位置，我们要通过这种操作把一个顺序的排列变成给定的排列。这样是容易达成的，我们考虑每次将一个数换到它本来的位置，那么只需要至多 $n-1$ 次，所以我们可以将这些传送门放在不同列中。
现在加入了竖着的限制，考虑一对传送门 $(x_1,y_1),(x_2,y_2)$，它的实际意义是交换横着的排列的 $(x_1,x_2)$，交换竖着的排列 $(y_1,y_2)$。
我们希望依次将 $1\sim n$ 的位置填好，假设现在是第 $i$ 次操作，横目标排列的第 $i$ 位是 $x$，竖目标排列的第 $i$ 位是 $y$。我们先找到 $x$ 在横现在排列中的位置 $p_x$ 与 $y$ 在竖现在排列中的位置 $p_y$，然后 $(i,p_x),(p_y,i)$ 就行了，注意判掉两点相等的情况。
PS：题目中给出的排列并非目标排列，只是说某个值要在某个位置。
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
| #include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
void read(int &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void read(ll &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
const int N=1005;
typedef pair<pii,pii> ppii;
int n,tmp;
int X[N],Y[N];
int NX[N],NY[N];
vector<ppii> O;
void Work(){
read(n);
for(int i=1;i<=n;++i) read(tmp),X[tmp]=i,NX[i]=i;
for(int i=1;i<=n;++i) read(tmp),Y[tmp]=i,NY[i]=i;
for(int i=1;i<n;++i){
int x=X[i],y=Y[i];
int px,py;
for(px=1;NX[px]!=x;++px);
for(py=1;NY[py]!=y;++py);
if(px!=i||py!=i) O.pb(mp(mp(i,py),mp(px,i)));
swap(NX[i],NX[px]),swap(NY[i],NY[py]);
}
printf("%d\n",O.size());
for(auto I:O) printf("%d %d %d %d\n",I.first.first,I.first.second,I.second.first,I.second.second);
}
int main(){Work();}
|
CF1172C Nauuo and Pictures
考虑 DP，我们发现概率的计算牵涉三个值，一个是不喜欢的图片的权值和，一个是喜欢的图片的权值和，还有一个是本身的权值。
我们记初始时喜欢的权值和是 $W_a$，不喜欢的权值和是 $W_b$，当前的是 $W’_a,W’_b$，一次操作会使得 $W_a’$ 加一或是 $W_b’$ 减一。
对于一张图片，我们在意的并非其编号，而是其初始权值，同时其它图片也可以看作两大类而无需分析，于是令 $F(w,i,a,b)$ 表示一个权值为 $w$ 的且被喜欢的图片，经过 $i$ 次操作，$W_a’=a,W_b’=b$ 时的期望权值，为了计算概率，我们选择在操作序列前插入一个操作，而非在操作序列后插入一个操作，那么一共有三种转移来源：
- 选到自己，概率为 $\frac{w}{a+b}$，从 $F(w+1,i-1,a+1,b)$ 转移过来；
- 选到喜欢的图片但不是自己，概率为 $\frac{a-w}{a+b}$，从 $F(w,i-1,a+1,b)$ 转移过来；
- 选到不喜欢的图片，概率为 $\frac{b}{a+b}$，从 $F(w,i-1,a,b-1)$ 转移过来。
所以有：
复杂度过高，需要优化。
发现 $w$ 这一维很恶心，可以去掉它吗？
经过观察，我们惊人地发现 $F(w,i,a,b)=wF(1,i,a,b)$！
证明可以使用归纳法。
那么我们令 $F(i,a,b)$ 表示原来的 $F(1,i,a,b)$，就有：
初值 $F(0,a,b)=1$，最后要求的是 $F(m,W_a,W_b)$。
我们观察 $F(m,W_a,W_b)$ 会从哪里转移过来，也就是有效的状态是哪些，可以发现后两维的变化量之和就等于第一维的变化量，而且随着第一维减少一，可能是第二维增加一，或者是第三维减少一。
我们新搞一个 $F^(a,b)$ 表示第二维和第三维的相较于 $W_a$ 与 $W_b$ 的变化量，那么我们知道 $F^(a,b)=F(m-a-b,W_a+a,W_b-b)$。
记 $W=W_a+a+W_b-b$，于是有转移：
类似的令 $G^*(a,b)$ 表示不喜欢的图片，有转移：
初值 $\forall a+b=m,F^(a,b)=G^(a,b)=1$，最终需要 $F^(0,0),G^(0,0)$。
时间复杂度 $O(n+m^2\log P)$，其中 $P=998244353$。
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
| #include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
void read(int &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void read(ll &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
const int N=2e5+10,M=3e3+10,Mod=998244353;
void Add(int &x,int y){(x+=y)>=Mod?x-=Mod:x;}
int Pow(int a,int b){
int res=1;
while(b){
if(b&1) res=1ll*res*a%Mod;
a=1ll*a*a%Mod,b>>=1;
}
return res;
}
int n,m;
int Wa,Wb;
int W[N],T[N];
int F[M][M],G[M][M];
void Work(){
read(n),read(m);
for(int i=1;i<=n;++i) read(T[i]);
for(int i=1;i<=n;++i) read(W[i]);
for(int i=1;i<=n;++i)
if(T[i]) Wa+=W[i];
else Wb+=W[i];
for(int i=m;~i;--i){
for(int a=0;a<=i;++a){
int b=i-a;
if(i==m){F[a][b]=G[a][b]=1;continue;}
int Wa_=Wa+a,Wb_=Wb-b;;
if(Wb_<0) continue;
int IW=Pow(Wa_+Wb_,Mod-2);
Add(F[a][b],1ll*(Wa_+1)*F[a+1][b]%Mod),Add(G[a][b],1ll*Wa_*G[a+1][b]%Mod);
if(Wb_) Add(F[a][b],1ll*Wb_*F[a][b+1]%Mod),Add(G[a][b],1ll*(Wb_-1)*G[a][b+1]%Mod);
F[a][b]=1ll*IW*F[a][b]%Mod,G[a][b]=1ll*IW*G[a][b]%Mod;
}
}
for(int i=1;i<=n;++i)
if(T[i]) printf("%d\n",1ll*W[i]*F[0][0]%Mod);
else printf("%d\n",1ll*W[i]*G[0][0]%Mod);
}
int main(){Work();}
|
CF1168D Anagram Paths
首先显然每个叶子的深度应该相等。
那么我们来观察两条链，它们共用一个链顶，每条链有 $n$ 条边。
对于一个字母，它在左边出现的次数为 $tl_c$，右边出现的次数为 $tr_c$，我们称一个字母在一侧是有效的，当且仅当这个字母在这一侧的出现次数大于在另一侧的出现次数，或者这一侧是左侧，且在两侧的出现次数是相等的。
记左侧有效字母数为 $L_{max}$，右侧有效字母数为 $R_{max}$，左侧无效字母数为 $L_{min}$，右侧无效字母数为 $R_{min}$，左侧问号数为 $L_?$，右侧问号数为 $R_?$。
那么我们有 $L_{max}+R_{max}+L_{min}+R_{min}+L_?+R_?=2n$。
另外，如果两条链是相关联的，那么 $L_{max}\le R_{min}+R_{?}$，$R_{max}\le L_{min}+L_{?}$。
那么我们可以推出 $L_{max}+R_{max}\le n$，相当于建立了必要性。
如何建立充分性？我们发现，通过相关联给出的两个不等式是同真同假的，因为我们有$L_{max}+L_{min}+L_?=R_{max}+R_{min}+R_{?}$。
我们还可以求出它的重排度。对于每个字母 $c$，$f(c)=\max(tl_c,tr_c)+R_{min}+R_{?}-L_{max}$，这是它本身的出现次数加上多出来的问号。
换句话说，它指出一个节点只向下拉两条单链，如果它子树内以它为 LCA 的叶子对都是相关联的，那么对于所有字符向下延伸的链中最大的出现次数之和，是不超过它到叶子的路径上包含的边数的。
推广到一般的二叉树，记点 $u$ 到它子树内的叶子最少需要经过 $d_u$ 条边，它向下的所有链中 $c$ 最大的出现次数 $t_{u,c}$。
我们猜测节点 $u$ 子树内以 $u$ 为 LCA 的叶子对都相关联当且仅当 $\sum_{c}t_{u,c}\le d_u$。
我们对于每一对叶子都能看成一个节点向下拉两条单链的结构，那么所谓的 $\sum_c t_{u,c}$ 实际上是对所有结构的 $L_{max}+R_{max}$ 取 $\operatorname{max}$。
接下来我们要求出重排度，我们对每个字母单独考虑，这可以分为两部分，一部分是 $t_{1,c}$，另一部分是从问号转化过来的，它就是 $d_1-\sum_{c}t_{1,c}$。
然后我们考虑怎么支持修改，这样需要维护 $t_{u,c}$，暴力跳父亲修改的复杂度是和树的深度相关的。
但是我们发现这是一棵二叉树，而且对于单链明显是可以缩的（不等式两边同时加一，显然同真同假），我们发现缩完之后树高是 $O(\sqrt{n})$ 级别的。这里简单说明一下，我们假设新树中最深的叶子的深度为 $d$，那么我们为了保留它到根上的边，肯定每个点都要另外拉出一条链，而且要保证拉出后叶子在原树中深度相等，所以要耗费节点 $1+2+\cdots+(d-1)$，这是 $O(d^2)$ 的，所以 $d$ 是 $O(\sqrt{n})$ 级别的。
在虚树中，每一条边对应了新树的一条单链，我们用一个桶存它上面的字母。
实现上使用 set 维护不合法的 $u$，时间复杂度 $O(n\Sigma+q\Sigma\sqrt{n})$。
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
| #include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
void read(int &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void read(ll &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void chkmax(int &x,int y){if(y>x)x=y;}
void chkmin(int &x,int y){if(x<y)x=y;}
void chkmax(ll &x,ll y){if(y>x)x=y;}
void chkmin(ll &x,ll y){if(x<y)x=y;}
const int N=2e5+10,sig=27;
int ch_to_int(char c){return isalpha(c)/2*(c-'a'+1);}
int n,q;
int p[N],pc[N];
vector<pii> Edge[N];
int dep[N],Mdep;
int fat[N],bel[N],buc[N][sig],t[N][sig];
vector<int> son[N];
int ed_buc[sig];
void dfs(int now,int fa){
if(Edge[now].size()^1&&now^1){
for(int i=1;i<sig;++i) buc[now][i]=ed_buc[i],ed_buc[i]=0;
fat[now]=fa,son[fa].pb(now),fa=now;
}
for(auto I:Edge[now]){
int v=I.first,c=I.second;
++ed_buc[c],dep[v]=dep[now]+1,chkmax(Mdep,dep[v]),dfs(v,fa);
}
}
void Build(int now){
for(int v:son[now]) Build(v);
for(int v:son[now])
for(int i=1;i<sig;++i) chkmax(t[now][i],t[v][i]+buc[v][i]);
for(int i=1;i<sig;++i) t[now][0]+=t[now][i];
}
bool intr(int now){return now==1||Edge[now].size()!=1;}
void EXIT(){for(int i=1;i<=q;++i) puts("Fou");exit(0);}
set<int> S;
void Work(){
read(n),read(q);
for(int i=2;i<=n;++i){
char c;
read(p[i]),scanf("%c",&c),pc[i]=ch_to_int(c);
Edge[p[i]].pb(mp(i,pc[i]));
}
dfs(1,1),Build(1);
for(int i=1;i<=n;++i)
if(Edge[i].size()==0&&dep[i]!=Mdep) EXIT();
for(int i=1;i<=n;++i){
if(!intr(i)) continue;
if(t[i][0]>Mdep-dep[i]) S.insert(i);
}
for(int i=1;i<=n;++i)
if(intr(i)){
int now=p[i];bel[i]=i;
while(!intr(now)) bel[now]=i,now=p[now];
}
for(int i=1;i<=q;++i){
char ch;int x;
read(x),scanf("%c",&ch);
int c=ch_to_int(ch),u=bel[x];
--buc[u][pc[x]],++buc[u][pc[x]=c];
u=fat[u];
while(u){
for(int i=0;i<sig;++i) t[u][i]=0;
for(int v:son[u])
for(int i=1;i<sig;++i) chkmax(t[u][i],t[v][i]+buc[v][i]);
for(int i=1;i<sig;++i) t[u][0]+=t[u][i];
if(t[u][0]>Mdep-dep[u]) S.insert(u);
else S.erase(u);
u=fat[u];
}
if(S.size()) puts("Fou");
else{
int sum=0;
for(int i=1;i<sig;++i) sum+=i*(Mdep-t[1][0]+t[1][i]);
printf("Shi %d\n",sum);
}
}
}
int main(){Work();}
|
CF1163F Indecisive Taxi Fee
分析一条边边权改变对最短路的影响，我们先任意求出一条 $1\rightarrow n$ 的最短路，那么：
- 这条边不在这条最短路上，直接取原图的最短路和强制经过这条边的最短路的最小值；
- 这条边在这条最短路上，且
所以，我们现在只需考虑这条边边权比原来大，且在这条最短路上时的情况。
答案很显然是保留这条边时的最短路与删除这条边时的最短路的最小值。
前者好算，只要给原最短路加上边权变化量即可，现在只需考虑计算后者。
设 $L_u$ 表示 $1\rightarrow u$ 的最短路与我们求出的那条最短路的尽可能短（这里指的是 $1\rightarrow u$ 的任意一条最短路中与我们求出的那条最短路最短的，下同）的最长前缀（最后一个共用点的编号），$R_u$ 是 $u\rightarrow n$ 的最短路与我们求出的那条最短路的尽可能短的最长后缀（第一个共用点的编号）。
特别地，对于在最短路上的点，我们认为 $R_u=L_u+1$，而 $L_u$ 仍是正常定义。
我们要求删掉原最短路上一条边 $(u,v)$ 时的最短路，那么我们知道一定存在一个对点 $u’,v’$，我们新最短路是先走 $1\rightarrow u’$，然后在不在原最短路上的边走，最后走 $v’\rightarrow n$。
我们考虑一条不在那条最短路的边 $(u,v)$，我们可以走 $1\rightarrow u$，然后走 $(u,v)$，最后走 $v\rightarrow n$，那么它一定会走原来那条最短路的 $1\rightarrow L_u$ 与 $R_v\rightarrow n$，我们发现它可以用来更新对于所有 $t\in[L_u,R_v)$，删掉原最短路上第 $t$ 条边时的新最短路。类似地，我们还可以用 $L_v,R_u$ 来更新。
现在问题是先对区间取 $\min$，再单点求值，这个东西当然可以直接上线段树，但是我们想要更优美的做法。
我们不妨对这些区间按取 $\min$ 的值从大到小排序，那么问题就相当于先区间赋值，再单点求值。
直接使用 set 维护值相等的极大连续段，记 $\Phi(\mathbf{A})$ 表示序列 $\mathbf{A}$ 中值相等的极大连续段数，初始时 $\Phi(\mathbf{A})=1$，之后每次操作会先使 $\Phi(\mathbf{A})$ 增加至多 $2$，然后再减少若干，我们的时间开销主要花费在减少上，由于 $\Phi(\mathbf{A})$ 非负且最多为 $2m+1$，所以减少的量不超过 $2m+1$。因而这部分的时间复杂度是 $O(m\log n)$ 的。
最后我们只需要遍历一下 set 求出答案就行了。
总的时间复杂度是 $O(m\log m+q)$ 的。
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
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
159
| #include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
void read(int &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void read(ll &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void chkmax(int &x,int y){if(y>x)x=y;}
void chkmin(int &x,int y){if(x<y)x=y;}
void chkmax(ll &x,ll y){if(y>x)x=y;}
void chkmin(ll &x,ll y){if(x<y)x=y;}
const int N=2e5+10;
const ll Inf=0x3f3f3f3f3f3f3f3fll;
int n,m,q;
struct Link{int u,v,w;}e[N];
struct Edge{int v,nxt,w,id;}ed[N<<1];
int head[N],cnt;
void adde(int u,int v,int w,int id){ed[++cnt]=(Edge){v,head[u],w,id},head[u]=cnt;}
void add(int u,int v,int w,int id){adde(u,v,w,id),adde(v,u,w,id);}
struct Node{
int id;ll dis;
Node(){};
Node(int _id,ll _dis){id=_id,dis=_dis;}
bool operator<(const Node &x) const {return dis>x.dis;}
};
ll dis[2][N];
int prenod[N],pred[N];
void dij(int s,int c){
memset(dis[c],0x3f,sizeof dis[c]);
priority_queue<Node> Q;
dis[c][s]=0,Q.push(Node(s,0));
while(Q.size()){
Node nod=Q.top();Q.pop();
int now=nod.id;
if(dis[c][now]!=nod.dis) continue;
for(int i=head[now];i;i=ed[i].nxt){
int v=ed[i].v,w=ed[i].w;
if(dis[c][now]+w<dis[c][v]){
dis[c][v]=dis[c][now]+w,Q.push(Node(v,dis[c][v]));
if(!c) prenod[v]=now,pred[v]=ed[i].id;
}
}
}
}
int k;
vector<int> Nod,Edg;
int vis[N],vise[N];
int Lu[N],Ru[N];
void GetL(int now,int tp){
Lu[now]=tp,vis[now]=1;
for(int i=head[now];i;i=ed[i].nxt){
int v=ed[i].v,w=ed[i].w;
if(vis[v]||dis[0][now]+w!=dis[0][v]) continue;
GetL(v,tp);
}
}
void GetR(int now,int tp){
Ru[now]=tp,vis[now]=1;
for(int i=head[now];i;i=ed[i].nxt){
int v=ed[i].v,w=ed[i].w;
if(vis[v]||dis[1][now]+w!=dis[1][v]) continue;
GetR(v,tp);
}
}
vector< pair<ll,pii> > Inter;
struct setnod{
int l,r;
mutable ll val;
setnod(){};
setnod(int _l){l=_l;}
setnod(int _l,int _r,ll _val){l=_l,r=_r,val=_val;}
bool operator<(const setnod &x) const {return l<x.l;}
};
set<setnod> S;
typedef set<setnod>::iterator si;
si split(int pos){
si it=S.lower_bound(setnod(pos));
if(it!=S.end()&&pos==it->l) return it;
--it;
int l=it->l,r=it->r;
ll val=it->val;
S.erase(it),S.insert(setnod(l,pos-1,val));
return S.insert(setnod(pos,r,val)).first;
}
void Assign(int l,int r,ll val){
si itr=split(r+1),itl=split(l);
S.erase(itl,itr),S.insert(setnod(l,r,val));
}
ll Ans[N];
void Prework(){
read(n),read(m),read(q);
for(int i=1;i<=m;++i){
int u,v,w;
read(u),read(v),read(w);
e[i]=(Link){u,v,w};
add(u,v,w,i);
}
dij(1,0),dij(n,1);
int now=n;
while(now^1) Nod.pb(prenod[now]),Edg.pb(pred[now]),vise[pred[now]]=1,now=prenod[now];
reverse(Nod.begin(),Nod.end()),reverse(Edg.begin(),Edg.end());
k=Nod.size();
for(int i=0;i<k;++i) vis[Nod[i]]=1;vis[n]=1;
for(int i=0;i<k;++i) GetL(Nod[i],i+1);GetL(n,k+1);
memset(vis,0,sizeof vis);
for(int i=0;i<k;++i) vis[Nod[i]]=1;vis[n]=1;
GetR(n,k+1);for(int i=k-1;~i;--i) GetR(Nod[i],i+1);
for(int i=1;i<=m;++i)
if(!vise[i]){
int u=e[i].u,v=e[i].v,w=e[i].w;
if(Lu[u]<Ru[v]) Inter.pb(mp(-dis[0][u]-w-dis[1][v],mp(Lu[u],Ru[v]-1)));
if(Lu[v]<Ru[u]) Inter.pb(mp(-dis[0][v]-w-dis[1][u],mp(Lu[v],Ru[u]-1)));
}
sort(Inter.begin(),Inter.end());
S.insert(setnod(1,k+1,Inf));
for(auto I:Inter){
ll w=-I.first;
int L=I.second.first,R=I.second.second;
Assign(L,R,w);
}
for(si it=S.begin();it!=S.end();++it)
for(int i=it->l;i<=it->r;++i) Ans[i]=it->val;
}
void Work(){
Prework();
for(int i=1;i<=q;++i){
int id,_w;
read(id),read(_w);
int u=e[id].u,v=e[id].v,w=e[id].w;
if(!vise[id]) printf("%lld\n",min(min(dis[0][u]+_w+dis[1][v],dis[0][v]+_w+dis[1][u]),dis[0][n]));
else{
if(_w<=w) printf("%lld\n",dis[0][n]-(w-_w));
else printf("%lld\n",min(dis[0][n]+(_w-w),Ans[min(Lu[u],Lu[v])]));
}
}
}
int main(){Work();}
|
CF1158D Winding polygonal line
每次取最外层的，第一次取 $y$ 最小的某一个点，之后每次取极角最大或者最小的就行了，这取决于下一次拐应该往左还是右，建议自己感受一下。
时间复杂度 $O(n^2)$。
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
| #include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
void read(int &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void read(ll &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void chkmax(int &x,int y){if(y>x)x=y;}
void chkmin(int &x,int y){if(x<y)x=y;}
void chkmax(ll &x,ll y){if(y>x)x=y;}
void chkmin(ll &x,ll y){if(x<y)x=y;}
const int N=2e3+10;
int n;
pii A[N];
int vis[N];
char str[N];
int now;
pii sub(pii a,pii b){return mp(a.first-b.first,a.second-b.second);}
ll cross(pii a,pii b){return 1ll*a.first*b.second-1ll*a.second*b.first;}
ll _crs(int a,int b){return cross(sub(A[a],A[now]),sub(A[b],A[now]));}
vector<int> P;
void Work(){
read(n);
for(int i=1;i<=n;++i) scanf("%d%d",&A[i].first,&A[i].second);
scanf("%s",str+1);
now=1;
for(int i=2;i<=n;++i)
if(A[i].second<A[now].second) now=i;
vis[now]=1,P.pb(now);
for(int i=2;i<n;++i){
if(str[i-1]=='L'){
int t=0;
for(int j=1;j<=n;++j)
if(!vis[j]) t=j;
for(int j=1;j<=n;++j)
if(t!=j&&!vis[j])
if(_crs(t,j)<0) t=j;
P.pb(t),vis[now=t]=1;
}
else{
int t=0;
for(int j=1;j<=n;++j)
if(!vis[j]) t=j;
for(int j=1;j<=n;++j)
if(!vis[j])
if(_crs(t,j)>0) t=j;
P.pb(t),vis[now=t]=1;
}
}
for(int i=1;i<=n;++i)
if(!vis[i]) P.pb(i);
for(int v:P) printf("%d ",v);
}
int main(){Work();}
|
CF1153F Serval and Bonus Problem
首先考虑计算 $l=1$ 的情况，容易发现最终只要乘上 $l$ 就能得到答案。
回顾这种连续型离散变量的期望，实际上是求了一个定积分，积分的函数是 $x$ 满足某个条件的概率。
在这里，令 $p(x)$ 表示 $x$ 被覆盖至少 $k$ 次的概率，我们枚举有 $t$ 条线段覆盖了它，这意味着这条线段的左右端点在 $x$ 两侧，否则就是在同一侧，于是我们有：
积分得：
记：
有：
故原式可化为：
注意到：
故有：
于是可以 $O(n)$ 计算。
CF1175G Yet Another Partiton Problem
考虑 DP。
令 $F(i,j)$ 表示将前 $i$ 个元素划分为 $j$ 段的最小花费，那么有：
注意到 $k$ 这一维较小，我们可以暴力做 $k$ 次 $F(\ast,j)\rightarrow F(\ast,j+1)$ 的转移。
现在我们的问题就是对 $i=1,2,\cdots,n$ 计算：
我们尝试通过枚举 $\max$ 的方式消去一些限制，换句话说，我们可以在笛卡尔树上计算。
考虑当前我们正在计算笛卡尔树上某个节点对答案的贡献，不妨记它的权值为 $a$，下标为 $p$，管辖的区间是 $[l,r]$，那么我们知道它将对所有 $i\in[p,r]$ 贡献：
如果求出了内层的 $\min$，那么我们就可以使用李超树去维护答案了。
观察这个式子，它本质上是对区间 $[l,p]$ 的所有 $t$，求最小的 $-at+b_t$，其中 $a,b_t$ 是定值。
这个东西，我们看作有 $n$ 个点，每个点形如 $(t,b_t)$，然后我们要用斜率为 $a$ 的直线去切这些点，使得截距最小。
数形结合一下，我们发现候选答案只可能在这些点的下凸包的斜率都是正的部分。更具体地，我们知道我们应该找到，最靠左边的，与下一个点相连的斜率大于 $a$ 的点，它就是答案。
此时简单的凸包启发式合并+二分已经可以解决问题了，但是由于儿子节点的 $a$ 一定不超过父亲节点的 $a$，所以可以直接单调队列维护。
时间复杂度 $O(nk\log^2 n)$。
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
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
159
160
161
162
| #include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef deque<int> dq;
void read(int &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void read(ll &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void chkmax(int &x,int y){if(y>x)x=y;}
void chkmin(int &x,int y){if(y<x)x=y;}
void chkmax(ll &x,ll y){if(y>x)x=y;}
void chkmin(ll &x,ll y){if(y<x)x=y;}
const int N=5e4+10,Inf=1e9;
int n,k;
int A[N];
int _lst[N];
namespace Cart{
int tot,_nd[N];
struct Node{int l,r,pos,son[2];}t[N];
set<int> S;
pii _[N];
void Build(int L){
S.clear(),tot=0,memset(_nd,0,sizeof _nd);
S.insert(L),S.insert(n+1),A[L]=A[n+1]=Inf;
for(int i=1;i<=n-L;++i) _[i]=mp(-A[i+L],i+L);
sort(_+1,_+n-L+1);
for(int i=1;i<=n-L;++i){
int pos=_[i].second;
_nd[pos]=++tot,t[tot].son[0]=t[tot].son[1]=0;
auto I=S.lower_bound(pos);
int suf=*I,pre=*(--I);
t[tot].l=pre+1,t[tot].r=suf-1,t[tot].pos=pos;
if(A[suf]<=A[pre]) t[_nd[suf]].son[0]=tot;
else t[_nd[pre]].son[1]=tot;
S.insert(pos);
}
}
}
namespace LiChao{
#define lson (now<<1)
#define rson (now<<1|1)
struct Node{
int k,b,f;
Node(){k=f=0,b=1e9;}
Node(int _k,int _b,int _f=1){k=_k,b=_b,f=_f;}
}t[N<<2];
int Line(int k,int b,int x){return k*x+b;}
void Build(int now,int l,int r){
t[now]=Node();
if(l==r) return;
const int mid=(l+r)>>1;
Build(lson,l,mid),Build(rson,mid+1,r);
}
void _Modify(int now,int l,int r,int k,int b){
const int mid=(l+r)>>1;
if(l==r){
if(!t[now].f) return t[now]=Node(k,b),void();
if(Line(t[now].k,t[now].b,l)>Line(k,b,l)) t[now]=Node(k,b);
return;
}
if(!t[now].f) return t[now]=Node(k,b),void();
int _L1=Line(t[now].k,t[now].b,l),_L2=Line(k,b,l);
int _R1=Line(t[now].k,t[now].b,r),_R2=Line(k,b,r);
if(_L1<=_L2&&_R1<=_R2) return;
if(_L2<=_L1&&_R2<=_R1) return t[now]=Node(k,b),void();
int _m1=Line(t[now].k,t[now].b,mid),_m2=Line(k,b,mid);
if(_m2<_m1) swap(t[now].k,k),swap(t[now].b,b),swap(_L1,_L2);
_L2<_L1?_Modify(lson,l,mid,k,b):_Modify(rson,mid+1,r,k,b);
}
void Modify(int now,int l,int r,int x,int y,int k,int b){
const int mid=(l+r)>>1;
if(l>=x&&r<=y) return _Modify(now,l,r,k,b);
if(mid>=x) Modify(lson,l,mid,x,y,k,b);
if(mid<y) Modify(rson,mid+1,r,x,y,k,b);
}
int Query(int now,int l,int r,int pos){
if(l==r) return t[now].f?Line(t[now].k,t[now].b,pos):Inf;
const int mid=(l+r)>>1;
int res=t[now].f?Line(t[now].k,t[now].b,pos):Inf;
if(mid>=pos) return min(res,Query(lson,l,mid,pos));
else return min(res,Query(rson,mid+1,r,pos));
}
#undef lson
#undef rson
}
dq conv[N];
#define _CONDI(x,y,z) 1ll*(_lst[y]-_lst[x])*(z-x)>=1ll*(_lst[z]-_lst[x])*(y-x)
void Merge(int L,int R,int tar){
if(conv[L].size()<conv[R].size()){
swap(conv[tar],conv[R]);
for(auto I=conv[L].rbegin();I!=conv[L].rend();++I){
while(conv[tar].size()>1&&_CONDI(conv[tar][1],*I,conv[tar][0])) conv[tar].pop_front();
conv[tar].push_front(*I);
}
}
else{
swap(conv[tar],conv[L]);
for(auto I=conv[R].begin();I!=conv[R].end();++I){
while(conv[tar].size()>1&&_CONDI(conv[tar][conv[tar].size()-2],conv[tar][conv[tar].size()-1],*I)) conv[tar].pop_back();
conv[tar].push_back(*I);
}
}
conv[L].clear(),conv[R].clear();
}
void Insert(int d,int val){
while(conv[d].size()>1&&_CONDI(conv[d][conv[d].size()-2],conv[d][conv[d].size()-1],val)) conv[d].pop_back();
conv[d].push_back(val);
}
#undef _CONDI
#define _CONDI(now,k) (_lst[conv[now][1]]-_lst[conv[now][0]])<=k*(conv[now][1]-conv[now][0])
namespace TRANS{
void Calc(int now){
int l=Cart::t[now].l,r=Cart::t[now].r,p=Cart::t[now].pos,a=A[p];
int ls=Cart::t[now].son[0],rs=Cart::t[now].son[1];
if(ls) Calc(ls);if(rs) Calc(rs);
while(conv[ls].size()>1&&_CONDI(ls,a)) conv[ls].pop_front();
int C=conv[ls].size()?_lst[conv[ls][0]]-a*conv[ls][0]:Inf;
chkmin(C,_lst[l-1]-a*(l-1));
LiChao::Modify(1,1,n,p,r,a,C);
Insert(ls,p),Merge(ls,rs,now);
}
#undef _CONDI
void Solve(int k){
Cart::Build(k-1);
for(int i=0;i<=Cart::tot;++i) conv[i].clear();
LiChao::Build(1,1,n);
Calc(1);
for(int i=1;i<=n;++i) _lst[i]=i>k?LiChao::Query(1,1,n,i):Inf;
}
}
void Work(){
read(n),read(k);
for(int i=1;i<=n;++i) read(A[i]);
int M=0;
for(int i=1;i<=n;++i) chkmax(M,A[i]),_lst[i]=i*M;
for(int i=1;i<k;++i) TRANS::Solve(i);
printf("%d\n",_lst[n]);
}
int main(){Work();}
|
CF1149D Abandoning Roads
仅保留 $a$ 边后，会有若干个连通块，在原图的最小生成树中，不可能存在一条 $b$ 边的两个端点出现在一个连通块中。
由于是最小生成树，所以不可能通过 $b$ 边重复经过一个连通块。
对此，我们状压一下，对每个点，我们额外记录一个状态 $S$，表示连通块的被经过状态，然后跑最短路。
这样的点数是 $O(2^nn)$，但是这个状态开得是否有些浪费了？
我们思考为什么要记录这个状态，它本质上是为了防止，在跑最短路的时候，我们通过 $b$ 边重复经过了一个连通块，之所以会出现这样的情况，是因为对于同一个连通块内的两个点 $u,v$，它们通过若干条 $a$ 边相连，但是通过走更少数量的 $b$ 边我们可以先跳到别的连通块上，然后再跳回来。
那么，对于包含点数小于等于 $3$ 的连通块，我们就没必要记录，因为它走 $a$ 边一定更优。
所以点数就降到了 $O(2^{n/4}n)$。
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
| #include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
void read(int &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void read(ll &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void chkmax(int &x,int y){if(y>x)x=y;}
void chkmin(int &x,int y){if(y<x)x=y;}
void chkmax(ll &x,ll y){if(y>x)x=y;}
void chkmin(ll &x,ll y){if(y<x)x=y;}
const int N=75,M=205;
int n,m,_a,_b;
struct Edge{int v,nxt,w;}ed[M<<1];
int head[N],cnt;
void adde(int u,int v,int w){ed[++cnt]=(Edge){v,head[u],w},head[u]=cnt;}
void add(int u,int v,int w){adde(u,v,w),adde(v,u,w);}
int bel[N],tot,siz;
void dfs(int now,int blc){
bel[now]=blc,++siz;
for(int i=head[now];i;i=ed[i].nxt){
int v=ed[i].v,w=ed[i].w;
if(w!=_a||bel[v]==blc) continue;
dfs(v,blc);
}
}
int dis[N][(1<<17)+5];
deque<int> Q;
void Work(){
read(n),read(m),read(_a),read(_b);
for(int i=1;i<=m;++i){
int u,v,w;
read(u),read(v),read(w);
add(u,v,w);
}
for(int i=1;i<=n;++i){
if(bel[i]!=0) continue;
++tot,siz=0;
dfs(i,tot);
if(siz<=3) dfs(i,-i),--tot;
}
for(int i=1;i<=n;++i)
for(int S=0;S<(1<<tot);++S)
dis[i][S]=1e9;
dis[1][0]=0;
Q.push_back(1);
while(Q.size()){
int u=Q.front()%n,S=Q.front()/n;Q.pop_front();
if(!u) u=n;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v,w=ed[i].w;
if(w==_b&&bel[v]>0&&((S>>(bel[v]-1))&1)) continue;
if(w==_b&&bel[u]==bel[v]) continue;
int _nxtS=((w==_a||bel[u]<0)?S:(S|(1<<(bel[u]-1))));
if(dis[v][_nxtS]<=dis[u][S]+w) continue;
if(w==_a) dis[v][_nxtS]=dis[u][S]+_a,Q.push_front(_nxtS*n+v%n);
else dis[v][_nxtS]=dis[u][S]+_b,Q.push_back(_nxtS*n+v%n);
}
}
printf("0 ");
for(int i=2;i<=n;++i){
int ans=1e9;
for(int S=0;S<(1<<tot);++S)
if(dis[i][S]) chkmin(ans,dis[i][S]);
printf("%d ",ans);
}
}
int main(){Work();}
|
CF1152F Neko Rules the Catniverse
由于要求元素互不相同，所以我们希望记录元素是否被选择的状态。
观察数据范围，我们应该需要记录与 $m$ 相关的信息。
我们考虑怎么构造出这个序列，如果直接在序列末尾插入的话，那么需要记录与 $n$ 相关的信息。
但是如果我们可以在任意位置插入，并且强制要求它插在一个比它小的元素后，那么此时就只需要记录与 $m$ 相关的信息。
容易发现，只要我们从小到大依次插入元素，那么插入的元素一定会让它的后继元素比它小，同样也满足条件。
我们考虑 DP，令 $F(i,j,S)$ 表示考虑前 $i$ 个数，插入了 $j$ 个数，$[i-m+1,i]$ 内的元素的状态，转移只需考虑第 $i+1$ 个数是否被插入。
这样复杂度过高，但是我们总是从 $i$ 转移至 $i+1$，而且 $F(i,\ast,\ast)$ 到 $F(i+1,\ast,\ast)$ 的转移可以用一个固定的矩阵刻画，于是可以使用矩阵快速幂计算。
时间复杂度 $O((k2^m)^3\log n)$。
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
| #include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
void read(int &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void read(ll &x){
static char c;
while(!isdigit(c=getchar())); x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
void chkmax(int &x,int y){if(y>x)x=y;}
void chkmin(int &x,int y){if(y<x)x=y;}
void chkmax(ll &x,ll y){if(y>x)x=y;}
void chkmin(ll &x,ll y){if(y<x)x=y;}
const int N=305,Mod=1e9+7;
void Add(int &x,int y){(x+=y)>=Mod?x-=Mod:x;}
int n,k,m,_S,_U;
struct Matrix{
int A[N][N];
Matrix(){memset(A,0,sizeof A);}
void Init(){for(int i=0;i<_S;++i)A[i][i]=1;}
Matrix operator*(Matrix o){
Matrix res;
for(int i=0;i<_S;++i)
for(int j=0;j<_S;++j)
for(int k=0;k<_S;++k)
Add(res.A[i][j],1ll*A[i][k]*o.A[k][j]%Mod);
return res;
}
};
Matrix Bas;
void GetTrans(){
#define pc(x) __builtin_popcount(x)
for(int C=0;C<_S;++C){
int i=C/_U,S=C%_U;
if(i>k||pc(S)>i) continue;
if(i<k) Add(Bas.A[(i+1)*_U+(S<<1|1)%_U][C],1+pc(S));
Add(Bas.A[i*_U+(S<<1)%_U][C],1);
}
#undef pc
}
Matrix res;
void Pow(int b){
res.Init();
while(b){
if(b&1) res=res*Bas;
Bas=Bas*Bas,b>>=1;
}
}
void Work(){
read(n),read(k),read(m);
_U=1<<m,_S=(k+1)*_U,GetTrans(),Pow(n-1);
int Ans=0;
for(int S=0;S<_U;++S) Add(Ans,res.A[k*_U+S][0]),Add(Ans,res.A[k*_U+S][_U|1]);
printf("%d\n",Ans);
}
int main(){Work();}
|
