526互联

The 10th Jimei University Programming Contest

发布时间 2023-11-10 18:30:23作者: PHarr

外校打星队伍，排名22/450，还算凑合吧。

A. A+B问题

直接枚举进制

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;


void solve() {
    string str;
    vi a, b, s;
    cin >> str;
    for (auto c: str) {
        if (c >= '0' and c <= '9') a.push_back(c - '0');
        else a.push_back(c - 'A' + 10);
    }

    cin >> str;
    for (auto c: str) {
        if (c >= '0' and c <= '9') b.push_back(c - '0');
        else b.push_back(c - 'A' + 10);
    }
    cin >> str;
    for (auto c: str) {
        if (c >= '0' and c <= '9') s.push_back(c - '0');
        else s.push_back(c - 'A' + 10);
    }

    auto f = [](vi a, int x) {
        if (*max_element(a.begin(), a.end()) >= x) return -1;
        int ans = 0;
        for (auto i: a)
            ans = ans * x + i;
        return ans;
    };

    for (int i = 2, A, B, S; i <= 16; i++) {
        A = f(a, i);
        if (A == -1) continue;
        B = f(b, i);
        if (B == -1) continue;
        S = f(s, i);
        if (S == -1) continue;
        if (S == A + B) {
            cout << i << "\n";
            return;
        }

    }

}

int main() {
    int TC;
    for (cin >> TC; TC; TC--)
        solve();

    return 0;
}

B. 看比赛

首先正反两遍最短路，这样就可以确定那些边一定是最短路上的边，删掉多余的方向和边就会形成一个有向无环图。

我们发现，在有向图上能一步到达 n 的点，对于这些点是先手必胜点。然后只能够走到先手必胜的点的点就是先手必败点，根据这个规律，我们把整张图反向，然后按照拓扑序根据这个规则去给点染色，最后判断 1 的属性即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e18;


void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> e(n + 1);
    vector<vi> g(n + 1);
    vector<array<int, 3>> edge(m);
    for (auto &[u, v, w]: edge) {
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
    }

    auto dij = [n, e](int x) {
        vi dis(n + 1, inf);
        vi vis(n + 1, 0);

        dis[x] = 0ll;
        priority_queue<pii, vector<pii>, greater<pii>> q;
        q.emplace(0, x);
        while (!q.empty()) {
            auto [d, u] = q.top();
            q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (auto [v, w]: e[u]) {
                if (dis[v] <= d + w)continue;
                dis[v] = d + w;
                q.emplace(dis[v], v);
            }
        }
        return dis;
    };

    auto d1 = dij(1) , d2 = dij(n);

    vi cnt(n+1) , f(n+1);
    for( auto [ u , v , w ] : edge ){
        if( d1[u] + w + d2[v] == d1[n] )
            g[v].push_back(u) , cnt[u] ++;
        else if ( d1[v] + w + d2[u] == d1[n] )
            g[u].push_back(v) , cnt[v] ++;
    }


    queue<int> q;
    q.push(n);
    while( !q.empty() ){
        int u = q.front();
        q.pop();
        for( auto v : g[u] ){
            if( f[u] == 0 ) f[v] = 1;
            cnt[v] --;
            if( cnt[v] == 0 ) q.push(v);
        }
    }
    if( f[1] ) cout << "Little M is the winner.\n";
    else cout << "Little I is the winner.\n";
    return ;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();

    return 0;
}

C. 方格染色

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e18;


int32_t main() {
    int n = 10, m = 10;
    vector f(n + 1, vector(m + 1, vi(3, 0)));
    f[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k < 3; k++) {
                if (j == 0 and k > 0) continue;
                for (int l = 0; l < 3; l++) {
                    if ((l & k) != 0) continue;
                    if( j - (k > 0) == 0 and l != 0 ) continue;
                    f[i][j][k] += f[i - 1][j - (k > 0)][l];
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            cout << accumulate(f[i][j].begin(), f[i][j].end(), 0ll) << " ";
        }
        cout << "\n";
    }
    return 0;
}

首先我写了一个这样的 dp 去打表，然后对于\((n,k)\)的答案，发现当\(n<k\)时一定无解。

为了方便令\(n=n-k+1\),发现递推式子\(f(n,k)=\frac{2\times k\times f(n-1,k)}{n-1}+f(n-2,k),f(0,k)=0,f(1,k)=2\)

这样子我们自然可以得到一个\(O(nk)\)的递推，但是我发现\(\sum k \le 5\times10^5\)，那么\(k\)的种类数最多就是\(1,2,3,\cdots\)这样取，也就是\(\frac{k(k-1)}{2}\le 5\times10^5\)，\(k\)最多大约是\(10^3\)中，这样的话配合记忆化就可以实现复杂度控制在\(O(10^8)\)这样

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;

using pii = pair<int, int>;

const int inf = 1e18;

const int N = 1e5 + 5;
const int mod = 998244353;

vector<vector<int>> f(N);
vi inv(N);

int power( int x , int y ){
    int ans = 1;
    while( y ){
        if( y & 1) ans = ans * x % mod;
        x = x * x % mod , y /= 2;
    }
    return ans;
}

void solve() {
    int n, k;
    cin >> n >> k;
    if (n < k) {
        cout << "0\n";
    } else if (k == 0) {
        cout << "1\n";
    } else {
        int t = n - k + 1;
        if (f[k].empty()) f[k].push_back(0), f[k].push_back(2);
        for (int i = f[k].size() - 1; i <= t; i++)
            f[k].push_back((2 * k % mod * f[k][i] % mod * inv[i] % mod + f[k][i - 1]) % mod);
        cout << f[k][t] << "\n";
    }
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    inv[0] = -1;
    for( int i = 1 ; i < N ; i ++ ) inv[i] = power( i , mod-2);

    int TC;
    for (cin >> TC; TC; TC--)
        solve();

    return 0;
}

E. 时间超限α

就是求一下前缀的最大值就好了。

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;


int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    int res = 0;
    vector< vi > a(n+1);

    for( int i = 1 , x ; i <= n ; i ++ ){
        cin >> x;
        a[i].resize( x + 1 );
        for( int j = 1 ; j <= x ; j ++ ) cin >> a[i][j];
    }
    int m;
    cin >> m;
    for( int i = 1 ; i <= n ; i ++ ){
        for( int j = 1 ; j <= min( m , (int)a[i].size()-1 ) ; j ++ )
            res = max( res , a[i][j] );
    }
    cout << res << "\n";
    return 0;
}

I. 期中考试

模拟一下就好了

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;


int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);


    set<int> x;
    for (int i = 1, v; i <= 3; i++)
        cin >> v, x.insert(v);
    int res = 0;
    int a0, a1, b0, b1;
    cin >> a0 >> a1 >> b0 >> b1;
    if (a0 == b0) {
        for (int i = a1; i < b1; i++) {
            if (x.count(i) == 0) res++;
        }
    } else {
        for (int i = a1; i <= 7; i++) {
            if (x.count(i) == 0) res++;
        }
        for (int i = 1; i < b1; i++) {
            if (x.count(i) == 0) res++;
        }
        int cnt = 0;
        for (int i = 1; i <= 7; i++) {
            if (x.count(i) == 0) cnt++;
        }
        for (int i = a0 + 1; i < b0; i++)
            res += cnt;
    }

    cout << res << "\n";
    return 0;
}

L. 兄弟校问题

首先兄弟学校之间的关系用并查集来维护就好了。

剩下就是如何判断兄弟学校，首先\(O(n^2)\)的根据城市判断一下。

然后再\(O(nm)\)的根据关键字判一下，因为这里面的字符串不太长，我直接截取下来，转成小写字母丢进 set 就好了。

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

#define lowbit(x) ( x & - x )

struct dsu {
    vi fa;
    dsu(int n = 1){
        fa = vi( n+1 , -1ll );
        fa[0] = 0;
    }

    int getfa(int x) {
        if (fa[x] < 0) return x;
        return fa[x] = getfa(fa[x]);
    }

    void merge(int x, int y) {
        x = getfa(x), y = getfa(y);
        if (x == y) return;
        if (fa[x] > fa[y]) swap(x, y);
        fa[x] += fa[y], fa[y] = x;
    }

    int size(int x) {
        x = getfa(x);
        return -fa[x];
    }
};

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    dsu d(n);
    vector<set<string>> keyWords(n+1);
    vector<string> city(n+1);

    auto toLow = [](string s) {
        for (auto &i: s)
            if (i >= 'A' and i <= 'Z') i = i + 'a' - 'A';
        return s;
    };

    for (int i = 1; i <= n; i++) {
        string s , t = "";
        cin >> s >> city[i];
        s += '_';
        for ( auto c: s) {
            if (c == '_') {
                keyWords[i].insert(toLow(t) );
                t = "";
            } else t += c;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (city[i] != city[j]) continue;
            d.merge(i, j);
        }
    }
    string key;
    for (int i = 1, p, q; i <= m; i++) {
        cin >> key;
        for (p = 1; p <= n; p++)
            if (keyWords[p].count(key)) break;

        for (q = p + 1; q <= n; q++) {
            if (keyWords[q].count(key)) d.merge(p, q);
        }
    }
    for( int i = 1 ; i <= n ; i ++ )
        cout << d.size(i) - 1 << "\n";

    return 0;
}