本文章施工中……
进度[===================>] 10/10 100%
施工完成。
A. 托米的字符串
题目描述
小D面前有$n$个黑色的气球。
假设第$i$个黑色气球的高度是一个正整数$h_i$，现在小D知道了任意两个不同气球的高度之和，你能帮小D还原出每个黑色气球的具体高度嘛？
题目分析
签到题，特判一下$n=2$的情况即可。
代码
来自cyy的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <bits/stdc++.h>
using namespace std;
int mt[1005][1005];
int main() {
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
scanf("%d",&mt[i][j]);
}
}
if (n == 2) {
if (mt[1][2] == 2) printf("1 1\n");
else printf("No Answer\n");
}
else {
int x1 = (mt[1][2] + mt[1][3] - mt[2][3]) >> 1;
printf("%d",x1);
for (int i=2;i<=n;i++) printf(" %d",mt[1][i]-x1);
printf("\n");
}
return 0;
}
|
B. 小吨的点分治
题目描述
有一天，小吨向火山哥请教了点分治的写法。火山哥教了小吨如下的点分治算法:
- 初始时当前连通块是整棵树。
- 首先，在当前连通块中找到任意一个点$u$作为该次的分治中心（不必是重心）。
- 其次，把点$u$在当前连通块中删去，可以得到若干个连通块。对于每个连通块再递归进行这样的操作。
不难发现，小吨从黑心火山哥那里学到的点分治在最坏情况下递归层数可以达到$O(n)$层。现在，好奇的小吨想要知道，对于一棵给定的包含$n$个节点的树，他有多少种不同的点分治方案呢？因为答案可能很大，你只需要输出它对$10^9+7$取模的值即可。
两种点分治方案不同当且仅当某一个连通块所选的点分治中心不同。
为了避免因为大家所学算法的具体细节不同出现歧义，我们还提供了一份暴力代码来具体描述这个算法。
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
| const int mod=1e9+7;
const int maxn=5005;
bool vis[maxn];
vector<int> e[maxn];
int n;
inline void view_all(vector<int> &cur,int x,int fa){
cur.push_back(x);
for(int p: e[x]){
if (vis[p]) continue;
if (p == fa) continue;
view_all(cur, p, x);
}
}
inline int calc(int x){
vector<int> cur;
int ans = 0;
view_all(cur, x, -1);
for(int w: cur){
int res = 1;
vis[w] = 1;
for(int p: e[w]){
if (vis[p]) continue;
res = 1ll * res * calc(p) % mod;
}
vis[w] = 0;
ans = (ans + res) % mod;
}
return ans;
}
inline int get_ans(){
return calc(1);
}
|
题目分析
题解ppt讲得很好了，由于不需要考虑重心的影响，故：
假设我们已经对一棵树进行了点分治得到对应的点分树。如果我们删去原树中的一条边，把得到的两个连通块中的点分别称为黑点和白点。对于点分树中的每个白点（黑点），我们找到它的祖先中最近的一个白点（黑点）作为它新的父亲，这样就能得到两棵全由白点组成的树和全由黑点组成的树（因为有且仅有一个白点和黑点找不到同色的祖先），它们分别为原树切分得到的两棵树的点分树。
反过来再考虑，如果我们把两棵树通过一条边$(u,v)$连接起来，我们怎样把原有的两棵点分树合并起来，并且保持原本点分树中的祖先后代关系呢？可以发现，我们只要把$u$到所在点分树根节点的路径以及$v$到所在点分树根节点的路径按任意顺序归并起来即可。
因此可以使用树形DP解决这个问题，合并的时候我们只需要关心树的根结点所在点分树的深度。
设$f(i,j)$表示，树根为$i$，$i$在点分树中深度为$j$的点分治方案数。
有：
普通的树形DP是$O(n^2)$的，其中$f(y,k)$可以做个前缀和降到$O(n^3)$。又观察到这是一个用树上背包的真实结点为代价进行转移的方程，故限制转移条件就可以做到$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
| #include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
typedef long long LL;
const int maxn=5005,p=1e9+7;
int n,Size[maxn];
LL f[maxn][maxn],sum[maxn][maxn],tmp[maxn],C[maxn][maxn];
vector<int> edges[maxn];
void AddEdge(int x,int y) {edges[x].push_back(y);}
void TreeDp(int Now,int fa) {
Size[Now]=1;
for(int i=2; i<=n; i++)f[Now][i]=0;
f[Now][1]=1;
for(int Next:edges[Now]) {
if(Next==fa)continue;
TreeDp(Next,Now);
Size[Now]+=Size[Next];
for(int i=0; i<=Size[Now]-Size[Next]; i++)tmp[i]=f[Now][i],f[Now][i]=0;
for(int i=1; i<=Size[Now]; i++)
for(int j=min(i-1,Size[Next]); j>=0&&i-j<=Size[Now]-Size[Next]; j--)
f[Now][i]=(f[Now][i]+tmp[i-j]*sum[Next][j]%p*C[i-1][i-j-1]%p)%p;
}
for(int i=Size[Now]; i>=0; i--)sum[Now][i]=(sum[Now][i+1]+f[Now][i])%p;
}
int main() {
n=Get_Int();
C[0][0]=1;
for(int i=1; i<=n; i++) {
C[i][0]=C[i][i]=1;
for(int j=1; j<i; j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
}
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
TreeDp(1,0);
printf("%lld\n",sum[1][0]);
return 0;
}
|
C. 无向图定向
题目描述
火山哥手里有一个$n$个点$m$条边的无向图。
现在，火山哥请你把无向图的每条边确定一个方向，使之成为一个DAG，并且最小化最长路的长度。
这里一条路径的长度指的是经过边的数量。
题目分析
题解表示这道题是eazy。
过题人数表示这道题是eazy。
但是为什么我们就没想出来呢？！！一点都不eazy好吧！
这道题可以用到Dilworth定理来思考，也可以不用，但是用了Dilworth可能可以更好理解（可以装逼）
Dilworth定理：偏序集能划分成的最少的全序集个数等于最大反链的元素个数。
本题原本要求最长路的最小长度，我们假设偏序集为点对无法连通，则反链为点对能连通的偏序关系，则最长反链为最长路。
根据Dilworth定理，可以转化为最少全序集的个数。也就是原题题意变为将无向图定向后，将点集划分为若干个集合，满足集合内的点两两不连通，最小化这样的集合数目。也就是最小化独立集的数目。
（上述说明从偏序应满足的性质考虑有问题，尚未想到如何修改）
可以证明，在原无向图中随意找出一个两两不连边的点集，总有一种定向方案使得它们在有向图中是一个独立集。（证明之后再讲）
那么这道题就变成一个简单的状压DP了。
另一种不用Dilworth定理的思考方法：
上面第一种方法的证明同样可以用图中分层编号的思想证明。
代码
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
| #include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
int n,m,a[20][20],Disable[1<<17],f[1<<17];
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
a[x][y]=a[y][x]=1;
}
for(int S=1; S<(1<<n); S++)
for(int i=1; i<=n; i++)
if(S>>(i-1)&1)
for(int j=i+1; j<=n; j++)
if((S>>(j-1)&1)&&a[i][j])Disable[S]=1;
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int S=1; S<(1<<n); S++)
for(int T=S; T; T=S&(T-1))
if(!Disable[T])f[S]=min(f[S],f[S^T]+1);
printf("%d\n",f[(1<<n)-1]-1);
return 0;
}
|
D. 求和
题目描述
令$f(n)=\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j,n)$，求$\sum_{i=1}^n f(i)$
请输出答案对$mod$取模的值。保证$mod$是个质数。
题目分析
简单莫比乌斯反演，就是打这篇题解有点麻烦。
故：
用杜教筛处理欧拉函数，用数论根号分块计算答案，故时间复杂度为：
根据积分可得$T(n)=O(n^{\frac 56})$
代码
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>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
typedef long long LL;
#define pii pair<LL,LL>
#define mp make_pair
const LL limit=1000000,hashmod=999959;
bool vst[limit+5];
int cnt=0,Prime[limit+5];
LL n,mod,Phi[limit+5],inv2,inv6;
vector<pii> Hash[hashmod+5];
void Table(int n) {
Phi[1]=1;
for(int i=2; i<=n; i++) {
if(!vst[i]) {
Prime[++cnt]=i;
Phi[i]=i-1;
}
for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
vst[i*Prime[j]]=1;
if(i%Prime[j]==0) {
Phi[i*Prime[j]]=Phi[i]*Prime[j];
break;
}
Phi[i*Prime[j]]=Phi[i]*Phi[Prime[j]];
}
}
for(int i=2; i<=n; i++)Phi[i]=(Phi[i]+Phi[i-1])%mod;
}
void Add(int x,LL p,LL v) {
Hash[x].push_back(mp(p,v));
}
LL Cal(LL n) {
if(n<=limit)return Phi[n];
for(pii x:Hash[n%hashmod])if(x.first==n)return x.second;
LL next,ans=0;
for(LL i=2; i<=n; i=next+1) {
next=n/(n/i);
ans=(ans+(next-i+1)%mod*Cal(n/i)%mod)%mod;
}
ans=(n%mod*(n%mod+1)%mod*inv2%mod-ans+mod)%mod;
Add(n%hashmod,n,ans);
return ans;
}
LL g(LL x) {return x*(x+1)%mod*(2*x+1)%mod*inv6%mod;}
LL Quick_Pow(LL a,LL b) {
LL sum=1;
for(; b; b>>=1,a=a*a%mod)if(b&1)sum=sum*a%mod;
return sum;
}
int main() {
n=Get_Int();
mod=Get_Int();
inv2=(mod+1)/2;
inv6=Quick_Pow(6,mod-2);
Table(min(n,limit));
LL next=1,ans=0,last=0;
for(int i=1; i<=n; i=next+1) {
next=n/(n/i);
LL now=Cal(next);
ans=(ans+(now-last+mod)%mod*g(n/i)%mod)%mod;
last=now;
}
printf("%lld\n",ans);
return 0;
}
|
E. 棋技哥
题目描述
火山哥和鸡老八在下棋。
这张棋盘是$n\times m$的。每一个格子要么是黑色的，要么是白色的。
两个人轮流进行操作。火山哥先手。每一次可以选择一个黑色的格子，以这个格子为右下角，棋盘左上角为左上角，将这个矩阵的所有格子的颜色由黑变成白，由白变成黑。如果找不到一个黑色的格子，那么那个人就输了。
现在两个人都想让火山哥赢，请问谁能赢呢。
题目分析
注意到一个性质，每人每次操作时，总会使左上角的格子反色。
那么考虑，如果火山哥先手时，左上角格子是黑色，那么火山哥操作后左上角格子变白，如果游戏还未结束，那么轮到火山哥操作时，左上角的格子还是黑色。
由于游戏一定会结束，而在火山哥状态时游戏必然不结束，故火山哥先手左上角格子是黑色时，火山哥必胜（和谁想谁赢一点关系都没有）。
如果火山哥先手时，左上角格子是白色，那么两者恰好相反，火山哥必败。
代码
来自cyy的奥利给代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <bits/stdc++.h>
using namespace std;
char mt[505][505];
int main() {
int T;
scanf("%d",&T);
while (T --) {
int n,m;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) {
scanf(" %c",&mt[i][j]);
}
if (mt[1][1] == '1') printf("call\n");
else printf("aoligei\n");
}
return 0;
}
|
F. 社团管理
题目描述
火山哥管理着一个$n$个人的社团。
有一天，这$n$个人要外出执行$k$个任务。这$n$个人从左到右站成了一排，其中第$i$个人支持$a_i$当老大。为了方便管理，火山哥决定把这$n$个人分成恰好$k$段(每段非空)分别执行各自的任务。
但是为了社团平衡，火山哥决定要让执行同一任务且$a_i$相同的二元组$(i,j)$尽量少，即假设在第$i$段里支持第$j$个人的个数是$c(i,j)$，那么火山哥就需要最小化
请你输出这个最小值。
题目分析
cf原题，868F。
dp方程很好写，但是状态转移的代价函数无法处理。
不过这道题有决策单调性，证明参见这里。
考虑用分治进行决策单调性的转移。
设$Solve(k,L,R,l,r)$表示用$f(k-1,l\sim r)$为决策转移求出$f(k,L\sim R)$。
每次暴力求出$f(k,mid=\frac{L+R}2)$，得到最优决策点$id$，递归$Solve(k,L,mid-1,l,id)$和$Solve(k,mid+1,R,id,r)$。
怎么计算$cost$函数呢？这里就体现出来了用分治实现决策单调性的优越性，可以用莫队的方式暴力统计，每次指针移动到对应区间即可。
每次$Solve$时枚举次数上界是$O(r-l+1)$，而统计指针的移动次数显然是关于它线性的。
那么时间复杂度是$O(nk\log n)$，至于$l,r$区间每一层会出现的一个重复点时间影响可以忽略不计。
代码
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>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=100005;
typedef long long LL;
int L,R,a[maxn];
LL cost,f[25][maxn],cnt[maxn];
LL Move(int left,int right) {
while(L<left)cost-=--cnt[a[L++]];
while(L>left)cost+=cnt[a[--L]]++;
while(R<right)cost+=cnt[a[++R]]++;
while(R>right)cost-=--cnt[a[R--]];
return cost;
}
LL Cal(int k,int from,int to) {return f[k-1][from]+Move(from+1,to);}
void Solve(int k,int Left,int Right,int left,int right) {
if(Left>Right)return;
int mid=(Left+Right)>>1,id=left;
f[k][mid]=Cal(k,left,mid);
for(int i=left+1; i<=min(mid-1,right); i++) {
int tmp=Cal(k,i,mid);
if(tmp<=f[k][mid]) {f[k][mid]=tmp;id=i;}
}
Solve(k,Left,mid-1,left,id);
Solve(k,mid+1,Right,id,right);
}
int n,k;
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
f[1][i]=f[1][i-1]+cnt[a[i]]++;
}
for(int i=2; i<=k; i++) {
fill(cnt+1,cnt+n+1,0);
L=R=1;
cnt[a[1]]=1;
Solve(i,1,n,0,n-1);
}
printf("%lld\n",f[k][n]);
return 0;
}
|
G. 火山哥周游世界
题目描述
在赌场打了一晚德扑的火山哥靠着把把All in的精湛技巧赚的盆满钵满，所以他决定拿这笔钱来周游世界。
世界上一共有$n$个国家，标号从$1\sim n$。他们由$n−1$条边连接着，经过每条边都有一定的时间花费。任意两个国家之间两两可达。
火山哥一共决定去$K$个国家。现在他想要知道:如果他从第$i$个国家出发，经过这$K$个国家的最短时间是多少？(请注意他可以在任意一个国家停下)
题目分析
答案=欧拉环游序-最长链
这两者显然都可以用换根DP维护，所以时间复杂度$O(n)$。
可以建虚树做，复杂度多个$log$。
需要注意的是，有可能换根会换到不在最佳环游序上的点，这样环游长度会变化。
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=500005;
struct Edge {
int from,to;
LL dist;
Edge(int x=0,int y=0,LL v=0):from(x),to(y),dist(v) {}
};
vector<Edge> edges[maxn];
int n,k,Mark[maxn],From[maxn];
LL Size[maxn],Dist[maxn],Long[maxn],Sec[maxn],Ans[maxn],f[maxn];
void Dfs(int Now,int fa) {
Size[Now]=Mark[Now];
for(Edge &e:edges[Now]) {
int Next=e.to;
if(Next==fa)continue;
Dfs(Next,Now);
Size[Now]+=Size[Next];
if(Size[Next]) {
if(Long[Next]+e.dist>Long[Now]) {
Sec[Now]=Long[Now];
Long[Now]=Long[Next]+e.dist;
From[Now]=Next;
} else if(Long[Next]+e.dist>Sec[Now])Sec[Now]=Long[Next]+e.dist;
Dist[Now]+=Dist[Next]+2*e.dist;
}
}
}
void TreeDp(int Now,int fa,LL up) {
f[Now]=max(Long[Now],up);
for(Edge &e:edges[Now]) {
int Next=e.to;
if(Next==fa)continue;
Ans[Next]=Ans[Now]+((Size[Next]==0)?2*e.dist:0);
LL tmp=k-Size[Next]?up+e.dist:0;
if(From[Now]==Next&&Sec[Now])tmp=max(tmp,Sec[Now]+e.dist);
else if(From[Now]!=Next&&Long[Now])tmp=max(tmp,Long[Now]+e.dist);
TreeDp(Next,Now,tmp);
}
}
void AddEdge(int x,int y,int v) {edges[x].push_back(Edge(x,y,v));}
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
AddEdge(x,y,v);
AddEdge(y,x,v);
}
for(int i=1; i<=k; i++)Mark[Get_Int()]=1;
Dfs(1,0);
Ans[1]=Dist[1];
TreeDp(1,0,0);
for(int i=1; i<=n; i++)printf("%lld\n",Ans[i]-f[i]);
return 0;
}
|
H. 火山哥的序列
题目描述
火山哥有一个长度为$n$的序列$a$。序列里的数互不相同。
现在他定义$g(x,y)$为序列删去了第$x$个到第$y$个元素之后最大的$\gcd$值，即为
特别地，当序列被删到只剩下一个元素时，$g(x,y)=0$。
现在他想要知道$\displaystyle \sum_{i=1}^n \sum_{j=i}^n g(i,j)$
题目分析
还没搞明白，搞明白了回来补。
I. N门问题
题目描述
火山哥参加了一个抽(猜)奖活动。
现在他的面前有$N(N\geq 2)$扇门，只有$1$扇门的背后有大奖，其余的门后都是空的。活动有一个主持人，他事先知道哪扇门后有大奖。每次当火山哥选择一扇门(不打开)后，主持人会从剩下的没有打开的、且不是对应大奖的门中，等概率地随机挑选一扇门打开，然后再给火山哥一次选择门的机会(火山哥可以选择保持之前的选择不变或者换成任意一扇他想要的门)，直到只剩两扇门为止，此时火山哥的选择就是他的最终选择。
火山哥想获得大奖，但他不知道任何信息，于是他决定每次在”所有可选的门”中挑选一个”在他的视角中背后有奖的概率最大”的门，如果这样的门有多个，则他会在其中等概率地随机挑选一个。(显然第一次选门时，他的视角中每扇门背后有大奖的概率都是$\frac{1}{N}$，所以他会随机在$N$扇门中选一扇)
换言之，火山哥选门的过程可以抽象为以下过程：
- while(剩余门的数量 >= 2):
- $\quad$火山哥按照上文所述选定一扇门，不打开
- $\quad$if(剩余门的数量 == 2):
- $\quad\quad$这扇门是火山哥的最终选择; break;
- $\quad$主持人按照上文所述打开一扇门(同时意味着剩余门的数量-1)
- $\quad$火山哥重新计算每扇门后有奖的概率
现在活动主办方安排你作为主持人，并要求你埋伏火山哥一手，换言之你每次可以在剩下的门中(除了火山哥选择的和最终大奖的门之外)主动选择某扇门(而非随机地)来打开，目的就是让火山哥最终选择到大奖门的概率最小。现在给你$N$，求这个最小的概率。
注意: 火山哥并不知道你的存在。换言之，他依然认为主持人是正常的而不会去揣测他的用意。
题目分析
首先，这道题的这个模型肯定要进行转化，下面是官方题解的转化过程：
贪心地让每一步中正确的门的概率最小、每次打开概率最大的门、每次打开概率最小的门，这些策略都是错误的，枚举一些N=5、6的情况大概可以感受到。
事实上，通过归纳法可以证明，无论打开了哪扇门，A选择的那扇门在门打开之后都会变成全场唯一概率最小的门。
通过这一结论我们可以把问题转成类似一个序列操作问题：
一开始有N个球一起放在序列头，有一个是正确球。
每次A从序列头的所有球中随机抽一个，然后B可以丢弃剩下球中不是正确球的任意一个，然后A把他抽的球单独地放在序列末尾。
可以感受到，当N足够大时，B一定可以通过控奇偶性让A必败。(这也可以坑到只观察序列前三项而认为序列单调递增趋于1的选手)
首先，本人认为题解中提到的“A选择的那扇门在门打开之后都会变成全场唯一概率最小的门”并不成立，题解也没有给出证明过程，但题解似乎把单步概率和全局概率混淆了？
所以我对这个结论保留质疑态度，如果有读者会证明请教教我（
但是转化后的问题就很好做了。
设$f(i,j,k)$表示有$i$个球，第一列有$j$个球，正确球（黑球）在第$k$列，考虑它的转移。
$f(i,j,1)$的转移
需要注意的是，因为火山哥是随机选取，所以最终$f(i,j,1)$应该是火山哥选择黑球获得的概率$+$火山哥选择白球获得的概率。而主持人删球是主持人选取的，故火山哥选择黑/白球的时候概率应该取$\min$。
$f(i,j,k)$的转移
火山哥只有一种选择，所以这里都应该取$\min$
$f(i,1,k)$的转移
$f(i,1,1)$的转移
只有一种转移：
动规告诉我们，当$n\gt10$的时候，火山哥获胜的概率为$0$，也就是说火山哥必败。
注意求$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
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxm=50005;
void Exgcd(LL a,LL b,LL &d,LL &x,LL &y) {
if(!b)d=a,x=1,y=0;
else Exgcd(b,a%b,d,y,x),y-=(a/b)*x;
}
LL Quick_Mul(LL a,LL b,LL p) {
LL sum=0;
for(; b; b>>=1,a=(a<<1)%p)if(b&1)sum=(sum+a)%p;
return sum;
}
LL Excrt(int n,LL *r,LL *m) {
LL M=m[1],ans=r[1];
for(int i=2; i<=n; i++) {
LL a=M,b=m[i],x,y,c=(r[i]-ans%m[i]+m[i])%m[i],gcd;
Exgcd(a,b,gcd,x,y);
if(c%gcd)return -1;
x=Quick_Mul(x,c/gcd,b/gcd);
ans+=x*M;
M=M/gcd*b;
ans=(ans%M+M)%M;
}
return ans;
}
LL n,m,a[maxm],b[maxm];
double f[15][15][15];
double Dp(LL x,LL y,LL z) {
if(y==0) {
if(z!=1)return Dp(x,1,z-1);
else return Dp(x,1,x);
}
if(x==2) {
if(y==1)return z==1;
else return 0.5;
}
if(f[x][y][z]!=-1)return f[x][y][z];
if(y==1) {
if(z==1)return f[x][y][z]=Dp(x-1,1,x-1);
else {
if(z==2)return f[x][y][z]=Dp(x-1,1,1);
else if(z==x)return f[x][y][z]=Dp(x-1,1,z-2);
else return f[x][y][z]=min(Dp(x-1,1,z-1),Dp(x-1,1,z-2));
}
} else {
if(z==1) {
double black=1,white=1;
if(y>=2)black=Dp(x-1,y-2,x-y+2);
if(x>y)black=min(black,Dp(x-1,y-1,x-y+1));
if(y>2)white=Dp(x-1,y-2,1);
if(x>y)white=min(white,Dp(x-1,y-1,1));
return f[x][y][z]=black*(1.0/y)+white*((y-1.0)/y);
} else {
f[x][y][z]=1;
if(y>=2)f[x][y][z]=Dp(x-1,y-2,z);
if(z>2)f[x][y][z]=min(f[x][y][z],Dp(x-1,y-1,z-1));
if(z<x-y+1)f[x][y][z]=min(f[x][y][z],Dp(x-1,y-1,z));
return f[x][y][z];
}
}
}
int main() {
m=Get_Int();
for(int i=1; i<=m; i++) {
a[i]=Get_Int();
b[i]=Get_Int();
}
n=Excrt(m,a,b);
if(n<2)puts("error");
else if(n>10)puts("0.000000");
else {
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++)
for(int k=0; k<=n; k++)f[i][j][k]=-1;
printf("%.6lf\n",Dp(n,n,1));
}
return 0;
}
|
J. 简单字符串
题目描述
对于字符串$s$和整数$k$，定义$f(s,k)$为，将$s$划分为至多$k$段$u_1,u_2,\ldots u_l$，最小化$\max_{1\leq i\leq l} u_i$(比较按照字典序)，求最小化的结果。
现在我们有一个字符串$S$，$q$次询问$f(s[l_i\ldots |s|],k_i)$的值，对于每个询问输出$a_i,b_i$表示$f(s[l_i\ldots |s|], k_i)=S[a_i\ldots b_i]$，其中要求$S[a_i \ldots b_i]$在一个可能的划分中。
如果有多个，输出$a_i$最小的解，要求$a_i \geq l_i$。
题目分析
需要用到lyndon分解，溜了溜了。
