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

Codeforces Round 909 (Div. 3)

时间:2023-11-21 22:47:17浏览次数:42  
标签:int ll 909 Codeforces long -- solve using Div

Codeforces Round 909 (Div. 3)

A. Game with Integers

题意:

给定一个数\(x\),\(A,B\)两人轮流进行操作,\(A\)先操作。每次给\(x\)加一或者减一,操作完后\(x \% 3 == 0\)者获胜。判断获胜者。

解题思路:

判断\(A\)操作完是否能获胜,如果不能,那么一定是\(B\)获胜。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    int n;
    cin >> n;
    int a = n + 1;
    int b = n - 1;
    if ((a % 3 == 0) || (b % 3 == 0))
    {
        puts("First");
    }
    else
    {
        puts("Second");
    }
}

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

B. 250 Thousand Tons of TNT

题意:

将一个数列\(a\)从左到右每\(k\)个相加得到一个和,使得这些和中最小和与最大和的差值最大。

解题思路:

直接暴力。

\(k\)一定是数列长度\(n\)的因子,用前缀和计算这\(k\)个数的和是\(O(1)\)的。

那么对于每个\(k\)的遍历时间复杂度就是\(\frac{n}{k}\)。

遍历\(k\)的时间复杂度是\(O(\sqrt{n})\)。

总体时间复杂度是\(O(n\sqrt{n} \times ln(n))\).调和级数。由于是因子,内层循环大小远小于\(O(nlnn)\)实际时间小这个很多。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<ll> s(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    ll ans = 0;
    for (int i = 1; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            ll x = i;
            ll y = n / i;
            ll minx = 1e18 + 10;
            ll maxx = 0;
            for (ll l = 1, r = 1 + x; l <= n; l += x, r += x)
            {
                ll t = s[r - 1] - s[l - 1];
                // cout << t << endl;
                minx = min(minx, t);
                maxx = max(maxx, t);
            }
            // cout << maxx << ' ' << minx << endl;
            ans = max(ans, maxx - minx);
            minx = 1e18 + 10;
            maxx = 0;

            for (ll l = 1, r = 1 + y; l <= n; l += y, r += y)
            {
                ll t = s[r - 1] - s[l - 1];
                minx = min(minx, t);
                maxx = max(maxx, t);
            }
            ans = max(ans, maxx - minx);
        }
    }
    cout << ans << endl;
}

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

C. Yarik and Array

题意:

给定一个数列,求最大连续子段和,要求子段和中相邻两数奇偶性不能相同。

解题思路:

\(dp\)求解最大子段和板子,加个相邻数奇偶性要不同的转移判断即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    vector<ll> f(n + 1);
    ll ans = -1e18;
    for (int i = 1; i <= n; i++)
    {
        if (i == 1)
        {
            f[i] = a[i];
            ans = f[i];
            continue;
        }
        int x = (a[i] & 1);
        int y = (a[i - 1] & 1);
        if (x != y)
        {
            f[i] = max(f[i - 1] + a[i], a[i]);
        }
        else
        {
            f[i] = a[i];
        }
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
}

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

D. Yarik and Musical Notes

题意:

给定数组\(a\),计算\(pair(i,j)(i < j )\)使得\((2^{a_{i}})^{a_j} == (2^{a_{j}})^{a_i}\)的个数。

解题思路:

首先我们会发现,如果\(a[i] == a[j]\)那么一定是对的。

对于\(a[i] \neq a[j]\),我们会发现,只有\((1,2),(2,1)\)这种数对是符合的。

统计计数即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    int n;
    cin >> n;
    map<int, ll> cnt;
    for (int i = 1; i <= n; i++)
    {
        ll x;
        cin >> x;
        cnt[x]++;
    }
    ll ans = 0;
    for (auto v : cnt)
    {
        ll num = v.second;
        ans += ((num) * (num - 1)) / 2;
        // cout << v.first << ' ' << num << ' ' << ans << endl;
    }
    ans += cnt[1] * cnt[2];
    cout << ans << endl;
}

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

E. Queue Sort

题意:

给定一个循环数组,问最少进行多少次操作后,数组完全升序。如果无论怎样都无法完全升序,那么输出\(-1\)。

操作为:将第一个数字移到最右端,一直和前一个数字比大小,直到遇到严格小于他的数才停下来,否则就一个一个地向前移动。

解题思路:

如果最终可以升序,那么最多操作\(n\)次。即所有数都操作一遍。

我们会发现,当不存在\(a[i] > a[j],(i < j)\)时,即后面的数都比我大了,那么该位置其实就不用操作了。

所以,我们从右往左找到第一个符合上述条件的位置,就是我们理论上的最小操作次数\(cnt\)。

然后,我们遍历前\(cnt\)个一定要操作的数,如果对于该操作数,整个数组中没有能让他停下来的数,即没有严格小于他的数,那么他就会一直循环,也就是无解。

若对于所有数都存在严格小于他的数,那么答案就是\(cnt\)。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int mina = 1e9 + 19;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    };
    ll ans = 0;
    for (int i = n; i; i--)
    {
        if (i == n)
        {
            mina = min(mina, a[i]);
            continue;
        }
        if (a[i] > mina)
        {
            ans = max((ll)i, ans);
        }
        mina = min(mina, a[i]);
    }
    for (int i = 1; i <= ans; i++)
    {
        if (a[i] <= mina)
        {
            ans = -1;
            break;
        }
    }
    cout << ans << endl;
}

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

F. Alex's whims

题意:

开始构造一棵树。然后我们有\(q\)次询问。每次询问给定一个\(d\),我们可以删去一条边,然后加上一条边,保证他仍然是一颗树的情况下,使得存在两个叶子间的距离为\(d\),输出操作方案,当然,如果树此时状态就存在\(d\),也可以不操作。

删边,加边操作为\((u,v_1,v_2)\),即删去边\((u,v_1)\),加上边\((u,v_2)\)。\(d_i\)每次询问给定。

解题思路:

开始构造一个\(1 \sim n\)的链。\(d\)是多少,就将\(n\)与当前链接的边断开\((当然,是通向结点1的方向的边)\),连到\(d\)点上。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i < n; i++)
    {
        cout << i << ' ' << i + 1 << endl;
    }
    int last = n - 1;
    int idx = 0;
    int dist = n - 1;
    while (q--)
    {
        int d;
        cin >> d;
        int u, v1, v2;
        if (dist == d)
        {
            u = -1;
            v1 = -1;
            v2 = -1;
        }
        else
        {
            u = n;
            v1 = last;
            v2 = d;
            last = v2;
            dist = d;
        }
        cout << u << ' ' << v1 << ' ' << v2 << endl;
    }
}

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

标签:int,ll,909,Codeforces,long,--,solve,using,Div
From: https://www.cnblogs.com/value0/p/17847788.html

相关文章

  • codeforces 50题精选训练
    本章节参考:2020,2021年CF简单题精选-题单-洛谷|计算机科学教育新生态(luogu.com.cn) T1:首先,很容易观察到点的一些特征:-都在第一象限;-点的分布越来越稀疏。以样例为例:   还有无限个点没有画出来。根据点的分布越来越稀疏的特性,能不能发现收集点的规......
  • Codeforces Round 905 (Div. 3) ABCDEG1
    CodeforcesRound905(Div.3)ABCDEG1A.Morning思路:签到,直接模拟。//AConemoretimes//nndbk#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmod=1e9+7;constintN=2e5+10;intmain(){ios::sync_with_stdio(fal......
  • Educational Codeforces Round 99 (Rated for Div. 2)
    https://codeforces.com/contest/1455很久没有vp了,感觉思维又僵化了A题直接看样例,直接猜是长度。B题首先如果是\(x=\frac{n(n+1)}{2}\),那么就是n否则如果\(x=\frac{n(n+1)}{2}+y\),分成两类y=n,ans=n+2,y<n,我们总可以找到前面一个替换,然后恰好的到n,选取z=n-y即可C题感觉比B......
  • Educational Codeforces Round 156 (Rated for Div. 2) ABCD
    EducationalCodeforcesRound156(RatedforDiv.2)ABCDA.SumofThree题意:给定正整数\(n\),判断是否存在正整数\(a\),\(b\),\(c\)满足:\(a+b+c=n\)。\(a\),\(b\),\(c\)均不是\(3\)的倍数。如存在,输出YES并构造一组方案,否则输出NO。思路:法一:我们分类讨论。根据......
  • Codeforces Round 904 (Div. 2)
    \(A.SimpleDesign\)https://codeforces.com/contest/1884/submission/233628914\(B.HauntedHouse\)https://codeforces.com/contest/1884/submission/233629446\(C.MediumDesign\)https://codeforces.com/contest/1884/submission/233632930\(D.Counting......
  • jquery 检测div宽度变化_jquery判断浏览器宽度小于指定值改变div样式
    浏览器原本样式当浏览器宽度小于1200px时样式变为代码如下:方法一:直接修改该div样式添加w1200,会覆盖前一个样式$(function(){var_width=$(window).width();//获取浏览器宽度if(_width<1200){$(".chenbin_org").addClass("w1200");}});方法二:修改该div的class属性......
  • Codeforces Round 910 (Div. 2) - D
    目录D.AbsoluteBeautyCodeforcesRound910(Div.2)D.AbsoluteBeauty观察可知,只要当交换的\(i\)和\(j\)满足$max(a_i,b_i)<min(a_j,b_j)$或者$min(a_i,b_i)>max(a_j,b_j)$......
  • CodeForces 合集第三弹
    这个合集主要是近期的CodeForces比赛题。1898.CodeforcesRound910(Div.2)https://codeforces.com/contest/1898A.MilicaandString很容易发现答案不超过\(1\),然后分类讨论当前B的个数然后选取一个前缀赋值即可。如果已经满足条件答案就是\(0\)。反正随便做做,时间......
  • Codeforces Round 785 (Div. 2)
    A-SubtleSubstringSubtraction/**__----~~~~~~~~~~~------___*..~~//====......__--~~~*-.\_|//|||\\~~......
  • Codeforces Round 908 (Div. 2)
    Preface补一下之前期中考落下的CFyysy因为这学期又开始断电了,所以除了周五周六晚上的CF可能都不一定会去打,都会以后面补题为主A.SecretSport由于题目保证给出的状态合法,因此直接输出最后一个字符即可#include<cstdio>#include<iostream>#include<utility>#include<vect......