Codeforces杂题

CF896B

Description

交互题,有nn个空格,每次给一个[1,c][1,c]的数字,回答填入哪一个格子,如果这个格子之前已经填过,那么新数字可以替换这个格子的数。要求在mm轮内使nn格填满且数列不递减

Hint

n,m2,1c1000,1nc21000n,m\ge 2,1\leq c\leq 1000,1\leq n \cdot \lceil\frac{c}{2}\rceil\leq 1000

Solution

考虑最简单的贪心,对于给出的一个数xx,每一次从左至右找到第一个严格大于xx或者空白的格子,填入。那么要填满nn个格子,至少要c×(n1)+1c\times (n-1)+1
把颜色分成[1,c2][1,\frac{c}{2}][c+12,c][\frac{c+1}{2},c]两个部分,对于前者由左至右填入到第一个严格大于xx的格子或者空白格子;对于后者由右至左填入到一个严格小于xx的格子或者空白格子。此时需要的最差总轮数为(n1)c2+1(n-1)\cdot \frac{c}{2}+1

key

贪心

CF15C

Description

nn个采石场,每个采石场有mim_i辆采矿车,对于一个采石场第jj个采矿车有xi+j1x_i+j-1个石头。两个人进行NIMNIM博弈,问先手和后手那个必胜

Hint

1n1051\leq n\leq 10^51xi,mi10161\leq x_i,m_i\leq 10^{16}

Solution

012(x1)x0\oplus1\oplus2\oplus\cdots\oplus(x-1)\oplus x

  1. xmod40x\mod{4}\equiv 0(0,1),(2,3),,(x2,x1)(0,1),(2,3),\cdots,(x-2,x-1)互相配对,他们的异或和为x2\frac{x}{2}(是个偶数)个11的异或和,那么答案就是xx
  2. xmod41x\mod{4}\equiv 1(0,1),(2,3),,(x1,x)(0,1),(2,3),\cdots,(x-1,x)互相配对,共x+12\frac{x+1}{2}11,此时答案为11
  3. xmod42x\mod{4}\equiv 2(0,1),(2,3),,(x2,x1)(0,1),(2,3),\cdots,(x-2,x-1)互相配对,共x12\frac{x-1}{2}11,答案是x1x\oplus 1
  4. xmod43x\mod{4}\equiv 3(0,1),(2,3),,(x3,x2),(x1,x)(0,1),(2,3),\cdots,(x-3,x-2),(x-1,x)互相配对,共x+12\frac{x+1}{2}11,答案就是00

key

数学

CF135C

Description

给出一个长度为nn的串,由01,?三种字符组成。?可以被替代成01。问A和B轮流删除一个字符,A先,删除到最后只剩下两个字符游戏结束,问最后结束时的游戏状态有几种。A要使得最后的结果最小,B要使得最后的结果最大,假设两个人足够聪明。

Hint

2n1052\leq n\leq 10^5

Solution

一个显然的贪心:每一次A从左向右删第一个1,B从左向右删第一个0
考虑没有?的情况。
假设1的个数为aa0的个数为bb
结果为00当且仅当a<ba<b
结果为11当且仅当a>b+1a>b+1
a=ba=b或者a=b+1a=b+1的时候,结果为01或者10,取决于最后一个字符为1或者0
考虑包含了?,假设结果为01,如果最后一个字符是?,那么c=c1c=c-1,a=a+1a=a+1
假设cc?中有xx个变成11
a+x=b+1+(cx)+((a+b+c)mod2)a+x=b+1+(c-x)+((a+b+c)\mod 2)
如果x0x\ge 0xcx\leq cxmod2=0x\mod 2 = 0,那么就是可能的。
10的情况类似。

key

贪心

CF605E

Description

nn个点,每个时刻第ii个点和第jj个点之间有pi,jp_{i,j}的概率存在一条边。每个时刻可以沿着一条边走或者留在原地。求从11号点走到nn号点的最优的期望时间。

Hint

1n10001\leq n\leq 1000

Solution

fif_i表示从ii点到nn点的期望步数。
fn=0f_n=0,考虑类似于dijkstradijkstra,每次从fnf_n最小的点扩展。
假设xx是当前第ff值第ii小的编号,AiA_i表示ff值为第ii小的编号

fx=1+j=1ifaj×paj,x×k=1j1(1pAk,x)f_x = 1 + \sum_{j=1}^if_{a_j}\times p_{a_j,x}\times \prod_{k=1}^{j-1}(1-p_{A_k,x})

解方程一下:

fx=1+j=1i1faj×paj,x×k=1j1(1pAj,x)1px,x×k=1i1(1pak,x)f_x=\frac{1+\sum_{j=1}^{i-1}f_{a_j}\times p_{a_j,x}\times \prod_{k=1}^{j-1}(1-p_{A_j,x})}{1-p_{x,x}\times \prod_{k=1}^{i-1}(1-p_{a_k,x})}

直接暴力转移更新即可。
这份代码是另一份写法,算fxf_x时把11放在式子里算,不是单独拿出来。

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 1100;
double p[N][N];
double f[N], g[N], s[N];
bool vis[N];
int n;
void solve() {
for(int i = 1; i < n; ++i) g[i] = 1, f[i] = 1e99;
f[0] = 1e99;
for(int i = 1; i <= n; ++i) {
int x = 0;
for(int j = 1; j <= n; ++j)
if(!vis[j] && f[j] < f[x]) x = j;
vis[x] = 1;
for(int j = 1; j <= n; ++j) if(!vis[j] && p[x][j] > 0) {
s[j] += (f[x] + 1)* p[x][j] * g[j];
g[j] *= (1 - p[x][j]);
f[j] = (s[j] + g[j])/ (1 - g[j]);
}
}
printf("%.10lf\n", f[1]);
}
int main() {
n = read();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
p[j][i] = read() / 100.0;
solve();
return 0;
}

key

期望,动态规划

BZOJ2698

Description

nn个格子,每一次会等概率选取一段长度在[S,T][S,T]之间的连续段染成白色,染色MM次,问最后被染成白色的格子个数的期望值。

Hint

1STN1000000,0M10000001\leq S\leq T\leq N\leq 1000000,0\leq M\leq 1000000

Solution

考虑每一个格子对答案的贡献即可。期望的线性性:
所有格子染成白色的期望个数=Pj×1=\sum P_j\times 1
其中PjP_j表示第jj个格子被染成白色的概率。

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;
const int N = 1200000;
ll n, m, s, t;
double ans = 0;
bool vis[N];
ll f[N], g[N];
int main() {
n = read(), m = read(), s = read(), t = read();
for(int i = 1; i <= n; ++i) {
f[i] = (s + t) * (t - s + 1) / 2;
g[i] = (n + 1) * (t - s + 1) - (s + t) * (t - s +1) / 2;
}
for(ll i = 1; i <= t; ++i) {
f[i] -= (max(s, i) + t) * (t - max(s, i) + 1) / 2 - min(t - i + 1, t - s + 1) * i;
f[n - i + 1] -= (max(s, i) + t) * (t - max(s, i) + 1) / 2 - min(t - i + 1, t - s + 1) * i;
}
for(int i = 1; i <= n; ++i)
ans += 1 - pow(1 - 1.0 * f[i] / g[i], m);
printf("%.3lf\n", ans);
return 0;
}

key

期望

BZOJ2698

Description

有一个大小为W×HW\times H的方阵,每一次小M会等概率随机选两个格子(可以是同一个),把以这两个格子为对角线的子矩阵染成白色,问KK轮之后方阵的白色格子的期望个数是多少?

Hint

1W,H1000,0K1001\leq W,H\leq 1000,0\leq K\leq 100

Solution

同BZOJ2698,大力分类讨论

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
#include<bits/stdc++.h>
typedef long long ll;
inline ll read() {ll x = 0;char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {
if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();
}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
using namespace std;

const int N = 1100;

ll K, n, m;
int a[N][N], b[N][N];
double ans = 0;
double t;
int main() {
K = read(), n = read(), m = read();
/* for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j)
for(int x = 1; x <= n; ++x)
for(int y = 1; y <= m; ++y)
{
for(int r = min(i, x); r <= max(i, x);++r)
for(int c = min(j, y); c <= max(j, y); ++c)
++b[r][c];
}
}*/
ll tot = n * m * n * m;
double res = 0;
/*for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j)
printf("%d ", b[i][j]), res += (double) b[i][j] / tot;
puts("");
}
cout<<res<<endl;

printf("tot=%lld\n", tot);*/
for(ll i = 1; i <= n; ++i) {
for(ll j = 1; j <= m; ++j) {
ll s = i * j * (n - i + 1) * (m - j + 1) * 2;
s += (n - i + 1) * j * i * (m - j + 1) * 2;
s -= (i * (n - i + 1) + j * (m - j + 1)) *2 - 1;
// printf("(%d,%d) s=%lld, v=%lf\n", i, j, s, (double) s/ tot);
ans += 1 - pow(1 - (double)s / tot, K);
}
}
//cout<<ans<<endl;
printf("%lld\n", (ll)floor(ans + 0.5));
return 0;
}

key

期望

Description

Hint

Solution

key

Description

Hint

Solution

key

Description

Hint

Solution

key