首页 > 其他分享 >Codeforces Edu Round 106 Div2

Codeforces Edu Round 106 Div2

时间：2023-01-12 05:00:10浏览次数：47  
标签：cnt int ll Codeforces long limit 106 Div2 define

解题

A. Domino on Windowsill

这个题给一个2xn的方格，一个行有k1个白块，第二行有k2个白块，那么现在有w个2x1的白块和b个2x1黑块，白对白，黑对黑，问能不能全放下
这个就是判断下白色的加起来和黑色的加起来/2向下取整有没有比w和b要大，因为没给布局

#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (2000000 + 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;
}
constexpr ll mod = 1e9 + 7;
ll quick_pow(ll base, ll expo){
    ll ans = 1;
    while(expo){
        if(expo & 1) ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans;
}
int n,m;
int a[limit];
void solve(){
    int k1,k2,w,b;
    cin>>n>>k1>>k2>>w>>b;
    int suma = k1 + k2;
    int sumb = (n << 1) - suma;
    if(suma / 2 >= w and sumb / 2 >= b) cout<<"YES"<<endl;
    else 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\n";
    return 0;
}

B. Binary Removals

这个题介绍花里胡哨，大意是给一个01串，可以删除一些0或者1，但是删除的位置不能连续，即间隔1，问是否能让整个数组sorted

首先，我们很容易想到，如果已经是sorted就肯定可以了（废话）

其次，我们观察样例，发现1100为no，大胆些了一发，然后wa，这是为什么呢？

后来发现结论浅了，连续出现两个相同的就意味着有一个要留在原来的位置上不能被删除，那么如果是00....11还好，但如果是11...00的话，显然就不行

所以暴力判断下就ok

#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (2000000 + 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;
}
constexpr ll mod = 1e9 + 7;
ll quick_pow(ll base, ll expo){
    ll ans = 1;
    while(expo){
        if(expo & 1) ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans;
}
int n,m;
int a[limit];
void solve(){
    string str;
    cin>>str;
    n = str.length();
    rep(i,1,n){
        a[i] = str[i - 1] - '0';
    }
    if(is_sorted(a + 1, a + 1 + n)){
        cout<<"Yes"<<endl;
        return;
    }
    int cnt = 0;
    per(i,2,n){
        cnt += !(a[i] + a[i - 1]);
        if(cnt and a[i] + a[i - 1] == 2){
            cout<<"No"<<endl;
            return;
        }
    }
    cout<<"Yes"<<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\n";
    return 0;
}

C. Minimum Grid Path

这个是问给nxn矩阵，给出一些费用a[i]，每次可以往两个方向走若干步，每次走的费用为步长 * a[i]，走完一步需要改变方向，从(0, 0)走到(n,n)，可以在某一步之前提前到达终点

问最少费用

那么很显然，如果我们有n步，那么我们要想让两个维度都到达n，平均每一步要走n / (n / 2)步，但是考虑到费用不同，所以我们假设我们n个数字，全部用完。其他的步，我们先走1步占位置，然后剩下的步全都给那个费用最小的。

除了这个，我们还要考虑提前到达的地方，这个时候我们可以维护一个下标和一个一个值，初始按照前面的步骤分配步数。我们枚举停止点i，每次往前，先减掉这点的贡献，然后再在这一步可以到达的前面，选取一个费用最小的，把当前的步数全都记到那个最小的位置去，然后记录一下min就好，下标的话，我们可以选取set + pair维护，不复杂

#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (2000000 + 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;
}
constexpr ll mod = 1e9 + 7;
ll quick_pow(ll base, ll expo){
    ll ans = 1;
    while(expo){
        if(expo & 1) ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans;
}
#define int ll
int n,m;
int a[limit];
int cnt[limit];
void solve(){
    cin>>n;
    rep(i,1,n){
        cin>>a[i];
        cnt[i] = 0;
    }
    //01走
    ll ans = 0;
    multiset<pi(int, int)>pa,pb;
    int even = 0;
    int odd = 0;
    rep(i,1,n){
        if(i & 1){
            pa.insert({a[i], i});
            ++odd;
        }else{
            pb.insert({a[i], i});
            ++even;
        }
        cnt[i] = 1;
    }

    even = n - even;
    odd = n - odd;
    auto [_, id] = *pa.begin();
    auto [__, id2] = *pb.begin();
    cnt[id] += odd;
    cnt[id2] += even;
    rep(i,1,n){
        ans += cnt[i] * a[i];
    }
    ll res = ans;
    per(i,3,n){
        res -= cnt[i] * a[i];
        if(i & 1){
            pa.extract({a[i], i});
            auto [val, id] = *pa.begin();
            cnt[id] += cnt[i];
            res += cnt[i] * val;
        }else{
            pb.extract({a[i], i});
            auto [val, id] = *pb.begin();
            cnt[id] += cnt[i];
            res += cnt[i] * val;
        }
        ans = min(res, 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\n";
    return 0;
}

以下是赛后补题，不想弄混了，每次写不出来题很难受，但是其实挣扎的本身是一次思考的过程，如果能在挣扎中想明白了，那么这比去看题解有意义得多。

D. The Number of Pairs

问c * lcm(a,b) - d * gcd(a,b) == x，这样ab有几对？

这个题数据范围1e7，一眼筛，但是我数学太差了。

首先我们

设g = gcd(a,b)
那么有c * a * b / g - d * g == x
根据裴蜀定理，我们那么x必然是gcd(a,b)的其中一部分
然后转化之后的有a / g * b / g这部分，这部分一定为质数，所以，根据裴蜀定理，有x整除g，所以我们枚举g
然后把化简完的柿子((x / g) + d) / c枚举以下，然后找出质因子个数，每个质因子可能参与和不参与，所以最后答案是2 ^ 柿子的质因子个数，然后因数分解完累加以下就行

思路来自于网络，不过感觉很妙

#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (20000000 + 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;
}
constexpr ll mod = 1e9 + 7;
ll quick_pow(ll base, ll expo){
    ll ans = 1;
    while(expo){
        if(expo & 1) ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans;
}
int vis[limit];
int cnt[limit];
void init(int n)
{
    for(int i = 2; i <= n;i++)
    {
        if(!vis[i])
        {
            cnt[i] = 1;
            for(int j = i + i;j <= n;j += i) vis[j] = true,cnt[j]++;
        }
    }
}
//赛后补题，非抄袭
int n,m;
int a[limit];
void solve(){
    ll c,d,x;
    cin>>c>>d>>x;
    ll ans = 0;
    int it = 0;
    for(int i = 1; i * i <= x; ++i){
        if(x % i == 0){
            a[++it] = i;
            if(x / i != i){
                a[++it] = x / i;
            }
        }
    }
    rep(i,1,it){
        auto numer = x / a[i] + d;
        if(numer % c == 0){
            ans += 1ll * 1ll << cnt[numer / c];
        }
    }
    cout<<ans<<endl;
};
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    init(2e7 + 3);
    int kase;
    cin>>kase;
    while (kase--)
        invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}

感觉这是我熟悉的cf风格，两年前的D题还不是计数的天下，偶尔也会有点算法，怀念！

标签：cnt,int,ll,Codeforces,long,limit,106,Div2,define
From： https://www.cnblogs.com/tiany7/p/17045331.html

相关文章

  • [Codeforces Round #822 (Div. 2)](https://codeforces.com/contest/1734)
    CodeforcesRound#822(Div.2)ProblemF.ZerosandOnes解法定义：\(f(x)\)为在\(S\)串中位置为\(x\)的值。显然\(f(x)\in0,1\)有一重要性质：若\(f(x)\)为1，那么二进制......
  • Codeforces Round #843 (Div. 2)
    Preface难得的7点场CF，结果反而遇上了我最困的时候（吃完晚饭血糖上来就贼困，我一般反而凌晨场比较清醒）但是这场表现还可以，写的题基本都是一发入魂而且速度也比较快比较可惜......
  • 【Codeforces 173B】 B. Chamber of Secrets
    【Codeforces173B】B.ChamberofSecretshttps://codeforces.com/problemset/problem/173/B题意+分析来自\(OI-wiki\)这题主要难度就是读题...还有注意初始方向......
  • Codeforces Round #843 (Div. 2)
    A-GardenerandtheCapybaras题意给出字符串S，S只由字符a,b组成，问怎么切分可以使字符串分为小大小，大小大这种的三段。思路在2~n-1的范围内找到字符a的位置，如果里......
  • Codeforces Round #843 (Div. 2)
    题目链接Atag：构造，分类讨论核心思路我们其实可以发现我们要是分很多情况去讨论abc,这题就不好做。所以我们可以假设a和b就是我们字符串的两个端点，这样题目就很好做了......
  • Codeforces Round #843 (Div. 2) Problem C
    C.InterestingSequencetimelimitpertest1secondmemorylimitpertest256megabytesinputstandardinputoutputstandardoutput  Petyaandhisfr......
  • Codeforces 1278 F Cards 增强版 题解 (斯特林数，推式子)
    原题链接增强版链接增强版中k=1e7为啥网上题解的式子都那么长啊.jpg首先令\(p=\frac1m\)。求某个数的次幂的题通常都是无脑转下降幂：\(x^k=\sum_{i=0}^kS_2(k,i)x^{\u......
  • Codeforces Round #823 (Div. 2)
    A.B.C.DCodeforcesRound#823(Div.2)A.Planets-签到题意题意是一些卫星在一些轨道上，操作1花费1摧毁一个卫星，操作2花费\(y\)摧毁一个轨道上的所有卫星，问摧......
  • 「Codeforces」寒假训练 2023 #4
    A.Coprime原题链接#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=2e5+10;intt,n,ans;map<int,int>mp;intgcd(intu,......
  • Educational Codeforces Round 1
    Problem-A-Codeforcesvoidsolve(){ios;intt;cin>>t;while(t--){intn;cin>>n;intsum=n*(n+......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99