CF1819B The Butcher 题解

· · 题解

前言

赛时没切出来，下大分，麻了。

赛后不敢相信这玩意只有 *1900。

解法

本题有一个非常关键的 Key Conclusion：

既然找到了可能的解，那么就尝试检验解的合法性。

一个解要合法，首先它的长和宽都必须是总面积的因数，如果不符合这个条件的一定不合法。

如果满足上面的条件，就可以进行下一步检查：具体地，我们把被放进箱子里地小长方形从箱子里往外一个一个拿，并尝试拼成目标图形。每一次先拿出长最大的小长方形，如果它的长等于目标图形的长，那么把它拼进去，目标图形的宽减去该图形的宽，箱子里减少一个长方形；否则就拿出宽最大的小长方形，如果它的宽等于目标图形的宽，那么拼进去，目标图形的长减去该图形的长，否则该解不合法。一直到 n 个小长方形都拿完，目标图形的长宽都被减为 0，那么该解合法。

实现时略有不同：每一次检查时我们拿出了所有的长 / 宽最大的小长方形，假设本轮拿的是长最大的若干个小长方形，那么下一次只能拿宽最大的（因为接下来长最大的小长方形的长就没办法与目标图形的长相等）。

可以使用 map 维护这个过程。单组测试数据时间复杂度为 O(n\log n)。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool check(int x,int y,vector<pair<int,int> > a,bool f){
  map<pair<int,int>,int,greater<> > m1,m2;
  for(auto [x,y]:a)m1[make_pair(x,y)]++,m2[make_pair(y,x)]++;
  for(int c=0;c<a.size();f^=1){
    if(f){
      if(m1.begin()->first.first!=x)return false;
      while(m1.begin()->first.first==x){
        y-=m1.begin()->first.second,c++;
        if(!--m2[make_pair(m1.begin()->first.second,x)])
          m2.erase(make_pair(m1.begin()->first.second,x));
        if(!--m1[make_pair(x,m1.begin()->first.second)])
          m1.erase(make_pair(x,m1.begin()->first.second));
        // 该轮需要检查长最大的
      }
    }
    else{
      if(m2.begin()->first.first!=y)return false;
      while(m2.begin()->first.first==y){
        x-=m2.begin()->first.second,c++;
        if(!--m1[make_pair(m2.begin()->first.second,y)])
          m1.erase(make_pair(m2.begin()->first.second,y));
        if(!--m2[make_pair(y,m2.begin()->first.second)])
          m2.erase(make_pair(y,m2.begin()->first.second));
        // 该轮需要检查宽最大的
      }
    }
  }
  return true;
}
main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,mx=0,my=0,c=0; cin>>n;
    vector<pair<int,int> > a(n),r;
    for(auto &[x,y]:a)
      cin>>x>>y,mx=max(mx,x),my=max(my,y),c+=x*y;
    if(!(c%mx)&&check(mx,c/mx,a,1))r.emplace_back(mx,c/mx);
    if(mx!=c/my&&!(c%my)&&check(c/my,my,a,0))r.emplace_back(c/my,my);
    // 注意两种情况可能产生长宽一样的图形，要判掉
    cout<<r.size()<<endl;
    for(auto [x,y]:r)cout<<x<<' '<<y<<endl;
  }
  return 0;
}