CodeForces | Codeforces Global R

2019-04-14 本文已影响0人 0与1的邂逅

不知不觉，也有一个多月没更新过了，现在打算一周更一次，整合自己在这一周的做题收获。(~~做题也只能是做很少的部分~~)

在上周中打了Codeforces1119——Codeforces Global Round 2，被打自闭了，后面又花了一些时间补了前五道题目。

PS：由于版面问题，题目就以截图形式，需要原题的同学可以自行去CF上查看。

A. Ilya and a Colorful Walk

题解：

题意：
有n个房子，编号为1~n，相邻编号的房子相邻(1与n不相邻)，这n个房子的颜色分别是 $c_1$ 、 $c_2$ 、······、 $c_n$ ，至少有两个房子的颜色是不同的。
每两个相邻之间的房子的距离为1，要求当两个房子i、j（ $i≠j$ ）的颜色 $c_i≠c_j$ 时，这两个房子之间的最大距离。
题解：【贪心】
要求最大距离，那么两个房子i、j必须更加靠近两端断点1和n。
令i=1，j从2~n开始，遍历一遍，求出此时最大的距离max_1。
再令j=n，i从1~n-1开始，遍历一遍，求出此时最大的距离max_2。
再比较max_1和max_2的最大值，即为解。
(即从头、尾对数组c分别进行一次遍历，求出最大的距离)

参考代码：

#include<iostream>
#include<cstdio>
using namespace std;
int c[300010];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
    }
    int count=0;
    int ans=0;
    for(int i=n;i>1;i--)
    {
        if(c[i]!=c[1])
        {
            count=i-1;
            break;
        }
    }
    ans=max(ans,count);
    for(int i=1;i<=n;i++)
    {
        if(c[n]!=c[i])
        {
            count=n-i;
            break;
        }
    }
    ans=max(ans,count);
    //printf("i:%d;j:%d\n",i,j);
    printf("%d\n",ans);
}

B. Alyona and a Narrow Fridge【思维】

题解：

题意：
现在有个 $H∗2$ 的立体冰箱，可以在任何一个格子顶部放隔板，现在有一些牛奶盒按顺序放入冰箱（牛奶盒不能叠起来，只能放在隔板上），第 $_i$ 个牛奶盒为 $a_i*1$ 的长方形，问最多能放几个牛奶盒。
题解：
将这些牛奶盒按照高度 $a_i$ 升序排序，假设现在 $a$ 数组有 $a_1$ 、 $a_2$ 、 $a_3$ 三个元素(牛奶盒的高度)，从右到左遍历数组 $a$ ，如果 $a_3<=h$ ，则 $a_3$ 对应的牛奶盒可以放入冰箱中，那么与 $a_3$ 相邻的 $a_2$ 必定可以放入冰箱中（将其放在 $a_3$ 的旁边），这时再考虑剩余的 $a_1$ ，如果 $a_3$ + $a_1$ < = h，说明 $a_1$ 也可以放入冰箱中。

【突破口：升序排序，从右到左遍历，如果 $a_i$ 可以放入冰箱，那么 $a_{i-1}$ 必定可以放入冰箱，即代码中的 $j-=2$ 】

注意这里牛奶盒是按照顺序开始放入冰箱的，所以，每输入一个 $a_i$ ，就需要对 $a$ 数组进行一遍排序。

参考代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int h;
int a[1010];
bool cmp(int x,int y)// sort的比较函数，这里可忽略
{
    if(x<y)return true;
    else return false;
}

int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d%d",&n,&h);
    while(~scanf("%d%d",&n,&h))
    {
        int i,j;
        int flag=0;
        int ans;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(flag==0)
            {
                sort(a+1,a+i+1,cmp);
                //for(int k=1;k<=i;k++)
                //printf("%d:%d ",k,a[k]);
                //puts("");
                long long sum=0;
                for(j=i;j>=1;j-=2)
                {
                    sum+=a[j];
                }
                if(sum<=h)
                {
                    if(i==n)ans=n+1;// 如果加上最后一个牛奶盒，仍然<= h，那个最后一个牛奶盒也算入其中(这里n+1是因为输出结果时需要减去1)
                }
                else if(sum>h)// 当超过冰箱的高度h，ans记录第一个不满足的牛奶盒的索引
                {
                    flag=1;
                    ans=i;
                }
            }
        }
        printf("%d\n",ans-1);// 最后需要减去1(因为此时ans为不满足条件的第一个牛奶盒的索引)
    }
    fclose(stdin);
    fclose(stdout);
}

C. Ramesses and Corner Inversion【奇偶性、规律】

题解：

题意：
给你两个01矩阵（只含有0、1的矩阵)，你只能执行一种操作：就是取上面矩阵中的子矩阵，将子矩阵的四个角的值由零变一，由一变零。求能否通过上述操作让矩阵A等于矩阵B。
题解：

解法：【规律性】

观察发现，

如果任意一列(行)的任意两个1变为0，那么此时这一列(行)的奇偶性不会改变。

如果一列(行)中的恰有一个1和一个0需要改变，那么 $1->0$ 、 $0->1$ ，奇偶性仍然没有变。

综上的发现，如果矩阵A每一行、每一列的奇偶性与矩阵B对应的每一行、每一列的奇偶性相同，那么就说明可以通过上述的操作，从矩阵A变为矩阵B。

判断奇偶性，可以使用位操作中的&操作
if target$1==1：说明target为奇数
if target&1==0：说明target为偶数

参考代码：【代码略长。。。逃~】

#include<iostream>
#include<cstdio>
using namespace std;

int mat_a[505][505];// 矩阵A
int mat_b[505][505];// 矩阵B
int row_a[505];// 记录矩阵A每一行的奇偶性
int column_a[505];// 记录矩阵A每一列的奇偶性
int row_b[505];// 记录矩阵B每一行的奇偶性
int column_b[505];// 记录矩阵B每一列的奇偶性
int n,m;

int main()
{
    //scanf("%d%d",&n,&m);
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    while(~scanf("%d%d",&n,&m))
    {
        int count_a=0;
        int count_b=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&mat_a[i][j]);
                count_a+=mat_a[i][j];
            }
            row_a[i]=(count_a&1);
            count_a=0;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&mat_b[i][j]);
                count_b+=mat_b[i][j];
            }
            row_b[i]=(count_b&1);
            count_b=0;
        }
        count_a=0,count_b=0;
        for(int j=1;j<=m;j++)
        {
            for(int i=1;i<=n;i++)
            {
                count_a+=mat_a[i][j];
                count_b+=mat_b[i][j];
            }
            column_a[j]=(count_a&1);
            column_b[j]=(count_b&1);
            count_a=0,count_b=0;
        }
        int flag=0;
        for(int i=1;i<=n;i++)
        {
            if(row_a[i]!=row_b[i])
            {
                flag=1;
                break;
            }
        }
        if(!flag)
        {
            for(int j=1;j<=m;j++)
            {
                if(column_a[j]!=column_b[j])
                {
                    flag=1;
                    break;
                }
            }
            if(flag)puts("No");
            else puts("Yes");
        }
        else puts("No");
    }
    fclose(stdin);
    fclose(stdout);
}

D. Frets On Fire【贡献计算 & 二分查找】

题解：参考博客

题意：这里就不过多赘述了~~(主要是因为懒)~~，看一下题目的Note，其实就很明显了。
题解：
题目给出多组的L、R，判断从第L列到第R列中，不重复的数字有多少个。(还是说了一下题意，orz)
根据题意，我们可以发现 $s_i$ 而言，值越大，其对结果的贡献就可能最大。多个相同的 $s_i$ ，只会对结果产生一次贡献。

对 $s$ 数组进行升序排序，在算一个点的贡献时：

与后一个有重叠：
当 $s[i]+r>=s[i+1]+l$ ，即 $r−l>=s[i+1]−s[i]$ 时， $s[i]$ 与 $s[i+1]$ 重叠的部分，都算在 $s[i+1]$ 里，则 $s[i]$ 的贡献为 $s[i+1] - s[i]$
无重叠时，贡献为 $r - l + 1$
$s[n]$ 的贡献一定是 $r - l + 1$

最后再处理一下，计算前i个元素对应的贡献值的和，方便进行二分查找，详细看代码。

贡献计算：
我的理解是：有若干个可能的条件，对结果产生贡献，但是这些条件有些贡献是相同的，在计算总的贡献时，就需要剔除重复的贡献。

参考代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

long long s[100010];
long long contri[100010];
long long sum[100010];
int n;
int q;
long long l,r;
bool cmp(long long x,long long y)// sort的比较函数，这里可忽略
{
    if(x<y)return true;
    else return false;
}

int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)scanf("%lld",&s[i]);
        sort(s+1,s+n+1,cmp);
        long long m=unique(s+1,s+n+1)-(s+1);// unique去除重复的s数组元素
        //printf("unique:%d\n",m);
        for(int i=1;i<m;i++)contri[i]=s[i+1]-s[i];// contri：记录贡献值
        sort(contri+1,contri+m,cmp);// 对贡献值升序排序
        for(int i=1;i<m;i++)sum[i]=sum[i-1]+contri[i];// 计算前i个的总贡献
        scanf("%d",&q);
        while(q--)
        {
            long long ans=0;
            scanf("%lld%lld",&l,&r);
            /*
            // 直接遍历，TLE，需要二分查找
            for(int i=1;i<m;i++)
            {
                long long temp=contri[i]<(r-l+1)?contri[i]:(r-l+1);
                ans+=temp;
            }
            ans+=(r-l+1);
            */
            // upper_bound：(大于)二分查找，找到最一个比r-l的位置，即第一个r-l+1的位置
            int pos=upper_bound(contri+1,contri+m,r-l)-contri;
            ans=sum[pos-1]+(r-l+1)*(m-pos+1);
            // 分成大[于等于r-l+1]和[小于r-l+1]两段，相加即为最后的结果
            printf("%lld ",ans);
        }
        puts("");
    }
    fclose(stdin);
    fclose(stdout);
}

E. Pavel and Triangles【思维】

题解：

题意：
有一个数组 $a_0$ 、 $a_1$ 、 $a_2$ …… $a_{n-1}$ ，表示长度为 $2^0$ 、 $2^1$ 、 $2^2$ …… $2^{n-1}$ 分别的木棒的数量，问：这些木棍最多可以组成的三角形的个数。
题解：
首先，根据三角形三边关系， $2^0$ 、 $2^1$ 、 $2^2$ 这三边不能组成一个三角形，进一步推论，可以发现任意三个 $i、j、k$ （ $i≠j$ && $i≠k$ && $j≠k$ ）， $2^i$ 、 $2^j$ 、 $2^k$ 不可能组成一个三角形。
所以，要组成三角形，只能是等腰三角形 $(2^i,2^j,2^j)$ 或者等边三角形 $(2^j,2^j,2^j)$ 。

构成三角形要么等边，要么等腰，等腰的话另外一边只能取小的，
如果小的有剩余，当然拿出2个大的来构成等腰更划算，如果没有那么就本身构成等边。
即temp=min(num/2,last)；

参考代码：

#include<iostream>
#include<cstdio>
using namespace std;

int n;
long long num;
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    //scanf("%d",&n);
    while(~scanf("%d",&n))
    {
        long long last=0,ans=0;// last：前面剩余的
        long long temp;// 与前面剩余的形成等腰三角形的个数
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&num);
            // 如果小的边有剩余 
            if(last)
            {
                temp=min(num/2,last);
                ans+=temp;
                last-=temp;
                num-=temp*2;
            }
            ans+=num/3;
            last+=num%3;
        }
        printf("%lld\n",ans);
    }
    fclose(stdin);
    fclose(stdout);
}

写在最后：

还有三道题目没有补~~（其实是不会做）~~，感兴趣的（大佬们）可以去AK，我（蒟蒻）就算了，等后面会做了再来更新吧。

附上几份题解：

codeforces上的题解
zhouyuheng2003
ccosi
D题参考：https://www.cnblogs.com/AlphaWA/p/10664509.html

Per Week，Hard Work！不管别人怎么样，坚持自己的选择，不为什么，只是喜欢。

CodeForces | Codeforces Global R

A. Ilya and a Colorful Walk

题解：

参考代码：

B. Alyona and a Narrow Fridge【思维】

题解：

参考代码：

C. Ramesses and Corner Inversion【奇偶性、规律】

题解：

解法：【规律性】

参考代码：【代码略长。。。逃~】

D. Frets On Fire【贡献计算 & 二分查找】

题解：参考博客

参考代码：

E. Pavel and Triangles【思维】

题解：

参考代码：

写在最后：

猜你喜欢

热点阅读