河南萌新赛

2022河南萌新联赛第（四）场：郑州轻工业大学

A ZZULI

B 大本营

---

C 最大公因数

题目描述
多实例。
每组实例给定 $l,r,x$，找出两个在 $[l,r]$ 内不同的数 $a,b$，满足 $gcd(a,b)=x$

输入描述:
一个正整数 $T$ 表示实例个数。
接下来 $T$ 行每行三个正整数 $l,r,x$
$1\le T\le 10^5$
$1\le l,r,x\le 10^9$

输出描述:
对于每个实例，如果能找到满足上述条件的，输出$a,b$。否则输出 $-1$。
如果有多个解，输出任意一个。

输入

4
1 10 5
3 10 2 
1 1000000000 100
12 12 5
1
2
3
4
5

输出

5 10
6 10
100 1000000000
-1
1
2
3
4

解题思路：

看见题目的第一想法，这题是不是和gcd(最大公因数)有关，但再仔细一读，a,b要在 $[l,r]$ 区间内，很明显这样的a,b 可能不唯一，如果两层 for 遍历，那么时间复杂度可能大的离谱，所以，在想一想gcd的特性，也就是a,b可以被x整除，所以我们只需要在区间内找到两个整数，是x的k倍（k=0,1,2,…）。

但是这里还会发现一个问题，例如测试样例里的 3 10 2 很明显x并不在区间内，所以需要找到一个在区间内的x的k倍的数。

我一开始的想法是找到离左端点L 最近的满足在区间内的x的k倍的数，但是问题是需要用倍增去寻找，还是有一定的时间开销，所以，换一个角度

令 m = R / x 很明显，右端点除以x 就是区间内 x 可以倍增到的最大倍数，所以我们只需要考虑 m * x和( m - 1) * x 在区间内即可输出，否则输出-1

解题代码：

void solve(){
    int l, r, x;
    cin >> l >> r >> x;
    int bei=r/x;
    if(bei*x>=l&&bei*x<=r&&(bei-1)*x>=l&&(bei-1)*x<=r){
        cout<<(bei-1)*x<<" "<<bei*x<<nl;
    }else
        cout<<-1<<nl;
}
1
2
3
4
5
6
7
8
9

---

D 大盗

E 睡大觉

F 小欧拉

---

G 迷宫

题目描述
大$Z$在与三体人战斗的过程中，不慎掉进了其布置的迷宫陷阱当中，他想要尽快从逃离这里。

迷宫由墙和路组成，大$Z$需要 ($(1,1)$ 走到 $(n,m)$，每走一步的时间是 $1s$，其中墙不能通过。

大$Z$发现在迷宫的路上长有神奇的花朵，吃了这种花朵可以让时间倒流 $1s$，每个花朵只能吃一次，且花朵状态不会跟随时间倒流。

现在大 $Z$ 想让你计算他从 $(1,1)$ 走到 $(n,m)$ 所花费的时间。

输入描述:
第一行两个整数 $n,m$ 表示迷宫的范围

随后 $n$ 行每行一个字符串表示对迷宫的描述

'.' 表示路

'#' 表示墙

'*' 表示花朵

$1\le n,m\le 2000$

保证第一行第一个字符为 '.'

输出描述:
一个数字 表示大$Z$从 $(1,1)$ 到 $(n,m)$ 的最短时间，如果不能到达，输出 $-1$

解题思路：

最短路问题，两两建边，如果目标点为花那么边权为 $1-1=0$ ，否则为 $1$

固定源点（起点）与汇点（终点），最短路的各种算法都可以写 。

---

当然我一开始不是这么想的，看到题目的第一感受

我想到了

从 $(1,1)$ 走到 $(n,m)$ 有多少不同的路径

然后就开始了动态规划

int mp[2010][2010];
ll dp[2020][2020];
void solve(){
    int n, m;
    cin >> n >> m;
    memset(dp, inf, sizeof(dp));
    for (int i = 1; i <= n;i++){
        for (int j = 1; j <= m;j++){
            char c;
            cin >> c;
            if(c=='.')
                mp[i][j] = 0;
            else if(c=='#')
                mp[i][j] = inf;
            else
                mp[i][j] = -1;
        }
    }
    if(mp[1][1]==inf){
        cout<<-1<<nl;
        return;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if(i==1&&j==1){
                dp[i][j]=0;
            }else{
                dp[i][j]=mp[i][j]+min(dp[i-1][j],dp[i][j-1])+1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<dp[i][j]<<" ";
        cout<<nl;
    }
    if(dp[n][m]<inf){
        cout << dp[n][m] << nl;
    }else{
        cout << -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

可恶的是 测试样例还过了

很明显错误的地方在于 状态并不是只能从上方或左边转移过来，而是可以从四个方向转移过来，直到我构造出了一组新的样例

5 5
...#.
..#..
.#...
...#.
####.
1
2
3
4
5
6

它可以往上绕着走（流泪 ）

然后就正经的来搜索吧：

结果 有个傻逼 非得写 DFS

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, m;
char mp[2020][2020];
bool vis[2020][2020];
int ans = inf;
int cnt;
void dfs(int x, int y){
    if(cnt>ans)return;
    if(x==n&&y==m){
        ans = min(ans, cnt);
        return;
    }
    for (int i = 0; i < 4;i++){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy]||mp[xx][yy]=='#')continue;
        vis[xx][yy] = true;
        if(mp[xx][yy]=='.'){
            cnt++;
        }
        dfs(xx, yy);
        if(mp[xx][yy]=='.'){
            cnt--;
        }
        vis[xx][yy] = false;
    }
}
void solve(){
    cin >> n >> m;
    for (int i = 1; i <= n;i++){
        for (int j = 1; j <= m;j++){
            cin >> mp[i][j];
        }
    }
    vis[1][1] = true;
    dfs(1, 1);
    if(ans!=inf)
        cout << ans << nl;
    else
        cout << -1 << nl;
}
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

不出意外的话，结果超时了，很明显递归深度太大啦，还没有剪枝

这不就体现到 BFS 的优势了嘛

int xx[] = {1, -1, 0, 0};
int yy[] = {0, 0, 1, -1};
int n, m;
char mp[2020][2020];//存图
int f[2020][2020];//记录当前位置的最优答案
queue<pii> q;
void bfs(int x,int y){
    q.push({x,y});
    f[x][y] = 0;
    while (!q.empty()){             //当队列不为空
        for (int i = 0; i < 4; i++){//四个方向
            int dx = q.front().first + xx[i];
            int dy = q.front().second + yy[i];
            if (dx <= n  && dy <= m  && dx > 0 && dy > 0 && mp[dx][dy] !='#' ){
                int num = 0;
                if(mp[dx][dy]=='.')
                    num++;
                if(f[dx][dy]>f[q.front().first][q.front().second]+num){
                    f[dx][dy]=f[q.front().first][q.front().second]+num;
                    q.push({dx, dy});//入队
                }
            }
        }
        q.pop();//出队
    }
}
void solve(){
    cin >> n >> m;
    memset(f, inf, sizeof(f));
    for (int i = 1; i <= n;i++){
        for (int j = 1; j <= m;j++){
            cin >> mp[i][j];
        }
    }
    bfs(1, 1);
    ans = f[n][m];
    if(ans!=inf)
        cout << ans << nl;
    else
        cout << -1 << nl;
}
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

所以这还不算是常规的最短路算法，这里就再写一个迪杰斯特拉（dijkstra）算法吧

模板：

// C++ Version
struct edge{
    int v, w;
};

struct node{
    int dis, u;
    bool operator>(const node &a) const { return dis > a.dis; }
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node>> q;

void dijkstra(int n, int s)
{
    memset(dis, 63, sizeof(dis));
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty())
    {
        int u = q.top().u;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto ed : e[u])
        {
            int v = ed.v, w = ed.w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}
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

正式题解：

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, m;
char mp[2020][2020];
int f[2020][2020];

struct node{
    int x,y,dis;
    bool operator<(const node &a) const {
        return dis > a.dis; 
    }
};
priority_queue<node> q;

void dijkstra(int x,int y,int dis){
    q.push({x, y, dis}); //起点的花费为0
    f[0][0] = 0;
    while(!q.empty()){
        auto t = q.top();
        q.pop();
        if(t.dis > f[t.x][t.y])
            continue;
        for (int i = 0; i < 4; i++){
            int xx = t.x + dx[i];
            int yy = t.y + dy[i];
            if(xx < 1 || xx > n || yy < 1 || yy > m)
                continue;
            if(mp[xx][yy] == '#')
                continue;
            int cost = t.dis + 1;
            if(mp[xx][yy] == '*')
                cost--;
            if (f[xx][yy] > cost){
                f[xx][yy] = cost;//更新从原点到xx，yy的距离
                q.push({xx, yy, cost});
            }
        }
    }
}
void solve(){
    cin >> n >> m;
    memset(f, inf, sizeof(f));
    for (int i = 1; i <= n;i++){
        for (int j = 1; j <= m;j++){
            cin >> mp[i][j];
        }
    }
    dijkstra(1, 1, 0);
    if (f[n][m] == inf)
        cout << -1 << nl;
    else
        cout << f[n][m] << nl;
}
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

---

H 安全区

解题思路：

解题代码：

---

I 密集

J 苹方树

解题思路：

解题代码：

---

K 试稥

L 固执