1162 B
题意
一个矩阵单调递增当且仅当它的行和列都单调递增。现在给你两个大小相同的矩阵 \((n,m\le 50)\) ,你可以交换两个矩阵位于相同位置的元素,问能否把两个矩阵都变成单调递增的。
Examples
input
2 2 2 10 11 5 9 4 3 12 output Possible input 2 3 2 4 5 4 5 6 3 6 7 8 10 11 output Possible input 3 2 1 3 2 4 5 10 3 1 3 6 4 8 output Impossible解
直接乱搞,如果 \(a_{i,j}>b_{i,j}\) 那么交换,然后检查是否合法即可。
1162 C
题意
有 \(n(\le 10^5)\) 个点,有 \(k\) 个询问,每次询问棋子在不在位置 \(x\) ,你在点 \(S\) 上有一个棋子,你最多可以移动你的棋子一次到相邻的格子(在某次询问前后,也可以不移动),记为 \(T\) ,现在问你存在多少对 \((S,T)\) ,使得每次询问的回答结果都是NO
。
Examples
inputCopy
5 3 5 1 4 output 9 input 4 8 1 2 3 4 4 3 2 1 output 0 input 100000 1 42 output 299997解
模拟即可。
1162 D
题意
一个圆盘上有 \(n\) 个点, \(m\) 条线段,问你将这个圆盘旋转 \(k(1\le k<n)\) 个单位后所形成的图像是否有可能和原图像重合。 \((n,m\le 10^5)\)
Examples
input
12 6 1 3 3 7 5 7 7 11 9 11 11 3 output Yes input 9 6 4 5 5 6 7 8 8 9 1 2 2 3 output Yes input 10 3 1 2 3 2 7 2 output No input 10 2 1 6 2 7 output Yes解
枚举 \(n\) 的所有因子,一一检查。
时间复杂度: \(O(n*f(n)),f(n)\) 表示 \(n\) 的因数个数。实测最坏情况下 \(f(n)≈100\) 。