首页 > 其他分享 >cf edu 1600

cf edu 1600

时间：2023-08-04 20:22:11浏览次数：32  
标签：res cin int 1600 pos long cf solve edu

600A. Extract Numbers

划分一下然后特判即可。

#include<bits/stdc++.h>

using namespace std;

int32_t main() {
    string s , t = "";
    cin >> s;
    vector<string> a , b;
    s += ";";
    for( auto i : s ){
        if( i == ',' or i == ';' ){
            if( t == "0" ) a.push_back(t);
            else if( t == "" ) b.push_back(t);
            else if( t[0] == '0' ) b.push_back(t);
            else{
                int f = 1;
                for( auto j : t ){
                    if( j >= '0' && j <= '9' ) continue;
                    f = 0;
                    break;
                }
                if(f) a.push_back(t);
                else b.push_back(t);
            }
            t = "";
        }
        else t += i;
    }
    if( a.empty() ) cout << "-\n";
    else{
        cout << "\"" << a.front();
        for( int i = 1 ; i < a.size() ; i ++ )
            cout << "," << a[i];
        cout << "\"\n";
    }

    if( b.empty() ) cout << "-\n";
    else{
        cout << "\"" << b.front();
        for( int i = 1 ; i < b.size() ; i ++ )
            cout << "," << b[i];
        cout << "\"\n";
    }
    return 0;
}

1342C. Yet Another Counting Problem

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 40005;
int len, p[N];

void build(int a, int b) {
    len = a * b, p[0] = 0;
    for (int i = 1; i <= len; i++)
        p[i] = p[i - 1] + ((i % a) % b != (i % b) % a);
    return;
}

int query(int l) {
    return p[len] * (l / len) + p[l % len];
}

int query(int l, int r) {
    return query(r) - query(l - 1);
}

void solve() {
    int a, b, q;
    cin >> a >> b >> q;
    build(a,b);
    for (int l, r; q; q--)
        cin >> l >> r, cout << query(l, r) << " ";
    cout << "\n";
    return;
}

int32_t main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

1455D. Sequence and Swaps

可以注意到的是每次能够被交换的数一定是递增的，同理每次能够放回去的数也是递增的，所以选择的\(i\)一定是递增的。所以我们从小到大枚举\(i\)遇见可以交换的就一定要交换，统计交换次数即可。

#include<bits/stdc++.h>

using namespace std;

#define mp make_pair

#define int long long
const int N = 205;
int g[N][N][N], a[N], b[N];

int read() {
    int x = 0, ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x;
}

void solve() {
    int n = read(), x = read();
    vector<int> a(n);
    for (auto &i: a) i = read();
    if(is_sorted(a.begin(), a.end())){
        cout << "0\n";
        return;
    }
    int res = 0;
    for( int i = 0 ; i < n ; i ++ ){
        if( a[i] > x ) swap( a[i] , x ) , res ++;
        if(is_sorted(a.begin(), a.end())) break;
    }
    if(is_sorted(a.begin(), a.end())) cout << res << "\n";
    else cout << "-1\n";
    return;
}

int32_t main() {
    for (int t = read(); t; t--)
        solve();
    return 0;
}

1398C. Good Subarrays

求前缀和后，则题目要求\(a_r-a_{l-1}=r-(l-1)\)。所以可以转换为\(a_r-r=a_{l-1}-(l-1)\)。这样我们统计\(a_i-i\)出现的次数，然后用组合数就可以计算了。

#include<bits/stdc++.h>

using namespace std;

#define mp make_pair

#define int long long

int res = LLONG_MIN;
vector<int> v, f;
vector<vector<int>> e;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> a;
    a.push_back(0);
    for (auto i: s)
        a.push_back(i - '0');
    for( int i = 1 ; i <= n ; i ++ )
        a[i] += a[i-1];
    map<int, int> cnt;
    for (int i = 0; i <= n; i++)
        cnt[a[i] - i]++;
    int res = 0;
    for (auto [k, v]: cnt)
        res += v * (v - 1) / 2;
    cout << res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

1389B. Array Walk

我们枚举向左跳\(i\)步，则向右跳\(k-i\)步，所以最终可以跳到\(k-2i\)步。然后就是选择最大的两个相邻的数反复走\(i\)次即可。

#include<bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n, k, z;
    cin >> n >> k >> z;
    vector<int> a(n);
    for (auto &i: a) cin >> i;
    int res = 0;
    for (int i = 0; i <= z; i++) {
        int pos = k - 2 * i;
        if( pos < 0 ) continue;
        int sum = 0 , m = 0;
        for( int i = 0 ; i <= pos ; i ++ ){
            if(  i < n-1 ) m = max( m , a[i] + a[i+1] );
            sum += a[i];
        }
        res = max( res , sum + m * i );
    }
    cout << res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

1373D. Maximum Sum on Even Positions

首先要想到的是有效的翻转区间一定是一段长度为偶数的区间。

如果翻转的区间是以奇数开头的，则对于区间内所有奇数下标的点\(i\)相当于\(a[i]-a[i-1]\)的贡献。

而我们要选择一个字段贡献最大，这样就转换成了最大字段和的问题。

翻转区间以偶数开头类似，只是贡献变为了\(a[i-1]-a[i]\)

#include<bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n, ans = 0, res = 0;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i % 2 == 0) res += a[i];
    }
    for (int i = 1, cnt = 0; i < n; i += 2) {
        cnt = max(0ll, cnt + a[i] - a[i - 1]);
        ans = max(ans, cnt);
    }
    for (int i = 2, cnt = 0; i < n; i += 2) {
        cnt = max(0ll, cnt + a[i - 1] - a[i]);
        ans = max(ans, cnt);
    }
    cout << ans + res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

1334C. Circle of Monsters

第一个攻击的怪兽无法接受前一个怪兽造成的爆炸伤害。最朴素的的方法自然是枚举第一个攻击的怪兽，然后依次攻击后面的怪兽。其实可以发现的是，每一个怪兽造成的受到的爆炸伤害是\(\min(a[i],b[i-1])\)。所以其实我么可以贪心的选择受到爆炸伤害最小的怪兽作为第一个怪兽。

#include<bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int cnt = 0, n, inc = LLONG_MAX;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++)
        cin >> a[i] >> b[i];
    for (int i = 0, ni, dec; i < n; i++) {
        ni = (i + 1) % n;
        dec = min(a[ni], b[i]);
        cnt += a[ni] - dec;
        inc = min(inc, dec);
    }
    cout << cnt + inc << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

1295C. Obtain The String

首先我们对\(s\)串来进行预处理，处理出\(nex[i][j]\)数组表示位置\(i\)之后字母\(j\)第一次出现的位置。

这样的话，我们用一个指针标记对于\(s\)串当前匹配的到位置，然后每次贪心的向后移动即可。

#include<bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    string s, t;
    cin >> s >> t;
    vector nxt(s.size() + 1, vector<int>(26, INT_MAX));
    for (int i = s.size() - 1; i >= 0; i--) {
        nxt[i] = nxt[i + 1];
        nxt[i][s[i] - 'a'] = i;
    }
    int res = 1;
    for (int i = 0, pos = 0; i < t.size() && res < INT_MAX; i++) {
        if (pos == s.size()) pos = 0, res++;
        if (nxt[pos][t[i] - 'a'] == INT_MAX)
            pos = 0, res++;
        if (nxt[pos][t[i] - 'a'] == INT_MAX && pos == 0) {
            res = INT_MAX;
            break;
        }
        pos = nxt[pos][t[i] - 'a'] + 1;
    }
    if (res == INT_MAX) res = -1;
    cout << res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

1303C. Perfect Keyboard

我自己的想法实际上是建图，然后跑一个类似拓扑序的东西？但是看题解明显要简单很多。

题解的思路其实就是贪心的放就可以了。我们遍历密码序列，序列中每一个元素都有两种状态，在答案序列中和不在答案序列中。如果在答案序列中就要检查和密码序列的上一位是否相邻？如果不在则一点要放在密码序列上一位的两侧，检查两侧是否可以放下。

#include<bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    string s;
    cin >> s;
    vector<bool> used(26);
    used[s[0] - 'a'] = true;
    string t(1, s[0]);
    int pos = 0;
    for (int i = 1; i < s.size(); i++) {
        if (used[s[i] - 'a']) {
            if (pos > 0 && t[pos - 1] == s[i]) pos--;
            else if (pos + 1 < t.size() && t[pos + 1] == s[i]) pos++;
            else {
                cout << "NO\n";
                return;
            }
        } else {
            if (pos == 0) t = s[i] + t;
            else if( pos == t.size() - 1 ) t += s[i] ,pos ++;
            else {
                cout << "NO\n";
                return ;
            }
            used[s[i]-'a'] = true;
        }
    }
    for( char i = 'a' ; i <= 'z' ; i ++ ) if( !used[i-'a'] )
        t += i;
    cout << "YES\n" << t << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

1327C. Game with Chips

注意到限制并不是\(2(n+m)\)而是\(2nm\)。点的位置根本不影响答案，先把所有的点移动到一个角，然后遍历整张图即可。

#include<bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    int n, m, k;
    cin >> n >> m >> k;
    if( n * m == 1 ){
        cout << "0\n";
        return 0;
    }
    string res = "";
    for (int i = 1; i < n; i++) res += "U";
    for (int i = 1; i < m; i++) res += "L";
    for (int i = 1; i <= n; i++) {
        if (i & 1) {
            for (int j = 1; j < m; j++)
                res += "R";
        } else {

            for (int j = 1; j < m; j++)
                res += "L";
        }
        if ( i != n )
            res += "D";
    }
    cout << res.size() << "\n" << res << "\n";
    return 0;
}

标签：res,cin,int,1600,pos,long,cf,solve,edu
From： https://www.cnblogs.com/PHarr/p/17606981.html

相关文章

  • [刷题笔记] CF1132F Clear the String & [CQOI2007] 涂色
    Problem1Problem2双倍经验qwqDescription初始时数组为空，每次可以选择一个区间\(l-r\)将其赋为同一个值，赋的值可以覆盖，给定数组的目标形式，求至少经过多少次操作使得空数组变成目标形式。Solution我们发现每次选择一个区间，大区间包含小区间，小区间可以推到大区间。因此考虑区间......
  • CF 下分记录
    7.27edu152\(+173=2048\)B没细看数据范围WA了一次D没判\(i-1=0\)WA了一次E.MaxtotheRightofMin考虑增大右端点，维护每个左端点的合法性当右端点从\(r-1\)增大到\(r\)时，若\(a[r-1]<a[r]\)：\(r\)只能作为区间最大值。记上一个\(>a[r]\)的位置是\(p\)，那......
  • 对于Spring中的@Scheduled注解，cron表达式的格式与传统的cron表达式有所不同。
    @Scheduled(cron="00*/1**?")对于Spring中的@Scheduled注解，cron表达式的格式与传统的cron表达式有所不同。Spring的cron表达式包含6个字段，分别是秒分时日月星期。其中，秒是可选的。根据您提供的@Scheduled(cron="00*/1**?")，这表示任务会在每个小时的0分0秒执......
  • 探秘企业DevOps一体化平台建设终极形态丨IDCF
    笔者从事为企业提供研发效能改进解决方案相关工作十几年，为国内上百家企业提供过DevOps咨询及解决方案落地解决方案，涉及行业包括：金融、通信、制造、互联网、快销等多种行业。DevOps的核心是研发效能改进，效能的提升离不开强大工具的支撑，因此在DevOps如火如荼的今天，承载研发效能改进的......
  • 大数据不就是写sql吗？—— Hive：把sql解析后用MapReduce跑 SparkSQL：把sql解析后
    应届生小祖参加了个需求分析会回来后跟我说被产品怼了一句： "不就是写SQL吗，要那么久吗" 我去，欺负我小弟，这我肯定不能忍呀，于是我写了一篇文章发在了公司的wiki： 贴出来给大家看看，省略了一些敏感的内容。当然内部版言辞也会温和一点，嘻嘻在哪里写SQL？ 这个问题高级点的问法是用哪种SQ......
  • Educational 151 DIV2 T3 strong password
    T3strongpassword就是对于输入的每一个\(l,r\),我们遍历\(s[l]~s[r]\)，对于每次遍历，我们设置一个临时指针\(cur\),然后通过指针右移寻找所需要的值在外面我们弄两个指针，分别代表每次遍历\([l,r]\)的区间的指针\(nmx\)和全局指针\(mx\)我们用临时指针更新单次区间的......
  • Educational Codeforces Round 38 C- F
    EducationalCodeforcesRound38C-Fhttps://codeforces.com/contest/938今天写出了三题ovoC.ConstructingTests多画几个图就能发现，对于\(n\timesn\)的正方形来说，要使得\(m\timesm\)的子正方形至少有一个\(0\)，则最少的\(0\)个数为\(\lfloor\frac{n}{m}\rfloo......
  • IfcFaceOuterBound
    IfcFaceOuterBound实体定义注：定义依据ISO/CD10303-42:1992面外边界是面边界的一个特殊子类型，它承载了在面上定义外边界的附加语义。此类表面的边界不得超过一个。注：实体适用于ISO10303-42中定义的face_outer_bound。IFC1.0中的新实体  Attributeinheritance#Attr......
  • CF1610F Mashtali a Space Oddysey
    撞了个题，还做过。将所有奇度给他建个边权为\(1\)的虚边和对应的虚点，图上一定存在欧拉回路，给欧拉回路定向，记录这个边的入边权值为\(1\)还是为\(2\)，优先走上一次走的边权。这样跑的话，会将边权抵消，可以取到答案上界，即相连边权为奇数的点数。#include<bits/stdc++.h>usingna......
  • CF626F. Group Projects
    我是傻逼。哈哈，现在还想不到拆贡献，小丑一个。人的输入顺序不重要，先排个序。这个\(\text{max}-\text{min}\)可以看作两两之差的和。定义\(f_{i,j,k}\)表示考虑前\(i\)个人，有\(j\)个组没有确定最大值，目前不和谐度之和为\(k\)的方案数，转移分四种情况：单独构成完整的一......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99