$\Huge\color{DeepSkyBlue}{第 40 周周赛题解}$

斐波那契字符串

打表是个好方法

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>

using namespace std;

const int N = 1010;

bool st[N];
int n, a[N];

void init(){
    st[1] = st[2] = st[3] = st[5] = st[8] = st[13] = st[21] = st[34] = st[55] = st[89] = st[144] = st[233] = st[377] = st[610] = st[987] = true;
}

int main(){

    // freopen("T1斐波那契字符串.in", "r", stdin);
    // freopen("T1斐波那契字符串.out", "w", stdout);

    init();
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ){
        if (st[i]) printf("O");
        else printf("o");
    }

    // fclose(stdin);
    // fclose(stdout);
    return 0;
}

序列处理

先排序成为单调不下降序列

贪心思想，因为是不可以变小的

a[i] = max(a[i - 1] + 1, a[i]);

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int a[N], n;

int main(){

    //freopen("T2序列处理.in", "r", stdin);
    //freopen("T2序列处理.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    sort (a + 1, a + n + 1);

    int sum = 0;
    for (int i = 1; i <= n; i ++ ){
        if (i == 1) continue;

        int k = a[i];

        a[i] = max(a[i - 1] + 1, a[i]);
        sum += a[i] - k;
    }

    cout << sum << endl;

    //fclose(stdin);
    //fclose(stdout);

    return 0;
}

数字重构

bubble_sort + 排序搞定

• 一种答案情况是$a.size() < b.size()$, 不上升排列即可
• 第二种情况就是$a.size() == b.size()$, 可以先从 $i$ 开始，往后面枚举每一个都要判断一个大小, 因为有一个很可恶的样例

102391019
491010301

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main(){

    string s1, s2;
    cin >> s1 >> s2;
    sort(s1.begin(), s1.end());

    if (s1.size() < s2.size()) {  
        reverse(s1.begin(), s1.end());
        cout << s1 << endl;
    } else {
        int n = s1.size();
        for (int i = 0; i < n; i ++ ){
            for (int j = i + 1; j < n; j ++ ){
                string tmp = s1;
                swap(tmp[i], tmp[j]);  
                if (tmp >= s1 && tmp <= s2) s1 = tmp;
            }
        }
        cout << s1 << endl;
    }
    return 0;
}

星空之夜

1. 搜索图，直到找到$1$关键字，存入坐标数组$v$和$dfs$递归搜索附近的星星
2. 计算这个星群内部星星的所有距离，即这个星群的内部距离
3. 判断距离是否存在过这里用$double$型数组来判断

4. 填图，填上该星群对应的字母$c$

5. • • 同时，要注意危险的宏定义问题，他是不会报错的

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;
const double eps = 1e-6;

int n, m, top;
PII q[N * N];
char g[N][N];

double get_dist(PII a, PII b){
    double dx = a.x - b.x;
    double dy = a.y - b.y;

    return sqrt(dx * dx + dy * dy);
}

double get_hash(){
    double sum = 0;

    for (int i = 0; i < top; i ++ )
        for (int j = i + 1; j < top; j ++ )
            sum += get_dist(q[i], q[j]);

    return sum;
}

char get_id(double key){
    static double hash[30];
    static int id = 0;
    for (int i = 0; i < id; i ++ ) // 原本就有
        if (fabs(hash[i] - key) < eps)
            return i + 'a';

    hash[id ++ ] = key;
    return id - 1 + 'a'; // 新的点
}

void dfs(int a, int b){
    q[top ++ ] = {a, b};
    g[a][b] = '0';

    for (int i = a - 1; i <= a + 1; i ++ )
        for (int j = b - 1; j <= b + 1; j ++ ){
            if (i == a && j == b) continue;

            if (i >= 0 && j >= 0 && i < n && j < m && g[i][j] == '1') dfs(i, j);
        }
}

int main(){

    scanf("%d%d", &m, &n);
    for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == '1'){
                top = 0;

                dfs(i, j);
                char c = get_id(get_hash());

                for (int k = 0; k < top; k ++ )
                    g[q[k].x][q[k].y] = c;
            }

    for (int i = 0; i < n; i ++ ) printf("%s\n", g[i]);

    return 0;
}

关押罪犯

• 可以用并查集求解，注意数组的大小，我就是因为数组开小了导致没有 AC

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200010;

int m, n, k, t, p[N];

struct Father{ // 设置结构体
    int x, y, val;
}a[N];

bool cmp(Father a, Father b){ // 定义新运算
    return a.val > b.val;
}

inline int find(int x){ // 板子 + 内联函数
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){

    // freopen("T5关押罪犯.in", "r", stdin);
    // freopen("T5关押罪犯.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n * 2; i ++ ) p[i] = i;
    for (int i = 1; i <= m; i ++ )
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].val);

    sort(a + 1, a + m + 1, cmp);
    for (int i = 1; i <= m; i ++ ){
        int x = a[i].x, y = a[i].y, val = a[i].val;
        int dadx = find(x), dady = find(y);
        if(dadx == dady){ // 如果在同一监狱里就会发生矛盾
            printf("%d\n",val);
            return 0;
        }
        p[dadx] = find(y + n); // x和y放入两个不同阵营，则x的敌人是y的朋友
        p[dady] = find(x + n); // y的敌人是x的朋友
    }
    puts("0");

    // fclose(stdin);
    // fclose(stdout);
    return 0;
}