Day6

字数统计: 3.6k字   |   阅读时长: 19min

写这篇博客，异常想吐槽。题目名竟然是“简，单，题”，但题一点也不简单qwq.

1.简

【问题描述】
一天 fateice 给了 fjzzq2002 一道简单题。
定义“n-好排列”为 1 到 n 的排列中，满足任何一个数都比前面的所有数大或者小。
比如“1 2 3 4”就是一个“4-好排列”，而“4 3 1 2”就不是一个“4-好排列”。
给出 n，求“n-好排列”个数。
fjzzq2002 一眼秒了，加了多组数据，把题目扔给了你。
良心出题人为了输出方便，加了答案对 p 取模。

【输入格式】
输入文件名为 jian.in。
第一行，一个数 T，表示数据组数。
接下来 T 行，每行两个数， n 和 p，含义如题所示。
【输出格式】
输出文件名为 jian.out
对于每组数据，一个数，表示答案。

输入：
2 
233
10 233
输出：
2
46

【数据规模与约定】
对于 30% 的数据， 1 ≤ n ≤ 10；
对于 60% 的数据， 1 ≤ n ≤ 106, 1 ≤ p ≤ 109；
对于 100% 的数据， 1 ≤ n, p ≤ 1018, 1 ≤ T ≤ 104。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int T;
inline LL mul(LL a,LL b,LL p)
{
    LL s=0;
    while(b>0){
        if(b%2==1) s=(s+a)%p;
        a=(a+a)%p;
        b=b>>1;
    }
    return s;
}
inline LL cifang(LL a,LL b,LL p)
{
    LL s=1;
    while(b>0){
        if(b%2==1) s=mul(s,a,p);
        a=mul(a,a,p);
        b=b>>1;
    }
    return s%p;
}
int main()
{
//	freopen("jian.in","r",stdin);
//	freopen("jian.out","w",stdout);
    scanf("%d",&T);
    for(int i=1;i<=T;i++)
    {
        LL ans,n,p;
        scanf("%lld %lld",&n,&p);
        ans=cifang(2,n-1,p);
        printf("%lld\n",ans);
    }
    return 0;
}

找到规律，这道题就变成了快速幂了。不过还要用快速乘，这道题p竟可以为1！！！！。

2.单

fjzzq2002 要攻打 fateice 的国家。
fateice 的国家有 n 座城市，有(n − 1)条带长度的无向路径连接城市，使城市两两连通。
现在定义城市的连通块为联邦。每一个联邦内最远的两个城市之间的距离称为联邦之间的弱
度。 fjzzq2002 手上有一个秘密武器，它可以随机轰炸一条路径使得其无法通行，也就是说
使得 fateice 的国家分成两个联邦。使用秘密武器的收益为分成的两个联邦的弱度的最大值。
fjzzq2002 的武器有点瑕疵，也就是说它是随机轰炸一条路径的，所以 fjzzq2002 想知道
他使用秘密武器的期望收益是什么。
良心出题人为了输出方便，将答案乘以(n − 1)输出。


【输入格式】
输入文件名为 dan.in。
输入文件内包含多组数据。
第一行，一个数 T，表示数据组数。
接下来 T 组数据，每组数据中：
第一行，一个数 n，表示城市数量。
接下来(n − 1)行，每行三个数 u， v， len，表示一条道路所连两个城市 u 和 v，以及它
的长度 len。
【输出格式】
输出文件名为 dan.out。
对于每组数据，输出一个数，表示 fjzzq2002 使用秘密武器的收益乘以(n − 1)后的值。


输入：
2 3 2
1 2
3 2 3
5 2
1 1
3 1 2
4 2 3
5 2 4

输出：
5 2
7

【数据规模与约定】
对于 30% 的数据， 1 ≤ n ≤ 10；
对于 60% 的数据， 1 ≤ n ≤ 103；
对于 100% 的数据， 1 ≤ n ≤ 105, 1 ≤ len ≤ 105, 1 ≤ T ≤ 10。

暴力代码（60分）

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>
using namespace std;
int T;
const int inf = 0x7fffffff;
int ne[300004],to[300004],head[300004],cnt,fa[200004],fr[2][200004],vis[200004];
long long len[3][100004],tmp,w[300004];
void add(int u,int v,long long wi)
{
    to[++cnt]=v;
    fa[cnt]=u;
    ne[cnt]=head[u];
    w[cnt]=wi;
    head[u]=cnt;
}
void dfs(int x,int fa)
{
    for(int i=head[x];i;i=ne[i])
    {
        int v=to[i];
        long long wi=w[i];
        if(v==fa) continue;
        dfs(v,x);
        if(wi+len[1][v]>len[1][x])
        {
            fr[1][x]=fr[0][x];
            len[2][x]=len[1][x];
            len[1][x]=wi+len[1][v];
            fr[0][x]=v;
        } 
        else if(wi+len[1][v]>len[2][x]) len[2][x]=wi+len[1][v],fr[1][x]=v; 
    }
    tmp=max(len[1][x]+len[2][x],tmp);
}
int main()
{
//	freopen("dan.in","r",stdin);
//	freopen("dan.out","w",stdout);
    scanf("%d",&T);
    for(int i=1;i<=T;i++)
    {
        int n;
        tmp=(long long)0;
        long long ans=(long long)0;
        scanf("%d",&n);
        for(int j=1;j<=n;j++)
        {
            ne[j]=ne[j+n]=0;
            w[j]=w[j+n]=0;
            to[j]=to[j+n]=0;
            head[j]=0;
            fa[j]=0;
            len[1][j]=len[0][j]=0;
            vis[j]=0;
            fr[0][j]=fr[1][j]=0;
        }
        for(int j=1,u,v;j<n;j++)
        {
            long long wi; 
            scanf("%d %d %lld",&u,&v,&wi);
            add(u,v,wi);
            add(v,u,wi);
        }
        dfs(1,0);
        long long dis=tmp;
        for(int j=1;j<=n;j)
        {
            if((len[1][j]+len[2][j])==tmp)
            {
                vis[j]=1;
                for(int t=fr[1][j];t!=0;t=fr[0][t])
                {
                    vis[t]=1;
                } 
                for(int t=fr[0][j];t;t=fr[0][t]) vis[t]=1;
                break;
            }
            else
            {
                j=fr[0][j];
            }
        }	
        for(int j=1;j<=cnt;j+=2)
        {
            int v=to[j],u=fa[j];
            if(vis[v]&&vis[u])
            {
                memset(len,0,sizeof(len));
                tmp=(long long)0;
                dfs(v,u);
                long long p=tmp;
                tmp=(long long)0;
                dfs(u,v);
                p=max(p,tmp);
                ans+=p;
            }
            else ans+=dis;
        }
        printf("%lld\n",ans);
        cnt=0;
    }
    return 0;
}

正解

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
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 2e5 + 10;
const int mod = 1e9+7;

int n;
int head[M], nxt[M], to[M], w[M], tot;
inline void add(int a, int b, int _w) {
	++tot; nxt[tot] = head[a]; head[a] = tot; to[tot] = b; w[tot] = _w;
}
inline void adde(int a, int b, int _w) {
	add(a, b, _w);
	add(b, a, _w);
}

int mx, re;
inline void dfs(int x, int fa, int v) {
	if(v > mx) mx = v, re = x;
	for (int i=head[x]; i; i=nxt[i]) if(to[i] != fa) dfs(to[i], x, v + w[i]);
} 

struct par {
	int fi, se, rfi, rse;//fi == first long ; se == second long ; rfi则为最长的路径的叶子节点 ； rse 则为次长的 
	par() {}
	par(int fi, int se, int rfi, int rse) : fi(fi), se(se), rfi(rfi), rse(rse) {}
}dp[2][M];
int G[2][M];

inline par comb(par a, par b, int c, int d) {//c为距离 ，b为父亲节点 ，a为儿子节点 ，d为儿子节点的编号 
	par ret;
	if(a.fi == -1 && a.se == -1) a.fi = c;//到达叶子节点 
	else if(a.se == -1) a.fi += c;// 更新a.fi 
	else if(a.fi != -1 && a.se != -1) a.fi += c, a.se += c;//更新a.fi,a.se; 
	ret = b; // 更新父亲节点 
	if(a.fi > ret.fi) {
		ret.se = ret.fi; ret.rse = ret.rfi;
		ret.fi = a.fi; ret.rfi = d;
	} else {
		if(a.fi > ret.se) ret.se = a.fi, ret.rse = d;
//		else if(a.se > ret.se) ret.se = a.se, ret.rse = d;//这句没有必要 
	}
	return ret;
}

par *f;
int *g;

inline void dfs2(int x, int fa) {
	f[x] = par(-1, -1, -1, -1); g[x] = 0;
	for (int i=head[x]; i; i=nxt[i]) {
		if(to[i] == fa) continue;
		dfs2(to[i], x);
		f[x] = comb(f[to[i]], f[x], w[i], to[i]);
		g[x] = max(g[x], g[to[i]]);
	}
	if(f[x].rfi != -1 && f[x].rse == -1) g[x] = max(g[x], f[x].fi); //
	else if(f[x].rfi != -1 && f[x].rse != -1) g[x] = max(g[x], f[x].fi + f[x].se);
}

int fr[M], w2[M];
bool gg;
inline void dfs3(int x, int fa, int dest) {//一找到dest就返回保证了fr[]和w2[]记录了直径上的点 
	if(gg) return ;
	for (int i=head[x]; i; i=nxt[i]) {
		if(gg) return ;
		if(to[i] == fa) continue;
		if(to[i] == dest) {
			fr[x] = to[i]; w2[x] = w[i];
			gg = 1;
			return ;
		}
		fr[x] = to[i]; w2[x] = w[i];
		dfs3(to[i], x, dest);
	}
}

void Main() {
	tot = 0; 
	scanf("%d", &n); for (int i=1; i<=n; ++i) head[i] = nxt[i] = fr[i] = w2[i] = 0;
	for (int i=1, u, v, _w; i<n; ++i) {
		scanf("%d%d%d", &u, &v, &_w);
		adde(u, v, _w);
	}
	int pa, pb;//直径的起点和终点 
	mx = -1, re = 0;
	dfs(1, 0, 0); pa = re;//找到最远点 
	mx = -1, re = 0;
	dfs(pa, 0, 0); pb = re;//找到直径 
	gg = 0; dfs3(pa, 0, pb);
	ll r = 0;
	int cnt = 0; 
	for (int i=pa; i!=pb; i=fr[i]) r += w2[i], ++cnt;//r=直径，cnt为边的个数。 
	f = dp[0]; g = G[0]; dfs2(pa, 0);//指针代替数组 
	f = dp[1]; g = G[1]; dfs2(pb, 0);
	long long ans = 1ll * (n-1 - cnt) * r;
	for (int i=pa, j, fp1, fp2; i!=pb; i=fr[i]) {
		j = fr[i];
//		printf("%d %d %d %d\n", i, j, G[0][j], G[1][i]);
		ans += max(G[0][j], G[1][i]);
	}
	cout<<ans<<endl;
}

int main() {
	freopen("dan.in", "r", stdin);
	freopen("dan.out", "w", stdout);
	int T; scanf("%d", &T);
	while(T--) Main();
	return 0;
}

暴力代码（更改后快了8s,但前几个小数据过不了了qwq）

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int T;
int ne[300004],to[300004],head[300004],cnt;
int pa,pb,fr[2][200004];
long long len[3][100004],tmp,w[300004],g[2][100004],ans;
void add(int u,int v,long long wi)
{
	to[++cnt]=v;
	ne[cnt]=head[u];
	w[cnt]=wi;
	head[u]=cnt;
}
void dfs(int x,int fa)
{
	for(int i=head[x];i;i=ne[i])
	{
		int v=to[i];
		long long wi=w[i];
		if(v==fa) continue;
		dfs(v,x);
		if(wi+len[1][v]>len[1][x])
		{
			fr[1][x]=fr[0][x];
			len[2][x]=len[1][x];
			len[1][x]=wi+len[1][v];
			fr[0][x]=v;
		} 
		else if(wi+len[1][v]>len[2][x]) len[2][x]=wi+len[1][v],fr[1][x]=v; 
	}
	tmp=max(len[1][x]+len[2][x],tmp);
}
void dfs2(int x,int fa,int tag)
{			
	g[tag][x]=0LL;
	for(int i=head[x];i;i=ne[i])
	{
		int v=to[i];
		long long wi=w[i];
		if(v==fa) continue;
		dfs2(v,x,tag);
		if(wi+len[1][v]>len[1][x])
		{
			fr[1][x]=fr[0][x];
			len[2][x]=len[1][x];
			len[1][x]=wi+len[1][v];
			fr[0][x]=v;
		} 
		else if(wi+len[1][v]>len[2][x]) len[2][x]=wi+len[1][v],fr[1][x]=v; 
		g[tag][x]=max(g[tag][x],g[tag][v]);
	}
	g[tag][x]=max(len[1][x]+len[2][x],g[tag][x]);
}
int main()
{
	freopen("dan.in","r",stdin);
	freopen("dan.out","w",stdout);
	scanf("%d",&T);
	for(int i=1;i<=T;i++)
	{
		int n;
		tmp=0LL;
		ans=0LL;
		scanf("%d",&n);
		for(int j=1;j<=n;j++)
		{
			ne[j]=ne[j+n]=0;
			w[j]=w[j+n]=0LL;
			to[j]=to[j+n]=0;
			head[j]=0;
			len[1][j]=len[0][j]=0LL;
			fr[0][j]=fr[1][j]=0;
			g[0][x]=g[1][x]=0LL;
		}
		for(int j=1,u,v;j<n;j++)
		{
			long long wi; 
			scanf("%d %d %lld",&u,&v,&wi);
			add(u,v,wi);
			add(v,u,wi);
		}
		dfs(1,0);
		int c=0;
		long long dis=tmp;
		int j;
		for(j=1;j<=n;j)
		{
			if((len[1][j]+len[2][j])==tmp)
			{
				for(int t=fr[1][j];t;t=fr[0][t])
				{
					c++;
					if(t) pa=t;
				} 
				for(int t=fr[0][j];t;t=fr[0][t])
				{
					c++;
					if(t) pb=t;	
				}
				break;
			}
			else
			{
				j=fr[0][j];
			}
		}	
		memset(len,0,sizeof(len));
		memset(fr,0,sizeof(fr));
		dfs2(pa,0,0);
		memset(fr,0,sizeof(fr));
		memset(len,0,sizeof(len));
		dfs2(pb,0,1);
		ans=(LL)(n-1-c)*dis;
		for(int i=pb,j;i!=pa;i=fr[0][i])
		{
			j=fr[0][i];
			ans+=max(g[1][j],g[0][i]);
		}
		cout<<ans<<endl;
		cnt=0;
	}
	return 0;
}

树上DP

3.题

【问题描述】
fjzzq2002 和 fateice 在玩骰子，他们每个人有 1 个骰子。
他们的骰子均为均匀的 n 面，也就是说，落到每一面的概率均为1
n
。这两个骰子每面标
有一个数字，这些数字互不相同，且均为[1, X]内的正整数。
游戏规则是这样的：双方随机选择一面比较该面数字大小，大的获胜。
fjzzq2002 的骰子因为年久失修一些面的数字模糊了，于是 fjzzq2002 需要自己标上数
字，但是要遵循以下规则:
1. 所标的数字必须为[1, X]间的整数，且不能和之前标的数字以及已有的任意数字重复。
2. 允许不标数字，视为数字 0，也就是说比任何有标数字的面都小；可以在多个位置
不标数字，也就是说可以出现多个 0。
3. 标完数字后应该尽量公平，也就是说，双方获胜的概率应该尽可能接近 0.5。
请求出最公平的情况下， fjzzq2002 的胜率。如果有多种方案都公平，输出 fjzzq2002 胜
率较小时 fjzzq2002 的胜率。
【输入格式】
输入文件名为 ti.in
第一行，一个数，骰子面数 n。
第二行， n 个位于[0, X]间的数，表示 fjzzq2002 的骰子，如果数字为 0 表示该面模糊了。
第三行， n 个位于[1, X]间的数，表示 fateice 的骰子。
第四行，一个数 X，含义如题所示。
【输出格式】
一行，一个小数，表示最公平的情况下， fjzzq2002 的胜率。
输出时保留 10 位小数。


输入：
4 0
2 7 0
6 3 8 10
12
输出：
0.4375000000


【数据规模与约定】
对于 30% 的数据， 2 ≤ n ≤ 5；
对于 60% 的数据， 2 ≤ n ≤ 30；
对于另外 10% 的数据， fjzzq2002 的骰子各面均为清晰可见的。
对于 100% 的数据， 2 ≤ n ≤ 50, 2n ≤ X ≤ 108。

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
#include<bits/stdc++.h>
using namespace std;
int n,a[60],b[60];
int len[60];
bool f[60][60][3600];
int main()
{
//	freopen("ti.in","r",stdin);
//	freopen("ti.out","w",stdout);
    memset(f,0,sizeof(f));
    int ans=0,tot=0;
    cin>>n;
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        tot+=(a[i]==0);
    }
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    cin>>x;
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    for(int i=1;i<n;i++) len[i]=b[i+1]-b[i]-1;
    len[n]=x-b[n];
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0) continue;
        int tmp=0;
        for(int j=1;j<=n;j++)
        if(a[i]>b[j]) ++tmp;
        if(tmp) len[tmp]--;
        ans+=tmp;
    }
    for(int k=0;k<=tot;k++) f[0][k][ans]=1;//在第零段，无论改几个零 ，f[0][k][ans]=1;已有ans个数大于。 
    for(int i=1;i<=n;i++)
        for(int j=0;j<=tot;j++)
            for(int k=0;k<=n*n;k++)
                for(int l=0,to=min(len[i],j);l<=to;l++)
                    if(k-i*l>=0)f[i][j][k]|=f[i-1][j-l][k-i*l];
                    
    double E=(double)n*n,minn=1e9,id;
    for(int i=0;i<=n*n;i++)
        if(f[n][tot][i])
            if(fabs(2*i-E)<minn)
            {
                minn=fabs(2*i-E);
                id=i;
            }
    printf("%0.10lf\n",id/E);
    return 0;
}

题解：

考虑两个人的骰子的数字顺序不影响，故均排序。
Fateice的数字将[1,X]分成n+1段。
我们考虑求fjzzq2002的每个数字的贡献，让贡献尽量接近n*n/2即可。
那么令𝑓_(𝑖,𝑗,𝑘)表示到第i段，当前处理了j个0，贡献为k是否可行。
本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/4d60e647.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

    			  jsonContent:
				meta: false
				pages: false
				posts:
				  title: true
				  date: true
				  path: true
				  text: false
				  raw: false
				  content: false
				  slug: false
				  updated: false
				  comments: false
				  link: false
				  permalink: false
				  excerpt: false
				  categories: false
				  tags: true


There's nothing