Codeforces Round #560 (Div. 3)

2019-05-17 本文已影响0人阿臻同学

A. Remainder

题意

给一个由0和1组成的数n，每次可以用0或1替换其中一个数，问最少要需要多少次操作才能使 $n \mod 10^x=10^y$ 。

关键字

数学、模拟

思路

统计如下操作的次数：

第x位的0替换成1。
在x-1到第y-1位中，将所有1替换成0。
第y位的0替换成1。
y以后的数字中，1替换成0.

代码

#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200006
#define MAXM 100006
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC
    int n, x, y;
    SCAND(n);
    SCAND(x);
    SCAND(y);
    int arr[MAXN];
    getchar();
    for (int i = 0; i < n; ++i)
    {
        arr[i] = getchar() - '0';
    }
    int ans = 0;
    for (int j = n - x; j < n; ++j)
    {
        if (j != 0 && j < n - y - 1 && arr[j] == 1)
            ans++;
        else if (j == n - y - 1 && arr[j] == 0)
            ans++;
        else if (j > n - y - 1 && arr[j] == 1)
            ans++;
    }

    PRINTD(ans);

#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

B. Polycarp Training

题意

有n套题目，从以第一天开始，每天可以选一套以前没选过的题目，第i天需要解决i道题目。每天做的题目中，多余i的作废。
问最多可以做多少天。

关键字

排序、模拟

思路

直接排个序，然后一天一天枚举过去即可。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 200005
#define MAXM 1000006
#define MAXK 10000010
#define MOD 998244353
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;


int main ()
{

#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC

    int n;
    SCAND(n);
    int arr[MAXN];
    for (int i = 0; i < n; ++i)
    {
        SCAND(arr[i]);
    }

    sort(arr, arr + n);
    int d = 0;
    for (int i = 0; i < n; ++i)
    {
        if (arr[i] >= d + 1)
            d++;
    }
    PRINTD(d);
    puts("");


#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

C. Good String

题意

给一个字符串，如果长度为偶数，且所有奇数位的字符与下一个字符不相同，则认为这是一个“好的”字符串。

每次可以移除其中一个字符，问最少需要多少次操作，让一个字符串变为一个“好的”字符串，并输出操作后的字符串。

关键字

贪心

思路

对于每一个位置的字符 $s_i$ ，从 $s_{i+1}$ 开始到 $s_{n}$ 枚举下一个位置的字符，直到下一个位置和当前位置不同，中间相同的都移除。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 200006
#define MAXM 100006
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

char str[MAXN];

int main ()
{

#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC
    int n;

    SCAND(n);
    set<char> se;
    getchar();
    bool tag = n % 2;
    for (int i = 0; i < n; ++i)
    {
        str[i] = getchar();
        se.insert(str[i]);
        if (i % 2 == 1 && str[i - 1] == str[i])
            tag = 0;
    }


    if (se.size() == 1)
    {
        printf("%d\n\n", n);
    }
     else
    {
        char s[MAXN];
        int ans = 0;
        int j = 0;
        for (int i = 0; i < n; ++i)
        {
            s[j++] = str[i++];
            while (s[j-1] == str[i])
            {
                i++;
                ans++;
            }
            if(i<n)
            {
                s[j++] = str[i];
                if(i == n-2)
                {
//                    ans++;
                }
            }
        }
        if(j%2 == 1)
        {
            j--;
            ans++;
        }

        s[j] = '\0';
        printf("%d\n%s\n", ans, s);
    }


#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

D. Almost All Divisors

题意

对于每组案例，给定n个数，问在假设这n个数为数x的除去1和x之外的所有因子，能不能唯一确定x。

关键字

数论。

思路

先对给定的 $n$ 个数排序，假设第 $i$ 个数为 $a_i$ 。
令: $x=\max\{a\} \cdot\min\{a\}$
枚举 $x$ 除去 $x$ 和 $1$ 之外的所有因子，判断是否和给定的 $n$ 个数恰好完全相同。

如果两边不一样，显然无解。
若一样，则结果即为上面 $x$ 的值（当 $n=1$ 时， $x$ 则为那个唯一的数的平方）。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 200005
#define MAXM 1000006
#define MAXK 10000010
#define MOD 998244353
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int main ()
{
//    SYNC
    int T;

    SCAND(T);
    while (T--)
    {
        int n;
        SCAND(n);
        vector<ll> vt;
        for (int i = 0; i < n; ++i)
        {
            ll t;
            scanf("%lld", &t);
            vt.pb(t);
        }
        sort(vt.begin(), vt.end());
        ll ans = vt.front() * vt.back();

        vector<ll> vt2;
        for (ll i = 2; i <= sqrt(ans); ++i)
        {
            if (ans % i == 0)
            {
                vt2.pb(i);
                ll res = ans / i;
                if (res != i)
                    vt2.pb(res);
            }
        }
        if (vt2.size() != n)
            ans = -1;
        else
        {
            sort(vt2.begin(), vt2.end());
            for (int i = 0; i < n; ++i)
            {
                if (vt[i] != vt2[i])
                {
                    ans = -1;
                    break;
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

E. Two Arrays and Sum of Functions

题意

给定2个数组 $a$ 和 $b$ ，可以对两个数组任意排序，要求求出任意区间 $[l,r]$ 中的 $\sum_{i=l}^{r}{a_i\cdot b_i}$ 的和。

关键字

排序、贪心

思路

首先可以确定的是，对于第 $i$ 个数，在求区间和的过程中，一共计算了 $i\cdot (n-i+1)$ 次。
所以，最终的结果一定是：
$\sum_{i=1}^{n} a_i\cdot b_i\cdot i \cdot (n-i+1)$
假设数组 $a$ 的顺序已经确定，则可以说 $a_i \cdot i \cdot (n-i+1)$ 都是已经知道了的，剩下需要处理的就是数组 $b$ 的顺序。
要使最终结果最小，则对于最大的 $a_i \cdot i \cdot (n-i+1)$ ，用最小的 $b_i$ 去乘即可。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 200005
#define MAXM 1000006
#define MAXK 10000010
#define MOD 998244353
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int n;
ll a[MAXN], b[MAXN];

int main ()
{

#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC
    SCAND(n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%lld", &a[i]);
        a[i] = (a[i] * (i + 1) * (n - i));
    }
    for (int i = 0; i < n; ++i)
    {
        scanf("%lld", &b[i]);
    }
    sort(b, b + n);
    sort(a, a + n, greater<ll>());

    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        ans = (ans + (a[i]%MOD * b[i]%MOD) % MOD) % MOD;
    }
    printf("%lld\n", ans);

#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

F. Microtransactions (hard version)

题意

给定n种商品需要购买的数量，和m种折扣（折扣<a,b>表示第 $a$ 天第 $b$ 种商品打折）。
每种商品正常价格为2，折扣价格为1，且每天余额会加1。
问买齐所有商品最少需要多少天。

关键字

二分、贪心

思路

二分枚举最少需要的天数 $d$ ，对于 $d$ 若满足一下情况即为合法的天数：
从第 $d$ 天到第 $1$ 天，倒过来枚举折扣。假设：

需要购买的商品总数为 $tot$ ，
当前的余额为 $m$ ，
每种商品需要的数量为 $k_i$ ，
对于当前的折扣 $<a,b>$ ， $b$ 种商品已购买的数量为 $num_b$ ，
则还需购买的数量 $cnt=\min(k_i-num_i, m)$ 。

在枚举的过程中，维护余额 $m$ 、已购买每种商品数量 $num_i$ 、使用优惠购买的总物品数量 $count$ ：

m -= cnt;
num[b] += cnt;
count += cnt;

如此即可判断对于当前的天数 $d$ （余额最多也为 $d$ ），在尽可能使用优惠购买后，余额能否购买余下的部分：

return 2*(tot-count)<=d-count

代码

#include <bits/stdc++.h>
#define Debug 0
#define MAXN 200005
#define MAXM 1000006
#define MAXK 10000010
#define MOD 998244353
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)
#define EPS 1e-6
#define null Point(EPS/10, EPS/10)
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int n, m;
int arr[MAXN];
vector<int> sale[2 * MAXN];
int tot = 0;
int num[MAXN];      // num[i]: 已购买第i种的数量
bool ok (int mid)
{
    int cnt = 0;    // 当前购买的数量
    int mon = mid;  // 余额
    MSET(num, 0);
    for (int i = mid; i > 0; --i)
    {
        if (mon > i)
            mon--;
        for (int j = 0; j < sale[i].size(); ++j)
        {
            int x = sale[i][j];     // 在第 i 天打折出售的商品
            // 对于第x种商品, 在 [当前余额能购买的数量] 和 [还需要购买的数量] 之间取最小值, 并购买这个数量
            int buy = min(arr[x] - num[x], mon);
            mon -= buy;
            num[x] += buy;
            cnt += buy;
        }
    }
    // 判断余额是否足够购买 所有不使用折扣的商品
    return 2 * (tot - cnt) <= mid - cnt;
}

int main ()
{

#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC

    SCAND(n);
    SCAND(m);
    for (int i = 1; i <= n; ++i)
    {
        SCAND(arr[i]);
        tot += arr[i];
    }
    for (int i = 1; i <= m; ++i)
    {
        int a, b;
        SCAND(a);
        SCAND(b);
        sale[a].pb(b);
    }
    int l = 1, r = 2 * MAXN;
    int mid;
    int ans;
    while (l <= r)
    {
        mid = ((l + r) >> 1);
        if (ok(mid))
        {
            r = mid - 1;
            ans = mid;
        } else
            l = mid + 1;
    }
    PRINTD(l);
    puts("");

#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}