2023.2.25 SZUACM入队热身赛
出题人：陈天行
- A: https://codeforces.com/contest/1762/problem/A
- B: https://codeforces.com/contest/1294/problem/B
- C: https://codeforces.com/problemset/problem/1461/C
- D:https://codeforces.com/problemset/problem/505/B
- E:https://codeforces.com/problemset/problem/1704/C
- F: https://codeforces.com/problemset/problem/1557/C
按照惯例，先配一个狗头：
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
::
:;J7, :, ::;7:
,ivYi, , ;LLLFS:
:iv7Yi :7ri;j5PL
,:ivYLvr ,ivrrirrY2X,
:;r@Wwz.7r: :ivu@kexianli.
:iL7::,:::iiirii:ii;::::,,irvF7rvvLujL7ur
ri::,:,::i:iiiiiii:i:irrv177JX7rYXqZEkvv17
;i:, , ::::iirrririi:i:::iiir2XXvii;L8OGJr71i
:,, ,,: ,::ir@mingyi.irii:i:::j1jri7ZBOS7ivv,
,::, ::rv77iiiriii:iii:i::,rvLq@huhao.Li
,, ,, ,:ir7ir::,:::i;ir:::i:i::rSGGYri712:
::: ,v7r:: ::rrv77:, ,, ,:i7rrii:::::, ir7ri7Lri
, 2OBBOi,iiir;r:: ,irriiii::,, ,iv7Luur:
,, i78MBBi,:,:::,:, :7FSL: ,iriii:::i::,,:rLqXv::
: iuMMP: :,:::,:ii;2GY7OBB0viiii:i:iii:i:::iJqL;::
, ::::i ,,,,, ::LuBBu BBBBBErii:i:i:i:i:i:i:r77ii
, : , ,,:::rruBZ1MBBqi, :,,,:::,::::::iiriri:
, ,,,,::::i: @arqiao. ,:,, ,:::ii;i7:
:, rjujLYLi ,,:::::,:::::::::,, ,:i,:,,,,,::i:iii
:: BBBBBBBBB0, ,,::: , ,:::::: , ,,,, ,,:::::::
i, , ,8BMMBBBBBBi ,,:,, ,,, , , , , , :,::ii::i::
: iZMOMOMBBM2::::::::::,,,, ,,,,,,:,,,::::i:irr:i:::,
i ,,:;u0MBMOG1L:::i:::::: ,,,::, ,,, ::::::i:i:iirii:i:i:
: ,iuUuuXUkFu7i:iii:i:::, :,:,: ::::::::i:i:::::iirr7iiri::
: :rk@Yizero.i:::::, ,:ii:::::::i:::::i::,::::iirrriiiri::,
: 5BMBBBBBBSr:,::rv2kuii:::iii::,:i:,, , ,,:,:i@petermu.,
, :r50EZ8MBBBBGOBBBZP7::::i::,:::::,: :,:,::i;rrririiii::
:jujYY7LS0ujJL7r::,::i::,::::::::::::::iirirrrrrrr:ii:
,: :@kevensun.:,:,,,::::i:i:::::,,::::::iir;ii;7v77;ii;i,
,,, ,,:,::::::i:iiiii:i::::,, ::::iiiir@xingjief.r;7:i,
, , ,,,:,,::::::::iiiiiiiiii:,:,:::::::::iiir;ri7vL77rrirri::
:,, , ::::::::i:::i:::i:i::,,,,,:,::i:i:::iir;@Secbone.ii:::
A
https://codeforces.com/contest/1762/problem/A
题意
多组数据，给定n个数字，每次可以选择一个数字，并对他进行整除2的操作。请问能让他们的和变成偶数的最小操作次数。
分析
可以一眼看出，当这些数字的和本来就是偶数的话，显然结果就是0。如果是奇数，很明显最小的话是操作一直对同一个数字做，直到他的奇偶性改变，分析一下时间复杂度，可以发现暴力操作的时间复杂度是$O(n)$，常数为$log(1e6)$，显然是可以接受的，具体就看代码吧。
solution
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
#include<bits/stdc++.h>
#define MAXN 51
using namespace std;
int T, n, m, a[MAXN];
signed main() {
cin >> T;
while(T--) {
cin >> n;
int sum = 0;
for(int i=1; i<=n; i++) cin >> a[i], sum += a[i];
if(sum&1) {
int minTime = INT_MAX;
for(int i=1; i<=n; i++) {
int temp = a[i], cnt = 0;
while(temp) {
++cnt, temp >>= 1;
if((temp&1)^(a[i]&1)) {
minTime = min(minTime, cnt);
break;
}
}
}
printf("%d\n", minTime);
} else puts("0");
}
return 0;
}
B
https://codeforces.com/contest/1294/problem/B
题意
你从(0, 0)出发，目标是只向上或者向下经过所有的目标点，问是否可行并且给出具体的路径。
分析
可以分析出每次到达某个点$(x_i, y_i)$，那么下一个能到达的点$(x_j, y_j)$，一定会有$x_i<=x_j$，$y_i<=y_j$，所以我们只要对受伤的点排序，然后一个一个验证并且走一走就行，时间复杂度$O(n\log(n))$。
solution
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>
#define MAXN 1001
using namespace std;
int T, n, m;
struct NODE {
int x, y;
} node[MAXN];
signed main() {
cin >> T;
while(T--) {
cin >> n;
for(int i=1; i<=n; i++) cin >> node[i].x >> node[i].y;
sort(node+1, node+n+1, [&](NODE a, NODE b){
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
});
bool check = true;
node[0].x = node[0].y = 0;
for(int i=1; i<=n; i++) {
if(node[i].y < node[i-1].y) {
check = false;
break;
}
}
if(!check) puts("NO");
else {
puts("YES");
for(int i=1; i<=n; i++) {
int dx = node[i].x - node[i-1].x;
int dy = node[i].y - node[i-1].y;
for(int j=1; j<=dx; j++) printf("R");
for(int j=1; j<=dy; j++) printf("U");
}
puts("");
}
}
return 0;
}
C
https://codeforces.com/problemset/problem/1461/C
题意
多组数据，有一个长度为n的排列，可以做m次操作，每次操作可以描述为$(r_i, p_i)$，代表着有$p_i$的概率使得子序列$[1~r_i]$有序。请问经过m次操作后，有多少的概率使得排列有序。
分析
因为是排列，所以最后的状态显然是：第$i$个位置上的数字为$i$。对于原序列最后一个$i != a_i$，应该有至少一次$r_i>=i$发生，就能使得排列有序，而且对于别的$r_i<i$其实是没有意义的，因为最后会被覆盖，所以就乱搞一下就行，时间复杂度$O(n+m)$。
solution
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>
#define MAXN 100001
using namespace std;
int T, n, m, a[MAXN], r[MAXN];
double p[MAXN], dp[MAXN];
signed main() {
cin >> T;
while(T--) {
cin >> n >> m;
double count = 1;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=m; i++) cin >> r[i] >> p[i];
int ed = 0; // 最后一个i!=a[i]
for(int i=n; i>=1; i--) {
if(a[i]==i) continue;
ed = i;
break;
}
if(!ed) puts("1.000000"); // 本来就有序
else {
for(int i=1; i<=m; i++) {
if(r[i]<ed) continue;
count = count*(1-p[i]);
}
printf("%.6lf\n", 1-count);
}
}
return 0;
}
D
https://codeforces.com/problemset/problem/505/B
题意
给定一个无向图，每一条边上的权代表其颜色，然后有m个询问，对于给定的起始点u和终点v，求有多少种颜色，满足：从u到v的路径上，能够只经过这种颜色。
分析
可以发现数据量很小，很典型的并查集，不过由于cf标签上给的是dfs，所以题解就写一个dfs吧。dfs的思路就是用dfs，对，不知道有什么好说的，对于所有颜色，从起点u出发，dfs走向所有的同色边，直到走到终点v，为了防止回头走所以加上一个walked作标记，注意回溯的时候对walked作还原。时间复杂度$O(n \times m)$
solution
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
#include<bits/stdc++.h>
#define MAXN 1001
using namespace std;
int T, n, m, u, v;
set<int> connect[MAXN][MAXN];
bool walked[MAXN];
bool dfs(const int& x, const int& target, const int& color) {
if(x==target) return true;
for(int i=1; i<=n; i++) {
if(!walked[i]&&!connect[x][i].empty()&&connect[x][i].find(color)!=connect[x][i].end()) {
walked[i] = true;
bool temp = dfs(i, target, color);
walked[i] = false;
if(temp) return true;
}
}
return false;
}
signed main() {
cin >> n >> m;
for(int i=1, c; i<=m; i++) {
cin >> u >> v >> c;
connect[u][v].insert(c), connect[v][u].insert(c);
}
cin >> T;
while(T--) {
cin >> u >> v;
int cnt = 0;
for(int i=1; i<=m; i++) {
walked[u] = true;
if(dfs(u, v, i)) ++cnt;
walked[u] = false;
}
cout << cnt << endl;
}
return 0;
}
E
https://codeforces.com/problemset/problem/1704/C
题意
多组数据，有一个长度为n的环，其中，初始时有m个房间带有病毒，每一天后每一个带有病毒的房间都会传染到相邻的未被感染且未受保护的房间，每一天你可以在当天发生传染前，你都可以选择一个未被感染的房间进行保护，这样从当天开始这个房间就不会被感染。请问最后最少有多少房间会被感染？
分析
显然每个连续的未被感染的房间可以看成一个区间，每次最优的策略就是堵住区间的两端，显然，如果某个区间被全部感染，那么他们就不会再产生感染的贡献，所以我们对于长度比较短的区间，我们期望他们能接受更多的感染，所以就是对区间长度排序，然后遍历一边就行，时间复杂度$O(nlog(n))$。
solution
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>
#define MAXN 10001
using namespace std;
int T, n, m, a[MAXN];
int main() {
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> a[i];
sort(a + 1, a + m + 1);
vector<int> K;
a[0] = -(n - a[m]);
for (int i = 1; i <= m; i++) K.push_back(a[i] - a[i - 1] - 1);
sort(K.begin(), K.end(), greater<int>()); // 从大到小排序
long long answer = 0, cntTime = 0;
for (auto x : K) {
if (x - cntTime * 2 >= 3) {
answer += x - (cntTime * 2 + 1);
cntTime += 2;
} else if (x - cntTime * 2 >= 1) {
answer += 1;
++cntTime;
} else break;
}
cout << n - answer << endl;
}
return 0;
}
F
https://codeforces.com/problemset/problem/1557/C
题意
多组数据，给定一个n和k，均为2e5级别，模数为1e9+7。要求你构造n个数字，每个数字的大小不大于$2^k$，问你有多少种可能使得这n个数字的与和大于异或和。
分析
一眼看出可以分不同二进制位讨论，为了方便描述，我们定义sumAnd和sumXor分别为与和以及异或和。从二进制的高位开始看起，如果在某一个高位sumAnd为1，sumXor为0，那么很显然接下来的所有二进制位可以任取。如果更高位两者全一致，那么这一位两者允许一致，或者sumAnd为1，sumXor为0，不允许sunAnd为0，sumXor为1。然后就设定2个状态进行dp就行。注意这里需要频繁计算组合数以及指数，所以需要预处理好，需要用到分数模（我数论一坨大便，所以不知道有没有更好的方法），注意需要long long，时间复杂度$O(k)$。
solution
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<bits/stdc++.h>
#define MAXN 200005
#define mod 1000000007
using namespace std;
long long T, n, m, k, fz[MAXN], fm[MAXN], pre[MAXN], dp[MAXN][2];
long long Pow(long long a,long long k) {//求a的k次方，快速幂
long long answer=1;
a%=mod;
while(k) {
if(k&1) answer=(answer*a)%mod;
a=(a*a)%mod;
k>>=1;
}
return answer;
}
long long f(long long b, long long a) {
return (b%mod)*Pow(a,mod-2)%mod;
}
void init() {
fz[0] = fm[0] = 1;
for(int i=1; i<=2e5; i++) fz[i] = (fz[i-1]*i)%mod, fm[i] = f(1, fz[i]);
}
long long C(long long b, long long a) {
return fz[a]*fm[a-b]%mod*fm[b]%mod;
}
signed main() {
cin >> T;
init();
while(T--) {
cin >> n >> k;
long long answer = 1;
pre[0] = 1;
for(int i=2; i<=n; i+=2) pre[i] = (pre[i-2]+C(i, n))%mod;
long long allC = Pow(2, n);
dp[k][0] = 1, dp[k][1] = 0;
for(int i=k-1; i>=0; i--) { // 0代表全一样，1代表之前已经打过了
if(n%2==0) {
dp[i][0] = (dp[i+1][0]*pre[n-2])%mod;
} else {
dp[i][0] = (dp[i+1][0]*(pre[n-1]+1))%mod;
}
dp[i][1] = (dp[i+1][1]*allC%mod+dp[i+1][0]*(n%2==0))%mod;
}
cout << (dp[0][0]+dp[0][1])%mod << endl;
}
return 0;
}
Comments powered by Disqus.