| Solved | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 11/11 | O | Ø | O | 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
题目描述
给定字符串，随机取一个子串，计算元音字母占子串长度比的期望。
解题思路
转化题意为求出所有子串中元音字母占子串长度比之和，除以子串个数。
枚举每个元音的贡献，设字符串$S=[S_1,S_2,…,S_l]$，$S_k$为元音，其总贡献即为$\sum_{i=1}^{k}\sum_{j=k}^{l}\frac 1{j-i+1}$，这个二维和可以通过维护$s(x)=\sum_{i=1}^{x}\frac 1x$的前缀和$t(x)=\sum_{i=1}^{x}s(x)$求出。
$\sum_{i=1}^{k}\sum_{j=k}^{l}\frac 1{j-i+1}$
$=\sum_{i=1}^{k}s(l-i+1)-s(k-i)$
$=t(l)-t(l-k)-t(k-1)$
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
typedef long long ll;
using namespace std;
char a[N];
double s[N],s2[N];
int main(){
int i,l;
scanf("%s",a+1);
l=strlen(a+1);
for(i=1;i<=l;i++){
s[i]=s[i-1]+1.0/i;
s2[i]=s2[i-1]+s[i];
}
double ans=0;
for(i=1;i<=l;i++)if(a[i]=='a'||a[i]=='e'||a[i]=='i'||a[i]=='o'||a[i]=='u'||a[i]=='y')ans+=s2[l]-s2[i-1]-s2[l-i];
printf("%.15f",ans/(l*(l+1.0)/2));
return 0;
}
B
题目描述
$x_1\oplus x_2\oplus…\oplus x_n=k$记为等式$1$，给定$x_i\in[0,m_i]$，给定$k$，求有多少种方法满足等式$1$。
解题思路
数位$DP$。
从高到低枚举每一位，设当前枚举到第$k$位。设$f[i][j]$表示前$i$个$m_p$的第$k$位为$1$的数中，选了$j$个$x_p$的第$k$位为$1$的总方案数（不设置异或和限制），则对每一个第$k$位为$1$的$x_p$有显然转移：
$f[i][j]=f[i-1][j-1]\times((x_p\text{&}((1<<k)-1))+1)+f[i-1][j]\times(1<<k)$
于是，设至少有一个在本位本来可以取$1$但是取$0$的数$x_l$，则其他位置怎么选都可以，但为了满足异或和为给定值$K$，$x_l$的值被确定，故$(count_k,j)$对答案的贡献为$\frac{f[i][j]}{2^k}$（$count_k$表示第$k$位为$1$的个数）。
如果可以全部取$1$，那么把$k-1$位当做最高位递归处理即可。枚举到$k<0$时，显然有方案数为$1$。
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
typedef long long ll;
using namespace std;
const ll mod=1000000007;
ll f[N][N],n,K,a[N];
ll qp(ll a,ll p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
ll solve(int k){
int i=0,j,p;
if(k<0)return 1;
memset(f,0,sizeof(f));
f[0][0]=1;
for(p=0;p<n;p++)
if(a[p]&(1<<k)){
i++;
for(j=0;j<=i;j++){
if(j)f[i][j]=(f[i-1][j-1]*((a[p]&((1<<k)-1))+1))%mod;
(f[i][j]+=f[i-1][j]*(1<<k))%=mod;
}
}else for(j=0;j<=i;j++)(f[i][j]*=(a[p]&((1<<k)-1))+1)%=mod;
ll ans=0,inv=qp(1<<k,mod-2);
for(j=((K>>k)&1);j<i;j+=2)
(ans+=f[i][j]*inv)%=mod;
if(i==j)(ans+=solve(k-1))%=mod;
return ans;
}
int main(){
int i;
while(~scanf("%lld%lld",&n,&K)){
for(i=0;i<n;i++)scanf("%lld",&a[i]);
printf("%lld\n",solve(30));
}
return 0;
}
C
题目描述
$n$堆石子，第$i$堆有$a_i$个石子，对前$i$堆石子分别玩$Nim$游戏，分别求先手保证胜利情况下第一轮有多少种不同的取法。
解题思路
solved by nikkukun
玩$Nim$游戏只要保证自己走完一步之后异或和为$0$即可。故设某次游戏中石子异或和为$x$，先手如果从第$p$堆石子里取，那么取完后该堆石子个数是$x\oplus a_p$，即（除了这堆石子以外的所有石子异或和）异或（这堆石子取完后剩余数量）为$0$。只要$a_p>x\oplus a_p$即可，即$x$的二进制最高位位置$a_p$为$1$的$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
typedef long long ll;
using namespace std;
ll a[100010],b[62];
int main(){
int i,j,n;
ll x=0;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%lld",&a[i]);
for(j=0;j<60;j++)if((a[i]>>j)&1)b[j]++;
x^=a[i];
if(!x)printf("0\n");
else{
for(j=59;j>=0;j--)if((x>>j)&1)break;
printf("%d\n",b[j]);
}
}
return 0;
}
D
题目描述
给定一个字符串，求对于字符串每一个前缀，$mex(lcp(suffix(i),suffix(j))(1\leq i<j\leq len))$。
解题思路
设有效节点表示$endpos$集合包含当前字符串最后一位的位置的节点（即$\text{parent tree}$上从根到$cur$的一条链上的所有节点）。
容易想出，$SAM$上如果根节点有两个以上孩子，那么这个前缀存在$lcp(i,j)=0$的两个后缀，而对其他有效节点$p$，如果有有效孩子$son(p)$，那么说明该节点有
$s_{e_1+len(p)}\in endpos(p),s_{e_2+len(p)}\in endpos(p)$（$e_2+len(p)=len(s)$），而
$s_{e_1+len(p)}\notin endpos(son(p)),s_{e_2+len(p)}\in endpos(son(p))$。
于是$lcp(suffix(e_1),suffix(e_2))=len(p)$，也即$lcp(p,son(p))=len(p)$。
$upd:$队友@nikkukun指出我以前的算法错误，已经删掉
有牛逼结论：如果一个有孩子的节点$p$对应长度$len(p)\in lcp(i,j)$，那么$len(p)-1\in lcp(i,j)$。可以从直观角度理解一下：
若$lcp(suffix(a),suffix(b))=len$，则$lcp(suffix(a+1),suffix(b+1))=len-1$。
所以在动态插入的时候维护一下是否存在$lcp=0$、最大$len$为多少这两个即可均摊$O(n)$求解了。
AC代码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
typedef long long ll;
using namespace std;
char a[N];
set<int>mex;
struct SAM{
int tr[N<<1][P],fa[N<<1],len[N<<1],siz[N<<1];
int cnt,last,count;
void init(){
cnt=last=1;
count=0;
memset(tr[1],0,sizeof(tr[1]));
fa[1]=len[1]=0;
}
void add(int c){
int p=last,np=++cnt;
memset(tr[cnt],0,sizeof(tr[cnt]));
siz[np]=1;
last=np;
len[np]=len[p]+1;
while(p&&!tr[p][c])tr[p][c]=np,p=fa[p];
if(!p){
fa[np]=1;
if(count<2){
count++;
if(count==2)mex.insert(0);
}
}
else{
int q=tr[p][c];
if(len[q]==len[p]+1)fa[np]=q,mex.insert(len[q]);
else{
int nq=++cnt;len[nq]=len[p]+1;
memcpy(tr[nq],tr[q],sizeof(tr[q]));
fa[nq]=fa[q];
fa[q]=fa[np]=nq;mex.insert(len[nq]);
while(tr[p][c]==q)tr[p][c]=nq,p=fa[p];
}
}
}
void insert(char a[]){
int i,ans=0;
for(i=0;a[i];i++){
add(a[i]-'a');
while(mex.count(ans))ans++;
printf("%d ",ans);
}
puts("");
}
}sam;
int main(){
int i,T;
scanf("%d",&T);
while(T--){
scanf("%s",a);
sam.init();
mex.clear();
sam.insert(a);
}
return 0;
}AC代码2
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
typedef long long ll;
using namespace std;
char a[N];
struct SAM{
int tr[N<<1][P],fa[N<<1],len[N<<1],siz[N<<1];
int cnt,last,count;
int mxlen;
void init(){
cnt=last=1;
count=0;
memset(tr[1],0,sizeof(tr[1]));
fa[1]=len[1]=mxlen=0;
}
void add(int c){
int p=last,np=++cnt;
memset(tr[cnt],0,sizeof(tr[cnt]));
siz[np]=1;
last=np;
len[np]=len[p]+1;
while(p&&!tr[p][c])tr[p][c]=np,p=fa[p];
if(!p)fa[np]=1,count++;
else{
int q=tr[p][c];
if(len[q]==len[p]+1)fa[np]=q;
else{
int nq=++cnt;len[nq]=len[p]+1;
memcpy(tr[nq],tr[q],sizeof(tr[q]));
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
while(tr[p][c]==q)tr[p][c]=nq,p=fa[p];
}
mxlen=max(mxlen,len[fa[np]]);
}
}
void insert(char a[]){
int i,ans=0;
for(i=0;a[i];i++){
add(a[i]-'a');
if(count<2)ans=0;
else ans=mxlen+1;
printf("%d ",ans);
}
puts("");
}
}sam;
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%s",a);
sam.init();
sam.insert(a);
}
return 0;
}
E
题目描述
定义树上一个节点的“结实程度”为，将这个节点的子树中的所有的节点编号拿出来之后，按照从小到大的顺序排列，然后将相邻元素做差之后求平方和。即假设子树的节点编号排序后的序列为$a_1,a_2,a_3,…,a_k$，这个节点的“结实程度”就是$\sum_{i=1}^{k-1}\left(a_{i+1}-a_i\right)^2$。求一棵树每个节点的”结实程度“。
解题思路
直接启发式合并，维护时把节点丢进$set$处理即可。
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
typedef long long ll;
using namespace std;
struct Edge{
int e,n;
}e[N];
int hd[N],cnt;
void add(int a,int b){e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;}
int siz[N],mxs[N];
void dfs(int p){
int i;
siz[p]=1;
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
dfs(q);
siz[p]+=siz[q];
if(!mxs[p]||siz[mxs[p]]<siz[q])mxs[p]=q;
}
}
ll ans[N],ANS;
set<int>S;
void mdf(int p,int flag){//add/del p to/from S&ANS
int l=((!S.empty()&&*S.begin()<p)?*(--S.lower_bound(p)):-1);//<p max
int r=((!S.empty()&&*--S.end()>p)?*S.upper_bound(p):-1);
int add=flag?1:-1;
if(l==-1&&r!=-1)ANS+=add*(1LL*p-r)*(p-r);
else if(l!=-1&&r==-1)ANS+=add*(1LL*p-l)*(p-l);
else if(l!=-1&&r!=-1)ANS+=add*((1LL*p-l)*(p-l)+(1LL*p-r)*(p-r)-(1LL*l-r)*(l-r));
if(!flag)S.erase(p);
else S.insert(p);
}
void bf(int p,int flag){
int i;
mdf(p,flag);
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
bf(q,flag);
}
}
void dfs2(int p,int flag){
int i;
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(q!=mxs[p])dfs2(q,0);
}
if(mxs[p])dfs2(mxs[p],1);
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(q!=mxs[p])bf(q,1);
}
mdf(p,1);
ans[p]=ANS;
if(!flag)bf(p,0);
}
int main(){
int i,n,f;
scanf("%d",&n);
for(i=2;i<=n;i++){
scanf("%d",&f);
add(f,i);
}
dfs(1);
dfs2(1,1);
for(i=1;i<=n;i++)printf("%lld\n",ans[i]);
return 0;
}
F
题目描述
在一棵树上，单点修改（在某点出现了$x$个新蘑菇），求从某处出发，采集到所有蘑菇所需的代价之和。从起点$v$收集在$u$节点的蘑菇所需代价定义为路径$(u,v)$上最靠近$v$的边的边权。
解题思路
先考虑用某种方式维护子树和（即子树$p$的孩子个数）（比如用树状数组在$dfs$序上维护），询问时枚举起点所连边，边权$\times $对应子树和/父树和即可求出答案。
但这样显然会被菊花图卡掉。考虑枚举的时候只考虑重儿子、父亲、所有轻儿子三部分，在修改时不仅更新子树和，还更新所有影响到的“轻儿子”部分（每个链的$top$的父亲的”轻儿子“部分），容易证明修改到的数量是$\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
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
typedef long long ll;
using namespace std;
int n,cnt,hd[N];
struct Edge{
int e,n,l;
}e[N<<1];
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 tosonlen[N],tofalen[N],lightsonsum[N];
int depth[N],fa[N],size[N],son[N],top[N];
void dfs1(int now,int f,int dep){
depth[now]=dep;
fa[now]=f;
size[now]=1;
int i,mx=0;
for(i=hd[now];i;i=e[i].n){
int p=e[i].e;
if(p!=f){
dfs1(p,now,dep+1);
size[now]+=size[p];
if(size[p]>mx){
mx=size[p];
son[now]=p;
}
}
}
}
void dfs2(int now,int Top){
int i;
top[now]=Top;
if(son[now])dfs2(son[now],Top);
for(i=hd[now];i;i=e[i].n){
int p=e[i].e;
if(p!=son[now]&&p!=fa[now])dfs2(p,p);
else if(p==fa[now])tofalen[now]=e[i].l;
else if(p==son[now])tosonlen[now]=e[i].l;
}
}
int tot,dL[N],dR[N];
void dfs(int p,int f){//full dfn
dL[p]=++tot;
int i;
for(i=hd[p];i;i=e[i].n)if(e[i].e!=f)dfs(e[i].e,p);
dR[p]=++tot;
}
ll bit[N<<1];//mushroom count in subtree of p, dfn prefix
void add(int p,int x){while(p<N<<1)bit[p]+=x,p+=p&(-p);}
ll query(int p){
ll ans=0;
if(p<0)return 0;
while(p)ans+=bit[p],p-=p&(-p);
return ans;
}
int root=1,sum;
/*
int debugcnt[N];
int dfs4debug(int p,int f){
int i,ans=debugcnt[p];
for(i=hd[p];i;i=e[i].n)
if(e[i].e!=f)
ans+=dfs4debug(e[i].e,p);
return ans;
}
ll debug(int p){
int i;
ll ans=0;
for(i=hd[p];i;i=e[i].n)ans+=1LL*e[i].l*dfs4debug(e[i].e,p);
return ans;
}
*/
int main(){
int i,q;
scanf("%d",&n);
for(i=1;i<n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
dfs1(1,0,1);
dfs2(1,1);
dfs(1,0);
scanf("%d",&q);
while(q--){
int opt,v,x;
scanf("%d%d",&opt,&v);
if(opt==1){
scanf("%d",&x);
sum+=x;
//debugcnt[v]+=x;
add(dR[v],x);//hard
while(v){
v=top[v];
lightsonsum[fa[v]]+=tofalen[v]*x;
v=fa[v];
}
}else root=v;
ll ans=0;
ans+=tofalen[root]*(sum-query(dR[root])+query(dL[root]));
ans+=tosonlen[root]*(query(dR[son[root]])-query(dL[son[root]]));
ans+=lightsonsum[root];
//if(ans!=debug(root))
printf("%lld\n",ans);
}
return 0;
}
G
题目描述
平面上有一些白点和黑点，求白点内部连边、黑点内部连边，保证白点互相连通、黑点互相连通，且没有两条边在城镇点以外的地方相交。保证没有三点共线或重叠。
解题思路
upsolved by qxforever
显然，凸包上必然是全黑/全白/一黑一白，不存在其余情况。
下面证明这三种情况必然能构造出连边方式：
先定义一个方法$work(w,b_1,b_2)$，表示白点$w$，黑点$b_1,b_2$（或$work(b,w_1,w_2)$）已经直接或间接相连，现在要把所有三角形内的白点同$w$相连，黑点同$b_1,b_2$相连。实现方式：如果三角形内存在白点$W$，那么连接$W,w$，执行$work(W,b_1,b_2),work(b_1,w,W),work(b_2,w,W)$；否则把所有黑点连向$b_1$即可。
对于全黑/全白两种情况，直接全连起来，枚举内部异色点$p$，不断调用$work(p,c_i,c_{i+1})$即可；否则把黑白分别相连然后找到凸包上分割黑白的点$p,q$，分别对两边剖成三角，分别进行$work$即可。
AC代码 - by qxforever
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
163
164
165
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-8;
typedef pair<int,int> pii;
struct Point{
double x,y;int id,c;
Point(double x=0,double y=0):x(x),y(y) {}
bool operator < (const Point &b)
{
return x<b.x||(x==b.x&&y<b.y);
}
void read(){scanf("%lf%lf",&x,&y);}
};
typedef Point Vector;
Point operator + (Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
Point operator - (Point A,Point B) {return Point(A.x-B.x,A.y-B.y);}
Point operator * (Point A,double B) {return Point(A.x*B,A.y*B);}
Point operator / (Point A,double B) {return Point(A.x/B,A.y/B);}
int dcmp(double x)
{
if(fabs(x)<eps) return 0;
return x<0 ? -1 : 1;
}
bool operator == (const Point &a,const Point &b)
{
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double dot(Vector a,Vector b)
{
return a.x*b.x+a.y*b.y;
}
double length(Vector a)
{
return sqrt(dot(a,a));
}
double angle(Vector a,Vector b)
{
return acos(dot(a,b))/length(a)/length(b);
}
double cross(Vector a,Vector b)
{
return a.x*b.y-a.y*b.x;
}
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2)
{
double c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1);
double c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
int isPointInPolygon(Point p,Point* poly,int n)
{
int wn=0;
for(int i=0;i<n;i++){
int k=dcmp(cross(poly[(i+1)%n]-poly[i],p-poly[i]));
int d1=dcmp(poly[i].y-p.y);
int d2=dcmp(poly[(i+1)%n].y-p.y);
if(k>0&&d1<=0&&d2>0) wn++;
if(k<0&&d2<=0&&d1>0) wn--;
}
if(wn!=0) return 1;
return 0;
}
int ConvexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
int m=0;
for(int i=0;i<n;i++){
while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-2;i>=0;i--){
while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
if(n>1) m--;
return m;
}
const int maxn = 3e3+23;
Point a[maxn<<1],ch[maxn<<1];
vector<pii> ans;
int n,m;
void work(Point x,Point y,Point z)
{
//printf("%d %d %d\n",x.id,y.id,z.id);
//ans.push_back({y.id,z.id});
Point tmp[]={x,y,z},ch[5],t;
ConvexHull(tmp,3,ch);ch[3]=ch[0];
bool f=true;
for(int i=0;i<n+m&&f;i++){
if(a[i].c==x.c&&a[i].id!=x.id&&isPointInPolygon(a[i],ch,3)) f=false,t=a[i];
}
if(!f){
work(t,y,z);
ans.push_back({x.id,t.id});work(y,x,t);
work(z,x,t);
}
else{
vector<Point> p;
for(int i=0;i<n+m;i++){
if(a[i].c==y.c&&a[i].id!=y.id&&a[i].id!=z.id&&isPointInPolygon(a[i],ch,3)) p.push_back(a[i]);
}
for(Point i:p) ans.push_back({i.id,y.id});
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n+m;i++) a[i].read(),a[i].id=i,a[i].c=(i>=n);
int t=ConvexHull(a,n+m,ch);ch[t]=ch[0];
bool f=true;
for(int i=0;i<t;i++){
if(ch[i].c!=ch[0].c) f=false;
}
if(f){
Point p;
for(int i=0;i<n;i++){
if(a[i].c!=ch[0].c) p=a[i];
}
//printf("%.3f %.3f\n",p.x,p.y);
for(int i=0;i<t;i++) {
//cout<<i<<endl;
//printf("%.3f %.3f\n",ch[i].x,ch[i].y);
if(i!=t-1)ans.push_back({ch[i].id,ch[i+1].id});
work(p,ch[i],ch[i+1]);
}
}
else{
int c=0;
for(int i=0;i<t;i++){
if(ch[i].c!=ch[i+1].c) c++;
}
if(c>2) return 0*printf("Poor Quailty");
int p=-1,q=-1;
for(int i=0;i<t;i++){
if(ch[i].c!=ch[i+1].c) p<0?p=i:q=i;
}
for(int i=(p+1)%t;i!=q;i=(i+1)%t){
ans.push_back({ch[i].id,ch[i+1].id});
work(ch[p],ch[i],ch[i+1]);
}
for(int i=(q+1)%t;i!=p;i=(i+1)%t){
ans.push_back({ch[i].id,ch[i+1].id});
work(ch[q],ch[i],ch[i+1]);
}
}
//printf("ans.size : %u\n",ans.size());
sort(ans.begin(),ans.end());
//for(pii i:ans) printf("%d %d\n",i.first,i.second);
for(int i=0;i<n-1;i++) printf("%d %d\n",ans[i].first+1,ans[i].second+1);
for(int i=n-1;i<n+m-2;i++) printf("%d %d\n",ans[i].first+1-n,ans[i].second+1-n);
}
/*
3 4
5 0
0 5
-5 0
1 1
1 2
-1 1
-1 2
*/
H
题目描述
一个长度为$ {n}$ 的序列$A$，元素的值域是$ {[1,m]}$。
对于任意$ x,y \in [1,m],x \neq y$，序列中存在一个位置 $p(1 \leq p < n)$，满足$ {A[p]=x,A[p+1]=y}$或者 ${A[p+1]=x,A[p]=y}$。
给定$n$，求$m$最大值，并构造一个这样的序列。
解题思路
转化成图论模型，是一个阶为$m$的完全图中，每一对$(u,v)$都经过的路径。
当$m$为奇数时，完全图每个节点的度即为偶数（$m-1$），直接求欧拉回路即可。
当$m$为偶数时，需要再连$\frac m2-1$条边形成一条欧拉路径。
欧拉回路求的时候用$cur[i]$代替$hd[i]$居然可以卡常数（赛时一直$TLE$，但因为情况比较少，手动构造过了
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
typedef long long ll;
using namespace std;
ll n,m;
vector<int>ans;
bool check(ll x)
{
return n>=(x&1?x*(x-1)/2+1:x*x/2);
}
int main()
{
scanf("%lld",&n);
ll L=0,R=2e9;
while(R-L>1){
//cout<<R<<endl;
ll mid=(L+R)/2;
if(check(mid)) L=mid;
else R=mid;
}
m=L;
printf("%lld\n",m);
if(n>2000000) return 0;
if(m%2){
if(m==1)return printf("1"),0;
ans.pb(1);ans.pb(2);ans.pb(3);ans.pb(1);
for(int o=4;o<=m;o+=2){
ans.pb(o);
for(int p=2;p<o;p+=2){
ans.pb(p+1);
ans.pb(o+1);
ans.pb(p);
ans.pb(o);
}
ans.pb(o+1);
ans.pb(1);
}
}else{
ans.pb(2);ans.pb(1);
for(int o=3;o<=m;o+=2){
ans.pb(o);
for(int p=2;p<o;p++){
ans.pb(p);
ans.pb(o+((p%2)==0));
}
ans.pb(o);
ans.pb(o+1);
ans.pb(1);
}
}
for(int i=0;i<ans.size();i++)printf("%d%c",ans[i]," \n"[i==n-1]);
for(int i=ans.size();i<n;i++)printf("1%c"," \n"[i==n-1]);
return 0;
}
直接求欧拉回路：（需要优化）
AC代码2 - by qxforever
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
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e6+23;
const int N = 4e3;
ll n,m;
int cnt;
int e[maxn<<1],hd[maxn<<1],nxt[maxn<<1];
int vis[maxn<<1];
void add(int x,int y)
{
e[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt;
}
int ans[maxn],tot;
bool check(ll x)
{
return n>=(x&1?x*(x-1)/2+1:x*x/2);
}
int cur[maxn<<1];
inline void euler(int u)
{
for(int i=cur[u];i;i=cur[u]){//优化
cur[u]=nxt[i];
if(vis[i]) continue;
vis[i]=vis[i+((i&1)?1:-1)]=1;
euler(e[i]);
ans[tot++]=e[i];
}
}
int main()
{
cin>>n;
ll L=0,R=2e9;
while(R-L>1){
//cout<<R<<endl;
ll mid=(L+R)/2;
if(check(mid)) L=mid;
else R=mid;
}
m=L;
assert(!check(m+1));
printf("%lld\n",m);
if(n>2000000) return 0;
for(int i=1;i<=m;i++){
for(int j=i+1;j<=m;j++) add(i,j),add(j,i);
}
if(m%2==0){
for(int i=2;i<m-1;i+=2) add(i,i+1),add(i+1,i);
}
for(int i=1;i<=m;i++)cur[i]=hd[i];
euler(1);
cnt=1;
printf("1");
for(int i=tot-1;i>=0;i--) printf(" %d",ans[i]);
for(int i=tot+1;i<n;i++) printf(" %d",1);
puts("");
return 0;
}
I
题目描述
有一个$n\times m$的矩阵，每个位置上都有一个宝箱，宝箱需要一定的投币才能打开。给定$m$个限定条件（某相邻两个宝箱的投币之和$\geq w$，求最少需要的硬币之和。
解题思路
看做一个二分图的最佳匹配即可，费用流/KM算法求解。
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
typedef long long ll;
using namespace std;
struct Edge{
int e,l,c,n;
}e[200*N];
struct Pre{
int pre,edge;
}pre[N];
int hd[N],vis[N],cnt=1,n,m,s,t;
ll maxflow,mincost,dis[N],flow[N];
void add(int a,int b,int l,int c){
e[++cnt].e=b;
e[cnt].l=l;
e[cnt].c=c;
e[cnt].n=hd[a];
hd[a]=cnt;
}
void addE(int a,int b,int l,int c){
add(a,b,l,c);
add(b,a,0,-c);
}
queue<int>Q;
int spfa(){
memset(dis,0x3f,sizeof(dis));
memset(flow,0x3f,sizeof(flow));
memset(vis,0,sizeof(vis));
while(!Q.empty())Q.pop();
int i,top,q;
Q.push(s);vis[s]=1;dis[s]=0;pre[t].pre=0;
while(!Q.empty()){
top=Q.front();
Q.pop();
vis[top]=0;
for(i=hd[top];i;i=e[i].n){
q=e[i].e;
if(e[i].l&&dis[q]>dis[top]+e[i].c){
dis[q]=dis[top]+e[i].c;
pre[q].pre=top;
pre[q].edge=i;
flow[q]=min(flow[top],(ll)e[i].l);
if(!vis[q]){
vis[q]=1;
Q.push(q);
}
}
}
}
return pre[t].pre;
}
void ek(){
int i;
while(spfa()){
maxflow+=flow[t];
mincost+=flow[t]*dis[t];
for(i=t;i!=s;i=pre[i].pre){
e[pre[i].edge].l-=flow[t];
e[pre[i].edge^1].l+=flow[t];
}
}
}
signed main(){
int i,j,k,x1,y1,x2,y2,w;
scanf("%lld%lld%lld",&n,&m,&k);
s=n*m;t=s+1;
while(k--){
scanf("%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&w);
x1--;y1--;x2--;y2--;
int a=x1*m+y1,b=x2*m+y2;
if((x1+y1)&1)swap(a,b);
addE(a,b,1,-w);
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if((i+j)&1)addE(i*m+j,t,1,0);
addE(s,i*m+j,1,0);
}
}
ek();
printf("%lld",-mincost);
return 0;
}
J
题目描述
给定了一个$2-sat$模板，问如何$hack$能够把时间复杂度卡到$O(n^2)$。
解题思路
观察发现，这个模板的特点是枚举变量值，不确定就入栈假设为$1$，如果推翻假设那么出栈更新。这样构造一个中间始终无法确定变量的值、最后如果都是$1$那么就会产生矛盾的数据即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef long long ll;
using namespace std;
int main(){
int i,n;
scanf("%d",&n);
printf("%d\n",n);
for(i=1;i<n;i++)printf("%d %d\n",-i,i+1);
printf("%d %d",-n,-n);
return 0;
}
K
题目描述
一个包含$n$个单词的词典，每个词有一定单价，要求恰好通过这些单词拼出给定字符串$T$，求最少花费。
解题思路
对词典建立$AC$自动机，在自动机上逐字符匹配$T$，保证当前节点始终对应的是自动机上最长的匹配$T$后缀的位置。
设$f[i]$为凑出$T$的前$i$个字符的最少花费，每次沿着失配指针向上跳枚举最后一次匹配的后缀起始位置进行$dp$即可。
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
typedef long long ll;
using namespace std;
ll f[N];
struct ACAM{
int tr[N][26],tot;
int fail[N],num[N],now,sign[N];
int q[N],hd,tl;
ll val[N];
int len[N];
void insert(int cost,char s[]){
int i;
now=0;
for(i=0;s[i];i++){
int p=s[i]-'a';
if(!tr[now][p])tr[now][p]=++tot;
now=tr[now][p];
len[now]=i+1;
}
if(!val[now])val[now]=cost;
else val[now]=min(val[now],(ll)cost);
}
void build(){
int i;
for(i=0;i<26;i++)if(tr[0][i])q[++tl]=tr[0][i];
while(hd<tl){
int p=q[++hd];
for(i=0;i<26;i++){
if(tr[p][i])fail[tr[p][i]]=tr[fail[p]][i],q[++tl]=tr[p][i];
else tr[p][i]=tr[fail[p]][i];
}
}
}
ll ask(char a[]){
int i,now=0;
for(i=0;a[i];i++){
now=tr[now][a[i]-'a'];
int suf=now;
while(suf){
if(val[suf]){
if(i+1==len[suf])f[i]=min(f[i],0+val[suf]);
else f[i]=min(f[i],f[i-len[suf]]+val[suf]);
}
suf=fail[suf];
}
}
if(f[i-1]>1e16)return -1;
return f[i-1];
}
}T;
char s[N],t[N];
int main(){
int i,n,cost;
memset(f,0x3f,sizeof(f));
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%s%d",t,&cost);
T.insert(cost,t);
}
T.build();
scanf("%s",s);
printf("%lld",T.ask(s));
return 0;
}