首页 > 其他分享 >Pinely Round 4 (Div. 1 + Div. 2)(A - F)

Pinely Round 4 (Div. 1 + Div. 2)(A - F)

时间：2024-07-29 18:10:21浏览次数：8  
标签：int Pinely back long solve using Div Round define

Pinely Round 4 (Div. 1 + Div. 2)(A - F)

A - Maximize the Last Element

解题思路:

只有奇数位置能选。偶数位置前后都有奇数个数字，无法删完。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
    int n;
    cin >> n;
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (i & 1)
        {
            mx = max(mx, x);
        }
    }
    cout << mx << '\n';
}

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

B - AND Reconstruction

解题思路：

\(b_i\)能确定\(a_i,a_{i+1}\)哪些二进制位一定为一，不冲突即可。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i < n; i++)
    {
        cin >> b[i];
        for (int j = 0; j <= 30; j++)
        {
            if (b[i] >> j & 1)
            {
                if (!(a[i] >> j & 1))
                {
                    a[i] += 1 << j;
                }
                if (!(a[i + 1] >> j & 1))
                {
                    a[i + 1] += 1 << j;
                }
            }
        }
    }
    bool ok = true;
    for (int i = 1; i < n; i++)
    {
        if ((a[i] & a[i + 1]) != b[i])
        {
            ok = false;
            break;
        }
    }
    if (ok)
    {
        for (int i = 1; i <= n; i++)
        {
            cout << a[i] << " \n"[i == n];
        }
    }
    else
    {
        cout << -1 << '\n';
    }
}

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

C - Absolute Zero

解题思路:

最多\(40\)次，我们可以暴力操作。

设当前最大值为\(r\)，最小值为\(l\)。每次减去\((r - l)/ 2+ l\)，这样操作之后，整体区间上界必然减半。\(2^{40}> 10^9\)，如果有解，一定足够。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int q = 40;
    vector<int> ans;
    while (q--)
    {
        int r = -1;
        int l = 1e9 + 1;
        for (int i = 1; i <= n; i++)
        {
            r = max(r, a[i]);
            l = min(l, a[i]);
        }
        int x = max(1, (r - l) / 2 + l);
        if (r - l == 0)
        {
            ans.push_back(r);
            for (int i = 1; i <= n; i++)
            {
                a[i] = 0;
            }
            break;
        }
        bool z = true;
        for (int i = 1; i <= n; i++)
        {
            a[i] = abs(a[i] - x);
        }
        ans.push_back(x);
    }
    bool ok = true;
    for (int i = 1; i <= n; i++)
    {
        if (a[i])
        {
            ok = false;
            break;
        }
    }
    if (ok)
    {
        cout << ans.size() << '\n';
        for (auto x : ans)
        {
            cout << x << ' ';
        }
        cout << endl;
    }
    else
    {
        cout << -1 << '\n';
    }
}

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

D - Prime XOR Coloring

解题思路：

正向思考连边数太多，尝试反向思考，考虑哪些点一定不会互相连边。

根据样例以及四色定理，当\(n \geq 6\)后，一定用四种颜色染色。

质数中除了\(2\)都是奇数。\(2\)的二进制表示为\((10)\)，其余质数二进制最低两位\((01),(11)\)。二进制最低两位为\((00)\)一定不是质数。

如果两个数字\(mod\ 4\)同余，那么他们异或起来二进制最低两位一定是\((00)\)，他们一定不连边，可以同色。

代码：

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

void solve()
{
    int n;
    cin >> n;
    if (n == 1)
    {
        cout << 1 << '\n';
        cout << 1 << '\n';
    }
    else if (n == 2)
    {
        cout << 2 << '\n';
        cout << 1 << ' ' << 2 << '\n';
    }
    else if (n == 3)
    {
        cout << 2 << '\n';
        cout << 1 << ' ' << 2 << ' ' << 2 << '\n';
    }
    else if (n == 4)
    {
        cout << 3 << '\n';
        cout << 1 << ' ' << 2 << ' ' << 2 << ' ' << 3 << '\n';
    }
    else if (n == 5)
    {
        cout << 3 << '\n';
        cout << 1 << ' ' << 2 << ' ' << 2 << ' ' << 3 << ' ' << 3 << '\n';
    }
    else
    {
        cout << 4 << '\n';
        for (int i = 0; i < n; i++)
        {
            cout << (i % 4) + 1 << " \n"[i == n];
        }
    }
}

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

E - Coloring Game

解题思路：

如果是二分图，选\(Bob\)。反之，选\(Alice\)。

不是二分图时，随便给\(n\)次颜色总归能赢。

选\(Bob\)：假定二分图为\((1,2)\)两种颜色，每次选择颜色时至少有其中一种，我们按设定去选点。直到有一种颜色\(x\)涂满了，接下来每次选择至少有\((3 - x, 3)\)其中一种，全部涂另一边即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
const int N = 1e4 + 10;
vector<int> e[N];
int color[N];
vector<int> v[3];
bool dfs(int u, int fa, int c)
{
    color[u] = c;
    for (auto v : e[u])
    {
        if (v != fa)
        {
            if (!color[v])
            {
                if (dfs(v, u, 3 - c))
                {
                    return true;
                }
            }
            else if (color[v] == c)
            {
                return true;
            }
        }
    }
    return false;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        e[i].clear();
        color[i] = 0;
    }
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    bool ok = true;
    for (int i = 1; i <= n; i++)
    {
        if (!color[i])
        {
            if (dfs(i, -1, 1))
            {
                ok = false;
                break;
            }
        }
    }
    auto pt = [&](int a, int b)
    {
        cout << a << ' ' << b << '\n';
        cout.flush();
    };

    if (ok)
    {
        for (int i = 1; i <= n; i++)
        {
            if (color[i] == 1)
            {
                v[1].push_back(i);
            }
            else
            {
                v[2].push_back(i);
            }
        }
        cout << "Bob\n";
        cout.flush();
        int a, b;
        for (int i = 1; i <= n; i++)
        {
            cin >> a >> b;
            if (a > b)
            {
                swap(a, b);
            }
            if (a == 1 && b == 2)
            {
                if (v[1].size() > 0)
                {
                    int u = v[1].back();
                    v[1].pop_back();
                    pt(u, 1);
                }
                else
                {
                    int u = v[2].back();
                    v[2].pop_back();
                    pt(u, 2);
                }
            }
            else if (a == 1 && b == 3)
            {
                if (v[1].size() > 0)
                {
                    int u = v[1].back();
                    v[1].pop_back();
                    pt(u, 1);
                }
                else
                {
                    int u = v[2].back();
                    v[2].pop_back();
                    pt(u, 3);
                }
            }
            else
            {
                if (v[2].size() > 0)
                {
                    int u = v[2].back();
                    v[2].pop_back();
                    pt(u, 2);
                }
                else
                {
                    int u = v[1].back();
                    v[1].pop_back();
                    pt(u, 3);
                }
            }
        }
    }
    else
    {
        cout << "Alice\n";
        cout.flush();
        int a, b;
        for (int i = 1; i <= n; i++)
        {
            cout << 1 << ' ' << 2 << '\n';
            cout.flush();
            cin >> a >> b;
        }
    }
}

int main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

F - Triangle Formation

解题思路：

假设\(a + b \leq c\)，根据\(a, b\)不断向序列后增添\(c\)，发现在\(c \leq 10^9\)限制下，最多大概\(44\)次\(c\)就会大于\(10^9\)，这是斐波那契数列\(a_1 + a_2 = a_3\)。

所以，如果区间长度大于大概\(50\)就一定有两组解。

剩下区间长度情况就可以暴力判断。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        if (r - l + 1 >= 60)
        {
            cout << "YES\n";
        }
        else
        {
            vector<int> v;
            for (int i = l; i <= r; i++)
            {
                v.push_back(a[i]);
            }
            sort(v.begin(), v.end());
            vector<int> pos;
            for (int i = 2; i < v.size(); i++)
            {
                if (v[i - 2] + v[i - 1] > v[i])
                {
                    pos.push_back(i);
                }
            }
            if (pos.size() >= 2)
            {
                if (pos.back() - pos[0] >= 3)
                {
                    cout << "YES\n";
                    continue;
                }
                auto check = [&](int i, int j, int k)
                {
                    return v[i] + v[j] > v[k];
                };
                if (pos.back() >= 5)
                {
                    int i = pos.back();
                    if (check(i - 5, i - 3, i - 2) && check(i - 4, i - 1, i))
                    {
                        cout << "YES\n";
                    }
                    else if (check(i - 5, i - 2, i - 1) && check(i - 4, i - 3, i))
                    {
                        cout << "YES\n";
                    }
                    else if (check(i - 5, i - 1, i) && check(i - 4, i - 3, i - 2))
                    {
                        cout << "YES\n";
                    }
                    else
                    {
                        cout << "NO\n";
                    }
                }
                else
                {
                    cout << "NO\n";
                }
            }
            else
            {
                cout << "NO\n";
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

标签：int,Pinely,back,long,solve,using,Div,Round,define
From： https://www.cnblogs.com/value0/p/18330698

相关文章

  • Codeforces Round 961 (Div. 2) 复盘
    第一次打div2的总结div2难度明显比div3要难一些，其实也不是很难前面的签到题，但是给了我一种每道题都可以直接暴力但是就是会超时的感觉，不知道是不是提前就在告诉你要考虑greedythinking。T11995A-Diagonals这道题说实话就是存粹的模拟，除了最长的一个对角线同长度只有一列，其......
  • CF Div3 962补题 E-F
    CFDiv3962补题E-FE.Decode链接:Problem-E-Codeforces简要题意:给你一个长度为\(n\)的二进制字符串\(s\)。对于每一对整数\((l,r)\)\((1\leql\leqr\leqn)\)中，数出\((x,y)\)\((l\leqx\leqy\leqr)\)这样的整数对的个数。\((l\leqx\leqy\leq......
  • NSSRound#4 Team
    [NSSRound#4SWPU]1zweb考察：phar的反序列化1.打开环境，审计代码1.非预期解直接用file伪协议读取flag,或直接读取flagfile:///flag/flag2.正常解法用读取文件读取index.php,upload.php的源码 index.php:<?phpclassLoveNss{public$ljt;public$dky;......
  • Pinely Round 4 (Div. 1 + Div. 2) 复盘总结
    PinelyRound4(Div.1+Div.2)发挥到极致了，写出了两题A.MaximizetheLastElement对于每个满足他左边的数的个数和他后面的数的个数都是奇数的数，取最大值即可。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;//#defineintlonglong#defi......
  • Pinely Round 4 (Div. 1 + Div. 2)
    打的挺惨的，也算是活该吧。。总是沉浸在自己的舒适圈里，不肯跳出来，最近的总结和复盘也没认真做，回寝室明明应该做事情，但是就一直打游戏。。要是少打点游戏，也不至于最近这么长时间一场cf都没有vp过，手感这么差了。不过这次的题目也确实是我的漏洞。B因为初值的原因爆炸了，到最后都不知......
  • Pinely Round 4 (Div. 1 + Div. 2) 补题记录（A~F）
    打成乐子A容易证明下标为奇数的地方可以取到，下标为偶数的地方不可以取到。直接模拟时间复杂度为\(O(n)\)。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1000100;inta[N];signedmain(){intT;scanf("%lld",&T);......
  • Codeforces Round 961 (Div. 2)
    Preface菜的批爆，B2一直WA道心破碎了直接白兰去了，鉴定为纯纯的飞舞本来想着周末补题的然后又摆了一天，E1和E2都没时间补了，鉴定为纯纯的懒狗A.Diagonals签到，贪心枚举即可#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>#in......
  • SMU Summer 2024 div2 3rd
    文章目录TheThirdWeek一、前言二、算法1.KMP算法2.线性DP<1>（最长上升子序列II）3.背包DP<1>（「木」迷雾森林）4.其它<1>（Ubiquity）三、总结TheThirdWeek战略上藐视敌人，战术上重视敌人————毛泽东主席一、前言周六打了场cf，只过了俩题而且比较慢，给我的id上......
  • Solution - Atcoder ARC114F Permutation Division
    令\(a\)为题目中的\(P\)。首先考虑后手的重排策略是什么。因为\(a\)是个排列，元素互不相同，那么肯定就是按照每一段的第一个数的大小，越大的放在越前面。那么当\(a_1\lek\)的时候，显然先手会把以\(1\simk\)开头来划分段。因为否则存在一个开头\(>k\)的段，后手把其放......
  • Codeforces Round 962 (Div. 3) 题解 A-F
    A.LegsProblem-A-Codeforces1.1翻译农夫约翰的农场又迎来了美好的一天。农夫约翰来到农场后，数了数n条腿。众所周知，农场里只住着鸡和牛，一只鸡有2条腿，而一头牛有4条腿。假设约翰农场主数清了所有动物的腿，那么他的农场里最少有多少动物？1.2思路求最少有几只动物......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99