首页 > 其他分享 >Codeforces Round 793 div2 (A-D)

Codeforces Round 793 div2 (A-D)

时间：2022-12-15 08:55:08浏览次数：47  
标签：793 int ll Codeforces long 偶数 str div2 define

A题，题意是给一个回文串，问有多少个字符删掉，还是一个回文串

这个题看样例，肯定是从中间开始查相同字符的段长度，没啥难度

代码：

#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (3000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#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].nxt)
#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 b[limit];


void solve(){
    cin>>n;
    string str;
    cin>>str;
    str = " " + str;
    int ans = 0;
    int l = (n + 1) / 2;
    per(i, 1, l){
        if(str[i] != str[l]){
            break;
        }
        ++ans;
    }
    rep(i, l + 1, n){
        if(str[i] != str[l]){
            break;
        }
        ++ans;
    }

    cout<<ans<<endl;

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

B题，题意是选取一个非负整数X，当p[i] & p[j] == X，可以交换i和j，然后在任意次交换位置之后让permutation p 有序

如果有很多X输出最大的X

这个题属实没啥难度，很容易联想到交换位置的话，所有不在排序后自己位置上的元素都需要swap，然后通过某种冒泡排序，就能交换到有序

那么这个X一定是被所有的不在位置上的元素share的，所以把他们串起来取and就行了

#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (3000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#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].nxt)
#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 b[limit];


void solve(){
    cin>>n;
    rep(i,1,n){
        cin>>a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    ll ans = LONG_LONG_MAX;
    rep(i,1,n){
        if(b[i] != a[i]){
            ans &= a[i];
        }
    }
    cout<<ans<<endl;

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

 

C题，给一个序列，你可以任意安排这个序列的所有元素顺序，使得min(a, reverse(a))的LIS长度最小值最大

然后很容易想到那就各取一半，然后首先每个不重复的元素对答案的贡献是1/2，因为可以被加到前后的LIS里面，然后每个重复的元素对答案贡献是1

简单题，我怎么感觉我还没蓝之前做过这个？

#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (3000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#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].nxt)
#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 b[limit];


void solve(){
    cin>>n;
    map<int, int>mp;
    rep(i,1,n){
        cin>>a[i];
        mp[a[i]]++;
    }
    int tot = 0;
    int ans = 0, delta = 0;
    for(auto [k, v] : mp){
        if(v == 1){
            ++delta;
        }else if(v >= 2){
           ++ans;
        }
    }
    cout<<ans + (delta + 1) / 2<<endl;




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

 

D题，D真的是个喵喵题，给出一个01串，n个点，顺时针排成圆形，每个位置上0或者1代表这个点的deg是奇数或者偶数，让你构造一棵树，使得

1. 每个点度数奇偶性满足要求

2. 不能有遍的重叠

或者返回这棵树根本不存在

首先很容易想到的有几个很明显的点

1. 树的度数一定为偶数（n - 1条边，每条边对度数的共线为2）

2. 奇数个数节点也必然是偶数

3. 奇数的节点可以为叶子节点，但偶数的节点一定不是叶子节点

然后想了半晌，emmmm，没辙，脑子里只有一个很模糊的想法，就是先找到偶数节点前后一致的点作为树根，然后乱搞，遂g

想了40分钟之后决定看看答案，答案其实很妙，因为看到了第一句话我就会了

就是将01串贪心处理成所有

regex: 1(0)*的链的形式，然后把所有的链处理出来，连边

最后我们会剩下至少两个链/点，然后把一个长度大于1的链的偶数节点当作树根，然后把其他链的最后一个偶数节点链接上去

这样因为我们必定有偶数个链（偶数个1），所以那个树根的度数也必然是偶数

nice！

然后要注意一下，比如n个1的情况，这个就把剩下的n - 1个点（奇数个）连到1上就行了，特判一下

#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (3000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#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].nxt)
#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 b[limit];
int deg[limit];
void solve(){
    cin>>n;
    string str;
    cin>>str;
    str = " " + str;
    int total = 0;
    if((total = count(str.begin(),str.end(),'1') ) & 1){
        cout<<"No"<<endl;
        return;
    }
    if(!total){
        cout<<"No"<<endl;
        return;
    }
    vector<pi(int, int)>ans;
    auto nxt = [&](int x)->int{
        ++x;
        if(x > n) x = 1;
        return x;
    };
    vector<pi(int, int)>chain;
    int appender = -1;
    for(int i = 1, tot = 1; tot <= n; ){
        if(str[i] == '1'){
            chain.push_back({i, i});
            ++tot;
            int last = i;

            i = nxt(i);

            while(tot <= n and str[i] == '0'){
                chain.back().second = i;
                ++tot;
                ans.push_back({last, i});
                last = i;
//                cout<<i<<" "<<last<<endl;
                i = nxt(i);
            }

            auto [l, r] = chain.back();
//            cout<<l<<" "<<r<<endl;
            if(l != r and appender == -1){
                appender = last;
                chain.pop_back();
            }
        }
        else{
            i = nxt(i);
        }
    }
    if(appender == -1){
        ans.clear();
        rep(i,2,n){
            ans.push_back({1, i});
        }
    }else{
        for(auto [l, r] : chain){
            ans.push_back({appender, r});
        }
    }
    cout<<"Yes"<<endl;
    for(auto [l, r] : ans){
        cout<<l<<" "<<r<<endl;
    }

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

能花时间细细想想问题还是对自己思维有帮助的，要不然思维完全就退化了，这很致命，尤其是在当下的寒冬，不能坐在ICPC和队友的功劳簿上吃一辈子！

 

标签：793,int,ll,Codeforces,long,偶数,str,div2,define
From： https://www.cnblogs.com/tiany7/p/16984182.html

相关文章

  • Codeforces Round #837 (Div. 2) A-C
    A.HossamandCombinatorics题意：给定一个长度为n的序列，求两个不同位置的数的差值等于所有数差值的最大值的数对数量。分析：显然排序后取最大最小就是差的绝对值最大，再......
  • Educational Codeforces Round 139 (Rated for Div. 2)
    题目链接A核心思路：这个其实就是一个简单的dp状态定义：dp[i]表示的是\(1\simi\)中的完美数的个数状态划分：这个还是比较显然的，我们只需要根据最后一个位置进行状态划分......
  • Codeforces Round #655 (Div. 2) ABCDEF题解
    题号博客链接cf分数算法标签A​​https://blog.nuoyanli.com/2020/07/14/codeforces-round-655-div-2-a/​​800简单B​​https://blog.nuoyanli.com/2020/07/14/codeforces......
  • Educational Codeforces Round 139 (Rated for Div
    A.ExtremelyRound当n为3位数时，例如\(n=120\)，满足题目要求的情况有123456789102030405060708090100以上19种情况，一位和二位去满各有九种情况，三位只......
  • Educational Codeforces Round 139 (Rated for Div. 2)
    题目链接A直接计算即可位数为k首位数为a则\(ans=a+(k-1)\times9\)点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintmaxn=2e5+......
  • codeforces 598 div3 Minimize the Permutation（贪心找规律）
    题目大意：有n个排列数。现在定义操作：交换第i和i+1个元素。我们对每个i位置只能操作一次。问经过这种操作后，我们最少能够得到的字典序序列是多少。解题思路：我们贪心从小到大选......
  • codeforces ECR 74 Standard Free2play(找规律)
    题目大意：有一座山，山有h层。每一层都有平台。有些平台凸出来，有些平台是凹进去。主角一开始站在h层平台，他的目标是落到第0层。主角能够下山的方式只有一种：让高为x的平台和高为......
  • codeforces 596 div2 p-binary（数位复杂度压缩）
    题目大意：已知： 同时  ，问k最少为多少。解题思路：首先，我们看到这里有2的n次方，我们考虑能不能从二进制表示下手，我们通过移位来表示：得到公式 ，很直接的想法是我们让k从小到大......
  • codeforces 594 div2 Ivan the Fool and the Probability Theory （DP 推公式）
    题目大意：现在有n*m个格子。然后我们可以对这些格子染上黑色或者白色。规定每个格子最多允许相邻1个与它同样颜色的格子，问你我们有多少中不同的染色方案。解题思路：首先考虑1*......
  • codeforces 1354D - Multiset (线段树或者2分)
    题目大意：已知一个数列an,我们每次可以添加一个数k，或者把第k大的数字去掉。问我们经过k次操作后，数列中任意1个剩余的数字。n,q<=1e6解题思路：首先最简单的思路是线段树。线段......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99