Codeforces 636(Div.3)

A题

题意：给你一个n，解方程，(1+2+4+…+2^(k-1))*x=n，保证k>1。

思路：这道题的话，因为保证有解，我们枚举一下k就行。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        ll sum = 4;
        while (n % (sum - 1) != 0)
            sum *= 2;
        cout << n / (sum - 1) << endl;
    }
    return 0;
}

B题

题意： 给一个偶数n，构造一个数组，前面都是偶数，后面都是奇数，且互不相同。且前面n/2个数的和与后面n/2个数的和相等。

思路：这道题的话，首先如果n/2是奇数肯定不成立。前面是偶数，后面是奇数，不相等。如果n/2是偶数我们就尝试构造。偶数就2,4,6,8这样输出，奇数就1,3,5,7这样输出。然后在最后一个数把前面的差补全就好了。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        if ((n / 2) % 2 != 0)
            cout << "NO" << endl;
        else
        {
            cout << "YES" << endl;
            for (int i = 1; i <= n / 2; ++i)
                cout << 2 * i << " ";
            for (int i = 1; i <= n / 2 - 1; ++i)
                cout << 2 * i - 1 << " ";
            cout << n / 2 * 3 - 1 << endl;
        }
    }
    return 0;
}

C题

题意：给一个序列a，问你最长连续正负子序列的和最大是多少。

思路：这道题的话，我们可以将序列a的正负分开来算，所以这个序列被分成了几个正连续子序列和负连续子序列，我只要将每一段序列求出它在这段的最大值最后将所有段的最大值相加就是答案。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 200010;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353;
using namespace std;
ll a[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        ll sum = 0;
        cin >> a[1];
        ll maxx = a[1];
        for (int i = 2; i <= n; i++)
        {
            cin >> a[i];
            if (a[i] * a[i - 1] < 0)
            {
                sum += maxx;
                maxx = a[i];
            }
            else
            {
                maxx = max(maxx, a[i]);
            }
        }
        sum += maxx;
        cout << sum << endl;
    }
    return 0;
}

D题

题意：给你n个数的数组，n为偶数。每一个数都不超过k，修改之后的值也不能超过k。现在求最小的修改次数，使得$a[i]+a[n-i+1]=const$。

思路：这道题的话，1.我们发现，将a[i]和a[n-i+1]全变为1是sum最小的值,将a[i]和a[n-i+1]全变为2k是sum最大的值。所以sum的取值范围为【2,2k】；
2.我们发现每一对a[i]和a[n-i+1]都分三种情况：1）修改1次 2）修改2次 3）不修改。
分析修改一次的情况：将a[i]和a[n-i+1]修改一次后，最小值的话就是将最大的数变1，用公式表示为 min（a[i],a[n-i+1]）+1；则最大值公式为：max（a[i],a[n-i+1]）+k；所以修改一次的区间为【min（a[i],a[n-i+1]）+1，max（a[i],a[n-i+1]）+k】，在此区间内，其修改次数全是1，分析修改零次的情况：当sum刚好等于a[i]+a[n-i+1]，不用修改。分析修改2次的情况：除了一次和零次外，其余段全是修改两次。根据以上特性我们可以用差分，来维护区间内修改次数，枚举sum，看sum落在哪个区间内。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 200010;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353;
using namespace std;
int vis[maxn << 1];
ll a[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n / 2; i++)
        {
            int l = min(a[i], a[n - i + 1]) + 1;
            int r = max(a[i], a[n - i + 1]) + k;
            int sum = a[i] + a[n - i + 1];
            vis[2] += 2;
            vis[l]--;
            vis[r + 1]++;
            vis[sum]--;
            vis[sum + 1]++;
        }
        int ans = inf;
        for (int i = 2; i <= 2 * k; i++)
        {
            vis[i] += vis[i - 1];
            ans = min(ans, vis[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦