首页 > 其他分享 >Codeforces Round 896 Div2 A-D题解

Codeforces Round 896 Div2 A-D题解

时间：2023-07-16 19:12:42浏览次数：42  
标签：int 题解 rep Codeforces long back cycle Div2 define

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;
}

只能说还是得多练习咯

标签：int,题解,rep,Codeforces,long,back,cycle,Div2,define
From： https://www.cnblogs.com/tiany7/p/17558353.html

相关文章

  • Codeforces Round #875 (Div. 2) A-D
    比赛链接A代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;boolsolve(){intn;cin>>n;for(inti=1;i<=n;i++){intx;cin>>x;cout<<n-x+1<<"......
  • 题解 CF1842H【Tenzing and Random Real Numbers】
    看了题解。好难受，想用积分求概率，算了半天。发现没啥规律，不是不能算，就是太可怕了。Problem有\(n\)个\([0,1]\)范围内的均匀随机变量\(x_{1\cdotsn}\)和\(m\)条限制，每条限制形如\(x_i+x_j\le1\)或\(x_i+x_j\ge1\)。请你求出所有限制均满足的概率。对\(998244353\)......
  • Codeforces Round 884
    目录写在前面ABCDEF1F2学到了什么写在前面比赛地址：https://codeforces.com/contest/1844。什么？你怎么知道我连C都没过掉了一伯伍拾昏？吐槽一下马娘前期甚至动画第一季都没出之前的很多个人角色曲，听起来就是很无聊的动漫op风。比如进王的这首：感觉给哪个笨蛋阳光系角色都能......
  • Educational Codeforces Round 137 (Rated for Div. 2)
    EducationalCodeforcesRound137(RatedforDiv.2) A.Passwordvoidsolve(){intn=read();for(inti=1;i<=n;i++)intx=read();cout<<combination(10-n,2)*6<<'\n';//puts(ans>0?"YES":"NO");......
  • Noip优质模拟赛口胡题解
    HDU5719题意概括：第一行输入t表示输入数据,每组数据第一行n，表示对1—n进行排序。接下来输入n个数b[n]表示排列中第i个数之前的最小值为b[i]。第三行n个数c[n]，表示排列中第i个数之前的最大值为c[i]。解题思路：递推,排除掉6种不可能的情况,1、b[i]>b[i-1]2、c[i]<c[i-1]3、b[i]......
  • 2023.07.16 高质量 NOIP 模拟赛题解
    HDU5719Arrange【模拟】给定数列\(B_n,C_n\)，求出满足\[B_i=\min_{j=1}^i\{A_j\},\quadC_i=\max_{j=1}^i\{A_j\}\]的排列\(A\)的数量。维护每个位置可能的数字数量，然后乘法原理即可。代码：http://acm.hdu.edu.cn/viewcode.php?rid=38654445。HDU5807KeepInTouch......
  • HHHOJ #1247. 「NOIP 2023 模拟赛 20230715 A」1 题解--zhengjun
    法老找来的题，说是找了三道其他模拟赛的T4拼成T1~T3，另外搞了道T4。思维好题，但是放在T1有点搞心态，但是还好大样例够强，400没挂。然而T3大样例输出错了，浪费了我0.5h，差评。首先发现向左走之后向右走是一定不优的，所以最短路的情况只能先向右再向左。考虑枚举起点\(s......
  • 题解 P2839【[国家集训队] middle】
    Problem一个长度为\(n\)的序列\(a\)，设其排过序之后为\(b\)，其中位数定义为\(b_{n/2}\)，其中\(a,b\)从\(0\)开始标号，除法下取整。给你一个长度为\(n\)的序列\(s\)。回答\(Q\)个这样的询问：\(s\)的左端点在\([a,b]\)之间，右端点在\([c,d]\)之间的子区间中，最大的中......
  • 你省（福建）省队集训 Day5 T1 题解
    简要题意有两个正整数\(a<b\le10^9\)，给出\(\dfrac{a}{b}\)的小数点后\(19\)位，要求还原\(a,b\)，保证有解。solution一个科技：\(\texttt{Stern-Brocottree}(SBT)\)，可以参考这个博客学习。先给出\(O(n)\)找的代码：......
  • 云斗杯 T2 派蒙是最好的伙伴！ 题解
    云斗杯T2题解赛时脑抽了只打了60pts暴力xwx。题目描述给定两个长度为\(n\)的\(01\)序列\({a_n}\)和\({b_n}\)，与另一个矩阵\({c_{n,n}}\)。矩阵\({c_{n,n}}\)的生成规则如下：\[c_{i,j}=a_i\timesb_j\]现给定一个数\(k\)，求在矩阵\(c_{n,n}\)内，有多少个......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99