526互联

Codeforces Round 888 (Div. 3)

发布时间 2023-07-30 23:16:05作者: north_h

传送门

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;
}