Codeforces Round #636 (Div. 3) A-C

Codeforces Round #636 (Div. 3) A-C

/ 0评 / 1233次 / 1

前三题还是比较水的。除了C题受制于英文理解成了正负交替子序列和最大值当成了条dp,也都没浪费什么时间

A. Candies

数学题

$$x=\frac{n}{2^k-1}$$

/*
 * @Author: Gehrychiang
 * @LastEditTime: 2020-04-22 22:11:28
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 * @ProbTitle: 
 */
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//(2^k-1)=n;
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    int t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        ll p = 2;
        while (n % ((1 << p) - 1) != 0)
        {
            ++p;
        }
        cout << n / ((1 << p) - 1) << endl;
    }
    return 0;
}

B. Balanced Array

也算个数学题,显然可以推出来n只有是4的倍数的时候才可以,在奇数最后一个补上前面奇数拉下的差值即可

/*
 * @Author: Gehrychiang
 * @LastEditTime: 2020-04-22 22:12:41
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 * @ProbTitle: 
 */
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//n%4==0
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        if (n % 4 != 0)
        {
            cout << "NO" << endl;
        }
        else
        {
            cout << "YES" << endl;
            for (int i = 1; i <= n / 2; i++)
            {
                cout << i * 2 << " ";
            }
            for (int i = 1; i <= n / 2 - 1; i++)
            {
                cout << i * 2 - 1 << " ";
            }
            cout << n - 1 + n / 2 << endl;
        }
    }
    return 0;
}

C. Alternating Subsequence

因为是要找最长的里面的最大值(注意先要保证最长)也就是说每一次遇到正负交替的时候一定要进行更新,而当符号相同时更新大值即可。小贪心

/*
 * @Author: Gehrychiang
 * @LastEditTime: 2020-04-22 22:14:07
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 * @ProbTitle: 
 */
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200005];
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        ll cursum = a[0];
        ll flag = a[0]; //保存上一个
        for (int i = 1; i < n; i++)
        {
            if (a[i] > 0)
            {
                if (flag < 0) //上一个为负 本次读+
                {
                    cursum += a[i];
                    flag = a[i];
                }
                else if (flag > 0 && a[i] > flag) //上一个为+ 本次读-
                {
                    cursum += (a[i] - flag);
                    flag = a[i];
                }
            }
            else if (a[i] < 0)
            {
                if (flag > 0) //上一个为+ 本次读-
                {
                    cursum += a[i];
                    flag = a[i];
                }
                else if (flag < 0 && a[i] > flag) //上一个为-本次读+ 更新更大的
                {
                    cursum += (a[i] - flag);
                    flag = a[i];
                }
            }
        }
        cout << cursum << endl;
    }
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。

你好 No.63967