首页 > 其他分享 >D. The Butcher(思维+构造)

D. The Butcher(思维+构造)

时间:2023-04-17 16:25:50浏览次数:51  
标签:思维 int sum 矩阵 构造 yy Butcher maxb maxa

题目

Codeforces Round 866 (Div. 2)D. The Butcher

题意

  • n个数对a,b,表示矩形
  • 这n个矩形通过原先一个大矩形分割而来
  • 每次分割只在上一次分割的矩阵其中之一
  • 现在原先的矩阵大小未知,问有原先的矩阵(在切割过程中不会旋转矩阵)多少种,并输出
  • 保证至少存在一种方法

思路

  • 从题意可得,在所有子矩阵中,必然有一条边和原先矩阵完全重合且相等,这条边最大
  • 所以可以通过这一条最大的边,来判断是否能把矩阵拼好
  • 同时,我们还能得出原先矩阵的面积,通过这一条最长边,可以算出另一条对应的长度
  • 通过一个分解函数,来逐步分割检查能不能拼成,具体思路见代码

代码

void solve()
{
    int n;
    cin >> n;
    map<int, multiset<int>> a, b;
    set<PII> ans;
    int sum = 0;
    int maxa = 0, maxb = 0;
    for (int i = 0; i < n;i ++)
    {
        int x,y;
        cin >> x >> y;
        a[x].insert(y);
        b[y].insert(x);
        sum += x * y;
        maxa = max(maxa, x);
        maxb = max(maxb, y);
    }

    auto check = [&](int X, int Y, int id, map<int, multiset<int>> xx, map<int, multiset<int>> yy)
    {
        int start = n;
        while(X > 0 && Y > 0)
        {
            
            int temp = start;
            //X
            if(id == 0)
            {
                for(auto it:xx[X])
                {
                    Y -= it;
                    // debug2(Y, it);
                    // yy.erase(it);//删除所有yy中为it的元素,应该是只删除一个
                    yy[it].erase(yy[it].find(X));
                    temp--;
                }
                xx.erase(X);
                id ^= 1;
            }
            else    //Y
            {
                // debug3(X, Y,yy.count(Y));
                for (auto it : yy[Y])
                {
                    X -= it;
                    // debug2(X, it);
                    xx[it].erase(xx[it].find(Y));
                    temp--;
                }
                yy.erase(Y);
                id ^= 1;
            }
            
            if(temp == start)
                return false;
            start = temp;
            
        }
        return X == 0 || Y == 0;
    };

    if ((sum % maxa) == 0 && check(maxa, sum / maxa, 0,a,b))
        ans.insert({maxa, sum / maxa});
    if ((sum % maxb) == 0 && check(sum / maxb, maxb, 1,a,b))
        ans.insert({sum / maxb, maxb});

    cout << ans.size() << endl;
    for(auto x:ans)
        cout << x.fi << " " << x.se << endl;
}

标签:思维,int,sum,矩阵,构造,yy,Butcher,maxb,maxa
From: https://www.cnblogs.com/cfddfc/p/17326221.html

相关文章

  • 《花雕学AI》21:脑筋急转弯---ChatGPT能够灵活运用逻辑推理和创造性思维吗?
    当我们谈到脑筋急转弯时,很多人都会感到兴趣和好奇。脑筋急转弯是一种智力游戏,可以锻炼我们的思维能力以及解决问题的能力。然而,对于许多人来说,脑筋急转弯也是一项相当具有挑战性的任务。在这个过程中,我们需要运用逻辑推理、上下文理解等能力才能解决问题。随着技术的发展,ChatGPT......
  • 构造加逊
    MakeItConnect题意给定一个无向图\(E\),每次操作需要选择一个点\(u\),然后对其余的的所有点\(v\)进行操作,如果\((u,v)\inE\)则删去这条边,否则将这条边加入图中,求最少几次类似操作能够使得图联通并输出操作方案做法首先统计联通块数量以及各点的度数当原图......
  • 算法-二叉树的构造
    namespaceBinary;publicclassBinaryTree{publicNode<char>Head{get;privateset;}privatestringcStr{get;set;}publicBinaryTree(stringconstructStr){this.cStr=constructStr;th......
  • 利用AntDesign中a-tree和checkbox构造组织单位人员树选择组件
    业务效果图核心代码<template><divclass="select-container"><a-modalv-model:visible="visible"@ok="handleOk"@cancel="handleCancel"width="1500px"><template#title>......
  • 算法-丑数2-构造小根堆
    intNthUglyNumber(intn){if(n==1)return1;List<long>arr=newList<long>();//这里用list,它会自己扩容,用数组就需要自己操作这些了arr.Add(1);int[]uglyArr={2,3,5};HashSet<long>hs=newHashSet<long>();hs.Add(1);......
  • 【面试题】思维逻辑方面
    1、有一个没有刻度的长方形的铁盒子,没有盖子,可以随意摆动,它的容积是1升。请罗列出你能想到的:只使用这个盒子称量,列出你可以想到的能够准确地量出多少升的水?答案:0.5L  2、排队,小明站在从前往后数的第x个,从后往前数的第y个,则小明所在的列共有多少人?答案:x+y-13、桌子......
  • 百强药企「普正药业」联合Smartbi构造以指标管理为核心的ABI平台
    江西普正制药股份有限公司(以下简称“普正药业”),是以天然植物药的成方制剂研发、生产、营销为主,集天然植物药种植、物流及国药文化传播、健康产业投资为一体的民营企业集集团,是中国中药百强企业,其天然植物药主导产品驰誉全国。普正药业致力于天然植物精品药,为医患提供慢性病与疑难病......
  • Chain of Thought(思维链)
    "思维链"(ChainofThought)是指一系列有逻辑关系的思考步骤或想法,这些步骤或想法相互连接,形成了一个完整的思考过程。它是指导我们思考和解决问题的一种方法,可以帮助我们更好地理解问题、分析问题和解决问题。一个有效的思维链应该具有以下特点:逻辑性:思维链中的每个思考步骤都应......
  • 技术文章的写作思维
    后台有许多同学留言问我:为什么我一方面可以日更,另一方面文章可读性也比较友好,不会太晦涩难懂。最近在抽空整理之前的一些学习笔记和文章草稿,在整理的过程中,我也在思考如何持续的输出高质量的文章。这背后一方面需要大量的知识储备和实践;但更重要的,我认为是清晰的结构性思维。即......
  • 计算机网络思维导图,快快收藏学习啦!
    第一章(概述) P0-计算机网络<思维导图>第二章(物理层) P1-计算机网络<思维导图>便签中的内容:①香农公式:C=W*Log2(1+S/N)(bit/s)C:极限传输速率W:信道带宽(单位Hz)S:信道内所传信号的平均功率N:信道内的高斯噪声功率②ADSL技术:AsymmetricDigitalSubscriberLine非对称数字用户......