当前位置:网站首页>Codeforces Round #804 (Div. 2) - A, B, C
Codeforces Round #804 (Div. 2) - A, B, C
2022-07-05 20:23:00 【Dimple】
https://codeforces.com/contest/1699
C. The Third Problem
The question
Given a 0 0 0 To n − 1 n-1 n−1 The whole arrangement , Ask how many 0 0 0 To n − 1 n-1 n−1 The full arrangement of is similar to this arrangement ?
The answer is right 1e9+7 modulus .
Similarity definition : If two full permutations meet the following conditions , Let's say that the two are similar in full arrangement .
- For any interval [ l , r ] ( 1 ≤ l ≤ r ≤ n ) [l, r] (1 \le l \le r \le n) [l,r](1≤l≤r≤n) All satisfied with : 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])
For a pile of numbers c 1 , c 2 , … , c k c_1,c_2,\ldots,c_k c1,c2,…,ck Of MEX \operatorname{MEX} MEX Refer to , In collection c c c The first non negative integer that does not appear in x x x.
Ideas
from 0 To n-1, Count one by one , See where it can be placed . Multiplication of all possible positions is the answer .
Number of tags x
The position in the original arrangement is p[x]
.
- First, it's easy to determine ,0 and 1 The position in a similar arrangement does not change , All for
p[0]
. set upl
Is the left end position ,r
Is the right end position . - about 2:
1. Ifp[2]
be located[l, r]
in , that 2 Can be placed in[l, r]
All free locations in ;
(2 Originally in[l, r]
in , that MEX [ l , r ] \operatorname{MEX}[l, r] MEX[l,r] To achieve 3 了 , So in a similar arrangement 2 Only on the[l, r]
in )
2. otherwise ,2 It can only be placed in its original positionp[2]
; thenp[2]
takel
perhapsr
to update ;
(2 Originally in[l, r]
outside , that MEX [ l , r ] \operatorname{MEX}[l, r] MEX[l,r] It can only reach 2,2 Can't be in[l, r]
in ; And if its position changes , There will be intervals MEX Value change , So in this case 2 The position of the cannot be changed ) - about 3:
1. Ifp[3]
be located[l, r]
in , that 3 Can be placed in[l, r]
All free locations in ;
2. otherwise ,3 It can only be placed in its original positionp[3]
; thenp[3]
takel
perhapsr
to update ; - …
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;
}
Experience
When there is no idea, you should calm down and push back bit by bit from the initial situation , Maybe there is a way to push .
Instead of looking at the sample and thinking ..
B. Almost Ternary Matrix
The question
Construct a n*m Of 01 matrix , bring :
- For each location , In its directly adjacent position , There are exactly two locations that are different from this location element .
2 ≤ n , m ≤ 50 2 \le n,m \le 50 2≤n,m≤50 And all are even .
Ideas
So constructed :
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
The question
Give a number n n n, Find three numbers a , b , c a, b, c a,b,c Satisfy :
- ( a ⊕ b ) + ( b ⊕ c ) + ( a ⊕ c ) = n (a\oplus b)+(b\oplus c)+(a\oplus c)=n (a⊕b)+(b⊕c)+(a⊕c)=n
Output not found − 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
Ideas
from a + b = a ⊕ b + 2 ⋅ ( a a + b = a \oplus b + 2 \cdot (a a+b=a⊕b+2⋅(a & b ) b) b) You know , a ⊕ b a \oplus b a⊕b and a + b a + b a+b Having the same parity .
that n = ( a ⊕ b ) + ( b ⊕ c ) + ( a ⊕ c ) n = (a\oplus b)+(b\oplus c)+(a\oplus c) n=(a⊕b)+(b⊕c)+(a⊕c) Just like ( 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) Having the same parity , It must be an even number .
- When n by Odd number output -1.
- otherwise Make b = c = 0 b=c=0 b=c=0, Then the original formula becomes : a + a = n a + a = n a+a=n, that 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;
}
Experience
Focus on special circumstances .
边栏推荐
- 解决Thinkphp框架应用目录下数据库配置信息修改后依然按默认方式连接
- 银河证券在网上开户安全吗?
- nprogress插件 进度条
- 欢迎来战,赢取丰厚奖金:Code Golf 代码高尔夫挑战赛正式启动
- Guidelines for application of Shenzhen green and low carbon industry support plan in 2023
- Informatics Orsay all in one 1339: [example 3-4] find the post order traversal | Valley p1827 [usaco3.4] American Heritage
- 【c语言】快速排序的三种实现以及优化细节
- 2.8、项目管理过程基础知识
- Informatics Olympiad 1340: [example 3-5] extended binary tree
- Leetcode skimming: binary tree 10 (number of nodes of a complete binary tree)
猜你喜欢
js实现禁止网页缩放(Ctrl+鼠标、+、-缩放有效亲测)
[quick start of Digital IC Verification] 7. Basic knowledge of digital circuits necessary for verification positions (including common interview questions)
ROS2专题【01】:win10上安装ROS2
微信小程序正则表达式提取链接
小程序页面导航
[quick start to digital IC Verification] 8. Typical circuits in digital ICs and their corresponding Verilog description methods
物联网智能家居基本方法实现之经典
. Net distributed transaction and landing solution
鸿蒙系统控制LED的实现方法之经典
[Yugong series] go teaching course in July 2022 004 go code Notes
随机推荐
走入并行的世界
Process file and directory names
Mysql频繁操作出现锁表问题
Informatics Orsay all in one 1339: [example 3-4] find the post order traversal | Valley p1827 [usaco3.4] American Heritage
Codeforces Round #804 (Div. 2) - A, B, C
Ffplay document [easy to understand]
Summer Challenge harmonyos - realize message notification function
19 mongoose modularization
2022年7月4日-2022年7月10日(ue4视频教程mysql)
Schema和Model
[quick start of Digital IC Verification] 9. Finite state machine (FSM) necessary for Verilog RTL design
Guidelines for application of Shenzhen green and low carbon industry support plan in 2023
小程序全局配置
[Yugong series] go teaching course in July 2022 004 go code Notes
【数字IC验证快速入门】9、Verilog RTL设计必会的有限状态机(FSM)
Informatics Olympiad 1337: [example 3-2] word search tree | Luogu p5755 [noi2000] word search tree
Solve the problem that the database configuration information under the ThinkPHP framework application directory is still connected by default after modification
Leetcode brush question: binary tree 13 (the same tree)
Relationship between mongodb documents
How to choose a good external disk platform, safe and formal?