2022“杭电杯”中国大学生算法设计超级联赛（1）补题
[0,1]生成n个数，m次操作，每次有1/2概率删除最大值，1/2概率删除最小值，问最终期望总和模1e9+7
思路：答案是(n-m)/2,即(n-m)*inv(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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int mod=1e9+7;
ll ksm(ll a,ll b){
ll ans=1,base=a%mod;
while(b){
if(b&1)
ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans;
}
ll inv(ll x){
return ksm(x,mod-2)%mod;
}
int main(){
IOS
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
cout<<(n-m)*inv(2)%mod<<endl;
}
}
|
Alice和Bob玩游戏，有n个数在黑板上，当数中没有0的时候，Alice可以选择把这些数分为两个集合，然后Bob可以选择删掉其中一个集合的所有数，并将另一个集合中的数全部减去1，重复直至当黑板上出现0时,Alice胜利，否则当黑板上所有的数都被删掉时，Bob胜利
思路：如果一开始就有0，Alice胜，否则看最后1的个数是否大于2（这种情况下分区间并且减一就会出现至少1个0），1的数量大于2就Bob胜，否则Alice胜
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;
typedef long long ll;
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=1e6+5;
int n,a[maxn];
int main(){
IOS
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<=n;i++)
cin>>a[i];
for(int i=n;i>=1;i--)
a[i-1]+=a[i]/2;
if(a[0])
cout<<"Alice"<<endl;
else
cout<<"Bob"<<endl;
}
}
|
在一个(n,m)的区域内有k面墙
勇者从(xs+0.5,ys+0.5)出发到恶龙的位置( xt+0.5, yt+0.5)。
求勇者最少要消去多少面墙
思路：将每个坐标都乘以2，使0.5变成整数，我们发现最多只有15面墙，二进制枚举每一面墙的存在状态，对每种情况bfs，结果取最小
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
| #include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int N = 30 + 10;
int n, m, k;
int path[N], g[N][N], d[N][N];
int mi, xs, ys, xt, yt;
struct tk {
int x1, x2, y1, y2;
}wall[N];
struct T {
int x, y;
};
void init() {
memset(g, 0, sizeof g);
memset(d, 0, sizeof d);
d[ys][xs] = 1;
int x1, y1, x2, y2;
for(int i = 1; i <= k; i++) {
if(path[i]) {
x1 = wall[i].x1;
x2 = wall[i].x2;
y1 = wall[i].y1;
y2 = wall[i].y2;
x1 *= 2; x2 *= 2; y1 *= 2; y2 *= 2;
if(x1 == x2) {
for(int i = min(y1,y2); i <= max(y1,y2); i++) g[i][x1] = 1;
} else if(y1 == y2) {
for(int i = min(x1,x2); i <= max(x1,x2); i++) g[y1][i] = 1;
}
}
}
}
void bfs() {
int now = 0;
for(int i = 1; i <= k; i++) {
if(path[i] == 0)
now++;
if(now >= mi)
return;
}
queue<T> q;
q.push({xs,ys});
init();
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while(q.size()) {
T t = q.front();
q.pop();
for(int i = 0; i < 4; i++) {
int x = t.x + dx[i], y = t.y + dy[i];
if(x >= 0 && y >= 0 && x <= n && y <= m && g[y][x] == 0 && d[y][x] == 0) {
if(x == xt && y == yt) {
mi = now;
return ;
}
q.push({x,y});
d[y][x] = 1;
}
}
}
}
void dfway(int u) {
if(u == k + 1) {
bfs();
return ;
}
path[u] = 1;
dfway(u + 1);
path[u] = 0;
dfway(u + 1);
}
void solve() {
cin >> n >> m >> k;
cin >> xs >> ys >> xt >> yt;
n *= 2; m *= 2; xs *= 2; ys *= 2; xt *= 2; yt *= 2;
xs++; ys++; xt++; yt++;
for(int i = 1; i <= k; i++) {
int x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
wall[i] = {x1, x2, y1, y2};
}
mi = k;
dfway(1);
cout << mi << endl;
}
int main() {
IOS;
int t;
cin >> t;
while(t--)
solve();
}
|
代码参考自这个式姐不太冷
