首页 > 其他分享 >CF1268B题解

CF1268B题解

时间:2023-02-10 22:45:56浏览次数:55  
标签:杨图 int 题解 void 杨表 骨牌 CF1268B

CF1268B 题解

题目翻译

给你一个杨表,用一个有 \(n\) 个元素的数组 \(a\) 表示杨表每一列的高度。你需要用 \(1 \times 2\) 或 \(2 \times 1\) 的骨牌填充这个杨表,求出最多填充的骨牌数量。

题目分析

我们先来处理一个问题:什么是杨表?

  • 杨表是一种每行长度(或每列高度) 单调递减的不规则图,注意这里 并非 要求严格递减,相邻行的长度(或列的高度)可以相同。

对于这道题,我们将杨表交替染色。为了统一标准,我们规定第奇数行的第奇数个位置染为黑色,交错排列。

例如题目中给出的图片,染色后如下图。

染色图片

染色之后,我们可以从小的杨表入手,推导关系。如下图所示,我们可以发现,用左上角的两个单位杨图,可以以拼成任意白色和黑色个数相同的杨图,此时填充的骨牌数量即为白色格子数。在该类型图上,我们可以继续拓展,得到所有的杨图,若从一个该类型杨图拓展到目标图需要的格子最少,则可以证明拓展的部分不能再放骨牌(否则会产生新的单位杨图)。

排列图片

因此,我们得出了结论,可以摆放的骨牌数等于单位杨图数量即黑白块中个数较少的块数

Codes

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define max_n 300100
void read(int &p)
{
    p = 0;
    int k = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            k = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return;
}
void write_(int x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x>9)
    {
        write_(x/10);
    }
    putchar(x%10+'0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    putchar('\n');
}
int n,num;
int sum1,sum2;
signed main()
{
    #if _clang_
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif 
    read(n);
    for(int i = 1;i<=n;i++)
    {
        read(num);
        sum1 += num /2;
        sum2 += num/2;
        if(num%2 != 0)
        {
            if(i % 2 !=0)
            {
                sum1++;
            }
            else
            {
                sum2++;
            }
        }
    }
    writeln(min(sum1,sum2));
    return 0;
}

标签:杨图,int,题解,void,杨表,骨牌,CF1268B
From: https://www.cnblogs.com/yuhang-ren/p/17110534.html

相关文章

  • 题解:[PA2021] Drzewo czerwono-czarne
    题目链接:[PA2021]Drzewoczerwono-czarne首先对于起始和终止相同以及起始中只有一种颜色并且终止和起始不相同这两种情况是平凡的。考虑最后一步,一定是将某一条边上的一......
  • CF1296D 题解
    题目传送门简单题做了好久,哈哈。题目分析首先,对于单个怪物,先将它的血量通过取余处理到小于\(a+b\)的时候,因为无论怪物血量多少,如果大于\(a+b\),显然不可能出现最后一......
  • 关于node-sass和sass-loader版本不兼容的问题解决
    安装node-sass和sass-loader时,提示我版本不兼容如:ValidationError:Invalidoptionsobject.SassLoaderhasbeeninitializedusinganoptionsobjectth......尝试......
  • 问题解决:WARNING!The remote SSH server rejected X11 forwarding request.
    截图解决X11forwarding依赖xorg-x11-xauth软件包,安装xorg-x11-xauth软件包。yuminstallxorg-x11-xauth-y安装后重新连接即可......
  • 【题解】P5278 算术天才⑨与等差数列
    有趣的乱搞做法和一个没想到的trick,一起记一下。思路线段树+哈希/trick.首先是乱搞做法。意识到可以像P3792由乃与大母神原型和偶像崇拜那个被疯狂hack的题......
  • Codeforces Round #851 (Div. 2) 题解
    CodeforcesRound#851(Div.2)题解A.OneandTwo取\(\log_2\),变成加号,前缀和枚举\(s[i]=\dfrac{s[n]}{2}\)。B.SumofTwoNumbers对于每一位,如果是偶数则平均......
  • 问题解决:由于找不到msvcr110.dll,无法继续执行代码
    报错解决下载地址:https://www.microsoft.com/zh-cn/download/details.aspx?id=30679......
  • CF1389E Calendar Ambiguity 题解
    可能更好的阅读体验题面传送门toluogu题目大意假设一年有\(m\)月,每个月有\(d\)天,每周有\(w\)天。保证一年的第一天一定是周一。求\((x,y)\),满足\(x<y\)并且......
  • 【题解】CF850F Rainbow Balls
    整体方向很常规,但是最后的处理比较仙,记一下。思路期望dp.首先意识到最终会变成同一种颜色,并且不同颜色的期望步数不同。考虑到\(n\leq2.5\times10^3\),考虑钦定最......
  • 【题解】CF1093G Multidimensional Queries
    记一下这种有趣的trick.思路线段树。绝对值按照惯例是可以拆的,并且可以拆出一正一负两个数。考虑到维数很小,可以考虑状压表示拆除绝对值之后每一维值的正负。并且因......