牛客寒假算法基础集训营4

发表于 更新于 分类于
本文字数： 15k 阅读时长 ≈ 13 分钟

A.Applese 的取石子游戏

题目描述：

Applese 和 Bpplese 在玩取石子游戏，规则如下：
一共有偶数堆石子排成一排，每堆石子的个数为 $ a_i $。两个人轮流取石子，Applese先手。每次取石子只能取最左一堆或最右一堆，且必须取完。最后取得的石子多者获胜。假设双方都足够聪明，最后谁能够获胜呢？

输入描述:

第一行是一个正偶数 n，表示石子的堆数。
第二行是 n 个正整数 $ a_1,a_2\cdots,a_n $，表示每堆石子的个数。

输出描述:

输出一个字符串“Applese”或“Bpplese”，表示胜者的名字。

输入

1
2
4
2 3 3 3

输出

1
Applese

备注:

$ 2 \leq n \leq 10^5 $
$ 1 \leq a_i \leq 10^5 $
$\sum a_i $ 为奇数

思路：

签道题！题解：TAG：脑洞，博弈
这是一道经典的博弈问题。
可以使用动态规划来解决：dp[i][j]表示进行了 i 轮，从前面取走了 j 个时候的最大收益。这个老师上课的时候教过。
实际上，由于题面中的两个限制条件，可以得出先手有必胜策略：即选择所有的奇数项或者偶数项。如果奇数项的和较大，先手就取第一个，这样每一次轮到后手都只能取到偶数项。反之亦然同理。
因此，作为本场比赛的签到题之一，直接输出Applese即可通过。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, x;
int main() {
    while(cin >> n) {
        while(n--) cin >> x;
        cout << "Applese" << endl;
    }
    return 0;
}

B.Applese 走方格

题目描述：

精通程序设计的 Applese 又写了一个游戏。在这个游戏中，它位于一个 n 行 m 列的方阵中的左上角（坐标为 $ (0, 0) $，行的序号为 $ 0 \sim n−1 $，列的序号为 $ 0 \sim m−1)$。
现在它想不重复地走过所有格子(除了起点)，最后回到左上角的一个方案。
每次只能往上下左右其中一个方向走一格。

输入描述:

仅一行两个整数 n 和 m，表示方阵的大小。保证大于 $ 1×1 $。

输出描述:

如果存在方案，则输出一行操作，包含”L”、”R”、”U”、”D”，分别表示左、右、上、下。如果有多种方案，输出任意一种即可。如果没有方案，则在一行中输出”-1”。

输入

1
2
3
2 2

2 3

输出

1
2
3
RDLU

RRDLLU

备注:

$ 1 \leq n, m \leq 10 $.

思路：

做完签道题之后就开这题，一看数据很小，心里美滋滋，dfs深搜搞一搞，不过写丑了，输入 $ 8, 8 $ 之后就跑不出结果来QWQ，然后努力尝试着优化（未果），打标记发现递归在某一处进入死胡同，一直在那几个状态来回转移QWQ…..经过几个小时地挣扎之后，其实早已想到可以不用递归来解决，不过一直觉得可能是哪里没剪枝，相信只要设置一下条件……这是所有比赛以来第一次大胆尝试着用dfs写，回想当初学递归算法的时候，其实我的心里一直是抗拒的，日后的缺少训练导致现在比赛中不能轻易地AC掉某些很简单的题目，譬如本场比赛的 $ I $ 题QWQ，幸亏在队友的提示下，修改了一处（非递归）代码就AC了！感谢大佬！赛后看了一下用dfsAC的代码，果然是我写搓了，条件的构造真的太重要了！！！重新补了一下递归和模拟版（找一条固定路径）的解法。总结了一下，要多尝试，多思考，多做题！贴一下在比赛中自己缝缝补补的dfs：state：TLE！QWQ

TLE代码：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
int n,m; char ans[maxn];
bool flag, vis[20][20];
int dir[4][2] ={{1,0},{-1,0},{0,-1},{0,1}};//下，上，左，右
bool check(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >=m) return false;
    return true;
}
void dfs(int x,int y, int cnt, int now) {
    if(flag) return;
    if(!check(x,y))return;
    if(x == 0 && y == 0) {
        if(now +1 == n*m){
            flag = true;
            cout << ans << endl;
            return;
        }
        else vis[x][y]=false,now-=1; //到原点之后，若还未访问完其他坐标点，则当前已访问的个数减1
    }
    for(int i = 0; i < 4; ++i){
        int dx = x + dir[i][0], dy = y + dir[i][1];
        if(check(dx,dy)&&!vis[dx][dy]) {
            vis[dx][dy]=true; //先标记为true
            if(i==0) ans[cnt]='D'; //下
            else if(i==1)ans[cnt]= 'U'; //上
            else if(i==2)ans[cnt] ='L'; //左
            else ans[cnt] = 'R'; //右
            dfs(dx,dy,cnt+1,now+1);
            vis[dx][dy] = false; //返回时标记为false
        }
    }
}
int main() {
    while(cin >> n >> m) {
        flag = false;
        memset(ans, '\0', sizeof(ans));
        memset(vis,false,sizeof(vis));
        dfs(0, 0, 0, 0);
        if(!flag) puts("-1");
    }
    return 0;
}

AC代码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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 15;
int n, m; bool flag, vis[maxn][maxn];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};//下，右，上，左
char fuck[5] = "DRUL";
bool check(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >= m) return false;
    return true;
}
void dfs(int x, int y, string ans) { //坐标：(x, y)，答案：字符串ans
    if(flag) return;
    if(x == 0 && y == 0 && n * m == (int)ans.size()) {
        flag = true; cout << ans << endl; return;
    }
    for(int i = 0; i < 4; ++i) {
        int dx = x + dir[i][0], dy = y + dir[i][1];
        if(check(dx,dy) && !vis[dx][dy]) {
            vis[dx][dy] = true; //先尝试着访问该坐标点
            dfs(dx, dy, ans + fuck[i]);
            vis[dx][dy] = false; //回溯时标记为未访问状态
        }
    }
}
int main() {
    while(cin >> n >> m) {
        flag = false;
        if(n * m % 2) { puts("-1");continue;} //剪枝
        memset(vis, false, sizeof(vis));
        dfs(0, 0, "");
        if(!flag) puts("-1");
    }
    return 0;
}

AC代码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
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n, m, x, y;
int main() {
    while(~scanf("%d%d", &n, &m)) {
        if(n == 1 && m == 2) {puts("RL"); continue;} //2种特殊情况
        if(n == 2 && m == 1) {puts("DU"); continue;}
        if((n * m % 2) || (n == 1 || m == 1)) { puts("-1"); continue;} //剪枝
        if(n % 2 == 0) { //按偶数行构造固定路径
            for(int i = 2; i <= n; ++i) printf("D");
            printf("R");
            for(int i = n; i >= 1; --i) {
                if(i & 1) {
                    for(int j = m - 1; j >= 2; --j) printf("L");
                    if(i != 1) printf("U");
                    else printf("L");
                } else {
                    for(int j = 2; j <= m - 1; ++j) printf("R");
                    printf("U");
                }
            }
        }else if(m % 2 == 0) { //否则按偶数列构造固定路径
            for(int j = 2; j <= m; ++j) printf("R");
            printf("D");
            for(int j = m; j >= 1; --j) {
                if(j & 1) {
                    for(int i = n - 1; i >= 2; --i) printf("U");
                    if(j != 1) printf("L");
                    else printf("U");
                }else {
                    for(int i = 2; i <= n - 1; ++i) printf("D");
                    printf("L");
                }
            }
        }
        puts("");
    }
    return 0;
}

C.Applese 走迷宫

题目描述：

精通程序设计的 Applese 双写了一个游戏。
在这个游戏中，它被困在了一个 n×m 的迷宫中，它想要逃出这个迷宫。
在迷宫中，有一些方格是水池，只有当 Applese 处于水属性的时候才可以通过；有一些方格是岩浆，只有当 Applese 是火属性的时候可以通过；有一些方格是墙壁，无论如何都无法通过；另一些格子是空地（包括起点和终点），可以自由通过。
在一些空地上有神秘道具可以让 Applese 转换自己的属性（从水属性变为火属性或从火属性变为水属性，需要一个单位的时间）。
已知 Applese 在一个单位的时间内可以朝四个方向行走一格，且开始处于水属性，位于空地的道具拾取后只能在该处立即使用（或者不使用），且可以多次使用。求它走出迷宫需要的最少时间。

输入描述:

第一行两个正整数 n, m 表示迷宫的大小。
接下来 n 行，每行长度为 m 的字符串。描述地图。
其中 ‘S’ 表示起点，’T’ 表示终点，’.’ 表示空地，’w’表示岩浆，’~’表示水池，’@’ 表示道具，’#’表示障碍。
保证地图中的起点和终点只有一个，道具都位于空地。

输出描述:

输出一个整数，表示 Applese 走出迷宫的最短时间。特别地，如果 Applese 走不出迷宫，输出 “-1”。

输入

1
2
3
4
5
6
5 5
.w@..
.S#..
~w#..
.w..~
@w.~T

输出

1
18

备注：

$ 1 \leq n, m \leq 100 $.

思路：

典型的bfs求最短路。由于题目多加了一个状态：水、火，故求最短路也要多加一维，0：水，1：火。注意一个坑：某坐标点有道具，若有必要使用道具改变属性，则需在原地花费一个单位时间进行转化。

AC代码：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 105;
const int inf = 0x3f3f3f3f;
int n, m, sx, sy, tx, ty, ans, dist[maxn][maxn][2], dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char mp[maxn][maxn];
struct node{
    int x, y, state;
    node(int _x, int _y, int _state) : x(_x), y(_y), state(_state) {}
};
bool check(int x, int y) {
    if(x < 0 || y < 0 || x >= n || y >= m) return false;
    return true;
}
queue<node> que;
void bfs(int x, int y, int state) {
    while(!que.empty()) que.pop();
    que.push(node(x, y, state));
    dist[x][y][0] = 0;
    while(!que.empty()) {
        node nod = que.front(); que.pop();
        for(int i = 0; i < 4; ++i) {
            int dx = nod.x + dir[i][0], dy = nod.y + dir[i][1];
            if(check(dx, dy) && mp[dx][dy] != '#') {
                if(!nod.state && mp[dx][dy] == 'w') continue;
                if(nod.state && mp[dx][dy] == '~') continue;
                if(dist[dx][dy][nod.state] > dist[nod.x][nod.y][nod.state] + 1) {
                    dist[dx][dy][nod.state] = dist[nod.x][nod.y][nod.state] + 1;
                    que.push(node(dx, dy, nod.state));
                }
                if(mp[dx][dy] == '@' && dist[dx][dy][nod.state ^ 1] > dist[dx][dy][nod.state] + 1) { //若当前是道具，并且状态改变可以使得从起点到达该坐标点的最短路更短，则应该更新状态改变后对应的最短路，同时当前坐标点入队
                    dist[dx][dy][nod.state ^ 1] = dist[dx][dy][nod.state] + 1;
                    que.push(node(dx, dy, nod.state ^ 1));
                }
            }
        }
    }
}
int main() {
    while(cin >> n >> m) {
        for(int i = 0; i < n; ++i) cin >> mp[i];
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(mp[i][j] == 'S') sx = i, sy = j;
                else if(mp[i][j] == 'T') tx = i, ty = j;
            }
        }
        memset(dist, 0x3f, sizeof(dist));
        bfs(sx, sy, 0);
        ans = min(dist[tx][ty][0], dist[tx][ty][1]);
        if(ans == inf) cout << -1 << endl;
        else cout << ans << endl;
    }
    return 0;
}

E.Applese 涂颜色

题目描述：

精通程序设计的 Applese 叕写了一个游戏。
在这个游戏中，有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大，你需要将答案对 $ 10^9 + 7 $ 取模。

输入描述:

仅一行两个正整数 n, m，表示方阵的大小。

输出描述:

输出一个正整数，表示方案数对 $10^9 + 7 $ 取模。

输入

1
2
3
1 1

2 2

输出

1
2
3
2

4

备注：

$ 1 \leq n,m \leq 10^{100000} $.

思路：

由于左右相邻两格的颜色不能相同，那么无论m是多少，每一行只有两种确定的填充状态，而每一行的状态又可以互相组合，所以答案就是 $ 2^n \% (10^9 + 7) $。由于n超大，并且2 与大质数 $ 1e9 + 7 $ 互质，所以要用扩展欧拉定理对指数降幂再用快速幂求解，公式： $ a ^ b \equiv a^{ b \% \varphi(p)} \;(mod \; p), \gcd(a, p) = 1 $。感想：赛后看了一下18级的通过率，本以为榜单中这题应该是全部绿色的，没想到才过了一半QWQ，看来有待加强训练。比赛前一整天就在机房里给ACM协会成员讲了数论四大定理（包括公式的由来及证明），次日比赛就用到了。从前几场比赛来看，都涉及了一些数论知识，日后要加强数学和思维方面的训练，ACM数学和思维真的很重要！！！

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
const LL mod = 1e9+7;
LL k, phi; string s1,s2;
LL quick_mod(LL a, LL b) {
    LL res = 1LL;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int main() {
    while(cin >> s1 >> s2){
        k = 0LL;
        phi = mod - 1LL;
        for(int i = 0; s1[i]; ++i) k = (k * 10 + s1[i] - '0') % phi;
        cout << quick_mod(2LL, k) << endl;
    }
    return 0;
}

F. Applese 的QQ群

题目描述：

Applese 有一个QQ群。在这个群中，大家互相请教问题。如 b 向 a 请教过问题，就把 a 叫做是 b 的”老板”。这样一个群中就会有很多老板。
同时规定：如果 a 是 b 的老板，b 是 c 的老板，那么 a 也是 c 的老板。
为了不破坏群里面和谐交流的氛围，Applese 定了一个群规：不允许出现 a 既是 b 的老板， b 又是 a 的老板。
你需要帮助 Applese 判断大家是否遵守了群规。

输入描述:

第一行两个整数 n, m，表示群里的人数以及请教问题的数量。
接下来 m 行，每行两个整数 a, b，表示 a 是 b 的”老板”，即 b 向 a 请教了一个问题。
注：无论是否违反了群规，a 都会成为 b 的老板。

输出描述:

对于每次提问，输出一行”Yes”表示大家都遵守了群规，反之输出”No”。

输入

1
2
3
4
5
4 4
1 2
2 3
3 1
1 4

输出

1
2
3
4
Yes
Yes
No
No

备注：

$ 1 \leq n \leq 10^5 $
$ 1 \leq m \leq 2 \cdot 10^5 $
$ 1 \leq a, b \leq n $

思路：

一开始想用并查集，但样例中第四个输出是”No”，并且由于并查集是无向的，即已归并集合中元素之间的关系不能确定，所以用并查集的做法肯定是错的！显然这题要判断是否存在环，若存在环，即违反了群规，则之后每一次提问的输出都是”No”。正解：dfs或拓扑排序判环。由于不存在撤销操作，可以发现答案一定是一连串的Yes后再有一连串的No，所以只需二分最后一个Yes的位置即可。注意：dfs前应该建一条从b指向a老板（因为老板可能有很多个属下，若这样建图则多出了遍历儿子的时间，交一发超时，相反属下最多只有一个老板），然后dfs时，一路沿着儿子的父亲往上走，若找到已和当前相同的节点，则返回true，否则返回false。

AC代码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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n, m, a, b; bool flag;
vector<int> vec[maxn];
bool dfs(int son, int per) {
    for(size_t i = 0; i < vec[son].size(); ++i) {
        if(vec[son][i] == per) return true; //若son的父亲是per，则返回true，表示找到环
        else if(dfs(vec[son][i], per)) return true; //否则若son的父亲的父亲......和per相同，则返回true，也表示找到环
    }
    return false; //否则返回false
}
int main() {
    while(~scanf("%d%d", &n, &m)) {
        for(int i = 0; i <= n; ++i) vec[i].clear();
        flag = false;
        while(m--) {
            scanf("%d%d", &a, &b);
            if(flag || dfs(a, b)) { //从节点a去找，若找到其父亲为b，说明存在环
                flag = true;
                printf("No\n");
            }
            else printf("Yes\n"), vec[b].push_back(a); //建一条从属下b指向老板a的边
        }
    }
    return 0;
}

AC代码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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n, m, a, b, lt, rt, mid, x, y, cnt, indeg[maxn];
struct EDGE{
    int from, to;
    EDGE(int _u, int _v) : from(_u), to(_v) {}
};
queue<int> que;
vector<int> vec[maxn];
vector<EDGE> edges;
bool check(int up) {
    while(!que.empty()) que.pop();
    memset(indeg, 0, sizeof(indeg)); cnt = 0;
    for(int i = 0; i <= n; ++i) vec[i].clear();
    for(int i = 0; i <= up; ++i) vec[edges[i].from].push_back(edges[i].to), ++indeg[edges[i].to];
    for(int i = 1; i <= n; ++i)
        if(!indeg[i]) que.push(i);
    while(!que.empty()) {
        x = que.front(), que.pop(), cnt++;
        for(size_t j = 0; j < vec[x].size(); ++j)
            if(--indeg[vec[x][j]] == 0) que.push(vec[x][j]);
    }
    return cnt == n; //若拓扑点的个数cnt与n相同，则说明当前图中不存在环
}
int main() {
    while(~scanf("%d%d", &n, &m)) {
        edges.clear();
        for(int i = 1; i <= m; ++i) {
            scanf("%d%d", &a, &b);
            edges.push_back(EDGE(a, b));
        }
        lt = 0, rt = m - 1;
        while(lt <= rt) { //跳出时是 ans = lt - 1
            mid = (lt + rt) >> 1;
            if(check(mid)) lt = mid + 1;
            else rt = mid - 1;
        }
        for(int i = 0; i < lt; ++i) printf("Yes\n"); 
        for(int i = lt; i < m; ++i) printf("No\n");
    }
    return 0;
}

G.Applese 的毒气炸弹

题目描述：

众所周知，Applese 是个很强的选手，它的化学一定很好。今天他又AK了一套题觉得很无聊，于是想做个毒气炸弹玩。毒气炸弹需要 k 种不同类型元素构成，Applese一共有 n 瓶含有这些元素的试剂。
已知元素混合遵循 m 条规律，每一条规律都可以用 “x y c” 描述。
表示将第 x 瓶试剂混入第 y 瓶试剂或者把第 y 瓶试剂混入第 x 瓶试剂，需要消耗 c 的脑力。特别地，除了这 m 条规律外，Applese 可以将任意两瓶相同元素的试剂混合，且不需要消耗脑力。
Applese 想要配出毒气炸弹，就需要使 S 中含有 $ 1 \sim k $ 这 k 种元素。它想知道自己最少花费多少脑力可以把毒气炸弹做出来。

输入描述:

第一行为三个整数 n, m, k 表示 Applese 拥有的试剂的数量，混合规律的数量和所需的元素种类数。
第二行为 n 个整数 $ a_1,a_2,\cdots,a_n $，分别表示每一瓶试剂的元素类型。
接下来m行，每行三个整数 x, y, c，含义如题目描述中所述。不保证 x, y的试剂种类不同。

输出描述:

输出一个正整数表示最小的耗费脑力。特别地，如果无法合成出毒气炸弹，输出 “-1”。

输入

1
2
3
4
5
6
7
8
9
10
6 8 2
1 1 1 2 2 2
1 2 1
2 3 2
1 3 3
3 4 6
4 5 1
4 6 3
5 6 2
1 6 2

输出

1
2

备注:

$ 1 \leq n,k,m \leq 10^5 $
$ 1 \leq x, y \leq n, x \neq y $
$ 1 \leq c \leq 10^9 $

思路：

把相同元素类型的试剂看作一个节点，然后用克鲁斯卡尔求刚好由k个点（k种元素配置毒气炸弹）组成的最小生成树，若不能找到，则输出-1。这题真的好简单QWQ。

AC代码：

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>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
int n, m, k, x, y, z, cnt, a[maxn], fa[maxn]; LL ans;
struct EDGE{int from, to, val;}edge[maxn];
bool cmp(EDGE gax, EDGE gay) {return gax.val < gay.val;}
int find_fa(int x) {
    return fa[x] == x ? x : fa[x] = find_fa(fa[x]);
}
void unite(int u, int v, int w) {
    u = find_fa(u), v = find_fa(v);
    if(u != v) fa[u] = v, ans += w, cnt++;
}
void kurskal() {
    for(int i = 0; i <= n; ++i) fa[i] = i;
    ans = 0LL; cnt = 1;
    sort(edge, edge + m, cmp);
    for(int i = 0; i < m; ++i) {
        unite(edge[i].from, edge[i].to, edge[i].val);
        if(cnt == k) break; //只需选择k种元素
    }
    if(cnt == k) cout << ans << endl;
    else cout << -1 << endl;
}
int main() {
    while(cin >> n >> m >> k) {
        ans = 0;
        for(int i = 1; i <= n; ++i) cin >> a[i]; // 注意：试剂瓶编号为1~n
        for(int i = 0; i < m; ++i) {
            cin >> x >> y >> z;
            edge[i].from = a[x], edge[i].to = a[y], edge[i].val = z; //建边：元素到元素的关系
        }
        kurskal();
    }
    return 0;
}

I.Applese 的回文串

题目描述：

自从 Applese 学会了字符串之后，精通各种字符串算法，比如……判断一个字符串是不是回文串。
这样的题目未免让它觉得太无聊，于是它想到了一个新的问题。如何判断一个字符串在任意位置(包括最前面和最后面)插入一个字符后能不能构成一个回文串？

输入描述:

仅一行，为一个由字母和数字组成的字符串 s。

输出描述:

如果在插入一个字符之后可以构成回文串，则输出”Yes”, 否则输出”No”。

输入

1
2
3
applese

java

输出

1
2
3
No

Yes

备注：

$ |s| \leq 10^5 $.

思路：

dfs简单过QWQ！题目要求插入一个字符后能否构成一个回文串，换个角度也就是删除任意一个字符能否构成一个回文串。因为删除的字符只有一个，且当删除字符的个数大于1，很快被return掉，所以用dfs可以简单快速求解！以后要多学学dfs的技能姿势QWQ！
题解：可以认为插入和删除是等价的操作。想到这一点，这题就会好做很多。如果这个串本身就是回文串，答案一定是Yes。否则我们只需要考虑串中对称的位置不相等的两个字符，分别尝试把它们删掉后判断一下是不是回文的就行了。
总结：的确，我们只需判断三次就能确定答案，因为第一个不同的地方有两种情况，尝试着删除第一个不同位置的两个字符中任意一个，若删后能构成一个回文串，显然是满足条件的，否则肯定不能构成一个回文串。好一个思维题！

AC代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
char str[maxn]; bool flag;
void dfs(int st, int ed, int cnt) {
    if(flag || cnt > 1) return; // 若已找到，或者要删除的字符个数大于1，则直接返回
    if(st >= ed) {flag = true; return;} //注意是大于等于，
    if(str[st] != str[ed]) {
        dfs(st + 1, ed, cnt + 1); //尝试着删除左指针指向的字符，删除个数加1
        dfs(st, ed - 1, cnt + 1); //尝试着删除右指针指向的字符，删除个数加1
    }else dfs(st + 1, ed - 1, cnt); //否则继续往两边搜
}
int main() {
    while(cin >> str) {
        flag = false;
        dfs(0, strlen(str) - 1, 0);
        puts(flag ? "Yes" : "No");
    }
    return 0;
}

AC代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
string s1, s2, s3; int diff;
int check(string pat) {
    for(int i = 0, j = pat.size() - 1; i < j; ++i, --j)
        if(pat[i] != pat[j]) return i;
    return -1;
}
int main() {
    while(cin >> s1) {
        s2 = s3 = s1;
        diff = check(s1); 
        if(diff == -1) {cout << "Yes" << endl; continue;} 
        s2 = s2.erase(diff, 1); 
        s3 = s3.erase(s1.size() - diff - 1, 1);
        if(check(s2) == -1 || check(s3) == -1) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

J.Applese 的减肥计划

题目描述:

Applese 最近又长胖了，于是它打算减肥——练习举重。
他在举重的时候用两只手往不同方向用力，从而把杠铃举起来。
已知 Applese 两只手分别产生的力的大小，以及它们之间的夹角，试求两力合力的大小。

输入描述:

仅一行三个整数 $ f_1,f_2,a$，分别表示两只手产生的力的大小以及它们之间的夹角。

输出描述:

输出一个实数表示两力合力的大小，要求相对误差或绝对误差不超过 $ 10^{-6} $。
严格来讲，如果你的答案是 a，而标准答案是 b，那么当 $ \frac{|a-b|}{max{1,|b|}} \leq 10^{-6} $ 时，你的答案会被认为是正确的。

输入

1
2
3
6 8 90

10 10 60

输出

1
2
3
10.0000000000

17.3205080757

备注:

$ 1 \leq f_1,f_2 \leq 100 $
$ 0 \leq a \leq 180 $

思路：

签道题！根据余弦定理：$ cosA = \frac{b^2 + c^2 - a^2}{2bc} $ 可得 $ F = \sqrt{f_1^2 + f_2^2 + 2f_1 f_2 cos \alpha }$.
注意 $ \alpha $ 是弧度制，即 $1^{\circ} = \frac{\pi }{180} rad $。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+5;
const double pi = acos(-1.0);
double f1, f2, a;
int main() {
    while(cin >> f1 >> f2 >> a){
        cout << setiosflags(ios::fixed) << setprecision(10) << sqrt(f1 * f1 + f2 * f2 + 2.0 * f1 * f2 * cos(a * pi / 180.0)) << endl;
    }
    return 0;
}
0%