当前位置:网站首页>Noi online 2022 popular group problem solving & personal understanding
Noi online 2022 popular group problem solving & personal understanding
2022-07-29 06:27:00 【C2024XSC249】
NOI Online 2022 Popularization group Answer key & Personal insight
T1 Kingdom competition (kingdom)
Title Description
King of wisdom Kri Rule a kingdom .
On the day Kri Decided to hold a game , To test the wisdom of their ministers .
Competition by n n n The judgment questions consist of , Yes m m m A minister attended . Now you know the answers of all ministers , But I haven't got the answer yet , So you decide to predict first .
say concretely , For the first i i i Problem , Yes x x x Two ministers are right , y y y A minister was chosen wrong ( Obviously there is x + y = m x+y=m x+y=m ), If x > y x>y x>y , So you predict that the answer to this question is right , Otherwise it's wrong . For convenience , We promise m m m Is odd .
After the statistics are completed , You got the answer , You want to know how many questions you predicted correctly through your prediction method .
Input format
Two positive integers in the first line n , m n,m n,m , Guarantee m m m Is odd .
Next m m m That's ok , Each row n n n It's an integer , The first i i i Xing di j j j It's an integer a i , j a_{i,j} ai,j On behalf of the i i i The first minister is right j j j The answer to the question , 1 1 1 It means that he chose the right , 0 0 0 It means he chose the wrong one .
Next 1 1 1 That's ok n n n It's an integer , It means the answer of the competition , The first i i i Number b i b_i bi if 1 1 1 It means the first one i i i The answer to this question is right , if 0 0 0 Means the answer is wrong .
Output format
Output an integer , It means that you finally have several correct predictions .
Examples
The sample input 1
3 3
1 0 1
0 1 1
0 1 0
1 1 1
Sample output 1
2
Sample explanation 1
The first question is x = 1 , y = 2 x=1,y=2 x=1,y=2 You predict the answer is wrong ( namely 0 0 0 ), The actual answer is 1 1 1 , Wrong prediction .
The second question is x = 2 , y = 1 x=2,y=1 x=2,y=1 You predict that the answer is right ( namely 1 1 1 ), The actual answer is 1 1 1, The prediction is correct .
Third question x = 2 , y = 1 x=2,y=1 x=2,y=1 You predict that the answer is right ( namely 1 1 1 ), The actual answer is 1 1 1, The prediction is correct .
So the correct number of questions to predict is 2 2 2 .
The sample input 2
6 5
1 0 1 1 1 0
0 1 0 1 1 1
0 0 1 0 1 0
1 0 1 0 1 0
0 1 0 1 0 0
1 0 1 0 1 0
Sample output 2
4
Data range and tips
about 20 % 20\% 20% The data of , n ≤ 5 , m = 1 n \leq 5,m=1 n≤5,m=1.
about 50 % 50\% 50% The data of , n ≤ 10 , m ≤ 10 n \leq 10,m \leq 10 n≤10,m≤10.
about 100 % 100\% 100% The data of , n ≤ 1000 , m ≤ 1000 n \leq 1000,m \leq 1000 n≤1000,m≤1000, m m m It's odd .
NOI Official explanation
First of all, we should draw Kri The predicted answer , Then compare with the standard answer .
- Accumulate the selected questions 1 1 1 The number of Ministers
- obtain Kri The predicted answer
- Compare the standard answer , Contrast
Accepted
Code
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 5;
int n, m, y[MAXN], r[MAXN], x, ans;
int main () {
scanf ("%d %d", &n, &m);
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++) {
scanf ("%d", &x);
y[j] += x;
}
}
for (int i = 1; i <= n; i ++) {
scanf ("%d", &r[i]);
if (y[i] > m / 2) {
ans += r[i] == 1;
} else {
ans += r[i] == 0;
}
}
printf ("%d", ans);
return 0;
}
T2 Math games (math)
Title Description
Kri Like playing number games .
One day , He wrote down on the draft paper t t t Right integer , And for each pair of positive integers z = x × y × gcd ( x , y ) z=x \times y \times \gcd(x,y) z=x×y×gcd(x,y).
But naughty Zay eureka Kri Draft paper , Each group of y y y Wipe them all off , There may also be some changes z z z .
Now? Kri I'd like to ask you to help restore each group's y y y , In particular , For each group x x x and z z z , You need to output the smallest positive integer y y y, bring z = x × y × gcd ( x , y ) z=x \times y \times \gcd(x,y) z=x×y×gcd(x,y) . If so y y y non-existent , That is to say Zay Must have changed z z z , Then please output − 1 -1 −1 .
notes : gcd ( x , y ) \gcd(x,y) gcd(x,y) Express x x x and y y y Maximum common divisor of , That is, the largest positive integer d d d , Satisfy d d d both x x x The divisor of , again y y y The divisor of .
Input format
The first line is an integer t t t , Express t t t Right integer x x x and z z z .
Next t t t That's ok , Two positive integers per line x x x and z z z , The meaning is shown in the title description .
Output format
One line for each pair of digital outputs , If there is no positive integer that satisfies the condition y y y , Please export − 1 -1 −1 , Otherwise, the minimum positive integer satisfying the condition is output y y y .
Examples
The sample input 1
1
10 240
Sample output 1
12
Sample explanation 1
x × y × gcd ( x , y ) = 10 × 12 × gcd ( 10 , 12 ) = 240 x \times y \times \gcd(x,y)=10 \times 12 \times \gcd(10,12)=240 x×y×gcd(x,y)=10×12×gcd(10,12)=240.
The sample input 2
3
5 30
4 8
11 11
Sample output 2
6
-1
1
Data range and tips
about 20 % 20\% 20% The data of , t , x , z ≤ 1 0 3 t,x,z \leq 10^3 t,x,z≤103 .
about 40 % 40\% 40% The data of , t ≤ 1 0 3 , x ≤ 1 0 6 , z ≤ 1 0 9 t \leq 10^3,x \leq 10^6,z \leq 10^9 t≤103,x≤106,z≤109 .
For another 30 % 30\% 30% The data of , t ≤ 1 0 4 t \leq 10^4 t≤104 .
For another 20 % 20\% 20% The data of , x ≤ 1 0 6 x \leq 10^6 x≤106 .
about 100 % 100\% 100% The data of , 1 ≤ t ≤ 5 × 1 0 5 , 1 ≤ x ≤ 1 0 9 , 1 ≤ z ≤ 2 63 1 \leq t \leq 5 \times 10^5,1 \leq x \leq 10^9,1 \leq z \leq 2^{63} 1≤t≤5×105,1≤x≤109,1≤z≤263 .
NOI Official explanation
Make d = gcd ( x , y ) , x = p d , y = q d d=\gcd(x,y),x=pd,y=qd d=gcd(x,y),x=pd,y=qd,
be z = x × y × gcd ( x , y ) = p d ⋅ q d ⋅ d = p q d 3 z=x \times y \times \gcd(x,y)=pd \cdot qd \cdot d=pqd^3 z=x×y×gcd(x,y)=pd⋅qd⋅d=pqd3.
From the definition of the greatest common divisor : p p p、 q q q Coprime .( Reduction to absurdity : if p p p、 q q q Not mutual , be d d d No gcd ( x , y ) \gcd(x,y) gcd(x,y))
∴ p 2 ∴p^2 ∴p2、 q q q Coprime .
∴ d 2 = gcd ( p 2 d 2 , q d 2 ) ∴d^2=\gcd(p^2d^2,qd^2) ∴d2=gcd(p2d2,qd2), namely d 2 = gcd ( x 2 , z x ) d^2=\gcd(x^2, \frac{z}{x}) d2=gcd(x2,xz)
Immediate : d = gcd ( x 2 , z x ) d=\sqrt {\gcd(x^2, \frac{z}{x})} d=gcd(x2,xz)
Accetped
Code
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
long long T, x, d, z, y;
int main () {
scanf ("%lld", &T);
while (T --) {
scanf ("%lld %lld", &x, &z);
if (z % x) {
printf ("-1\n");
continue;
}
d = sqrt (__gcd (x * x, z / x));
y = z / x / d;
if (d * d == __gcd (x * x, z / x)) {
printf ("%lld\n", y);
} else {
printf ("-1\n");
}
}
return 0;
}
T3 character string (string)
Title Description
Kri I like strings very much , So he's looking for t t t Group string study .
The first i i i In this study , Kri Prepared two strings S S S and R R R, among S S S The length is n n n , And only by 0
、1
、-
Three characters make up ( notes : The third character here is the minus sign ), R R R Initially empty .
Each study ,Zay Will carry a beautiful length of m m m String T T T Come looking for Kri play ,Kri Very envious Zay Have such a beautiful string , I also want to use string S S S and R R R Change the string T T T.
In particular ,Kri There will be n n n operations . In every operation ,Kri Will take out S S S First character of ( Write it down as c c c), And take it from S S S Delete from . If c = c= c=-
, be Kri To delete R R R The beginning or end of a character ( After the data guarantee is deleted R R R Not empty ). otherwise ,Kri Will c c c Add to R R R At the end of .
When all operations are completed ,Kri Will check the R R R Whether and T T T equal . If R = T R=T R=T,Kri Will feel happy ; otherwise ,Kri Will feel uncomfortable .
In each study ,Kri How many ways to make yourself feel happy at last ? We define two different scenarios , If and only if in a certain operation of a certain scheme ,Kri Delete R R R The first character of . In this operation of another scheme ,Kri Delete R R R The ending character of .
Because the answer can be big , You just need to output the answer divided by 1 , 000 , 000 , 007 1,000,000,007 1,000,000,007( namely 1 0 9 + 7 10^9+7 109+7) The remainder of .
Input format
First line a positive integer .
Next there is t t t Groups of data represent t t t Research on sub string , For each set of data :
The first line has two positive integers n , m n,m n,m, Each represents a string S , T S,T S,T The length of .
The second line is the string S S S.
The third line is the string T T T.
Output format
common t t t That's ok , The first i i i Line representation i i i Answers to group studies .
Examples
The sample input
3
6 2
10-01-
01
7 3
010-1-1
101
6 4
111-00
1100
Sample output
2
1
2
Sample explanation
For example , There are two options :
first -
Delete R R R The beginning of , the second -
Delete R R R The beginning of .
first -
Delete R R R Ending , the second -
Delete R R R The beginning of .
Data range and tips
about 20 % 20\% 20% The data of , n , m ≤ 15 n,m \leq 15 n,m≤15 .
about 30 % 30\% 30% The data of , n , m ≤ 30 n,m \leq 30 n,m≤30 .
about 70 % 70\% 70% The data of , n , m ≤ 80 n,m \leq 80 n,m≤80 .
For another 10 % 10\% 10% The data of , Make sure the answer doesn't exceed 1 1 1.
about 100 % 100\% 100% The data of , 1 ≤ t ≤ 5 1 \leq t \leq 5 1≤t≤5 , 1 ≤ n , m ≤ 400 1 \leq n,m \leq 400 1≤n,m≤400.
NOI Official explanation
First we have to make sure that , Each character added determines its result at the beginning : From R R R On the left, delete ( be called l
)、 From R R R Right delete ( be called r
)、 Become T T T Part of ( be called o
). Because the plus character can only be added from the back , So when we decide that it is going to be T T T Part of when , It's in T T T The subscript of is also uniquely determined .
because S S S Determine the operation of , character string R R R The length must also be determined .
For strings R R R, It must look like this :
l l l l o o o o r r r r
Explain why l
and r
There are no scattered o
, It's simple , Because if you want to delete what should be deleted on the left, you must delete it continuously , Don't delete what shouldn't be deleted , The same is true for the one on the right . To determine the R R R The form of , Dynamic planning is better .
set up Is when the implementation to the When operating , On the left Characters will be deleted , On the right Number of schemes when characters are to be deleted , Because of this time R R R The length must be , middle o
The quantity of is also determined .
Set this time R R R The length is len
, State transition is :
When S i S_i Si yes ‘-’ when :
d p i , j , k = d p i − 1 , j + 1 , k + d p i − 1 , j + 1 , k dp_{i,j,k}=dp_{i-1,j+1,k}+dp_{i-1,j+1,k} dpi,j,k=dpi−1,j+1,k+dpi−1,j+1,k
( At this time, select Delete left or delete right ).
When S i S_i Si Not ‘-’ when :
d p i , j , k = d p i − 1 , j , k − 1 dp_{i,j,k}=dp_{i-1,j,k-1} dpi,j,k=dpi−1,j,k−1
( As long as there is something that must be deleted after this time , It means that the newly added ones will also be deleted later , namely : k ≥ 1 k \geq 1 k≥1).
d p i , j , k = d p i , j , k + d p i − 1 , j , k dp_{i,j,k}=dp_{i,j,k}+dp_{i-1,j,k} dpi,j,k=dpi,j,k+dpi−1,j,k
( Can be added to the back and match , namely : k = 0 k=0 k=0 And T l e n − j = s i T_{len-j}=s_i Tlen−j=si).
d p i , j , k = d p i , j , k + d p i − 1 , j − 1 , k dp_{i,j,k}=dp_{i,j,k}+dp_{i-1,j-1,k} dpi,j,k=dpi,j,k+dpi−1,j−1,k
( A top priority , When it's all l
when , Add it to the back and delete it on the left ).
Accepted
Code
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
template <typename G>// Fast reading
inline void read (G& x) {
x = 0;
G f = 1;
char ch = getchar ();
while ((ch > '9' || ch < '0') && ch != '-') ch = getchar();
if (ch == '-') {
f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch ^ 48);
ch = getchar ();
}
x *= f;
}
const int MAXN = 405, p = 1e9 + 7;
int T, n, m, tot, dp[MAXN][MAXN][MAXN];//dp[i][j][k] by S front i Characters , structure R In the process of , The left side needs to be deleted j individual , The right side needs to be deleted k Number of schemes
char s[MAXN], t[MAXN];
int main () {
read (T);
while (T --) {
read (n), read (m);
scanf ("%s\n%s", s + 1, t + 1);
tot = 0;// Statistics '-' The number of
for (int i = 1; i <= n; i ++) {
if (s[i] == '-') {
tot ++;
}
}
if (n - tot * 2 != m) {
// The number of numbers after deletion is the same as T inequality
puts ("0");
continue;
}
int len = 0;//len by R The current length
memset(dp, 0, sizeof(dp));// Empty dp
dp[0][0][0] = 1;
for (int i = 1; i <= n; i ++) {
if (s[i] == '-')
len --;
else
len ++;
for (int j = 0; j <= tot; j ++) {
for (int k = 0; k <= tot - j; k ++) {
if (s[i] == '-') {
// You can delete the left , You can also delete the right
dp[i][j][k] = (dp[i - 1][j + 1][k] + dp[i - 1][j][k + 1]) % p;
} else {
if (k > 0)
dp[i][j][k] = dp[i - 1][j][k - 1];// Add numbers to the end and delete
if (k == 0 && t[len - j] == s[i])// The tail does not need to be deleted , Add it directly to the tail
dp[i][j][k] = dp[i - 1][j][k];
if (len == j)
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][k]) % p;
}
}
}
}
printf("%d\n", dp[n][0][0]);
}
return 0;
}
边栏推荐
- Leetcode 19. delete the penultimate node of the linked list
- Unity初学3——敌人的移动控制和掉血区域的设置(2d)
- Leetcode 344. reverse string
- LeetCode #7.整数反转
- Navicat for Oracle Cannot create oci environment
- Ue5 light shadow basic shadow full resolution sawtooth shadow solution lumen
- 官方教程 Redshift 03 各种GI的参数和常规使用说明
- 虹科分享 | FPGA 实现的直通与存储转发切换延迟
- [beauty of software engineering - column notes] 19 | as a programmer, you should have product awareness
- Overview and summary of GI engine in redshift 024, the official tutorial
猜你喜欢
虹科教您 | 想进入TSN领域?虹科教您如何搭建TSN测试系统
虹科分享 | 为什么说EtherCAT是提高控制系统性能的最佳解决方案?
UE5 光影基础 阴影全解析 锯齿阴影解决方案 Lumen
操作系统面试题
Personal views on time complexity
LeetCode #977.有序数组的平方
虹科分享 | 带您全面认识“CAN总线错误”(一)——CAN总线错误与错误帧
2022暑初二信息竞赛学习成果分享1
[beauty of software engineering - column notes] 20 | how to deal with the headache of requirement change?
虹科分享 | 带你全面了解“CAN总线错误”(三)——CAN节点状态与错误计数器
随机推荐
官方教程 Redshift 05 system参数详细解释
LeetCode #167.两数之和 II - 输入有序数组
STP生成树原理及选举规则举例
官方教程 Redshift 01 基础理论知识和基础特性学习
Redshift 2.6.41 for maya2018 水印去除
Computer factory interview questions
[leetcode skimming] array 2 - binary search
Leetcode 19. delete the penultimate node of the linked list
Leetcode 876. Intermediate node of linked list
官方教程 Redshift 02 4中GI引擎概述及总结
leetcode刷题笔记 605. Can Place Flowers (Easy) 605.种花问题
Overview and summary of GI engine in redshift 024, the official tutorial
Traditional model predictive control trajectory tracking - circular trajectory (function package has been updated)
V-ray 5 ACEScg 工作流程设置
SQL Developer图形化窗口创建数据库(表空间和用户)
Personal views on time complexity
虹科分享 | 测试与验证复杂的FPGA设计(2)——如何在IP核中执行面向全局的仿真
Leetcode scribble notes 763. Divide the letter range (medium)
官方教程 Redshift 06 Opt参数
JUC collection class is unsafe