头像

沙漠绿洲


访客:2437

离线:3小时前


活动打卡代码 AcWing 419. FBI树

#include <iostream>
using namespace std;
int n;

void work(string& ss){
    int cnt_0 = 0, cnt_1 = 0;
    for(char c : ss){
        if(c == '0') ++ cnt_0;
        else ++ cnt_1;
    }
    if(cnt_0 && cnt_1) cout << 'F';
    else if(cnt_0) cout << 'B';
    else cout << 'I';
}

void dfs(string s){
    if(s.size() > 1){
        dfs(s.substr(0, s.size() >> 1));
        dfs(s.substr(s.size() >> 1));
    }
    work(s) ; // 后序遍历
}

int main()
{
    cin >> n;
    string s;
    cin >> s;
    dfs(s);
    return 0;
}



C++ 代码

#include <iostream>
using namespace std;
int n;

void work(string& ss){
    int cnt_0 = 0, cnt_1 = 0;
    for(char c : ss){
        if(c == '0') ++ cnt_0;
        else ++ cnt_1;
    }
    if(cnt_0 && cnt_1) cout << 'F';
    else if(cnt_0) cout << 'B';
    else cout << 'I';
}

void dfs(string s){
    if(s.size() > 1){
        dfs(s.substr(0, s.size() >> 1));
        dfs(s.substr(s.size() >> 1));
    }
    work(s) ; // 后序遍历
}

int main()
{
    cin >> n;
    string s;
    cin >> s;
    dfs(s);
    return 0;
}



C++ 代码

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N];
int n, maxm = -1;

bool check(int ans){ 
    for(int i = 1; i <= n; ++ i){
        ans += (ans - h[i]);
        if(ans < 0) return false;
        if(ans > maxm) return true;
    }
    return true;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &h[i]);
        maxm = max(maxm, h[i]);
    } 
    int l = 0, r = maxm;
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}



C++ 代码

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
using PII = pair<int, int>;
const int N = 5010;
PII a[N];
int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; ++ i){
        cin >> a[i].second >> a[i].first;
    } 
    sort(a, a + n, [](const PII& p1, const PII& p2){
        return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);});
    int cnt = floor(1.5 * m) - 1;
    int it = cnt;
    while(a[it].first == a[cnt].first) ++ it;
    printf("%d %d\n", a[cnt].first, it);
    for(int i = 0; i < it; ++ i)
        printf("%d %d\n", a[i].second, a[i].first);

    return 0;
}



多源bfs

C++ 代码

#include <iostream>
#include <queue>
using namespace std;
using PII = pair<int, int>;
int n, m;
queue<PII> q;
vector<vector<char>> d;  // 原矩阵

int dxy[5] = {0, 1, 0, -1, 0};

int bfs(int cnt_1){
    int res = 0, cnt = 0;
    while(!q.empty()){
        int len = q.size();
        while(len --){
            PII t = q.front();
            q.pop();
            for(int i = 0; i < 4; ++ i){
                int x = t.first + dxy[i];
                int y = t.second + dxy[i + 1];
                if(x >= 0 && x < n && y >= 0 && y < m && d[x][y] == '1')
                {
                    d[x][y] = '2';
                    ++ cnt;
                    q.push({x, y});
                }
            }
        }
        ++ res;
    }
    if(cnt == cnt_1) return res - 1;
    return -1;
}

int main()
{
    string s;
    while(getline(cin, s)){
        vector<char> ans;
        for(int i = 0; i < s.size(); i += 2)
            ans.push_back(s[i]);
        d.emplace_back(ans);
    }
    n = d.size(), m = d[0].size();

    int cnt_1 = 0; // 产品经理的数量
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
        {
            if(d[i][j] == '2'){
                q.push({i, j});
            }else if(d[i][j] == '1')
                ++ cnt_1; 
        }

    cout << bfs(cnt_1) << endl;

    return 0;
}



C++ 代码

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<vector<int>> d;

int dfs(int i, int p){
    int res = 0;
    for(auto x: d[i])
        if(x != p){
            res += dfs(x, i);
        }
    return res + 1;
}

int main()
{
    cin >> n;
    d.resize(n + 1);
    for(int i = 1; i < n; ++ i) {
        int x, y;
        cin >> x >> y;
        d[x].push_back(y);
        d[y].push_back(x);
    }

    int ret = 0;
    for(auto& x : d[1])
        ret = max(ret, dfs(x, 1));
    cout << ret << endl;

    return 0;
}



算法1

这题数据范围较小,n最大只有50,可以尝试爆搜,加上剪枝就能过。
每次贿赂的金币最多只有2个,所以最多不会超过100枚金币,
但是怪兽的武力值很大,得开long long

C++ 代码

#include <iostream>
using namespace std;
const int N = 55;
using LL = long long;
LL a[N];
int c[N];
int n, ret = 110;

void dfs(int idx, LL sum, int pay){
    if(pay >= ret) return; // 最优性剪枝

    if(idx == n - 1){
        if(sum < a[idx]) pay += c[idx];
        ret = min(ret, pay);
        return;
    }

    // 打不过就必须贿赂, 打得过可以贿赂, 也可以不鸟它
    dfs(idx + 1, sum + a[idx], pay + c[idx]);

    if(sum >= a[idx])   
    {   
        dfs(idx + 1, sum, pay);
    }
}

int main()
{
    cin >> n;

    for(int i = 0; i < n; ++ i) cin >> a[i]; // 武力值
    for(int i = 0; i < n; ++ i) cin >> c[i]; // 贿赂所需金币值

    dfs(0, 0, 0); // 爆搜

    cout << ret << endl;

    return 0;
}



C++ 代码

#include <iostream>
using namespace std;
int n;

int main(){
    cin >> n;
    string s;
    while(n --){
        cin >> s;
        string ret;
        for(char c : s){
            if(ret.size() >= 2 && (ret.back() == c && ret[ret.size() - 2] == c) // 错误一
            || (ret.size() >= 3 && ret.back() == c && ret[ret.size() - 2] == ret[ret.size() - 3])) // 错误二
                continue;
            ret.push_back(c);
        }
        cout << ret << endl;
    }
    return 0;
}



C++ 代码

#include <iostream>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int ret = 0;
    int a[4] = {64, 16, 4, 1};
    N = 1024 - N;
    for(int i = 0; i < 4; ++ i){
        int cnt = N / a[i];
        N -= cnt * a[i];
        ret += cnt;
    }
    cout << ret << endl;

    return 0;
}



C++ 代码

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
char a[N]; // 数组模拟栈
int r = 0;

int main(){
    int n;
    string s;
    cin >> n >> s;

    for(char c : s){
        if(r == 0) {
            a[r ++] = c;
        }else{
            if(c == a[r - 1]) a[r ++] = c;
            else -- r;
        }
    }
    cout << r << endl;
    return 0;
}