首页 > 其他分享 >CF round 812 div2 A-D 题解

CF round 812 div2 A-D 题解

时间：2022-09-20 03:22:05浏览次数：80  
标签：rep int 题解 ll base 812 mod div2 define

首先第一题Traveling Sales Man Problem，给出一些坐标，就是问从原点出发，然后收集所有的点，问最少需要多少次移动

这个就是求收集完那曼哈顿距离，这个距离稍加观察可以发现，就是能围住所有的点的最小矩形的周长，那么只需要记录一下x和y坐标的大小极值就好了

#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].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;
}
const ll mod = MOD;
ll quickPow(ll base, ll expo){
    ll ans = 1;
    while (expo){
        if(expo & 1)(ans *= base) %= mod;
        expo >>= 1;
        base = base * base;
        base %= mod;
    }
    return ans % mod;
}
ll C(ll n, ll m){
    if(n < m)return 0;
    ll x = 1, y = 1;
    if(m > n - m)m = n - m;
    rep(i ,0 , m - 1){
        x = x * (n - i) % mod;
        y = y *  (i + 1) % mod;
    }
    return x * quickPow(y, mod - 2) % mod;
}

int n, m, k;
int a[limit];
void solve(){
    cin>>n;
    int maxx = 0, minx = 0;
    int maxy = 0, miny = 0;
    int ans = 0;
    rep(i,1,n){
        int x,y;
        cin>>x>>y;
        maxx = max(maxx, x);
        maxy = max(maxy, y);
        minx = min(minx, x);
        miny = min(miny, y);
    }
    int xlen = (maxx - minx);
    int ylen = (maxy - miny);
    cout<<2 *(xlen + ylen)<<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

然后第二题，每次可以选择一个子段，然后所有元素-1，F(a) = |让所有元素变成0的操作数|

问给出的数列的F(a)是不是在他所有的permutation里最少的，或者是最少的之一

这个显而易见，当我们只有一个峰值的时候，我们就不用分段去搞了，只用不断地缩小区间，所以单峰数组一定是费用最少的

写个函数判断一下就好了，我对is_sorted函数不太放心，就自己手写了个函数，不复杂

#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].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;
}
const ll mod = MOD;
ll quickPow(ll base, ll expo){
    ll ans = 1;
    while (expo){
        if(expo & 1)(ans *= base) %= mod;
        expo >>= 1;
        base = base * base;
        base %= mod;
    }
    return ans % mod;
}
ll C(ll n, ll m){
    if(n < m)return 0;
    ll x = 1, y = 1;
    if(m > n - m)m = n - m;
    rep(i ,0 , m - 1){
        x = x * (n - i) % mod;
        y = y *  (i + 1) % mod;
    }
    return x * quickPow(y, mod - 2) % mod;
}

int n, m, k;
int a[limit];
bool sorted(int x){
    rep(i,x + 1,n){
        if(a[i] > a[i - 1])return false;
    }
    return true;
}

void solve(){
    cin>>n;
    rep(i,1,n){
        cin>>a[i];
    }
    int flag = 0;
    rep(i,2,n){
        if(a[i] < a[i - 1]){
            if(!sorted(i)){
                cout<<"NO"<<endl;
            }else{
                cout<<"YES"<<endl;
            }
            return;
        }
    }
    cout<<"YES"<<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题，这个是说一个0-n-1的排列能不能让每个位置下标 + a[i] 都是完全平方数

这个怎么分析呢？首先先打表，我们可以打出来1-12（太多了需要很久），我们发现所有的数字组成的平方数都是分段出现的，所以说我们先想想这个分段的依据是什么。

然后我们观察到，虽然我们不确定后面的，但首先最开始的（n - 1）这个位置我们可以确定，所有的数小于 2 * (n - 1)，那么这个时候我们的安排空间就是(sq * sq - (n - 1))，那么我们可以据此复原出来，每次开头都这样搞，然后把能安排的安排妥当之后再下一个s, 每次子任务都是sq减去上一个n的后面形成的，所以我们有f(now) = O(1) + f(sq - now - 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].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;
}
const ll mod = MOD;
ll quickPow(ll base, ll expo){
    ll ans = 1;
    while (expo){
        if(expo & 1)(ans *= base) %= mod;
        expo >>= 1;
        base = base * base;
        base %= mod;
    }
    return ans % mod;
}
ll C(ll n, ll m){
    if(n < m)return 0;
    ll x = 1, y = 1;
    if(m > n - m)m = n - m;
    rep(i ,0 , m - 1){
        x = x * (n - i) % mod;
        y = y *  (i + 1) % mod;
    }
    return x * quickPow(y, mod - 2) % mod;
}

int n, m, k;
int a[limit];
void calc(int x){
    vector<int>v(x);
    iota(v.begin(), v.end(), 0);
    do{
        rep(i,0, x - 1){
            int d = i + v[i];
            if(int(sqrt(d)) * int(sqrt(d)) != d){
                goto label;
            }
        }
        for(auto &it : v){
            cout<<it<<" ";
        }
        cout<<endl;
        break;

label:
        int x = 1;
    }while(next_permutation(v.begin(), v.end()));
}
void solve(){
    cin>>n;
    int now = n - 1;
    vector<pi(int, int)>v;
    v.reserve(n + 1);
    while(now >= 0){
        int sq = sqrt(2 * now);
        sq = sq * sq;
        v.push_back({sq - now, sq});
        now = sq - now - 1;
    }
    for(auto  & [key, val] : v | ranges::views::reverse){
        rep(i,key, val){
            a[i] = val - i;
        }
    }
    rep(i,0,n-1){
        cout<<a[i]<<" ";
    }
    cout<<endl;
};
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
//    rep(i,3,12){
//        calc(i);
//    }
    int kase;
    cin>>kase;
    while (kase--)
        solve();
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}
AC Code

然后D题，是说有2^n个人初始按照顺序两两进行比赛，第一次比赛的次序是一定的，你每次可以问两个人，可以得知两个人赢的次数谁多，或者相同

首先在开头，我们有两条规律可以铭记在心

第一，两个赢的次数相同的人，二者皆无法成为最后胜者，这个很好理解，如果有人赢了，那么那个人一定赢的最多

第二，对于一个赢的，我们可以得知他最少赢了1场，而且他第一场比赛的对象因为是确定的，我们可以确认那个对象出局

有了这两条似乎就很好搞了

这个有点坑爹，首先是这个样例很让人迷惑，我纠结了好久这玩意儿咋tm推出来的

首先1和4比较，4胜出，那么说明3和1出局，1和6相等，说明6和1都没有笑到最后

然后5和7比较，咋就7赢了呢？6，8最后输了是肯定的，5也输了，这边是7，但是那个4是咋搞的。

后来发现，哦，原来8个人我可以取5-6次，那没事了

然后就bfs呗，拿两个人，1次比较可以干掉2个人，一次拿4个人，2次可以干掉3个，然后剩下的一个重复这个过程，总次数不超过1/3 * ceil(2 ^ (n + 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].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;
}
const ll mod = MOD;
ll quickPow(ll base, ll expo){
    ll ans = 1;
    while (expo){
        if(expo & 1)(ans *= base) %= mod;
        expo >>= 1;
        base = base * base;
        base %= mod;
    }
    return ans % mod;
}
ll C(ll n, ll m){
    if(n < m)return 0;
    ll x = 1, y = 1;
    if(m > n - m)m = n - m;
    rep(i ,0 , m - 1){
        x = x * (n - i) % mod;
        y = y *  (i + 1) % mod;
    }
    return x * quickPow(y, mod - 2) % mod;
}

int n, m, k;
int a[limit];
int ask(int x, int y){
    cout<<"? "<<x<<" "<<y<<endl;
    cout.flush();
    int xx;
    cin>>xx;
    return xx;
}
void solve(){
    cin>>n;
    deque<int>q;
    rep(i,1,(1 << n)){
        q.push_back(i);
    }
    while(q.size() >= 4){
        int fst = q.front();
        q.pop_front();
        int scd = q.front();
        q.pop_front();
        int thd = q.front();
        q.pop_front();
        int frt = q.front();
        q.pop_front();
        int result = ask(fst, thd);
        if(result == 0){//同时扔掉fst和thd, 这两者不可能相同
            int res = ask(scd, frt);
            if(res == 1){
                q.push_back(scd);
            }else{
                q.push_back(frt);
            }
        }else if(result == 1){
            int res = ask(fst, frt);
            if(res == 1){
                q.push_back(fst);
            }else{
                q.push_back(frt);
            }
        }else if(result == 2){
            int res = ask(scd, thd);
            if(res == 1){
                q.push_back(scd);
            }else{
                q.push_back(thd);
            }
        }
    }
    if(q.size() >= 2){
        int x = q.front();
        q.pop_front();
        int y = q.front();
        q.pop_front();
        if(ask(x, y) == 1){
            cout<<"! "<<x<<endl;
        }else{
            cout<<"! "<<y<<endl;
        }
    }else{
        cout<<"! "<<q.front()<<endl;
    }
};
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
//    rep(i,3,12){
//        calc(i);
//    }
    int kase;
    cin>>kase;
    while (kase--)
        solve();
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}
AC Code

 

标签：rep,int,题解,ll,base,812,mod,div2,define
From： https://www.cnblogs.com/tiany7/p/16709724.html

相关文章

  • EFCore 6级联删除问题解决Database operation expected to affect 1 row(s) but actua
    异常信息：Databaseoperationexpectedtoaffect1row(s)butactuallyaffected0row(s).Datamayhavebeenmodifiedordeletedsinceentitieswereloaded.See......
  • SP2128题解
    题意共有\(t\)个\(n\timesm\)的由.、x、o组成的字符矩阵。设矩阵中连续\(k\)格为x小A加一分，连续\(k\)格为o小B加一分。正文\(\Large{时间复杂度：}\l......
  • 【Coel.解题报告】【没事找事】CSP-S2 真题解析
    昨天刚考完CSP-S1，反正没什么想做的（最近好颓废…），来复盘一下。本次比赛评价（转载）：CSP-S1是由CCF自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「基数排序......
  • 牛客题解 珂朵莉与宇宙
    链接：https://ac.nowcoder.com/acm/problem/14600来源：牛客网题解作者岛田小雅这道题很仁慈地直接告诉了我们子区间的个数，如果直接暴力遍历所有的子区间，复杂度是\(O(\f......
  • PostgreSQL常见问题解决
    psql找不到动态链接库 2022-09-19 psql:symbollookuperror:psql:undefinedsymbol:PQsetErrorContextVisibility      解决办法：  找到PG......
  • 第十四章 Redis应用问题解决
    一、缓存穿透1.问题描述key对应的数据在数据源并不存在，每次针对此key的请求从缓存获取不到，请求都会压到数据源，从而可能压垮数据源。比如用一个不存在的用户id获取用户信......
  • 牛客题解 武藏牌牛奶促销
    链接：https://ac.nowcoder.com/acm/problem/13592来源：牛客网题解作者岛田小雅看到这一题我第一反应想直接模拟，看了下范围感觉可行，但是如果遇到无法判断的INF就会导致......
  • P1559 运动员最佳匹配问题 题解
    本篇使用\(\text{KM}\)算法求解。对于\(\text{KM}\)算法步骤如下：首先要用邻接矩阵存二分图，然后用贪心算法初始化标杆，运用匈牙利算法找到完美匹配，如果找不到则修改标......
  • SWERC 2021-2022 部分简要题解
    比赛链接：https://codeforc.es/contest/1662。前言「部分」「简要」题解。A-OrganizingSWERC直接判断。C-EuropeanTrip如果不考虑限制，我们可以直接矩乘。考虑......
  • 【题解】CF1311E Construct the Binary Tree
    题目链接-->Problem-E-Codeforces题目大意给定\(n\)和\(d\)，你需要构造一棵\(n\)个点的二叉树满足所有点的深度之和恰好为\(d\)。\(2≤n,d≤5000\)。分析......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99