首页 > 其他分享 >Codeforces Round 888 (Div. 3)

Codeforces Round 888 (Div. 3)

时间：2023-07-30 23:25:14浏览次数：41  
标签：__ const int 888 Codeforces long Div sizeof define

传送门

A Escalator Conversations

读懂题意即可

/*
    Author : north_h
    File : A.cpp
    Time : 2023/7/26/12:32
                    _   _         _     
   _ __   ___  _ __| |_| |__     | |__  
  | '_ \ / _ \| '__| __| '_ \    | '_ \ 
  | | | | (_) | |  | |_| | | |   | | | |
  |_| |_|\___/|_|   \__|_| |_|___|_| |_|
                            |_____|     
*/
#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.begin(),a.end()
#define int128 __int128
#define endl '\n'
const int N = 10010;
const int M = 110;
const int MOD = 998244353;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace std;

void solve() {
    int n, m, k, H;
    cin >> n >> m >> k >> H;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (abs(x - H) % k == 0 && abs(x - H) / k < m&&x!=H)ans++;
    }
    cout << ans << endl;
}

int main() {
    IOS;
    int h_h = 1;
    cin >> h_h;
    while (h_h--)solve();
    return 0;
}

B Parity Sort

排个序判断每个数所在位置的就是否相同即可

/*
    Author : north_h
    File : B.cpp
    Time : 2023/7/26/12:47
                    _   _         _     
   _ __   ___  _ __| |_| |__     | |__  
  | '_ \ / _ \| '__| __| '_ \    | '_ \ 
  | | | | (_) | |  | |_| | | |   | | | |
  |_| |_|\___/|_|   \__|_| |_|___|_| |_|
                            |_____|     
*/
#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.begin(),a.end()
#define int128 __int128
#define endl '\n'
const int N = 10010;
const int M = 110;
const int MOD = 998244353;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    set<int> b, c;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] & 1)b.insert(i);
        else c.insert(i);
    }
    sort(a.begin() + 1, a.end());
//    for (int i = 1; i <= n; i++)cout << a[i] << ' ';
//    cout << endl;
    for (int i = 1; i <= n; i++) {
        if (a[i] & 1 && !b.count(i)) {
            cout << "NO" << endl;
            return;
        }
        if (!a[i] & 1 && !c.count(i)) {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

int main() {
    IOS;
    int h_h = 1;
    cin >> h_h;
    while (h_h--)solve();
    return 0;
}

C Tiles Comeback

这个题也有两种情况，一是只有一个色块，另一种是由多个色块（但可以贪心的选两个色块就行了），要记住要从起点开始

/*
    Author : north_h
    File : C.cpp
    Time : 2023/7/26/12:53
                    _   _         _     
   _ __   ___  _ __| |_| |__     | |__  
  | '_ \ / _ \| '__| __| '_ \    | '_ \ 
  | | | | (_) | |  | |_| | | |   | | | |
  |_| |_|\___/|_|   \__|_| |_|___|_| |_|
                            |_____|     
*/
#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.begin(),a.end()
#define int128 __int128
#define endl '\n'
const int N = 10010;
const int M = 110;
const int MOD = 998244353;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace std;

void solve() {
    map<int, int> mp;
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)cin >> a[i];
    int now = a[1];
    int cnt = 0;
    bool ok = false;
    bool f = false;
    for (int i = 1; i <= n; i++) {
        if (a[i] == now)cnt++;
        if (cnt == k && !ok) {
            now = a[n];
            cnt = 0;
            ok = true;
            if (i == n || (i != n && a[n] == a[i])) {
                cout << "YES" << endl;
                return;
            }
            //cout<<i<<endl;
        }
        else if (cnt == k && ok && !f) {
            f = true;
        }
    }
    if (ok && f)cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main() {
    IOS;
    int h_h = 1;
    cin >> h_h;
    while (h_h--)solve();
    return 0;
}

D Prefix Permutation Sums

感觉赛时应该可以写出来，思路没错，就是利用一直前缀和数组那他的原数组还原出来，就会出现两种情况一种是丢失了最后一个，这种肯定可以还原出来原数组，另一种是丢失其他位置的，就要用比n还大的那个数或者重复出现的那个数去把排列里面还缺少的两个数凑出来，凑不出来就不行

/*
    Author : north_h
    File : D.cpp
    Time : 2023/7/26/13:29
                    _   _         _     
   _ __   ___  _ __| |_| |__     | |__  
  | '_ \ / _ \| '__| __| '_ \    | '_ \ 
  | | | | (_) | |  | |_| | | |   | | | |
  |_| |_|\___/|_|   \__|_| |_|___|_| |_|
                            |_____|     
*/
#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define int long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define int128 __int128
#define endl '\n'
const int N = 10010;
const int M = 110;
const int MOD = 998244353;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> vis(n + 1);
    vector<int> a(n + 1);
    vector<int> s(n + 1);
    for (int i = 1; i <= n - 1; i++)cin >> s[i];
    if (n == 2) {
        if (s[1] == 1 || s[1] == 3 || s[1] == 2)cout << "YES" << endl;
        else cout << "NO" << endl;
        return;
    }
    set<int> st;
    vector<int> ans;
    for (int i = 1; i <= n - 1; i++) {
        int x = s[i] - s[i - 1];
        if (x <= n) {
            if(st.count(x))ans.push_back(x);
            else st.insert(x);
        } else ans.push_back(x);
    }
    if (!ans.size())cout << "YES" << endl;
    else if (ans.size() > 1 || ans[0] > 2 * n)cout << "NO" << endl;
    else {
        for (int i = 1, j = ans[0] - 1; i < j; i++, j--) {
            if (!st.count(i) && !st.count(j) && i <= n && j <= n) {
                cout <<   "YES" << endl;
                return;
            }
        }
        cout << "NO" << endl;
    }
}

int32_t main() {
    IOS;
    int h_h = 1;
    cin >> h_h;
    while (h_h--)solve();
    return 0;
}

E Nastya and Potions

这个题的题意就是对于每一种药水给你两种选择，要么直接购买，要么用其他已经有的药水配出来，就可以直接进行搜索，但是要剪枝，加入记忆化，只要已经找到了这个的最小值，就不用搜了直接返回就可以，会大大的减少时间，少用memset，感觉有点慢，要么for循环赋初值，要么使用vector

/*
Author : north_h
File : E.cpp
Time : 2023/7/27/12:11
                  _   _         _     
 _ __   ___  _ __| |_| |__     | |__  
| '_ \ / _ \| '__| __| '_ \    | '_ \ 
| | | | (_) | |  | |_| | | |   | | | |
|_| |_|\___/|_|   \__|_| |_|___|_| |_|
                          |_____|     
*/
//#pragma GCC optimize(3)

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.begin(),a.end()
#define int128 __int128
#define endl '\n'
const int N = 200010;
const int M = 110;
const int MOD = 998244353;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace std;

ll a[N];
int vis[N];
ll cost[N];
vector<int> g[N];
int n, p;

ll dfs(int u) {
    if (vis[u])return cost[u];
    if (!g[u].size())return a[u];
    for (auto i: g[u]) {
        cost[u] += dfs(i);
    }
    cost[u] = min(cost[u], a[u]);
    vis[u]=true;
    return cost[u];
}

void solve() {
    cin >> n >> p;
    for (int i = 1; i <= n; i++)g[i].clear();
    for(int i=1;i<=n;i++)a[i]=0,vis[i]=false,cost[i]=0;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= p; i++) {
        int x;
        cin >> x;
        vis[x] = true;
        cost[x] = 0;
    }
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        for (int j = 0; j < x; j++) {
            int y;
            cin >> y;
            g[i].push_back(y);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i])cost[i] = dfs(i);
        cout << cost[i] << ' ';
    }
    cout << endl;
}


int main() {
    IOS;
    int h_h = 1;
    cin >> h_h;
    while (h_h--)solve();
    return 0;
}

标签：__,const,int,888,Codeforces,long,Div,sizeof,define
From： https://www.cnblogs.com/north-h/p/17592332.html

相关文章

  • CF1855B Longest Divisors Interval 题解
    原题链接：https://codeforces.com/contest/1855/problem/B题意：给定一个正整数n,找到满足该条件的区间[l,r]的长度的最大值：对于任意l<=i<=r，n均为i的倍数（多组数据）。思路：如果n是奇数，答案显然是1，因为任意两个连续的正整数一定会有一个2的倍数。将这一结论进行推广：......
  • Codeforces Round 889 (Div. 2) C1 - C2
    Problem-C1-CodeforcesProblem-C2-Codeforces题意：​ 有\(n\)个数字，可以选择任意两个位置\(i,j\)进行操作，使得\(a_i=a_i+a_j\)（也即是把\(a_j\)加到\(a_i\)上），输出任意操作方案使得数组最后是不降的。esay-version要求在50次操作内完成，hard-version要求在31次操作内完成。......
  • Codeforces #889 div2 B
    B.LongestDivisorsInterval做法：假设我们找到了一个最大区间[l,r]，这个区间的长度为k，那么这个区间里有一个数必定是k的倍数（自己举个例子就能知道了），因此n也是k的倍数。那么我们再缩小一下区间长度，变为k-1，这个区间可以是[l,r-1]，也可以是[l+1,r]，这其中必定有一个数是k-......
  • Codeforces Round 889 (Div. 2) 题解
    \(6\)题只做出来\(1\)题，损失惨重A.DaltontheTeacher显然，答案一定和最初的不满意人数有关，所以输入的时候统计一下然后，将不满意的人的座位每两个人交换一次即可，交换次数就是答案如果不满意人数是奇数，那么答案还要加\(1\)时间复杂度\(O(n)\)（输入的复杂度）B.LongestD......
  • CF1855B Longest Divisors Interval 题解
    题意：给定一个数\(n\)，求一个连续区间\([l,r]\)使得\(n\)是区间内每个数的倍数，最大化这个区间的长度(多组数据)。思路:逆向思考一波，（如果一个数\(x\)不是\(n\)的因数，那么\(x\)的倍数不能在区间内。举个例子，比如$n$是13，3不是13的因数，\(3,6,9,12\)也就不可能出现......
  • Codeforces Round 889 (Div. 1) 题解
    A1.Dual(EasyVersion)https://codeforces.com/contest/1854/problem/A1题意给定一个长度为\(n\)的序列\(a_1,a_2,\dots,a_n\)，你可以做以下操作：选定两个下标\(i,j(1\leqi,j\leqn)\)，\(i,j\)可以相同，然后\(a_i\leftarrowa_{i}+a_j\)。要求构造一种操作......
  • Round 889 Div.2 意识流简记。
    太丢人了！D2D狂吃6发罚时，D2C都不会！不过无所谓，反正老年选手就是打着玩。D2A.答案为\(\lceil\frac{\sum_{i=1}^n[a_i=i]}{2}\rceil\)。D2B.我不会啊，猜了一下只需要枚举\(\le2000\)的，莫名其妙过了。D2C1/C2.不会。D2D.考虑动态维护前\(i\)个能凑出的数的集合，适时......
  • Codeforces Round 105 (Div. 2) - D. Bag of mice DP 或 记忆化搜索 求概率
    D.Bagofmice题意待补充~思路可利用DP或者记忆化搜索求解本问题，实际上这两个方法等价。当\(w=0\)时必输当$w\ne0$但$b=0$时必赢剩下的情况，先考虑一个问题：赢的局面是怎么构成的？代码记忆化搜索//>>>Qiansui#include<bits/stdc++.h>#definelllong......
  • Educational Codeforces Round 152 (Rated for Div. 2)
    传送阵T1MorningSandwich题目大意\(t\)个测试，每个测试给三个正整数\(b,c,h\)，分别表示面包和两种馅料的个数，每两个面包之间必须放一个馅料，问最多能摆几层?思路我们发现\(c,h\)所表示的两种馅料其实相差不大，所以我们可以分两种情况\(a>c+h\)因为开头总是面包，所以要+......
  • Codeforces Round 888 (Div. 3)
    CodeforcesRound888(Div.3)T1​ 思路：直接模拟。T2​思路：首先记录原始数组的奇偶性，然后将奇数、偶数分为不同两组进行排序，然后再根据原数组的奇偶性按顺序填入奇数偶数，最后判断整个数组是否非递减。T3思路：我们已知开始在\(a_1\)，最后在\(a_n\)。那么当\(a_1\ne......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99