Codeforces Round #560 (Div. 3)

作者: 阿臻同学 | 来源:发表于2019-05-17 15:03 被阅读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;
}

Codeforces Round #560 (Div. 3)

A. Remainder

题意

关键字

思路

代码

B. Polycarp Training

题意

关键字

思路

代码

C. Good String

题意

关键字

思路

代码

D. Almost All Divisors

题意

关键字

思路

代码

E. Two Arrays and Sum of Functions

题意

关键字

思路

代码

F. Microtransactions (hard version)

题意

关键字

思路

代码

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读