526互联

Codeforces Round 896 Div2 A-D题解

发布时间 2023-07-16 19:09:29作者: tiany7

Codeforces Round 896

A. Politics

这题问的是，给一些人的在n个议题的观点，然后你可以随意安排顺序，每个议题人多的赢，反对派会离开，问随便安排议题，最多留下多少人，包括我自己

这个题刚开始愣了半天，但是想到，那只要把所有和我观点一致的给留下来不就行了？？？然后交上去就AC了

AC Code 
#include <bits/stdc++.h>

using namespace std;
constexpr int limit =  (4e5  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
int n,m;
int a[limit];

void solve() {
    vector<string>str;
    cin>>n>>m;
    rep(i,1,n){
        str.push_back("");
        cin>>str.back();
    }
    int ans = 0;
    for(const auto & it : str){
        if(str[0] == it)++ans;
    }
    cout<<ans<<endl;
}
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    int kase;
    cin>>kase;
    while (kase--)
    invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

B. Indivisible

这个题也是个sb题，给你一个permutation p，然后要求所有的子数组不能被自身长度整除，要求给出一种方案。

这个题我感觉在哪里见过，但是不记得怎么做，所以我暴力打了1-7的表，乐了，发现就是奇偶错位放置就好了，ac

AC Code 
#include <bits/stdc++.h>

using namespace std;
constexpr int limit =  (4e5  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
int n,m;
int a[limit];

void solve() {
    cin>>n;
    if(n == 1){
        cout<<1<<endl;
        return;
    }
    if(n & 1){
        cout<<-1<<endl;
        return;
    }
    deque<int>q,p;
    rep(i,1,n){
        if(i & 1){
            q.push_back(i);
        }else{
            p.push_back(i);
        }
    }
    rep(i, 1, n){
        if(i & 1){
            cout<<p.front()<<" ";
            p.pop_front();
        }else{
            cout<<q.front()<<" ";
            q.pop_front();
        }
    }
    cout<<endl;
}
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    int kase;
    cin>>kase;
    while (kase--)
    invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

C. Almost Increasing Sequence

这题给一个数组和一堆区间查询，定义Almost Increasing Sequence为不包含连续三个不上升元素的序列，问每个区间内的最长的Almost Increasing Sequence的长度。

这个题我一开始以为和区间LIS有关系，我想这可以把相邻的三个数字拆成6个partition然后dp搞一搞，后来发现，嗷，没有要求increasing，这个名字纯粹唬人的，我们不需要保证这个数组上升。

然后想着就是，3个相邻元素，那么我作为子序列肯定是要求越多越好，也就是我们不会存在一种情况就是一个元素因为不能满足这个要求被跳过，连续3个，也就意味着我们只需要贪心得删掉中间那个捣蛋鬼就能够满足要求，然后前缀和计算一下

需要注意的是，左右端点其实不产生贡献的（我暴力试了好几组数据猜出来的结论），然后我们把所有坏点删掉，之后再用区间长度减一下，就是答案了。

AC Code 
#include <bits/stdc++.h>

using namespace std;
constexpr int limit =  (4e6  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
int n,m;
int a[limit];
int vis[limit]; // 这个位置上有几个连续的下降序列
int pref[limit];
void solve() {
    cin>>n;
    cin>>m;
    a[0] = -INF;
    rep(i,1,n)vis[i] = 0;
    rep(i,1,n){
        cin>>a[i];
        vis[i] = 0;
        pref[i] = 0;
    }
    rep(i, 2, n - 1){
        if(a[i] <= a[i - 1] and a[i + 1] <= a[i]){
            vis[i] = 1;
        }
    }
    partial_sum(vis, vis + n + 1, pref);
    ll sum = 0;
    rep(i,1,n){
        sum += vis[i];
        assert(sum == pref[i]);
    }
    rep(i, 1, m){
        int l, r;
        cin>>l>>r;
        int len = r - l + 1;
        if(len <= 2){
            cout<<len<<endl;
        }else{
            cout<<len - (pref[r - 1] - pref[l])<<endl;
        }
    }
}
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
//    int kase;
//    cin>>kase;
//    while (kase--)
    invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

D. Almost All Divisors

妈的，这个题我vp的时候其实一开始就知道怎么做了。我把思考写在代码里了。

这个题要求找出来一个sub graph，并且这个graph只包括一个环和两条自由边

//第一条就是我们我们的答案只包含入度为4及以上的点，否则不可能有环和两条自由边
//第二条是我们可以枚举u和v去判断两个点common neighbor是否有一个点和u,v相连 but need 一个O(1)或者O(log)时间工具
//第三条就是我们可以求最大环然后来缩点
//我们可以先求所有的最大环归属，然后再剔除条件1的点，然后再剔除条件2的点，这样最后就可以枚举得到答案

刚开始觉得要求最大环，这算法我不会啊！然后后来发现是subgraph，意味着我们只需要删边就好了，也就是说我其实不用最大环，最大环可能会把有些有用的自由边删掉，所以为了避免这种情况，我们要求最小环。

然后尴尬的事情是，我也不会求最小环，然后网上和copilot生成的好像都不太对，结果一直等到比赛之后去找个别人的代码求环，您猜怎么着？AC了。尼玛

AC Code 
#include <bits/stdc++.h>

using namespace std;
constexpr int limit =  (4e6  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
int n,m;
int a[limit];
vector<int>g[limit];
int deg[limit];
bool vis[limit];
int cnt;
int flag;
deque<int>circle;
// 求以u为根节点的最小环,并且记录路径，如果没有环返回false
int du[limit],fa[limit];

void dfs(int begin,int x,int f)
{
    fa[x]=f;
    vis[x]=1;
    for (auto to:g[x])
    {
        if (to==f) continue;
        if (to==begin&&vis[begin]==1&&!flag)
        {
            int tmp=x;
            while(tmp!=begin) circle.push_back(tmp),tmp=fa[tmp];
            circle.push_back(begin);
            flag=1;
            return;
        }
        if (flag==1) return;
    }
    for (auto to:g[x])
    {
        if (to==f) continue;
        if (!vis[to]) dfs(begin,to,x);
        if (flag==1) return;
    }
}

void solve() {
    //第一条就是我们我们的答案只包含入度为4及以上的点，否则不可能有环
    //第二条是我们可以枚举u和v去判断两个点common neighbor是否有一个点和u,v相连 but need 一个O(1)或者O(log)时间工具
    //第三条就是我们可以求最大环然后来缩点
    //我们可以先求所有的最大环归属，然后再剔除条件1的点，然后再剔除条件2的点，这样最后就可以枚举得到答案
    cin>>n>>m;
    cnt = 0;
    for_each(g + 1, g + 1 + n, [&](auto && x) { x.clear(); });
    auto init = [&](){
        rep(i,1,n){
            vis[i] = 0;
            fa[i] = 0;
        }
        cnt = 0;
        flag = 0;
        circle.clear();
    };
    rep(i,1,m){
        int u,v;
        cin>>u>>v;
//        if(v > u)swap(u,v);
//        if(u == 2 or v == 2)continue;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int>pts;
    rep(i,1,n){
        if(g[i].size() >= 4){
            pts.push_back(i);
        }
    }
    for(const auto u : pts){
        init();
//        cout<<u<<endl;
        dfs(u, u, 0);
        if(!flag){
//            cout<<"!"<<u<<endl;
            continue;
        }
        vector<int>in_cycle;
        while(!circle.empty()){
            int x = circle.front();
            circle.pop_front();
//            cout<<x<<" ";
            in_cycle.push_back(x);
        }
        cout<<endl;
        set<int>st(in_cycle.begin(), in_cycle.end()); //记录每个在点上的
        vector<int>not_cycle;
        for(const auto & v: g[u]){
            if(!st.contains(v)){
                not_cycle.push_back(v);
            }
            if(not_cycle.size() >= 2){
                break;
            }
        }
        if(not_cycle.size() < 2)continue;
        cout<<"YES"<<endl;
        vector<pi(int, int)>ans;
        rep(i,0,in_cycle.size() - 1){
            ans.push_back({in_cycle[i], in_cycle[(i + 1) % in_cycle.size()]});
        }
        for(const auto & v : not_cycle){
            ans.push_back({u,v});
        }
        cout<<ans.size()<<endl;
        for(const auto & [vv,v] : ans){
            cout<<vv<<" "<<v<<endl;
        }
        return;
    }

    cout<<"NO"<<endl;



}
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    int kase;
    cin>>kase;
    while (kase--)
    invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

只能说还是得多练习咯