第20届上海大学程序设计联赛春季赛（同步赛） 签到题6题

题号 标题 已通过代码 通过率 我的状态
A 如何才能穿过传送门 点击查看 537/2713 通过
B 逃离魔爪 点击查看 47/341 未通过
C 古老的恩尼格玛机 点击查看 709/1004 通过
D 并不智能的卡牌 AI 点击查看 832/2679 通过
E 林荫小径 点击查看 3/10 未通过
F 到底是多少分啊 点击查看 13/51 未通过
G 多吃蘑菇 点击查看 229/926 通过
H 差不多得了 点击查看 670/1300 通过
I 数学题真难啊 点击查看 174/306 通过

A 如何才能穿过传送门

链接：https://ac.nowcoder.com/acm/contest/33785/A
来源：牛客网

题目描述
你走入了一条布满了传送门和墙的小巷。

小巷可以视为一条位于XX 轴上的线段，从 00 点开始，到 nn 点结束。你一次只能向左或者向右走一格。在小巷里面有若干对传送门，你不可以越过传送门而不进行传送。你从传送门的左侧一格进入，会从对应传送门出来并且下一次只能往右走；从传送门的右侧一格进入，会从对应传送门出来并且下一次只能往左走。同时中间现在有若干面墙，你不能走到墙上。保证所有的墙和传送门不会重合。你现在位于 00 点，请问你能否到达 nn 点？
输入描述:
第一行包含三个整数 nn, mm, qq (0 \le n, m, q \le 1000, 2 \times m + q \le n)(0≤n,m,q≤1000,2×m+q≤n) ，分别表示小巷的长度、传送门的对数和墙的数量。

接下来 mm 行，第 ii 行包含两个整数 x_ix
i
​
, y_iy
i
​
(0 \lt x_i \lt y_i \lt n)(0<x
i
​
<y
i
​
<n) 表示一对传送门的坐标。

接下来一行包含 qq 个整数 a_j (0 \lt a_j \lt n)a
j
​
(0<a
j
​
<n)，表示墙的坐标。

输出描述:
如果你能能穿过小巷（即到达n点），则在一行输出 “YES”，否则输出 “NO”（不包含引号，不区分大小写）。

示例1
输入
复制
10 2 2
1 3
4 6
2 5
输出
复制
YES
示例2
输入
复制
100 0 1
50
输出
复制
NO

思路：

• 因为你不可以越过传送门而不进行传送，所以直接往右走，遇到传送门就传送，然后再往右走就可以了。遇到墙就挂了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int mp[maxn], no[maxn];
int main(){
    memset(mp,-1,sizeof(mp));
    int n, m, q;  cin>>n>>m>>q;
    for(int i = 1; i <= m; i++){
        int x, y;  cin>>x>>y;
        mp[x] = y, mp[y] = x;
    }
    for(int i = 1; i <= q; i++){
        int x;  cin>>x;  no[x] = 1;
    }
    int ok = 1;
    for(int i = 0; i <= n; i++){
        if(mp[i]!=-1)i = mp[i];
        else if(no[i]==1)ok = 0;
    }
    if(ok)cout<<"YES\n";
    else cout<<"NO\n";
    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
 

• 开始想复杂了，写了个dfsWA了，过了94%的点

//dfs, 94%
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1050;
int n, m, q;  
vector<int>G[maxn];
int no[maxn];

int ans, vis[maxn];
void dfs(int u, int fa){
	// cout<<u<<" "<<fa<<"\n";
	if(u==n){
		ans = 1; return ;
	}
	if(vis[u])return ;
	vis[u] = 1;
	for(int to : G[u]){
		// cout<<"asdf"<<to<<" "<<fa<<"\n";
		if(to!=fa){
			if(no[to]==1)continue;
            if(G[u].size()>2 && (to==u+1 || to==u-1))continue;
			if(fa<u-1 && to==u-1 )continue;
			if(fa>u+1 && to==u+1 )continue;
			// cout<<"xxx"<<to<<"\n";
			dfs(to, u);
		}
	}
	// vis[u] = 0;
}

int main(){
	// memset(e,0,sizeof(e));
    cin>>n>>m>>q;
    for(int i = 0; i < n; i++){
        G[i].push_back(i+1);
		if(i!=0)G[i].push_back(i-1);
    }
	for(int i = 1; i <= m; i++){
		int x, y;  cin>>x>>y;
		G[x].push_back(y);
		// G[y].push_back(x);
	}
	for(int i = 1; i <= q; i++){
		int x;  cin>>x;  no[x] = 1;
	}
	dfs(0, 0);
    if(ans)cout<<"YES\n";
    else cout<<"NO\n";
    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
 

• 然后改成bfs过的

//bfs, ac
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int maxn = 1010;

PII b[maxn];
int a[maxn];
int n, m, q;
int vis[maxn][2],no[maxn],to[maxn];
struct node{ int p,cur;};

int main(){
    cin>>n>>m>>q;
    for(int i = 1; i <= m; i++) {
        int x,y;  cin>>x>>y;
        to[x] = y;  to[y] = x;
    }
    for(int i = 1; i <= q; i++) {
        cin>>a[i];  no[a[i]] = 1;
    }
    queue<node>q;
    q.push({0,0});
    while(q.size()){
        node now = q.front();q.pop();
        if(now.p == n){
            cout<<"YES\n"; return 0;
        }
        if(no[now.p])continue;
        if(now.p < 0 || now.p > n)continue;
        if(now.cur != 0) {
            if(now.cur == 1){
                if(vis[now.p][1])continue;
                if(to[now.p+1]) q.push({to[now.p+1],1});
                else q.push({now.p+now.cur,0});
                vis[now.p][1] = 1;
            }
            else{
                if(vis[now.p][0])continue;
                if(to[now.p-1]) q.push({to[now.p-1],-1});
                else q.push({now.p + now.cur,0});
                vis[now.p][0] = 1;
            }
        }else{
            if(vis[now.p][0]);
            else if(to[now.p-1])q.push({to[now.p-1],-1});
            else q.push({now.p-1,0});
            if(vis[now.p][1]);
            else if(to[now.p+1])q.push({to[now.p+1],1});
            else q.push({now.p+1,0});
            vis[now.p][1] = vis[now.p][0] = 1;
        }
    }
    cout<<"NO";
    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
 

C 古老的恩尼格玛机

链接：https://ac.nowcoder.com/acm/contest/33785/C
来源：牛客网

题目描述
你顺利入了城，看见了古老的恩尼格玛机。

恩尼格玛机（Enigma Machine）是第二次世界大战期间德国使用的信息加解密设备，其每次 Reflector 过程定义如下：

输入一个大写字母;
根据转换关系，输出该字母对应的输出字母。

其中的转换关系通过 1313 个字符对（共 2626 个字母，其中两两不重复）给出。

以下是一次 Reflector 过程的举例：

对输入的一段字符串 “ABC“，假定存在转换关系 A-B 和 C-D，则其对应的输出字符串为 ”BAD’'。

你需要实现一个 Reflector 模块，在给定一系列转换关系的情况下，对每个输入的字符串，给出其对应的输出字符串。

输入数据保证：

每个字符串长度 |s|\leq 255∣s∣≤255；
所有字符串总长度 \sum |s| \leq 10^5∑∣s∣≤10
5
；
所有字符串中仅包含大写字母。
输入描述:
第一行包含 2626 个不重复大写字母，以空格分隔，其中第 2i-12i−1 和 2i2i 个字母表示一对转换关系 (1 \leq i \leq 131≤i≤13)。

第二行包含一个整数 kk (1 \leq k \leq 10^51≤k≤10
5
)，表示输入的字符串个数。

接下来一行包含 kk 个由空格分隔的非空字符串。

输出描述:
仅一行，表示每个输入字符串对应的输出结果，字符串间以空格分隔。
示例1
输入
复制
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
4
ABC QWQ HELLO WORLD
输出
复制
BAD RXR GFKKP XPQKC

思路：

• 直接开个映射存起来，输出即可。

#include<bits/stdc++.h>
using namespace std;

int e[500];

int main(){
    for(int i = 1; i <= 13; i++){
        char a, b;  cin>>a>>b;
        e[a] = b;  e[b] = a;
    }
    int k;  cin>>k;
    for(int i = 0; i < k; i++){
        string s;  cin>>s;
        for(char ch : s){
            cout<<(char)e[ch];
        }
        cout<<" ";
    }
    return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

D 并不智能的卡牌 AI

链接：https://ac.nowcoder.com/acm/contest/33785/D
来源：牛客网

题目描述
公元 2202 年，你漫步在元宇宙的世界中，遇见了守着 SHU 城门的 Foxity AI。Foxity AI 正被一个翻牌问题困扰着，并请求你帮帮他。

Foxity AI 面前存在 mm 张背面朝上的卡牌。在一步里，Foxity AI 可以将至多 nn 张牌翻面，Foxity AI 想知道他能不能通过若干步操作，使面前的所有卡牌都变为正面朝上的状态（即不存在牌背面朝上）。如果能的话，请告诉他至少需要多少步。
输入描述:
输入仅一行，包含两个整数 mm, nn (0\le m,n \le 10^8)(0≤m,n≤10
8
) ，含义如题目背景所述。
输出描述:
如果 Foxity AI 能做到将面前的所有卡牌都变为正面朝上的状态，则在一行一个整数，表示 Foxity AI 最少需要的步数；否则在一行输出 -1 ,表示不能做到。
示例1
输入
复制
8 6
输出
复制
2
示例2
输入
复制
8 0
输出
复制
-1
示例3
输入
复制
0 8
输出
复制
0

思路：

• 直接m/n即可，注意特判一下n=m=0的情况

#include<bits/stdc++.h>
using namespace std;

int main(){
    int m, n;  cin>>m>>n;
    if(n==0 && m==0){
        cout<<"0\n";
        return 0;
    }
    if(n==0){
        cout<<"-1\n";
        return 0;
    }
    int x = m/n;
    if(m%n!=0)x++;
    cout<<x<<"\n";
    return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

G 多吃蘑菇

链接：https://ac.nowcoder.com/acm/contest/33785/G
来源：牛客网

题目描述
Crazycth 看见了穿过传送门的你，他邀请你帮助他的室友。

Crazycth 的室友经常深夜看马里奥录播，现在他正梦到自己被库巴追，被迫逃进了一个迷宫。

迷宫可以视为一棵 nn 个节点的树，在第 ii 个节点有一个大小 w_iw
i
​
，颜色为 c_ic
i
​
的蘑菇。

Crazycth 的室友喜欢吃蘑菇，但是相同颜色的蘑菇他只想吃一个，同时每个节点只能经过一次。他可以瞬间算出以任一节点为终点时他所能吃的蘑菇大小总和的最大值。不过他此时忙于在迷宫入口（11 号节点）吃蘑菇，聪明的你能帮忙解决这个问题吗？
输入描述:
第一行包含一个正整数 n (2\le n \le 10^5)n(2≤n≤10
5
)，表示迷宫节点的个数。

第二行包含 nn 个正整数 w_1,w_2, \ldots, w_nw
1
​
,w
2
​
,…,w
n
​
(1 \le w_i \le 10^8)(1≤w
i
​
≤10
8
) ，分别表示第 ii 个节点的蘑菇的大小。

第三行包含 nn 个正整数 c_1,c_2, \ldots, c_n (1 \le c_i \le n)c
1
​
,c
2
​
,…,c
n
​
(1≤c
i
​
≤n)，分别表示第 ii 个节点的蘑菇的颜色。

接下来 n - 1n−1 行，每行两个正整数 u_i,v_i (1 \le u_i \lt v_i \le n)u
i
​
,v
i
​
(1≤u
i
​
<v
i
​
≤n)，表示连接 u_iu
i
​
和 v_iv
i
​
的一条边 。

输入数据保证不存在重边，并且每个节点都可以由起点唯一到达，11 号节点为起点。

输出描述:
输出 nn 行，第 ii 行包含一个整数，即从 11 号点出发最终到达 ii 号点时，能吃到的蘑菇的大小总和的最大值。
示例1
输入
复制
5
1 4 5 5 9
1 2 2 3 4
1 2
2 3
3 5
1 4
输出
复制
1
5
6
6
15

思路：

• 直接dfs遍历每个点，开个数组维护一下到当前为止每个颜色最大的蘑菇，然后回溯的时候改回去就行。
• 注意蘑菇大小1e8加起来会爆int，要开ll

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 2e5+10;
LL w[maxn], c[maxn];
vector<LL>G[maxn];

// map<LL,LL>mp;
LL cc[maxn];
LL now = 0;
LL ans[maxn];
void dfs(LL u, LL fa){
    // if(!mp.count(c[u]))mp[c[u]] = 0;
    LL t = cc[c[u]], ok = 0;
    if(w[u] > cc[c[u]]){
        cc[c[u]] = w[u];
        now -= t;
        now += w[u];
        ok = 1;
    }
    ans[u] = now;
    for(LL to : G[u]){
        if(to != fa)dfs(to, u);
    }
    if(ok==1){
        now += t;
        now -= w[u];
    }
    cc[c[u]] = t;
}

int main(){
    LL n;  cin>>n;
    for(LL i = 1; i <= n; i++)cin>>w[i];
    for(LL i = 1; i <= n; i++)cin>>c[i];
    for(LL i = 1; i < n; i++){
        LL u, v;  cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, -1);
    for(LL i = 1; i <= n; i++){
        cout<<ans[i]<<"\n";
    }
    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
 

H 差不多得了

链接：https://ac.nowcoder.com/acm/contest/33785/H
来源：牛客网

题目描述
Auggie 非常喜欢说差不多，而 Crazycth 非常喜欢说得了，于是他们在一起玩时经常发出差不多得了的声音。

对于一个由正整数组成的数组 aa，定义 ss 为 aa 数组所有元素之和，即\displaystyle s=\sum_{i=1}^{n} a_{i}s=
i=1
∑
n
​
a
i
​
。Auggie 会将数组中的一些数取出并按原来顺序拼接成一个新的子数组 bb，即 bb 是 aa 的一个子序列，而一个数组的子序列被称为差不多得了的当且仅当它的所有元素之和等于 s-1s−1。

Crazycth 想知道数组 aa 有多少种本质不同的差不多得了的 bb。你能帮他解答吗？

对于数组 xx 与 yy，它们是本质不同的当且仅当它们长度不同或存在 ii 使得 x_i \neq y_ix
i
​


​
=y
i
​
。

输入描述:
第一行包含一个整数 T (1 \le T \le 1000)T(1≤T≤1000)，表示测试数据的组数。对于每组数据：

第一行包含一个整数 n (1 \le n \le 30)n(1≤n≤30)，表示数组元素的个数。

第二行包含 nn 个整数 a_1,a_2,\ldots,a_n (1 \le a_i \le 10^9)a
1
​
,a
2
​
,…,a
n
​
(1≤a
i
​
≤10
9
)，表示数组的每个元素。
输出描述:
对于每组数据，在一行输出一个整数表示有多少种本质不同的差不多得了的数组 bb 的数量。
示例1
输入
复制
3
3
1 2 3
2
100 4
5
3 4 2 1 1
输出
复制
1
0
1
备注:
子数列，又称子序列，在数学中，某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列，如空数组， {(1,2,4)}(1,2,4) 和 {(1,2,3,4)}(1,2,3,4) 是 {(1,2,3,4)}(1,2,3,4) 的子序列， 而 {(1,4,3)}(1,4,3) 不是。

思路：

• 统计一下有多少段连续的1即可。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        int cnt = 0, ok = 0;
        for(int i = 1; i <= n; i++){
            int x;  cin>>x;
            if(x==1){
                if(ok==0)cnt++;
                ok = 1;
            }else{
                ok = 0;
            }
        }
        cout<<cnt<<"\n";
    }
    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
 

I 数学题真难啊

链接：https://ac.nowcoder.com/acm/contest/33785/I
来源：牛客网

题目描述
你告别了 Crazycth 继续上路，又遇到了不喜欢数学的 DavidXu_JJ 讲故事。

DavidXu_JJ 有一天和他的队友在训练时，遇到这么一道题：

有一个长度为 nn 的数组 a = [a_1, a_2, \ldots, a_n]a=[a
1
​
,a
2
​
,…,a
n
​
]，数组中的每个元素可以是 0 \sim 90∼9 中的任意一个整数。如果它所有元素之和 \sum a∑a 是 33 的倍数，那么就称它为有趣的数组，你需要求出所有长度为 nn 的数组中有多少种数组是有趣的。

DavidXu_JJ 和他的队友决定构造它的 生成函数 并使用 快速傅立叶变换 来计算这个值，但在复盘时发现这题有极其简单的方法能够算出答案，导致他们当场脑淤血晕倒过去。

DavidXu_JJ 从病床上想到了一个更加困难的问题，但他因为心理阴影导致无法独立解决这个问题，请问你能否帮助他解决？题目描述如下：

有一个长度为 nn 的数组 a = [a_1, a_2, \ldots, a_n]a=[a
1
​
,a
2
​
,…,a
n
​
]，数组中的每个元素可以是 0 \sim 90∼9 中的任意一个整数。现将其下标为奇数的元素和偶数的元素分别取出，组成两个数组 a^{\text{odd}}a
odd
和 a^{\text{even}}a
even
。例如：数组 a = [1, 2, 3, 4, 5, 6, 7]a=[1,2,3,4,5,6,7] 被分为数组 a^{\text{odd}} = [1, 3, 5, 7]a
odd
=[1,3,5,7] 和数组 a^{\text{even}} = [2, 4, 6]a
even
=[2,4,6]。

如果 \sum a^{\text{odd}}∑a
odd
是 33 的倍数且 \sum a^{\text{even}}∑a
even
数组是 99 的倍数，那么就称 aa 为"不有趣的数组’'，请求出所有长度为 nn 的不有趣数组的个数。由于答案可能很大，你只需要输出答案对 998244353998244353 取模后的结果。
输入描述:
第一行包含一个整数 nn (1 \le n \le 3 \times 10^5)(1≤n≤3×10
5
)，表示数组 aa 的长度。
输出描述:
在一行输出一个整数，表示所有长度为 nn 的不有趣数组的个数对 998244353998244353取模后的结果。
示例1
输入
复制
2
输出
复制
8
示例2
输入
复制
5
输出
复制
4008
示例3
输入
复制
114514
输出
复制
549375874

思路：

• 打个表再思考一下，不难发现，3和9是独立考虑的，相当于奇数位加起来%3=0，偶数位加起来%3=0。
• 因为3和9的特殊性，加起来%3=0等价于这个数本身%3=0，所以问题转化为求1位数，2位数，3位数，，，n位数，里面%3=0的数的个数。 3和9都是n/2位数，如果有多的位数就加到3上。
• 考虑100%3=0的数的个数，就是个小学生问题直接/3即可。注意这里0也被算到%3=0上，所以/3后要+1。
• 然后就$(\frac{10^{n/2+1}-1}{3}+1)\ast (\frac{10^{n/2}-1}{9}+1)$即可，注意做除法的时候要用逆元，取模要多取一下。
• 关于+1-1的问题，举个例子：题目输入n=6, 所以3是三位数，9也是三位数，然后三位数是从000-999的，10^3 = 1000，所以要-1。999/3=333，但是0%3=0，所以是334。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;

LL pows(LL a, LL x) { if(x==0)return 1; LL t = pows(a, x>>1); if(x%2==0)return t*t%mod; return t*t%mod*a%mod; }
LL pows(LL a, LL x, LL p) { if(x==0)return 1; LL t = pows(a, x>>1, p); if(x%2==0)return t*t%p; return t*t%p*a%p; }
LL exgcd(LL a, LL b, LL &x, LL &y){ if(!b){ x = 1, y = 0; return a; }else{LL r = exgcd(b, a%b, x, y); LL t = x; x = y; y = t-a/b*y; return r; }}
void exgcd(LL a, LL b, LL &d, LL &x,  LL & y, LL MOD) { if (b==0) { d = a; x = 1; y = 0; } else { exgcd(b, a % b, d, y, x, MOD); y -= x * (a / b); } }
LL inv(LL a, LL MOD) { LL d=0, x=0, y=0; exgcd(a, MOD,  d,  x, y, MOD); return d == 1 ? (x + MOD) % MOD : -1; }

int main(){
    LL n;  cin>>n;
    LL x = n/2, y = n/2;
    if(n%2==1)x++;
    LL xx = (pows(10,x,mod)-1+mod)%mod*inv(3,mod)%mod+1, yy = (pows(10,y,mod)-1+mod)%mod*inv(9,mod)%mod+1;
    cout<<(xx*yy+mod)%mod<<"\n";
    return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/124651079