[Codeforces]672 div2
本文最后更新于 117 天前,其中的信息可能已经有所发展或是发生改变。

一场有趣的比赛

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/cf1417/

A

容易想到拿一个最小值来不断地加。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1100;
int T,n,a[maxn],k;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&k);
        int minn = 1<<30,mini = 1;
        for (int i = 1; i <= n; ++i) scanf("%d",a + i),minn = min(minn,a[i]);
        for (int i = 1; i <= n; ++i) if(minn == a[i]) mini = i;
        int ans = 0;
        for (int i = 1; i <= n; ++i) if(i != mini) ans += max(0,(k - a[i]) / minn);
        printf("%d\n",ans);
    }
    return 0;
}

B

容易发现是构造题。
如果 $T$ 是偶数,可以以 $\dfrac{T}{2}$ 为分界线,大于的放一起,小于的放一起,等于的均分。
如果是奇数,取出分界线即可保证没有任何一对。

#include <cstdio>
const int maxn = 1e5 + 100;
int T,n,k,a[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&k);
        for (int i = 1; i <= n; ++i) scanf("%d", a + i);
        if(k & 1)
        {
            int left = k / 2;
            for (int i = 1; i <= n; ++i) if(a[i] <= left) printf("0 ");
            else printf("1 ");
        }
        else
        {
            int mid = k / 2,last = 1;
            for (int i = 1; i <= n; ++i)
                if (a[i] < mid) printf("0 ");
                else if (a[i] > mid) printf("1 ");
                else printf("%d ", last ^= 1);
        }
        puts("");
    }
    return 0;
}

C

定义为:在所有长度为 $k$ 的子序列中都出现的数字的最小值。
考虑记录每个数字能在长度为 $k$ 的子序列中都出现,可以发现,就是要求每两个相同数字间的间隔 $\leq k$.
特判数组开头和结尾。
那么:
如果在一个较短的子序列中都能全部出现,更长的一定也可以。
做一个后缀最大值的处理即可。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 3e5 + 100;
int T,n,pos[maxn],a[maxn],mindis[maxn],minn[maxn],vis[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for (int i = 1; i <= n; ++i) pos[i] = 0, mindis[i] = 0, minn[i] = 1 << 30,vis[i] = 0;
        for (int i = 1; i <= n; ++i) scanf("%d", a + i),vis[a[i]] = 1;
        for (int i = 1; i <= n; ++i) 
            mindis[a[i]] = max(mindis[a[i]], i - pos[a[i]]), pos[a[i]] = i;
        for (int i = 1; i <= n; ++i) mindis[i] = max(mindis[i],n - pos[i] + 1);
        for (int i = 1; i <= n; ++i) if (vis[i] && mindis[i] <= n) minn[mindis[i]] = min(minn[mindis[i]], i);
        for (int i = 2; i <= n; ++i) minn[i] = min(minn[i],minn[i-1]);
        for (int i = 1; i <= n; ++i) if(minn[i] == 1<<30) printf("-1 "); else printf("%d ",minn[i]);
        puts("");
    }
    return 0;
}

D

构造题。

由于一是最灵活的,考虑全部转移到一再操作。

每个数最多两次操作就能转化到一:

  1. 利用一补足为 $i$ 的整倍数
  2. 转化到一

在操作过程中,补足所需最大为 $i – 1$,而一号位置初始至少有 $1$,往后聚集后一定更多,因此补足所需一定能满足。

最后再操作平均分配即可。

#include <cstdio>
const int maxn = 1e4 + 100;
int T, n, a[maxn], ans1[maxn * 3], ans2[maxn * 3], ans3[maxn * 3], cnt;
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        cnt = 0;
        int sum = 0;
        for (int i = 1; i <= n; ++i) scanf("%d", a + i), sum += a[i];
        if (sum % n) { puts("-1"); continue; }
        sum /= n;
        for (int i = 2; i <= n; ++i)
        {
            int need = (i - (a[i] % i)) % i;
            if (need) ans1[++cnt] = 1, ans2[cnt] = i, ans3[cnt] = need;
            ans1[++cnt] = i, ans2[cnt] = 1, ans3[cnt] = (a[i] + need) / i;
        }
        for (int i = 2; i <= n; ++i) ans1[++cnt] = 1, ans2[cnt] = i, ans3[cnt] = sum;
        printf("%d\n", cnt);
        for (int i = 1; i <= cnt; ++i) printf("%d %d %d\n", ans1[i], ans2[i], ans3[i]);
    }
    return 0;
}

E

异或后的值,同样是最高位定大小。
可以从高位往低位逐层遍历,将数组分成两类:该位为零与为一的。这两类之间的贡献可以直接计算,且由于是最高位,往后都无需考虑。
只需要考虑同类之间的贡献,继续递归即可。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 3e5 + 100;
int n;
long long sum[maxn][2];
void solve(vector<int> v, int bit)
{
    if (v.empty() || bit < 0) return;
    vector<int> zero, one;
    long long zeronum = 0, onenum = 0;
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        if (*it & (1 << bit)) one.push_back(*it), onenum += zero.size();
        else zero.push_back(*it) , zeronum += one.size();
    sum[bit][0] += zeronum, sum[bit][1] += onenum;
    solve(zero, bit - 1), solve(one, bit - 1);
}
int main()
{
    scanf("%d",&n);
    vector<int> v;
    for (int i = 1, x; i <= n; ++i) scanf("%d", &x), v.push_back(x);
    solve(v, 30);
    long long res = 0;
    int x = 0;
    for (int i = 30; i >= 0; --i)
        if (sum[i][0] <= sum[i][1]) res += sum[i][0];
        else res += sum[i][1], x += (1 << i);
    printf("%lld %d\n", res, x);
    return 0;
}
本文标题:[Codeforces]672 div2
本文作者:Clouder
本文链接: https://www.codein.icu/cf1417/
转载请标明。

评论

  1. 4月前
    2020-10-05 9:30:11

    tql 您又ak了

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇