2025-01-12崂山

一二节

P1106

保留 $n-k$ 个数。

我们每次选择合法位置（即后面的数还够选）的数中，最小数中位置最靠左的数。

注意 ：

• 开头不能为 0

• 要按照左右顺序拼接

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

int s[300], choose[300];

int ask(int l, int r) {
    return s[r] - s[l - 1];
}

void solve() {
    string str;
    int n, k;
    cin >> str >> k;
    n = str.size();
    str = ' ' + str;

    string res = "";
    for(int x = 1; x <= n - k; x ++) {
        memset(s, 0, sizeof s);
        for(int i = 1; i <= n; i ++) {
            s[i] = s[i - 1] + (choose[i] == 0);
        }
        // cout << ask(1, n) << '\n';
        pair<int, int> tmp = {1e9, 1e9};
        for(int i = 1; i <= n; i ++) {
            if(choose[i]) continue ;
            if(ask(i, n) >= n - k + 1 - x) {
                auto &[v, p] = tmp;
                auto val = str[i] - '0';
                // cout << val << ' ' << v << '\n';
                if(val < v || (val == v && i < p)) {
                    p = i;
                    v = val;
                }
            }
        }

        auto &[v, p] = tmp;
        // cout << v << ' ' << p << '\n';

        res += to_string(v);
        for(int i = 1; i <= p; i ++) {
            choose[i] = 1;
        }
    }
    int i = 0;
    while(i + 1 < res.size() && res[i] == '0') ++ i;
    cout << res.substr(i);
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    solve();
    return 0;
}

P8604

解法一 : 枚举关键点，并判断连通性

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

const int N = 1E3 + 10;

int res = 0;
int n, m, u, v;
int g[N][N];
bool st[N];

void dfs(int s, int x) {
    st[s] = true;
    for(int i = 1; i <= n; i ++){
        if(g[s][i] && !st[i] && i != x) {
            dfs(i, x);
        } 
    }
}

bool test(int x) {
    memset(st, false, sizeof st);  
    dfs(u, x); 
    return !st[v];
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        cin >> u >> v;
        g[u][v] = 1;
        g[v][u] = 1;
    }
    cin >> u >> v;

    dfs(u, n + 1);
    if(st[v] == false) {
        cout << "-1";
        return ;
    }

    for(int i = 1; i <= n; i ++) {
        if(i == u || i == v) continue ;
        res += test(i);
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    solve();
    return 0;
}

解法二 :

回溯判断每个点被 $u$ 到 $v$ 的路径经过几次，并求出路径总数。

如果经过 次数 = 路径总数 ，那么这个点就是关键点

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

const int N = 1E3 + 10;
vector<int> e[N];
int res = 0;
int n, m, u, v, sum = 0;
int cnt[N], tag[N];

void dfs(int u) {
    if(u == v) {
        sum ++;
        for(int i = 1; i <= n; i ++){
            cnt[i] += tag[i];
        }
        return; 
    }
    for(auto v : e[u]) {
        if(tag[v] == 0) {
            tag[v] = 1;
            dfs(v);
            tag[v] = 0;
        }
    }
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i ++) {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    cin >> u >> v;

    dfs(u);

    if(sum == 0) {
        cout << "-1";
        return ;
    }

    int res = 0;
    for(int i = 1; i <= n; i ++){
        res += cnt[i] == sum;
    }
    cout << res - 1 << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    solve();
    return 0;
}

三四节

P1765

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

int num[26] = {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 4};

int main(){
    string s;
    getline(cin, s);    

    int res = 0;
    for(int i = 0; s[i]; i ++){
        if(s[i] == ' ') res ++;
        else if(s[i] >= 'a' && s[i] <= 'z') res += num[s[i] - 'a'];
    }
    cout << res << '\n';

    return 0;
} 

P1125

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

void solve(){
    string str;
    cin >> str;

    vector<int> cnt(26, 0);
    for(char x : str) {
        cnt[x - 'a'] ++;
    }

    int maxn = *max_element(cnt.begin(), cnt.end());
    int minn = 1E9;
    for(int x : cnt) {
        if(x) minn = min(minn, x);
    }

    auto judge = [&] (int x) -> bool {
        if(x <= 1) return false;
        for(int i = 2; i <= x / i; i ++) {
            if(x % i == 0) {
                return false;
            }
        }
        return true;
    };

    if(judge(maxn - minn)) {
        cout << "Lucky Word\n";
        cout << maxn - minn << '\n';
    }
    else {
        cout << "No Answer\n0";
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    solve();
    return 0;
}

P5015

曲鑫

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    getline(cin,s);
    int k=s.size();
    int cnt=0;
    for(int i=0;i<k;i++){
        if(s[i]!=' ' && s[i]!='\n'){
            cnt++;
        }
    }
    cout<<cnt;
    return 0;
}