9.28考试

T1:他

题目

一张长度为N的纸带,我们可以从左至右编号为0−N(纸带最左端标号为
0)。现在有M次操作,每次将纸带沿着某个位置进行折叠,问所有操作之后纸带
的长度是多少。

数据类型

对于60%的数据,N, M ≤ 3000。
对于100%的数据,N ≤ 1018, M ≤ 3000。

题解

对于60%的数据 可以用并查集维护折叠效果相同的点
对于100%的数据 很显然无法维护并查集我们可以直接修改剩下的操作 具体如果修改开代码

代码

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define LL long long
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)
#define MM(x, y) memset(x, y, sizeof(x))
#define F(i, x, y) for(register int i=x; i<=y; i++)
#define R(i, x, y) for(register int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for(flag=false, ch=getchar(); ch<'0'||ch>'9'; ch=getchar()) flag |= ch=='-';
for(x=0; isdigit(ch); ch=getchar()) x = (x<<1) + (x<<3) + ch - '0';
x = flag ? -x : x;
}
LL n, f[3005];
int m;
inline int work()
{
freopen("he.in","r",stdin); freopen("he.out","w",stdout);
scanf("%lld%d", &n, &m);
F(i, 1, m) scanf("%lld", &f[i]);
LL l = 0, r = n;
F(i, 1, m) {
if (f[i] * 2 > l + r) r = f[i];
else l = f[i];
// 如果f[i]的左边长度大于右边长度 则让r变为f[i] 否则让l变为f[i]
F(j, i+1, m) {
if (f[j] > r) {
f[j] = r * 2 - f[j];
}
if (f[j] < l) {
f[j] = l * 2 - f[j];
}
// 如果f[j]不在[l,r]上 则将f[j]映射到[l,r]上
}
}
printf("%lld\n", r-l);
return 0;
}
int TAT = work();
int main() {;}

T3:它

题目

N个人坐成一圈,其中第K个人拿着一个球。每次每个人会以一定的概率向
左边的人和右边的人传球。当所有人都拿到过球之后,最后一个拿到球的人即为
胜者。求第N个人获胜的概率。(所有人按照编号逆时针坐成一圈)

题解

对于n==3的 如果从1开始则只要让下一个往2传则最终一定是3赢 同样如果从2开始则只要让
下一个往1传则最终赢得一定是3
有了n==3的 我们可以将其他情况都转换成n==3的情况
问题如何转换呢?进行合并
例如 如果要删掉b b的前一个是a b的后一个是c 令pa、pb、pc分别表示a、b、c往右走的概率
则now_pa = (papb)/(1-pa(1-pb)) –> 从a往右走到c的概率=从a到b从b到c的概率占除掉
从a到b再从b到a的概率的百分比 (因为我要求的是从a到c 所以要除掉再b回头的可能)
而1-now_pc = ((1-pc)(1-pb))/(1-pb(1-pc))则跟上同理
通过上边的办法可以将2~n-2直接并掉 此时只剩下1,n-1,n
对于k==1的情况和k==n-1的情况可以直接同返回you[1], zuo[2];
而对于k!=1&&k!=n-1的情况我们可以最后再删k这样我们就可以知道k->1和k->n-1的概率然后
再乘对应的决策概率再相加

代码

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define LL long long
#define LDB long double
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)
#define MM(x, y) memset(x, y, sizeof(x))
#define F(i, x, y) for(register int i=x; i<=y; i++)
#define R(i, x, y) for(register int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for(flag=false, ch=getchar(); ch<'0'||ch>'9'; ch=getchar()) flag |= ch=='-';
for(x=0; isdigit(ch); ch=getchar()) x = (x<<1) + (x<<3) + ch - '0';
x = flag ? -x : x;
}
int T, n, k;
LDB you[105], zuo[105];
int nex[105], pre[105];
inline void deal(int b)
{
int a = pre[b], c = nex[b];
LDB pa = you[a], pb = you[b], pc = you[c];
you[a] = pa * pb / (1 - pa * (1-pb));
zuo[a] = 1 - you[a];
zuo[c] = (1-pc)*(1-pb)/(1-pb*(1-pc));
you[c] = 1 - zuo[c];
nex[a] = c; pre[c] = a;
}
inline LDB solve()
{
if (n == 2) return 1;
if (n == 3) return k == 1 ? you[1] : zuo[2];
F(i, 1, n) {
nex[i] = i+1; pre[i] = i-1;
}
nex[n] = 1; pre[1] = n;
if (k == 1) {
F(i, 2, n-2) {
deal(i);
}
return you[1];
}
if (k == n-1) {
F(i, 2, n-2) {
deal(i);
}
return zuo[n-1];
}
F(i, 2, n-2) if (i!=k) deal(i);
deal(k);
return zuo[k]*you[1]+you[k]*zuo[n-1];
}
inline int work()
{
freopen("it.in","r",stdin); freopen("it.out","w",stdout);
in(T);
while(T--) {
in(n); in(k);
F(i, 1, n) {
double x;
scanf("%lf", &x);
you[i] = x;
zuo[i] = 1-x;
}
printf("%.9lf\n", (double)solve());
}
return 0;
}
int TAT = work();
int main() {;}