当前位置:网站首页>Codeforces Round #804 (Div. 2) - A, B, C
Codeforces Round #804 (Div. 2) - A, B, C
2022-07-05 20:08:00 【小酒窝.】
https://codeforces.com/contest/1699
C. The Third Problem
题意
给定一个 0 0 0 到 n − 1 n-1 n−1 的全排列,问一共有多少 0 0 0 到 n − 1 n-1 n−1 的全排列和该排列相似?
答案对 1e9+7 取模。
相似定义:如果两个全排列满足下面条件,就说两个这两个全排列相似。
- 对于任意区间 [ l , r ] ( 1 ≤ l ≤ r ≤ n ) [l, r] (1 \le l \le r \le n) [l,r](1≤l≤r≤n) 都满足: MEX ( [ a l , a l + 1 , … , a r ] ) = MEX ( [ b l , b l + 1 , … , b r ] ) \operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]) MEX([al,al+1,…,ar])=MEX([bl,bl+1,…,br])
对于一堆数 c 1 , c 2 , … , c k c_1,c_2,\ldots,c_k c1,c2,…,ck 的 MEX \operatorname{MEX} MEX 是指,在集合 c c c 中第一个未出现的非负整数 x x x。
思路
从 0 到 n-1,一个数一个数的判断,看其能放在哪些位置。所有可能的位置数相乘就是答案。
标记数 x
在原排列中所在位置为 p[x]
。
- 首先容易确定,0 和 1 在相似排列中的位置不变,都为
p[0]
。设l
为较左端位置,r
为较右端位置。 - 对于 2:
1. 如果p[2]
位于[l, r]
中,那么 2 可以放在[l, r]
中的所有空闲位置;
(2 原来在[l, r]
中,那么 MEX [ l , r ] \operatorname{MEX}[l, r] MEX[l,r] 就达到 3 了,所以在相似排列中 2 只能放在[l, r]
中)
2. 否则,2 只能放在原来位置p[2]
;然后p[2]
将l
或者r
更新;
(2 原来在[l, r]
之外,那么 MEX [ l , r ] \operatorname{MEX}[l, r] MEX[l,r] 只能达到 2,2不能在[l, r]
中;而其位置如果改变的话,会有区间的 MEX 值改变,所以这种情况下 2 的位置不能改变) - 对于 3:
1. 如果p[3]
位于[l, r]
中,那么 3 可以放在[l, r]
中的所有空闲位置;
2. 否则,3 只能放在原来位置p[3]
;然后p[3]
将l
或者r
更新; - …
Code
#include<bits/stdc++.h>
using namespace std;
#define Ios ios::sync_with_stdio(false),cin.tie(0)
const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], p[N];
signed main(){
Ios;
cin >> T;
while(T--)
{
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i], p[a[i]] = i;
int ans = 1;
int l = min(p[0], p[1]), r = max(p[0], p[1]);
for(int i=2;i<n;i++)
{
if(p[i] > l && p[i] < r)
{
ans = ans * (r-l+1 - i) % mod;
}
else{
if(p[i] < l) l = p[i];
else r = p[i];
}
}
cout << ans << endl;
}
return 0;
}
经验
当没有思路的时候应该沉下心来从最初始的情况一点一点往后推,也许推着推着就有思路了。
而不是看着样例胡乱想。。
B. Almost Ternary Matrix
题意
构造一个 n*m 的 01 矩阵,使得:
- 对于每个位置,其直接相邻的位置中,恰有两个位置和该位置元素不同。
2 ≤ n , m ≤ 50 2 \le n,m \le 50 2≤n,m≤50 且都为偶数。
思路
这样构造:
6 8
1 0 0 1 1 0 0 1
0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0
1 0 0 1 1 0 0 1
1 0 0 1 1 0 0 1
0 1 1 0 0 1 1 0
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 210, mod = 1e9+7;
int T, n, m;
int a[N] = {
1, 0, 0, 1}, b[N] = {
0, 1, 1, 0};
int ans[N][N];
signed main(){
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++)
{
for(int j=0;j<m;j++)
{
if(i%4 == 1 || i%4 == 0) ans[i][j] = a[j%4];
else ans[i][j] = b[j%4];
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
printf("%d ", ans[i][j]);
}
printf("\n");
}
}
return 0;
}
A. The Third Three Number Problem
题意
给定一个数 n n n,找到三个数 a , b , c a, b, c a,b,c 满足:
- ( a ⊕ b ) + ( b ⊕ c ) + ( a ⊕ c ) = n (a\oplus b)+(b\oplus c)+(a\oplus c)=n (a⊕b)+(b⊕c)+(a⊕c)=n
找不到输出 − 1 -1 −1。
1 ≤ n ≤ 1 0 9 , 0 ≤ a , b , c ≤ 1 0 9 1 \le n \le 10^9,\ 0 \le a, b, c \le 10^9 1≤n≤109, 0≤a,b,c≤109
思路
由 a + b = a ⊕ b + 2 ⋅ ( a a + b = a \oplus b + 2 \cdot (a a+b=a⊕b+2⋅(a & b ) b) b) 可知, a ⊕ b a \oplus b a⊕b 和 a + b a + b a+b 具有相同的奇偶性。
那么 n = ( a ⊕ b ) + ( b ⊕ c ) + ( a ⊕ c ) n = (a\oplus b)+(b\oplus c)+(a\oplus c) n=(a⊕b)+(b⊕c)+(a⊕c) 就和 ( a + b ) + ( b + c ) + ( a + c ) = 2 ⋅ ( a + b + c ) (a+b) + (b+c) + (a+c) =2 \cdot (a+b+c) (a+b)+(b+c)+(a+c)=2⋅(a+b+c) 具有相同奇偶性,一定为偶数。
- 当 n 为 奇数时输出 -1。
- 否则 令 b = c = 0 b=c=0 b=c=0,那么原式变为: a + a = n a + a = n a+a=n,那么 a = n 2 a = \frac n 2 a=2n。
Code
#include<bits/stdc++.h>
using namespace std;
#define Ios ios::sync_with_stdio(false),cin.tie(0)
const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
signed main(){
Ios;
cin >> T;
while(T--)
{
cin >> n;
if(n % 2 == 0) cout << n/2 << " " << 0 << " " << 0 << endl;
else cout << -1 << endl;
}
return 0;
}
经验
着重考虑特殊情况。
边栏推荐
- 强化学习-学习笔记4 | Actor-Critic
- Leetcode skimming: binary tree 10 (number of nodes of a complete binary tree)
- 【数字IC验证快速入门】8、数字IC中的典型电路及其对应的Verilog描述方法
- Unity编辑器扩展 UI控件篇
- Go language learning tutorial (XV)
- 如何安全快速地从 Centos迁移到openEuler
- Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
- 95后阿里P7晒出工资单:狠补了这个,真香...
- How to safely and quickly migrate from CentOS to openeuler
- gst-launch的-v参数
猜你喜欢
实操演示:产研团队如何高效构建需求工作流?
Leetcode skimming: binary tree 16 (path sum)
【数字IC验证快速入门】7、验证岗位中必备的数字电路基础知识(含常见面试题)
leetcode刷题:二叉树15(找树左下角的值)
零道云新UI设计中
- Oui. Net Distributed Transaction and Landing Solution
Win10 x64环境下基于VS2017和cmake-gui配置使用zxing以及opencv,并实现data metrix码的简单检测
S7-200smart uses V90 Modbus communication control library to control the specific methods and steps of V90 servo
leetcode刷题:二叉树11(平衡二叉树)
使用 RepositoryProvider简化父子组件的传值
随机推荐
Is it safe for CICC fortune to open an account online?
selenium 元素信息
Go language | 01 wsl+vscode environment construction pit avoidance Guide
Zero cloud new UI design
leetcode刷题:二叉树12(二叉树的所有路径)
Leetcode brush question: binary tree 13 (the same tree)
Gstreamer中的task
深度學習 卷積神經網絡(CNN)基礎
【数字IC验证快速入门】9、Verilog RTL设计必会的有限状态机(FSM)
Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
通配符选择器
图嵌入Graph embedding学习笔记
C langue OJ obtenir PE, ACM démarrer OJ
1: Citation;
Analysis of openh264 decoded data flow
js实现禁止网页缩放(Ctrl+鼠标、+、-缩放有效亲测)
Fundamentals of deep learning convolutional neural network (CNN)
Android interview classic, 2022 Android interview written examination summary
无卷积骨干网络:金字塔Transformer,提升目标检测/分割等任务精度(附源代码)...
Debezium series: PostgreSQL loads the correct last submission LSN from the offset