526互联

Codeforces Round 686 (Div. 3)

发布时间 2023-11-25 22:59:26作者: PHarr

A. Special Permutation

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve() {
    int n;cin>>n;
    cout<<n<<' ';
    for(int i=1;i<n;++i)cout<<i<<' ';
    cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}

B. Unique Bid Auction

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i32 = int32_t;
using pii = pair<int, int>;
using vi = vector<int>;

const int inf = 1e18;

void solve() {
    int n;
    cin >> n;
    map<int, int> cnt;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        if (cnt[x] == 0) cnt[x] = i;
        else cnt[x] = -1;
    }
    for (auto [k, v]: cnt) {
        if (v == -1) continue;
        cout << v << "\n";
        return;
    }
    cout << "-1\n";
    return;
}

i32 main() {
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

C. Sequence Transformation

我们分别统计出相同的每一种数字的位置，然后枚举保留那些数字，这些数字会把序列分层若干段，统计一下非空段的数量即。

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i32 = int32_t;
using pii = pair<int, int>;
using vi = vector<int>;

const int inf = 1e18;
const int A = 2e5;


void solve() {
    int n;
    cin >> n;
    int res = inf;
    map<int, vi> cnt;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        if (cnt[x].empty()) cnt[x].push_back(0);
        cnt[x].push_back(i);
    }
    for (auto [k, v]: cnt) {
        int ans = 0;
        v.push_back(n + 1);
        for (int i = 1; i < v.size(); i++)
            ans += (v[i] - v[i - 1]) > 1;
        res = min(res, ans);
    }
    cout << res << "\n";
}

i32 main() {
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

D. Number into Sequence

质因数分解一下，然后找到最高次项的因子，次方数就是\(k\)，然后把其他因子都乘到任意一个数字上就好。

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve() {
    int n,m;cin>>n;
    m=n;
    int c=0,ma;
    for(int i=2,cnt;i*i<=n;++i){
        if(n%i)continue;
        cnt=0;
        while(n%i==0)cnt++,n/=i;
        if(cnt>c)ma=i,c=cnt;
    }
    if(n>1)
        if(1>c)ma=n,c=1;
    for(int i=0;i<c-1;++i)m/=ma;
    cout<<c<<'\n';
    for(int i=0;i<c-1;++i)cout<<ma<<' ';
    cout<<m<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}

E. Number of Simple Paths

图是一个基环树，找到基环树上所有的点，然后把环上的边都删掉，这样就会形成若干个森林。

\(u\)是的点，统计出\(u\)的子树大小\(cnt[u]\)。

然后现在分情况讨论，对于两个点\(x,y\)之间在基环树上有多少个简单路径。

  1. 两个点在一个子树内，在基环树上只有一个简单路径
  2. 两个点不在一个子树内，在基环树上只有两个简单路径

所以我们对于每一个环上的点来考虑，对于两个点都在子树则\(C_{cnt[u]}^2\)，如果其中一个点在子树内，另一个点不在，则\(2cnt[x]\times(n-cnt[x])\)，对于这种情况，每对点会枚举两次，所以还要除以 2

#include<bits/stdc++.h>

using namespace std;

#define int long long

using i32 = int32_t;
using vi = vector<i32>;
using vI = vector<int>;

void solve() {
    i32 n;
    cin >> n;
    vector e(n + 1, vi());
    vi inDeg(n + 1);

    for (int i = 0, u, v; i < n; ++i) {
        cin >> u >> v;
        inDeg[u]++, inDeg[v]++;
        e[u].push_back(v), e[v].push_back(u);
    }

    // 拓扑
    vector<bool> visH(n + 1);
    queue<i32> q;
    for (i32 i = 1; i <= n; ++i)
        if (inDeg[i] == 1) q.push(i);
    for (i32 u; not q.empty();) {
        u = q.front(), q.pop();
        visH[u] = true;
        for (auto v: e[u])
            if (--inDeg[v] == 1)q.push(v);
    }
    int ans = 0;
    for (int i = 1, omg; i <= n; ++i) {
        if (visH[i])continue; // 不在环上
        vector<bool> vis(n + 1);
        omg = 0;
        queue<i32> que;
        que.push(i);
        for (int u; not que.empty();) {
            u = que.front(), que.pop(), omg++;
            vis[u] = true;
            for (auto y: e[u]) {
                if (visH[y] == false or vis[y] == true) continue;
                que.push(y);
            }
        }
        ans += omg * (omg - 1ll) / 2ll + (n - omg) * omg;
    }
    cout << ans << '\n';
    return;
}

i32 main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    i32 TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

F. Array Partition

首先可以知道的是对于一个区间，如果确定了区间的一个端点，区间的最值是单调的。所以可以提前预处理出前缀后缀的最大值。然后枚举\(x\)，去二分\(y\)。在二分的过程中需要知道区间的的最小值，所以套一个\(ST\)表就好。

#include<bits/stdc++.h>

using namespace std;

#define int long long

using i32 = int32_t;
using vi = vector<int>;


const int N = 2e5, logN = log2(N) + 1;
vi log_2(N);

void init() {
    log_2[0] = -1;
    for (int i = 1; i < N; i++)
        log_2[i] = log_2[i >> 1] + 1;
    return;
}

struct ST {
    vector<vi> f;

    ST(const vi &a) {
        f = vector(a.size(), vi(logN + 1));
        for (int i = 1; i < a.size(); i++)
            f[i][0] = a[i];
        for (int j = 1; j <= logN; j++)
            for (int i = 1; i + (1 << j) - 1 < a.size(); i++)
                f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
    }

    int query(int l, int r) {
        int s = log_2[r - l + 1];
        return min(f[l][s], f[r - (1 << s) + 1][s]);
    }
};

void solve() {
    int n;
    cin >> n;
    vi a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vi pre(n + 1), suf(n + 2);
    for (int i = 1; i <= n; i++)
        pre[i] = max(pre[i - 1], a[i]);
    for (int i = n; i >= 1; i--)
        suf[i] = max(suf[i + 1], a[i]);
    ST s(a);
    for (int i = 1, l, r, mid; i <= n; i++) {
        l = i+1, r = n;
        for (int mid, val; l <= r;) {
            mid = (l + r) / 2, val = s.query(i + 1, mid);
            if (pre[i] == val and val == suf[mid + 1]) {
                cout << "YES\n" << i << " " << mid - i << " " << n - mid << "\n";
                return;
            } else if (val > pre[i]) {
                l = mid + 1;
            } else if (val < pre[i]) {
                r = mid - 1;
            } else {
                if (val < suf[mid + 1]) l = mid + 1;
                else r = mid - 1;
            }
        }
    }
    cout << "NO\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}