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

Codeforces Round 929 (Div. 3)

时间：2024-02-29 09:04:57浏览次数：18  
标签：return int ll Codeforces long 929 using Div define

Codeforces Round 929 (Div. 3)

A - Turtle Puzzle: Rearrange and Negate

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        ans += abs(x);
    }
    cout << ans << endl;
}

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

B - Turtle Math: Fast Three Task

解题思路:

如果当前数组总和为\(3\)的倍数，无需操作。

如果当前数组总和\(res \%3 = 1\),那么尝试减去一个模\(3\)等于\(1\)的元素，如果存在，那么操作数为\(1\)；如果不存在，选择任意一个数加两次\(1\)即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
    int n;
    cin >> n;
    ll res = 0;
    vector<int> cnt(5);
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        res += x;
        cnt[x % 3]++;
    }
    int t = res % 3;
    if (t == 0)
    {
        cout << 0 << endl;
        return;
    }
    if (t == 1)
    {
        if (cnt[1] > 0)
        {
            cout << 1 << endl;
        }
        else
        {
            cout << 2 << endl;
        }
    }
    else
    {
        cout << 1 << endl;
    }
}

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

C - Turtle Fingers: Count the Values of k

解题思路:

\(a,b\)增长速度很快，枚举即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;

ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}

void solve()
{
    ll a, b, l;
    cin >> a >> b >> l;
    map<ll, bool> cnt;

    for (int i = 0; i <= 20; i++)
    {
        if (qmi(a, i) > l)
        {
            break;
        }
        for (int j = 0; j <= 20; j++)
        {
            if (qmi(b, j) > l)
            {
                break;
            }
            ll t = qmi(a, i) * qmi(b, j);
            if (t > l)
            {
                break;
            }
            if (l % t == 0)
            {
                cnt[l / t] = true;
            }
        }
    }
    cout << cnt.size() << endl;
}

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

D - Turtle Tenacity: Continual Mods

解题思路:

升序排序。

若最小数只有一个，模到最后得到的就是最小数。

有多个最小数，分情况讨论：

  • 若最小数是\(1\)，无解。
  • 否则尝试用大数模最小数，看是否能得到小于当前最小数的余数，若能得到，有解；否则，说明后面的数都是最小数的倍数，最小数一定会和相同的自己模得到零，无解。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    map<int, int> cnt;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
    }
    sort(a.begin() + 1, a.end());
    if (cnt.size() == n || a[1] != a[2])
    {
        puts("YES");
    }
    else
    {
        if (cnt[1] > 1)
        {
            puts("NO");
        }
        else
        {
            if (cnt[1] == 1)
            {
                puts("YES");
            }
            else
            {
                for (int i = 3; i <= n; i++)
                {
                    if (a[i] % a[1])
                    {
                        puts("YES");
                        return;
                    }
                }
                puts("NO");
            }
        }
    }
}

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

E - Turtle vs. Rabbit Race: Optimal 训练

解题思路:

观察发现，随着\(r\)从左到右遍历，成绩先增大后减小。具有凸性。三分求最优答案。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;

void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n + 10);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    int q;
    cin >> q;

    while (q--)
    {
        ll tl, u;
        cin >> tl >> u;
        ll l = tl - 1;
        ll r = n + 1;
        auto f = [&](ll mid) -> ll
        {
            if (mid < tl)
            {
                return -1e18;
            }
            ll len = a[mid] - a[tl - 1];
            ll st = u;
            ll ed = u - len + 1;
            ll res = (st + ed) * len / 2;
            return res;
        };
        while (l + 1 < r)
        {
            ll mid = (r - l) / 3;
            ll ml = l + mid;
            ll mr = r - mid;
            if (f(mr) > f(ml))
            {
                l = ml;
            }
            else
            {
                r = mr;
            }
            if (mid == 0)
            {
                break;
            }
        }
        ll ta = f(l);
        ll tb = f(l + 1);
        ll tc = f(l + 2);
        if (l == n)
        {
            cout << l << ' ';
        }
        else if (l == n - 1)
        {
            if (ta >= tb)
            {
                cout << l << ' ';
            }
            else
            {
                cout << l + 1 << ' ';
            }
        }
        else if (l <= n - 2)
        {
            if (ta >= tb && ta >= tc)
            {
                cout << l << ' ';
            }
            else if (tb >= tc)
            {
                cout << l + 1 << ' ';
            }
            else
            {
                cout << tc << ' ';
            }
        }
    }
    cout << endl;
}

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

F - Turtle Mission: Robot and the Earthquake

解题思路:

考虑和石头的相对位置变化。向下走等于相对向下走两步，向右走等于向右下走一步，向上等于不动。

所以，如果可以先向下或者向右，然后在向上。我们一定也可以先向上，然后向下或者向右。

考虑先通过向下向右走到最后一列，最后通过向上调整位置走到终点。

最短路\(bfs\)。

注意：若根据相对位置移动，由于每次都有一个向下的相对偏移量，在最后一列向上移动之前，记得要减回去。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> g[i][j];
        }
    }
    queue<pii> q;
    q.push({0, 0});
    vector<vector<int>> dis(n + 1, vector<int>(m + 1, 0));
    int ans = 1e9;
    while (q.size())
    {
        auto [x, y] = q.front();
        q.pop();
        // 在最后一列向上走到终点
        if (y == m - 1)
        {
            // 由于每次都有一个向下的相对偏移量，这里记得要减回去
            ans = min(1ll * ans, dis[x][y] + ((x - (n - 1 + dis[x][y]) % n + n) % n));
        }
        int nx = (x + 1) % n;
        int ny = y + 1;
        // 右下走一步
        if (ny <= m - 1 && g[nx][ny] == 0 && !dis[nx][ny])
        {
            dis[nx][ny] = dis[x][y] + 1;
            q.push({nx, ny});
        }
        nx = (x + 2) % n;
        ny = y;
        // 向下走两步
        if (g[(x + 1) % n][y] != 1 && g[(x + 2) % n][y] != 1 && !dis[nx][ny])
        {
            dis[nx][ny] = dis[x][y] + 1;
            q.push({nx, ny});
        }
    }
    if (ans == 1e9)
    {
        puts("-1");
    }
    else
    {
        cout << ans << endl;
    }
}

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

G - Turtle Magic: Royal Turtle Shell Pattern

解题思路:

横着标准图：

\[0011\\1100\\0011\\1100 \]

竖着标准图:

\[0101 \\0101\\ 1010\\ 1010 \]

横图分别选择第\(1, 2, 3,4\)列作为第一列，就是四种情况。竖图分别选择第\(1, 2, 3,4\)行作为第一行，就是四种情况。

总共有八种情况。

对于加入的每个字符，我们一次判断是否符合八种情况即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;

void solve()
{
    int n, m, q;
    cin >> n >> m >> q;
    cout << 8 << endl;
    int ans = 8;
    vector<bool> vis(10, false);
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        string s;
        cin >> s;
        auto find = [&](int x, int y, int k)
        {
            // 偏移到标准图上
            // 标准图:0011
            // 标准图:1100
            if (k < 4)
            {
                y += k;
                // 在 0011
                if (x & 1)
                {
                    return y % 4 == 3 || y % 4 == 0;
                }
                // 在 1100
                else
                {
                    return y % 4 == 1 || y % 4 == 2;
                }
            }
            // 标准图：01
            // 标准图：01
            // 标准图：10
            // 标准图：10
            else
            {
                x += k;
                // 竖着 0011
                if (y & 1)
                {
                    return x % 4 == 3 || x % 4 == 0;
                }
                // 竖着 1100
                else
                {
                    return x % 4 == 1 || x % 4 == 2;
                }
            }
        };
        if (s[0] == 'c')
        {
            int t = 0;
            for (int i = 0; i < 8; i++)
            {
                if (!vis[i])
                {
                    if (find(x, y, i) != t)
                    {
                        vis[i] = true;
                        ans--;
                    }
                }
            }
        }
        else
        {
            int t = 1;
            for (int i = 0; i < 8; i++)
            {
                if (!vis[i])
                {
                    if (find(x, y, i) != t)
                    {
                        vis[i] = true;
                        ans--;
                    }
                }
            }
        }
        cout << ans << endl;
    }
}

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

标签：return,int,ll,Codeforces,long,929,using,Div,define
From： https://www.cnblogs.com/value0/p/18042604

相关文章

  • 13 Codeforces Round 886 (Div. 4)G. The Morning Star（简单容斥）
    G.TheMorningStar思路：用map记录x，y，以及y-x、y+x从前往后统计一遍答案即可公式\(ans+=cnt[x]+cnt[y]-2*cnt[x,y]+cnt[y+x]+cnt[y-x]\)\(cnt[x]+cny[y]-2*cnt[x,y]\)是统计坐标轴方向的，-2倍是需要把本身这个点给减去容斥是减一倍，这里还需要把自己给挖掉\(cnt[y+x]+cnt[y......
  • Codeforces 264E Roadside Trees
    首先考虑时间增长的问题，设第\(i\)棵树的种植时间为\(t_i\)。那么第\(x\)棵树比第\(y\)棵树高就是\(h_x+(t_y-t_x)>h_y\)，也就是\(h_x-t_x>h_y-t_y\)。所以可以直接用\(h_i-t_i\)当作第\(i\)棵树的高度，即\(h'_i\leftarrowh_i-t_i\)。对于增加，考虑......
  • CodeForces 1844H Multiple of Three Cycles
    洛谷传送门CF传送门首先环是不用管的，只用判环长是否为\(3\)的倍数即可。考虑设\(f(x,y,z)\)表示\(x\)个\(1\)链，\(y\)个\(2\)链，\(z\)个\(0\)链，组成所有环长都为\(3\)的倍数的方案数。注意到\(f(x,y,z)=(x+y+z)f(x,y,z-1)\)（可以接到剩下的任意......
  • Codeforces Round 929 (Div. 3)
    B.TurtleMath:FastThreeTask数学#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1e5+10;inta[N];voidsolve(){ intn; cin>>n; intsum=0; map<int,int>mp; intmx=0; for(inti=1;i<=n;i++){ cin......
  • 11 .Codeforces Round 891 (Div. 3)E. Power of Points(推公式+前缀和优化)
    E.PowerofPoints题解参考#include<bits/stdc++.h>#defineintlonglong#definerep(i,a,b)for(inti=(a);i<=(b);++i)#definefep(i,a,b)for(inti=(a);i>=(b);--i)#define_for(i,a,b)for(inti=(a);i<(b);++i)#definepii......
  • CF-929(已更新：B-E)
    CF-929开学以来打得最烂的一场(⊙﹏⊙)B两种操作：删除一个元素、把一个元素的权值增加1。求使得序列元素和整除于3的最小操作次数。分析如果序列和sum模3的余数为0，答案为0，若为2，可以进行第二种操作，答案为1，但是若为1，答案就不一定为2，因为若能进行第一种操作删去一个模3为1的元素，......
  • Codeforces Round 929 (Div. 3) 题解（D-G）
    比赛链接：https://codeforces.com/contest/1933官解暂未放出。质量不错的一场D3。CF1933D.TurtleTenacity:ContinualMods题意将数组\(a_{1..n}\ge1\)重排，问是否能使\(((a_1\mathbin{\rmmod}a_2)\mathbin{\rmmod}a_3)\cdots\mathbin{\rmmod}a_n\ne0\)......
  • Codeforces Round 929 (Div. 3)
    CodeforcesRound929(Div.3)比赛链接A.TurtlePuzzle:RearrangeandNegate思路根据题意，很明显数组中所有元素的绝对值总和就是答案Code#include<bits/stdc++.h>usingnamespacestd;#defineall(x)x.begin()+1,x.end()#defineintlonglongvoidsolve(){......
  • D. Vlad and Division
    原题链接题解对于一个数，我们将其转换成二进制，然后补零到31位我们发现，能和数x配对的数只有一个，那就是按位翻转后的x，即x和\(2^{31}-1\)异或的值所以我们要找有没有能互相配对的值，以及组数，配对用map？code#include<bits/stdc++.h>usingnamespacestd;constintval=2147483......
  • Codeforces 441E Valera and Number
    首先看到\(\times2\)\(+1\)和最后答案的计算方式，能想到看成二进制来处理。考虑到\(\times2\)就是在最后加了一个\(0\)。不妨倒过来看，\(\times2\)就相当于舍弃了最低位。于是可以考虑\(\text{DP}\)，\(f_{i,j}\)为考虑后面的\(i\)个操作，目前\(+\)的值为\(j\)的......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99