9,2训练复盘

T1斐波那契字符串

原题链接：4305. 斐波那契字符串 - AcWing题库

解题思路

挺简单的一道题，先求一段最大数小于等于n的最长斐波那契数列，然后开一个布尔数组记录那些数在斐波那契数列里面，最后根据布尔数组输出就行了

源代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1010;

int n;
int f[N];//斐波那契数列
bool ans[N];//记录那些数在数列里

int main()
{
    scanf("%d", &n);
    f[0] = 1;
    f[1] = 1;
    ans[1] = true;
    for(int i = 2; f[i - 1] <= n; i ++)
    {
        f[i] = f[i - 1] + f[i - 2];//求斐波那契数列
        ans[f[i]] = true;//记录
    }   
    for(int i = 1; i <= n; i ++)
    {
        if(ans[i])printf("O");
        else printf("o");
    }
    return 0;
} 

T2序列处理

原题链接：4306. 序列处理 - AcWing题库

解题思路

我们可以用数组记录每个数的个数，我们的目标就是让这个数组里面全部变成0和1,

我们先遍历数组，找到一个数量>1是数，在把这个数的数量-1，再找一个离得最近的空位也就是0，这个0和这个数的距离就是操作数，最后把这个0改成1，这样，循环往复直到，这个数只剩下一个

还有由于是往后找位置，数组要开大一些，要不然一直往后找空位可能会越界

源代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 6100;//记得开大一点！！！

int n;
int a[N];//原数组
int s[N];//这个数的数量
int cnt = 0;//答案

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        s[a[i]] ++;
    }
    for(int i = 1; i <= n; i ++)
    {
        while(s[i] > 1)//一直取数直到没有重复
        {
            s[i] --;//取走一个数原数就-1
            int j = i;
            while(s[j] > 0)//找空位
            {
                j ++;
                cnt ++;
            }
            s[j] ++;//填空位
        }
    }

    printf("%d", cnt);

    return 0;
}

T3数字重构

原题链接：4307. 数字重构 - AcWing题库

解题思路

我们可以用深搜的方式找答案，我们先优先在最大的一位上上找比b对于位置上小的尽量大的数，然后递归下一位，但是有时候取跟b对应位一样大没办法保证整个数比b小，如果后面的位没办法找到b对应位小的数就回溯到前面的位，直到前面的位能变小，让a比b小

如果a取的b的对应位上的数比b小，后面是数就可以从大到小取了，因为a肯定b小

源代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

#define LL long long

using namespace std;

const int N = 30;

LL A, B;
int a[N], b[N];//两个数拆成数组之后
int la, lb;//a, b的长度
int s[N];//a中各个数的数量
int ans[N];//答案

bool dfs(int x)//计算从ans的后x位（x~个位），并返回是否能够比b小
{
    bool find = false;//是否成功
    for(int i = 9; i >= 0; i --)//在第x位的数，从大到小
    {
        if(i == b[x] && s[i] > 0)//最大时与b[x]相等
        {
            s[i] --;
            ans[x] = i;
            int ne = dfs(x - 1);
            if(!ne && x != 1)//后面没办法做到比b小就回溯，用比b[x]小的数
            {
                s[i] ++;
                continue;
            }
            else//如果可以就返回1
            {
                find = true;
                return 1;
            }
        }
        else if(i < b[x] && s[i] > 0)//比b[x]小的情况
        {
            s[i] --;
            ans[x] = i;
            find = true;
            int p = 1;
            for(int j = 0; j <= 9; j ++)//由于第x位比b[x]小，后面的数可以按位数从大到小取了
            {
                while(s[j])
                {
                    s[j] --;
                    ans[p] = j;
                    p ++;
                } 
            }
            return 1;
        }
    } 
    if(!find)return 0;//如果不能bib小返回0
} 

int main()
{
    cin >> A >> B;

    for(int i = 1; A; i ++)//把整数按位拆成数组
    {
        a[i] = A % 10;
        A /= 10;
        la ++;
    }
    for(int i = 1; B; i ++)
    {
        b[i] = B % 10;
        B /= 10;
        lb ++;
    }   

    if(la < lb)//b比a位数多，a怎么改都比b小
    {
        sort(a + 1, a + 1 + la);//各位直接从大到小
        for(int i = la; i >= 1; i --)printf("%d", a[i]);
     } 
    else
    {
        for(int i = 1; i <= la; i ++)s[a[i]] ++;
        dfs(la);
        for(int i = la; i >= 1; i --)cout << ans[i];
    }

    return 0;
}

T4星空之夜

原题链接：257. 关押罪犯 - AcWing题库

解题思路

我们可以用连通块中各个点之间的距离之和作为一个连通块的特征，就可以通过这个来判断两个连通块的特征

连通块的判断我们可以利用floodfill判断，然后把连通块中的方格加入一个vector

如何对应字母呢，我们可以利用一个哈希表来对应字母，如果对应不上就加入新的键值对

源代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>

using namespace std;

const int N = 110;

struct block
{
    int x;
    int y;
};

int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};//方向
int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};
int n, m;
char ans[N][N];//记录输入，还可以记录一个点有没有访问过，还可以记录答案
map<double, char> ha;//记录字母编号的哈希表
vector<block> cluster;//记录连通块中的方块
int num = 0;
//int num;

double get_dist(block a, block b)//计算方块中的距离
{
    double x = a.x - b.x;
    double y = a.y - b.y;
    return sqrt(x * x + y * y);
}

double get_hash()//获取各个方格的距离之和
{
    double sum = 0;
    for(int i = 0; i < cluster.size(); i ++)
    {
        for(int j = i + 1; j < cluster.size(); j ++)
            sum += get_dist(cluster[i],cluster[j]);
    }
    return sum;
}

char get_id(double key)//获取的对应字母
{
    for(auto i = ha.begin(); i != ha.end(); i ++)
    {
        if(fabs(i->first - key) < 1e-6)//浮点数计算不能写==0，要写小于一个很小的数
        {
            return i->second;
        }
    }
    ha[key] = ha.size() + 'a';//建立新的键值对

    return ha[key];
}

void floodfill(int x, int y)//找连通块
{
    ans[x][y] = '0';
    cluster.push_back({x, y});
    for(int i = 0; i < 8; i ++)
    {
        int x2 = x + dx[i];
        int y2 = y + dy[i];
        if(x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && ans[x2][y2] == '1')
            floodfill(x2, y2);
    }
}

void fill(char c)//把连通块填上编号
{
    for(int i = 0; i < cluster.size(); i ++)
    {
        ans[cluster[i].x][cluster[i].y] = c;
    }
}

int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            cin >> ans[i][j];
        }
    }

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(ans[i][j] == '1')
            {
                floodfill(i, j);
                double key = get_hash();
                char id = get_id(key);
                fill(id);
                cluster.clear();//清空连通块
            }
        }
    }

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            cout << ans[i][j];
        }
        cout << endl;
    }

    return 0;
}

T5关押罪犯

原题链接：257. 关押罪犯 - AcWing题库

解题思路

我们可以用二分图做这道题，囚犯之间的怒气就是边权，我们用二分求最大值

那判断这个值是不是最大值limit的方法是，把这个点放在二分图一边的组里，如果在这个组里面有两个人之间的边权大于limit那么这个limit肯定不是最大值，如果一个点还不在图例，边权大于最大值就把它放在另外一半，看看能不能把全部都成功放到图里

源代码

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

using namespace std;

const int N = 20010;
const int M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int prison[N];

void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}

bool DFS(int u, int c, int limit)
{
    prison[u] = c;
    for(int i = h[u]; ~i; i = ne[i])
    {
        if(w[i] <= limit)continue;//小的边对最大值没有影响
        int j = e[i];
        if(prison[j])//如果在图内
        {
            if(prison[j] == c)return false;//在这个组内最大值就不是limit
        }
        else if(!DFS(j, 3 - c, limit))return false;//如果不在图内，要加在另外一个组里
    }
    return true;
}

bool check(int limit)
{
    memset(prison, 0, sizeof prison);

    for(int i = 1; i <= n; i ++)
    {
        if(prison[i] == 0)//不在图内
        {
            if(!DFS(i, 1, limit))return false;//能不能加进去
        }
    }

    return true;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while(m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);//加边
        add(a, b, c);
        add(b, a, c);
    }

    int l = 0, r = 1e9;
    //cout << l;
    while(l < r)//二分求最大值
    {
        int mid = (l + r) >> 1;
        if(check(mid))r = mid;
        else l = mid + 1;
    }

    cout << l;

    return 0;
}