Codeforces Global Round 2 Editorial

A. Ilya and a Colorful Walk

题意

给n个不同颜色的房子，求出两个不同颜色的房子的最远距离是多少。

关键词

贪心

思路

对于每一个房子，用来和第一个、最后一个房子比较颜色并求距离，用这个距离来更新最大距离就是答案。

代码

#include <bits/stdc++.h>
#define Debug 0
#define MAXN 300056
#define MAXM 200
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int arr[MAXN];
int pos[MAXN];
vector<Pair> vt;
int ans = 0;
int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
    SYNC
    int n;
    cin>>n;
    memset(pos, -1,sizeof(pos));
    for (int i = 0; i < n; ++i)
    {
        cin>>arr[i];
    }
    for (int i = 0; i < n; ++i)
    {
        if(arr[i]!=arr[0])
        {
            ans = max(ans, i);
        }
        if(arr[i] != arr[n-1])
        {
            ans = max(ans, n-1-i);
        }
    }
    cout<<ans<<endl;
#ifdef FILE_IN
    fclose(stdin);
#endif
    return 0;
}

B. Alyona and a Narrow Fridge

题意

给一个宽为2，高为h冰箱，以及n个宽为1，高为ai的瓶子。
可以在冰箱中添加不占空间的夹板，问最多能放多少个瓶子。

关键词

贪心

思路

对瓶子高度降序排序，每次选取最近的两个，以两个中较高的一个的高度放置隔板，直到无法再放下任何瓶子或者瓶子放完。

代码

#include <bits/stdc++.h>
#define Debug 0
#define MAXN 300056
#define MAXM 200
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;

int ans = 0;
vector<int> pq;
int n,h;
int arr[MAXN];
int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC
    cin>>n>>h;
    int tag = 1;
    for (int i = 0; i < n; ++i)
    {
        cin>>arr[i];
        pq.pb(arr[i]);
        sort(pq.begin(), pq.end(), greater<int>());
        int hh = h;
        for (int j = 0; j <= i; ++j)
        {
            int t1 = pq[j];
            if(j<i)
            {
                t1 = max(t1, pq[j+1]);
                ++j;
            }
            if(hh<t1)
            {
                tag = 0;
                break;
            }else
            hh -= t1;
        }
        if(!tag)
        {
            break;
        } else
        {
            ans = i+1;
        }
    }
    cout<<ans<<endl;
#ifdef FILE_IN
    fclose(stdin);
#endif
    return 0;
}

C. Ramesses and Corner Inversion

题意

给定两个n*m的矩阵A和B，问能否在矩阵A中，通过若干次变换一个子矩阵的四个角来得到B矩阵。

关键词

构造、贪心、奇偶

思路

计算每行每列中，有多少个不同的地方，一旦某行或某列出现奇数个不同的，就是No，必须都是偶数才是Yes。
显然，每次变换一个子矩阵的四个角，意味着四个角所在行或者列都会改变2个元素。
进行若干次变换，每行每列改变的元素个数必然也是偶数个。
所以，当某一行或者某一列出现奇数个不同的地方，就无法从矩阵A得到矩阵B。

代码

#include <bits/stdc++.h>
#define Debug 0
#define MAXN 556
#define MAXM 200
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;
bool ans = 1;
int n,m;
int a[MAXN][MAXN],b[MAXN][MAXN],df[MAXN][MAXN];
int r[MAXN] = {0}, c[MAXN] = {0};
int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC
    cin>>n>>m;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin>>a[i][j];
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin>>b[i][j];
            df[i][j] = b[i][j] == a[i][j];
            if(!df[i][j])
            {
                r[i]++;
                c[j]++;
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        if(r[i] %2== 1)
        {
            ans = 0;
            break;
        }
    }
    for (int i = 0; i < m; ++i)
    {
        if(c[i] %2== 1)
        {
            ans=  0;
            break;
        }
    }
    if(ans)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
#ifdef FILE_IN
    fclose(stdin);
#endif
    return 0;
}

D. Frets On Fire

题意

给定n个序列的起始值。
设第i个序列的起始值为si，该序列之后的每一个数等于前一个数加1（即序列i可描述为：[si,si+1,si+2,……,∞]）。
再给出q个询问，每个询问中包含两个整数l和r。
需要求出，在每个序列中，选取[l,r]这个区间中的值，求出现过的数字种类和，即：重复的数字只算一次。

关键词

排序、二分。

思路

对si排序，求差值，再排序，求和。二分查找输入区间长度所在的位置。
在这道题目中，每一个区间内具体选中了哪些数字其实并不重要。
首先对si排序，求出相邻两个si的差值。
对于每一段区间，去分析它在[l,r]这个查询中贡献的数字数量。记[l,r]的区间长度为w，w=r-l+1。对如下三种情况进行分析：

  1. 如果si+1-si>w，si所代表的区间最多只能贡献w个数。
  2. 否则如果w>si+1-si，si所代表的区间最多只能贡献si+1-si个数。超过的部分算作si+1所代表的区间所贡献的部分。
  3. 且，最后一个序列所贡献的数字数量为w，因为它后面没有了其他区间，可以假设其与后面一项差值为∞。

所以，对于区间长度w，可以对之前求的差值进行排序，使用二分快速求出有多少个区间满足第一种情况，多少个满足第二种情况。对第二种情况累加求和，加上第一种情况的数量*w即为答案
用第一个案例的第二个查询举例子：


第一个案例的第二个查询

按照这个思路去编程即可。

代码

#include <bits/stdc++.h>
#define Debug 0
#define MAXN 100005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

ll arr[MAXN];
ll num[MAXN];  // 区间差值
ll sum[MAXN] = {0};  // 差值求和

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

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
    sort(arr, arr + n);  // 对输入排序
    for (int i = 0; i < n - 1; ++i)
    {
        num[i] = arr[i + 1] - arr[i];
    }
    sort(num, num + n - 1);  // 对差值排序
    for (int i = 0; i < n - 1; ++i)
    {
        // 对排序后的差值求和，方便后续直接取值
        if (i)
            sum[i] = sum[i - 1] + num[i];
        else
            sum[i] = num[i];
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; ++i)
    {
        ll l, r;
        cin >> l >> r;
        ll t = r - l + 1;
        // 找到分界的位置，在这个位置之前都是小于r-l+1的
        int ind = upper_bound(num, num + n - 1, t) - num;
        // 由于使用的upper_bound，所以分别处理分界位置ind为0
        // 和ind为n-1(求差值后只剩n-1个数且从0开始，所以n-1为所有区间长度都小于r-l+1)的情况
        ll ans = 0;
        if (ind < n - 1)
        {
            if(ind)
            {
                // 通常情况
                ind--;
                ans = sum[ind] + (n - 1 - ind) * t;
            } else
            {
                ans = n*t;
            }
        }
        else
            ans = t + sum[n-2];
        cout << ans << endl;

    }

#ifdef FILE_IN
    fclose(stdin);
#endif
    return 0;
}

E. Pavel and Triangles

题意

给定n种长度的棍子，接下来的n个整数，第i个整数表示长度为2i的棍子有多少个。
求出使用这些木棍最多能构成多少个三角形。
每个木棍都只能使用一次，且不可折断。

关键词

贪心

思路

对于当前长度的棍子，优先考虑使用两根当前长度的加一根较短的棍子去构成等腰三角形。无法构成等腰三角形时，再考虑使用三根当前长度的棍子去构成等边三角形。剩下的留给后面构造等腰三角形用。

代码

#include <bits/stdc++.h>
#define Debug 0
#define MAXN 300005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#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;
    cin >> n;
    ll r = 0; // The remainder
    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        ll t;
        cin >> t;
        ll t2 = min(t / 2, r);
        t -= t2 * 2;
        r -= t2;
        ans += t2;
        ans += t/3;
        r += t%3;
    }
    cout << ans << endl;
#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

G. Get Ready for the Battle

题意

给定n个士兵，可以划分到m个组中，其中有些组可以为空。
再给定m组个敌人，每组敌人生命值为输入的该组人数。
每一轮可以选择自己的士兵去攻击敌人，每个组在每一轮中只可以攻击一次，但可以多个组攻击同一组敌人。每一组的攻击可以造成相当于组中人数的伤害，敌人生命值为零时，这个组就算被击败了（下一轮就不能再攻击这个组了）。
并且自己的士兵分组都不会受到伤害（也就是只有我们打敌人）。
问最少需要多少轮才能将敌人全部击败。
需要输出自己士兵的分组情况和每一轮攻击的安排。

关键词

构造、排序

思路

对敌人的生命值累加求和，并且将前 i 项之和对n求余并保存在一个数组中。将对这个数组最后一项修改为n，然后排序后求差值。这个数组即为己方士兵的分组情况。按照这个分组，依照敌人输入的次序一轮一轮去杀敌即可。

  • 最优解法：

    1. 假设和已知前提：用 hpi 表示第i个敌人的生命值，ki 表示第i个敌人在生命值低于n时的生命值（可能是攻击后的结果，也可能是初始值）,sum表示敌人生命之和。我方士兵一轮攻击最高伤害为n。
    2. 攻击策略：从第一个敌人开始（i=1），在hpi 高于n的时候，显然，这一轮攻击无法击败这个敌人，需要所有伤害都打到它身上；在生命值小于n的时候，即生命值为ki的时候，最好的情况就是我方士兵存在一个伤害恰好为ki的组合，其他的士兵开始针对下一个敌人展开攻击，这样就不会在这个一轮攻击中可以击败的敌人身上浪费伤害，尽可能提高了攻击的效率。当然，在面对最后一个敌人的时候，就不需要考虑这么多了。
    3. 结论：在最优的攻击策略下，每一轮都能打满n的伤害，所以需要攻击的轮数就是对sum/n向上取整。满足最优的攻击策略只需要对于前m-1组敌人中的每一个ki，在我方士兵的分组中都能找到一个满足的组合即可。
    4. 求解：

  • 补充解释：

    1. 累加求余：求出上面定义的ki。因为是对累加求余，所以处理了在某一轮攻击中，按照上述的攻击策略将前面的敌人击败后，还攻击了第i个敌人使其生命值低于n的这种情况对ki影响。
      可以更形象地理解为，配合后面一步的排序将超过一轮攻击的情况合并到一轮攻击中来。
    2. 排序：让我们通过ki求出我们需要的分组方案。按照上面的策略，我们只需要知道一共有多少种ki需要我们去考虑，具体出现的位置并不会影响最终的答案，因为我们的策略就是只考虑如何能让我们的士兵分组组合出ki来。
      对接下来下一步相减求差值的理解：对于排序后的ki，i为1时，是最少一种敌人情况，直接按照这个分组即可；i>1时（可以拿i=2代入），说明前面的ki-1已经考虑过，只需要考虑从ki-1的组合增加一个小的分组使其得到ki即可，这个小的分组的人数就是ki-ki-1了。
    3. 末项为n：显然对已排序序列的求差值后，其中各项之和一定等于最后一项。一轮攻击下来最多能造成n的伤害。这里将最后一项修改为n，就是为了保证在后面的步骤中，一轮下来最多有n点伤害。
    4. 不足补0：一共有m（7）个分组，且题意说明了可以存在空的组，没有分配士兵的组就是0。

代码

#include <bits/stdc++.h>
#define Debug 0
#define MAXN 1000005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int hp[MAXN] = {0};
int b[MAXN] = {0};
ll sum = 0;
int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d", &hp[i]);
        sum += hp[i];
        b[i] = sum % n;
    }
    b[m] = n;
    sort(b + 1, b + 1 + m);
    for (int i = m; i >= 0; --i)
    {
        b[i] = b[i] - b[i - 1];
    }
    printf("%lld\n", (sum - 1) / n + 1);

    for (int i = 1; i <= m; ++i)
    {
        printf("%d%c", b[i], (i==m?'\n':' '));
    }

    int cur = 1; // Evlampy's army group
    for (int i = 1; i <= m; ++i)
    {
        // The enemy currently under attack
        int t = hp[i];
        while (t > 0)
        {
            t -= b[cur];
            ++cur;
            printf("%d%c", i, (cur>m?'\n':' '));
            if (cur > m)
            {
                cur = 1;
            }
        }
    }
    while (cur > 1 && cur <= m)
    {
        cout << 1 << (cur == m ? "\n" : " ");
        cur++;
    }
#ifdef FILE_IN
    fclose(stdin);
#endif
    return 0;
}

留坑

F. Niyaz and Small Degrees

题意

关键词

思路

代码

H. Triple

题意

关键词

思路

代码
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 205,386评论 6赞 479
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,939评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,851评论 0赞 341
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,953评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,971评论 5赞 369
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,784评论 1赞 283
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,126评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,765评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,148评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,744评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,858评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,479评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,080评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,053评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,278评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,245评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,590评论 2赞 343