[Codeforces]Global Round 10
|
64
|
0
|
题解

940 字
|
4 分钟
本文最后更新于 159 天前，其中的信息可能已经有所发展或是发生改变。

Before the Beginning

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

前言

补题。

C

一次选择一段连续的单调不减的元素加一，问最少多少次操作后，整个数组单调不减。
差分一下，$d(i) = a(i) – a(i-1)$，然后每个 $d(i) < 0$ 都加上其绝对值就是答案。
对于连续的一段 $d(i) < 0$ 即单调递减，最优操作是将每个数调整到相等后，对一整段进行操作。
猜结论题。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e5 + 100;
int T;
int n,a[maxn],d[maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for (int i = 1; i <= n; ++i) read(a[i]);
        for (int i = 1; i <= n; ++i) d[i] = a[i] - a[i-1];
        long long ans = 0;
        for (int i = 1; i <= n; ++i) if(d[i] < 0) ans += std::abs(d[i]);
        printf("%lld\n",ans);
    }
    return 0;
}

B

每次操作后，$a_i := \max a – a_i$，那么第二次 $d = \max a – \min a$，$a _i := \max a – \min a – (\max a – a_i)$，即 $a_i := a_i – \min a$，第三次 $d = \max a – \min a$，又是 $a_i := \max a – \min a – (a_i – \min a)$ 得到 $a_i := \max a – a_i$，因此操作一次与操作三次等价，操作两次与操作四次等价，周期为二。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e5 + 100;
int T;
int n,a[maxn];
long long k;
inline void solve()
{
    int maxx = a[1];
    for (int i = 2; i <= n; ++i) maxx = std::max(maxx, a[i]);
    for (int i = 1; i <= n; ++i) a[i] = maxx - a[i];
}
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        read(k),k %= 2;
        for (int i = 1; i <= n; ++i) read(a[i]);
        if(k) solve();
        else solve(),solve();
        for (int i = 1; i <= n; ++i) printf("%d ",a[i]);
        putchar('\n');
    }
    return 0;
}

A

每次合并相邻的不相等的两个数，求不能操作时最短长度。
显然对于某一段来说，操作顺序不会影响结果。因此若合并 $[i,j]$，结果为 $sum(i) – sum(j – 1)$，考虑如何到达最终状态。
最终状态显然是全部数相等，此时剩余多少个元素呢？我们大胆猜测，除非开始就全部相等，否则一定可以只剩一个元素。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e5 + 100;
int T,n;
int a[maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for (int i = 1; i <= n; ++i) read(a[i]);
        for(int i = 1;i<n;++i)
        {
            if(a[i] != a[i+1])
            {
                puts("1");
                goto end;
            }
        }
        printf("%d\n",n);
        end:;
    }
    return 0;
}

D

每个玩家有两种情况：

  1. 如果被一个人攻击，则必须回击。
  2. 如果被两个或无人攻击，则随意攻击。

在第二种情况中，若没人攻击该玩家，该玩家随意攻击，则被攻击的一定要回击，除非他是被二人攻击的人。

那么符合条件的情况是怎么样的呢？
显然被两个人攻击的情况很少，而大多数在互相攻击。
如果一个人被两个人攻击，他攻击一个人，而另一个未被他攻击的人，一定不能被其他人攻击，因此被2人攻击的人旁边一定有被0人攻击的人。
那么什么时候才不合法呢？
只有三个连续的 $L/R$ 才会不合法，而对于三个连续的 $L/R$，只要改变一个就可以合法。

#include <algorithm>
#include <cstdio>
#include <ctype.h>

const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(char* s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 4e5 + 100;
int T, n;
char s[maxn];
int len[maxn];
int main()
{
    read(T);
    while (T--)
    {
        read(n);
        read(s + 1);
        for (int i = 1; i <= n; ++i) s[i + n] = s[i];
        int ans = (n + 2) / 3;
        for (int i = 1; i <= n; ++i)
        {
            if (s[i] != s[i + n - 1])
            {
                int res = 0;
                len[i - 1] = 0;
                for (int j = i; j <= i + n - 1; ++j)
                    if (s[j] == s[j - 1]) len[j] = len[j - 1] + 1;
                    else len[j] = 1, res += len[j - 1] / 3;
                res += len[i + n - 1] / 3;
                ans = res;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

E

交互题，你给矩阵任意赋值，程序告诉你一个数，该数为从 $(1,1)$ 到 $(n,n)$ 的某路径上数字和，保证每次只向下或向右移动，要求还原该路径。

$n \le 25$，一开始的想法是给每个格子都分配一位，就可以轻松地判断，然而对值的大小有要求，因此需要优化。
首先，可以每两行留空一行，空行可以通过上行和下行的进入点判断路径。
不必每个格子都占据一位，只需要保证合法路径值两两不同即可。
只要最低位无重复，就一定可以判断出某行的进入点。
还要保证向右向下可以区分，因此可以如下构造：

$0,0,0,\ldots,0$
$2^2,2^3,2^4,\ldots,2^{n+2}$
$0,0,0,\ldots,0$
$2^4,2^5,2^6,\ldots,2^{n+4}$
$0,0,0,\ldots,0$
$2^{n},2^n,2^{n+1},\ldots,2^{2n – 1}$

$a(i,j) = 2^{i+j-1}$，检查时，第 $x$ 步能走到 $(i,j)(i+j-2=x)$，那么第 $x$ 步对应第 $x + 1$ 位。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
inline char nc(){return getchar();}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 30;
int n;
long long a[maxn][maxn];
int in[maxn];
int X[maxn*2],Y[maxn*2],cnt;
int main()
{
    read(n);
    for (int i = 1; i <= n; ++i) 
        for(int j = 1;j<=n;++j)
            if((i % 2) == 0) a[i][j] = 1ll<<(i+j-1);
    for (int i = 1; i <= n; puts(""), ++i) for (int j = 1; j <= n; ++j) printf("%lld ", a[i][j]);
    fflush(stdout);
    int m;
    read(m);
    while(m--)
    {
        long long k;
        read(k);
        puts("1 1");
        int x = 1, y = 1;
        for(int i = 1;i<=n * 2 - 2;++i)
        {
            long long flag = k & (1ll<<(i+1));
            if(x + 1 <= n && a[x+1][y] == flag) ++x;
            else ++y;
            printf("%d %d\n",x,y);
        }
        fflush(stdout);
    }
    return 0;
}

相关文章

  1. [Atcoder]M-Solutions 题解 Before the Beginning 转载请将本段放在文章开头显眼处，如有二次创作请标明。原文链接：htt […]...
  2. [Codeforces]Round 659 div2 Before the Beginning 转载请将本段放在文章开头显眼处，如有二次创作请标明。原文链接：htt […]...
  3. [Atcoder][CF]简单题选做练习笔记2 一些题的练习笔记。...
  4. [Atcoder][Codeforces]简单题选做练习笔记 title: ‘Atcoder简单题选做练习笔记’date: 2020-11-12 1 […]...
本文标题：[Codeforces]Global Round 10
本文作者：Clouder
本文链接： https://www.codein.icu/cf1392/
转载请标明。
Codeforces比赛
暂无评论

发送评论 编辑评论




























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



上一篇
下一篇