首页 > 其他分享 >题解 CF1965E【Connected Cubes】

题解 CF1965E【Connected Cubes】

时间:2024-04-30 17:55:45浏览次数:32  
标签:Cubes return int 题解 rep CF1965E operator Modint friend

场切了 1E,第一次上 IGM,纪念一下。

多图警告。

我们称题目中的一个方块为“某色混凝土”。感受一下,发现本题主要的难点在于这些混凝土方块排布得太紧密了,导致容易出现互相遮挡的现象,进而难以构造。于是,我们先思考能否通过一些操作使得这些混凝土互相分离。

如下图的方式可以将每两列混凝土中间插入一列空气:

至此,我们在每两列之间都塞了一列空气,且最上层的每块混凝土都显然与最下层对应的混凝土连通。

显然,最上层所有混凝土均至少紧挨着一格空气,我们只需要把所有空气替换成一种颜色的混凝土,那么这种颜色的所有混凝土就连通了:

于是就做完了。出于美观考虑,上面示意图中的构造与代码中的构造略有出入,但主要思路完全一致。代码中最坏情况 \(p=373700\),足以通过本题。这个构造显然还有很大的优化空间,但是我懒了。

谢谢大家!

// Problem: E. Connected Cubes
// Contest: Codeforces - Codeforces Round 941 (Div. 1)
// URL: https://codeforces.com/contest/1965/problem/E
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const int N = 55;

int n, m, k, a[N][N], px[N][N], py[N][N];
vector<tuple<int, int>> pos[N];
vector<tuple<int, int, int, int>> ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    // rep(i, 1, n) rep(j, 1, m) cin >> a[i][j];
    rep(i, 1, n) rep(j, 1, m) a[i][j] = k;
    rep(i, 1, n) rep(j, 1, m) px[i][j] = i, py[i][j] = j;
    rep(z, 1, m) {
        if(z >= 2) {
            rep(i, 1, n) rep(j, 1, m) ans.emplace_back(px[i][j], py[i][j], z, a[i][j]);
        }
        rep(i, 1, n) {
            rep(j, 1, m) {
                if(j == m - z + 1) {
                    int gy = 2 * j - 1;
                    rep(y, j + 1, gy) ans.emplace_back(i, y, z, a[i][j]);
                    px[i][j] = i;
                    py[i][j] = gy;
                }
            }
        }
    }
    int z = m;
    rep(c, 1, k) {
        rep(i, 1, n + 1) {
            rep(j, 1, 2 * m - 1) {
                if(i == n + 1) ans.emplace_back(i, j, z, c);
                else if(j % 4 == 2 || j >= 2 * m - 3 && j % 2 == 0) ans.emplace_back(i, j, z, c);
                else if(int u = a[i][(j + 1) / 2]; (j & 1) && z != m && u >= c) ans.emplace_back(i, j, z, u);
            }
        }
        ++z;
    }
    cout << ans.size() << endl;
    for(auto [x, y, z, c] : ans) cout << x << " " << y << " " << z << " " << c << endl;
    return 0;
}

标签:Cubes,return,int,题解,rep,CF1965E,operator,Modint,friend
From: https://www.cnblogs.com/ruierqwq/p/18168496/CF-1965E

相关文章

  • CF1956F Nene and the Passing Game 题解
    题目链接点击打开链接题目解法首先答案为连边之后连通块的个数把限制中的\(i,j\)分开,则\(i,j\)能传球当且仅当\(i+l_i\lej-l_j\)且\(j-r_j\lei+r_i\)这是一个二维偏序的形式先考虑怎么暴力做,考虑将\((i+l_i,0),\;(i-l_i,1)\)排序,然后按顺序加入如果碰到操作\(......
  • npm下载包时报错 Unexpected token '.'问题解决
    1.出现问题当通过nvm切换nodejs版本为16以上时,npminstall[package]报错:Unexpectedtoken'.'2.问题原因该问题不是npm的问题,也不是nodejs的问题,是nvm-windows的问题。3.解决问题nvm-windows已经更新版本解决了这个问题我是通过更新nvm-windows到版本1.19解决了这个问题......
  • Atcoder ABC 351 全题解
    乾岩我:G题来咯!!!大火:这G题,大家都不敢做,说是有人在里面放了毒瘤。我:做,做,为什么不做!不做也别想活着!!!(两天后)我:我的G题完成辣!!!!!!AB不讲C显然$2^a*2=2^{a+1}$。考虑用一个栈存球的大小是$2$的多少次方,每次插入球后,不断取出后面两个球,大小相同则合并,否则插入下一个......
  • XYCTF pwn部分题解 (部分题目详解)
    hello_world(签到)思路:✅这道题就是利用printf函数泄露libc的基地址,然后再次进行栈溢出通过system,/bin/sh来获取shellwp:invisible_flag思路:✅题目提示orw,那我们先看看是否开了沙盒那么是开了沙盒的,试试orw读取flag虽然保护全开但是程序会执行我们写的shellcdoe那么就可......
  • 二叉树笔试题解题思路
    数据结构二叉树笔试题:解题思路:1.判断是否为空树,若为空树,则返回0;2.定义两个指针备份根结点地址,定义两个整型变量a,b并初始化为0,记录左右子树的深度;先对根结点的左子树进行遍历,若根结点的左结点不为NULL,则a++,把根结点的左结点赋值为新的根结点,再进行上述操作,若根结点的左结点......
  • AtCoder-abc350_g 题解
    原题链接题意简述有一个无向图,初始时没有边。接下来有一些操作:将\(u,v\)连边。询问\(u,v\)的距离是否为\(2\),如果是,则输出中间的那个点的编号,否则输出0。每次询问后,更新\(lastans\)为询问的答案,初始时为\(0\)。每次操作的\(opt,u,v\)使用\(lastans\)解码,......
  • AtCoder-abc350_f 题解
    原题链接题意简述给定一个字符串\(S\),对于每个匹配的括号,将括号内的字符左右翻转并大小写反转,然后删除括号。输出最后的序列。思路本题为文艺平衡树的模板题。扫一遍字符串进行括号匹配,每次把最内层的括号进行操作。最后遍历一遍平衡树,将不为括号字符的字符输出。FHQ_Treap......
  • 【题解】 量化交易1
    题目描述applepi训练了一个可以自动在股票市场进行量化交易的模型。通常来说,applepi写出的模型,你懂得,就好比一架印钞机。不过为了谨慎起见,applepi还是想先检查一下模型的效果。applpie收集了“塞帕思股份(surpass)”在最近的连续N天内的价格。在每一天中,他可以做如下事情之一:......
  • 【题解】 量化交易2
    题目描述applepi训练了一个可以自动在股票市场进行量化交易的模型。通常来说,applepi写出的模型,你懂得,就好比一架印钞机。不过为了谨慎起见,applepi还是想先检查一下模型的效果。applpie收集了“塞帕思股份(surpass)”在最近的连续N天内的价格。在每一天中,他可以做如下事情之一:......
  • 问题解决:Failed to download metadata for repo ‘appstream‘: Cannot prepare inter
    大家都知道Centos8于2021年年底停止了服务,大家再在使用yum源安装时候,出现下面错误“错误:Failedtodownloadmetadataforrepo‘AppStream’:Cannotprepareinternalmirrorlist:NoURLsinmirrorlist”1、进入yum的repos目录代码语言:javascript复制cd/etc/yum......