Codeforces Round #811 (Div. 3)无DF

为什么，为什么我写不出D呜呜呜呜呜，字符串一生之敌了属于是，F心态崩了题都没看笑死，明天起床再补罢

Problem - A - Codeforces

问题解析

初始h和m变量记录睡着的时间，h1和m1记录醒来的最近一个闹钟。

• 当闹钟时间在睡着时间之前**（h1<h||(h1==h&&m1<m)）**，说明我们如果要通过这个闹钟醒来，那我们就要睡到第二天，h1+=24
• 当闹钟时间在睡着时间之后，h1和m1不做改动。

在此过程中维护最小的那个闹钟时间即可。最后计算差值。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 5e5 + 50, MOD = 998244353;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)res = (1LL) * res * a % MOD;
        b >>= 1;
        a = (1LL) * a * a % MOD;
    }
    return res;
}


void solve()
{
    int n, h, m, a, b;
    cin >> n >> h >> m;
    int h1 = 1e9, m1 = 1e9;
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        if (a < h || (a == h && b < m))
        {
            a += 24;
        }
        
        if (a < h1)
        {
            h1 = a, m1 = b;
        }
        else if (a == h1)
        {
            m1 = min(m1, b);
        }
    }
    if (m1 < m)
    {
        m1 += 60;
        h1--;
    }
    cout << h1 - h << " " << m1 - m << endl;
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Problem - B - Codeforces

问题解析

从后往前遍历数组，同时记录每个数的出现次数，当有一个数出现了两次时，说明从这个位置开始（包括这个位置），剩下的数都要被删掉。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 5e5 + 50, MOD = 998244353;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)res = (1LL) * res * a % MOD;
        b >>= 1;
        a = (1LL) * a * a % MOD;
    }
    return res;
}


void solve()
{
    int n;
    cin >> n;
    vector<int>v(n+1);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    map<int, int>mymap;
    for (int i = n; i > 0; i--)
    {
        if (mymap.count(v[i]))
        {
            cout << i << endl;
            return;
        }
        else mymap[v[i]]++;
    }
    cout << 0 << endl;
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Problem - C - Codeforces

问题解析

题目要求构造的数最小，那么就是左边的数要尽量小，右边的数尽量大，而且数组的长度要最小。

贪心角度来说，我们从右往左，且最右边的数为9开始逐步构造数字，当n的值不够构造当前位数时，直接用n就行。

比如n==7，不够9，那就直接输出7。

比如n==20，只够9 8，那么第三位就是2。

最后把构造出的数再按照正常顺序输出即可。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 5e5 + 50, MOD = 998244353;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)res = (1LL) * res * a % MOD;
        b >>= 1;
        a = (1LL) * a * a % MOD;
    }
    return res;
}


void solve()
{
    int n, x = 9;
    cin >> n;
    vector<int>v;

    while (n)
    {
        if (n >= x)
        {
            v.push_back(x);
            n -= x;
            x--;
        }
        else
        {
            v.push_back(n);
            break;
        }
    }
    int len = v.size();
    for (int i = len - 1; i >= 0; i--)cout << v[i];
    cout << endl;
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Problem - E - Codeforces

问题解析

我们通过打表后发现：

• 尾数为1 2 3 4 6 7 8 9的数，最后经过多次操作都会变成尾数为2 4 6 8的样子。
• 尾数为0的数不论多少次操作，大小不会发生改变。
• 尾数为5的数，只能通过一次操作变成尾数为0的数
• 对于尾数2 4 6 8的数，经过多次操作使得新的数尾数和原来一样时，他们的差值是20，比如原本x=2，那么下一个尾数为2的数是22（变换顺序2 4 8 16 22）

我们可以根据数组第一个数的尾数来当标准。

如果第一个数的尾数是5或0，我们可以把数组所有的数都变成尾数为0的样子，如果有一个数不能变成尾数为0，就是no。如果变成0后，整个数组不是完全相等的，也是no。

否则，我们可以把数组所有的数都统一变成一个固定的尾数x（我选的8），把所有数都变成尾数为x的样子后，看他们两两之间的差值是否是20的倍数，如果是，就是yes，反之no。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 5e5 + 50, MOD = 998244353;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)res = (1LL) * res * a % MOD;
        b >>= 1;
        a = (1LL) * a * a % MOD;
    }
    return res;
}


void solve()
{
    int n;
    cin >> n;
    vector<int>v(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    if (v[1] % 10 == 0 || v[1] % 10 == 5)
    {
        int flag = -1;
        for (int i = 1; i <= n; i++)
        {
            int cnt = 0;
            while (v[i] % 10 != 0)
            {
                v[i] += v[i] % 10;
                if (cnt == 20)
                {
                    cout << "NO" << endl;
                    return;
                }
                cnt++;
            }
            if (flag == -1)flag = v[i];
            else if (flag != v[i])
            {
                cout << "NO" << endl;
                return;
            }
        }
        cout << "YES" << endl;
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            int cnt = 0;
            while (v[i] < 20 || v[i] % 10 != 8)
            {
                v[i] += v[i] % 10;
                if (cnt == 20)
                {
                    cout << "NO" << endl;
                    return;
                }
                cnt++;
            }
            v[i] -= v[i]%10;
        }
        int st = v[1] % 20;
        for (int i = 2; i <= n; i++)
        {
            if (v[i] % 20 != st)
            {
                cout << "NO" << endl;
                return;
            }
        }
        cout << "YES" << endl;
    }
    
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Problem - G - Codeforces

问题解析

dfs+二分

我们以1为起点开始dfs，记录两个元素，一个是记录路径上a值总和的变量suma，一个是记录路径上b值前缀和的数组v（如果路径上b值为1 3 5 7 9，那么在数组v中，是1 4 9 16 25的样子）。

那么当我们到达一个新的点时，更新suma的值和v的元素。然后根据suma的值，在数组v中二分查找不大于suma的v[i]的位置，这个i就是到达这个点的消耗r。

至于这个数组v，我们可以用c++的vector，初始插入一个数字0，那么到达第一个新的点时，我们给v尾部插入一个v.back()+b（PS:back()这个函数是返回数组v中的最后一个元素），这样就做到了更新前缀和。当我们离开路径时（用不上这个点了），用pop_back()函数把尾部的最后一个元素去掉（即我们这次插入的前缀和）。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 998244353;

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)res = (1LL) * res * a % MOD;
        b >>= 1;
        a = (1LL) * a * a % MOD;
    }
    return res;
}

map<int, map<int, int>>a, b;
map<int, vector<int>>tree;
int f[N];
void dfs(int x, int y, int suma, vector<int>& v)
{
    int l = 0, r = v.size() - 1;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        if (v[mid] <= suma)l = mid;
        else r = mid - 1;
    }
    f[x] = l;
    for (auto i : tree[x])
    {
        suma += a[x][i];
        v.push_back(v.back() + b[x][i]);
        dfs(i, x, suma, v);
        suma -= a[x][i];
        v.pop_back();
    }
}

void solve()
{
    a.clear(), b.clear();
    tree.clear();
    int n, x, y, z;
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        cin >> x >> y >> z;
        tree[x].push_back(i);
        a[x][i] = y;
        b[x][i] = z;
    }
    vector<int>v(1);
    dfs(1, 0, 0, v);
    for (int i = 2; i <= n; i++)cout << f[i] << " ";
    cout << endl;
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}