JZTXT

ABC324

发布时间 2023-10-16 03:49:45作者: V_Melville

T1：Same

set

代码实现 
n = int(input())
a = list(map(int, input().split()))
if len(set(a)) == 1:
    print('Yes')
else:
    print('No')

T2：3-smooth Numbers

把 \(N\) 里的 \(2\) 和 \(3\) 都除干净即可

代码实现 
n = int(input())
while n%2 == 0: n /= 2
while n%3 == 0: n /= 3
if n == 1:
    print('Yes')
else:
    print('No')

T3：Error Correction

条件 \(4\) 就是 \(|S| = |T|\) 并且两字符串的汉明距离为 \(1\)
条件 \(2\) 和条件 \(3\) 是对称的
条件 \(2\) 就是验证 \(S\) 是否是 \(T\) 的子序列，可以用双指针实现

代码实现 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int ham(string& s, string& t) {
    if (s.size() != t.size()) return 999;
    int res = 0;
    rep(i, s.size()) if (s[i] != t[i]) res++;
    return res;
}

bool f(string& s, string& t) {
    if (s.size() != t.size()+1) return false;
    int si = 0;
    rep(ti, t.size()) {
        while (si < s.size() and s[si] != t[ti]) si++;
        if (si == s.size()) return false;
        si++;
    }
    return true;
}

int main() {
    int n;
    string t;
    cin >> n >> t;
    
    vector<int> ans;
    rep(i, n) {
        string s;
        cin >> s;
        
        bool ok = false;
        if (s.size()+1 >= t.size()) {
            if (s == t) ok = true;
            if (f(s, t)) ok = true;
            if (f(t, s)) ok = true;
            if (ham(s, t) == 1) ok = true;
        }
        
        if (ok) ans.push_back(i+1);
    }
    
    cout << ans.size() << '\n';
    for (int i : ans) cout << i << ' ';
    
    return 0;
}

T4：Square Permutation

枚举平方根

验证平方数是否是 \(S\) 的某个排列比较容易，可以分别对 \(S\) 和这个平方数做排序即可，或者是统计数位 \(0 \sim 9\) 的出现次数

代码实现 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    string s;
    cin >> n >> s;
    
    vector<int> sc(10);
    for (char c : s) sc[c-'0']++;
    
    int ans = 0;
    for (ll x = 0;; ++x) {
        string t = to_string(x*x);
        if (t.size() > s.size()) break;
        
        vector<int> tc(10);
        for (char c : t) tc[c-'0']++;
        tc[0] += s.size()-t.size();
        if (sc == tc) ans++;
    }
    
    cout << ans << '\n';
    
    return 0;
}

T5： Joint Two Strings

对于每个 \(s\)，维护两个指针 \(l\) 和 \(r\)，\(l\) 表示对 \(s\) 从左到右扫描和 \(t\) 能匹配到的最多的字符个数， \(r\) 表示对 \(s\) 从右到左扫描和 \(t\) 能匹配到的最多的字符个数
然后就变成了统计满足 \(l_i + r_j \geqslant |t|\) 的 \((i, j)\) 的对数
可以通过预处理 \(r_j\) 的后缀和，然后固定 \(i\)，\(O(1)\) 求 \(j\) 的个数

代码实现 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    string t;
    cin >> n >> t;
    int m = t.size();
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    
    vector<int> l(n), r(n);
    rep(ri, 2) {
        rep(i, n) {
            for (char c : s[i]) {
                if (l[i] < m and t[l[i]] == c) l[i]++;
            }
        }
        swap(l, r);
        reverse(t.begin(), t.end());
        rep(i, n) reverse(s[i].begin(), s[i].end());
    }
    
    vector<int> c(m+1);
    rep(i, n) c[r[i]]++;
    for (int i = m-1; i >= 0; --i) c[i] += c[i+1];
    ll ans = 0;
    for (int nl : l) ans += c[m-nl];
    
    cout << ans << '\n';
    
    return 0;
}

T6：Beautiful Path

注意到 \(u_i < v_i\) 保证了图是 DAG

可以考虑二分

假设答案为 \(X\)
\(\frac{\sum b}{\sum c} \geqslant X\)
\(\sum b \geqslant X\sum c\)
\(\sum b - X\sum c \geqslant 0\)
\(\sum (b-Xc) \geqslant 0\)

代码实现 
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

struct Edge {
    int to, b, c;
    Edge(int to=0, int b=0, int c=0): to(to), b(b), c(c) {}
};

inline void chmax(double& a, double b) { if (a < b) a = b; }

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<Edge>> g(n);
    rep(i, m) {
        int u, v, b, c;
        cin >> u >> v >> b >> c;
        --u; --v;
        g[u].emplace_back(v, b, c);
    }
    
    auto f = [&](double x) {
        const double INF = 1e18;
        vector<double> dp(n, -INF);
        dp[0] = 0;
        rep(i, n) {
            for (auto e : g[i]) {
                chmax(dp[e.to], dp[i]+e.b-e.c*x);
            }
        }
        return dp[n-1] >= 0;
    };
    
    double ac = 0, wa = 1e4;
    rep(ti, 50) {
        double wj = (ac+wa)/2;
        if (f(wj)) ac = wj; else wa = wj;
    }
    
    printf("%.10f\n", ac);
    
    return 0;
}