Lruihao's Note

A. Adjacent Replacements

第一次打 cf 就做出一道这样的找规律的题，打到自闭。

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

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

int main(){
    int n,a[1001];
    cin>>n;
    int i;
    int flag=0;
    for(i=0;i<n;i++){
        cin>>a[i];
        if(!(a[i]&1)) a[i]--;
        if(!flag) {cout<<a[i];flag=1;}
        else cout<<" "<<a[i];
    }
    return 0;
}

迷宫问题

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 32323 Accepted: 18471

Description

定义一个二维数组：

int maze[5][5] = {
  0, 1, 0, 0, 0,
  0, 1, 0, 1, 0,
  0, 0, 0, 0, 0,
  0, 1, 1, 1, 0,
  0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的 1 表示墙壁，0 表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

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

题目描述

现在有一棵被 Samsara-Karma 染了 k 种颜色的树，每种颜色有着不同的价值，Applese 觉得 Samsara-Karma 染的太难看了，于是打算把整棵树重新染成同一种颜色，但是，由于一些奥妙重重的原因，每一次染色 Applese 可以选择两个有边相连的点，将其中一个染成另一个的颜色。而进行一次这样的操作需要付出两种颜色价值和的代价，
现在，Applese 的钱要用来买书 (game)，所以他想要最小化代价

百度知道 1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

Oil Deposits

翻译
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 41406 Accepted Submission(s): 23977

Problem Description

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

假设有一个 n 行 m 列的迷宫，每个单位要么是空地（用 1 表示）要么是障碍物（用 0 表示）.
如和找到从起点到终点的最短路径？利用 BFS 搜索，逐步计算出每个节点到起点的最短距离，
以及最短路径每个节点的前一个节点。最终将生成一颗以起点为根的 BFS 树。此时 BFS 可以求出任意一点到起点的距离。

那天晚上报名了没打，第二天早上打的，也只出了两题。

A. Game Shopping

 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<iostream>
using namespace std;

int main(){
    int n,m,s=0;
    cin>>n>>m;
    int i,j;
    int c[1000],a[1000];
    for(i=0;i<n;i++)
        cin>>c[i];
    for(i=0;i<m;i++)
        cin>>a[i];
    for(i=0,j=0;i<n;){
        if(j==m)
            break;
        if(c[i]<=a[j]){
            s++;
            j++;
            i++;
        }
        else i++;
    }
    if(i==n&&s==0)
        cout<<"0\n";
    else cout<<s<<endl;
    return 0;
}

B. Minimum Ternary String

 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

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

string s, ans;

int main(){
    cin >> s;
    int one = 0;
    for (int i = 0; i < s.size(); i++){
        if (s[i] == '0') ans += "0";
        if (s[i] == '1') one++;
        if (s[i] == '2') ans += "2";
    }
    bool flag = false;
    for (int i = 0; i < ans.size(); i++){
        if (ans[i] == '2' && !flag) flag = true, cout << string(one, '1');
        cout << ans[i];
    }
    if (!flag) cout << string(one, '1');
    return 0;
}

/*

100210

11222121

20

2001

020201

2012101

111

000

*/

广度优先搜索（BFS）

广度优先搜索在进一步遍历图中顶点之前，先访问当前顶点的所有邻接结点。访问了就入队。

深度优先搜索（DFS）

深度优先搜索在搜索过程中访问某个顶点后，需要递归地访问此顶点的所有未访问过的相邻顶点。

2018 年全国多校算法寒假训练营练习比赛（第二场）B(0 1 背包变化 特殊处理一个物品）
链接：https://www.nowcoder.com/acm/contest/74/B
来源：牛客网

题目描述

Taotao 的电脑带不动绝地求生，所以 taotao 只能去玩 pc 版的荒野行动了，和绝地求生一样，游戏人物本身可以携带一定重量 m 的物品，装备背包之后可以多携带 h（h 为 0 代表没有装备背包）重量的东西。玩了几天 taotao 发现了一个 BUG，当装备背包之后，如果可携带重量没有满，就可以拿一个任意重的东西（解释看样例）有一天 taotao 空降到了一个奇怪的岛上，岛上有 n 件装备，每个装备都有重量 Wi 和威力值 Vi, 但 taotao 不认识这些装备，所以他来求助你，挑选威力最大的装备，帮助他吃鸡。

时间限制：C/C++ 1 秒，其他语言 2 秒
空间限制：C/C++ 262144K，其他语言 524288K
64bit IO Format: %lld

题目描述

有一个长度为 n 的序列 a，已知 a[1]=a[n]=1，且对于 2 <= x <= n，a[x] / a[x-1] 是以下三个数字之一 [ 1，-2，0.5 ], 问有多少种不同的序列满足题意。
两个序列不同当且仅当它们有至少一个位置上的数字不同，序列 a 可以为任何实数。