Noi online 2022 popular group problem solving & personal understanding

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$ The judgment questions consist of , Yes $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$ Problem , Yes $x$ Two ministers are right ,$y$ A minister was chosen wrong （ Obviously there is $x+y=m$ ）, If $x>y$ , So you predict that the answer to this question is right , Otherwise it's wrong . For convenience , We promise $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$ , Guarantee $m$ Is odd .

Next $m$ That's ok , Each row $n$ It's an integer , The first $i$ Xing di $j$ It's an integer $a_{i,j}$ On behalf of the $i$ The first minister is right $j$ The answer to the question ,$1$ It means that he chose the right , $0$ It means he chose the wrong one .

Next $1$ That's ok $n$ It's an integer , It means the answer of the competition , The first $i$ Number $b_i$ if $1$ It means the first one $i$ The answer to this question is right , if $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$ You predict the answer is wrong （ namely $0$ ）, The actual answer is $1$ , Wrong prediction .

The second question is $x=2,y=1$ You predict that the answer is right （ namely $1$ ）, The actual answer is $1$, The prediction is correct .

Third question $x=2,y=1$ You predict that the answer is right （ namely $1$ ）, The actual answer is $1$, The prediction is correct .

So the correct number of questions to predict is $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\%$ The data of ,$n\le 5,m=1$.

about $50\%$ The data of ,$n\le 10,m\le 10$.

about $100\%$ The data of ,$n\le 1000,m\le 1000$,$m$ It's odd .

NOI Official explanation

First of all, we should draw Kri The predicted answer , Then compare with the standard answer .

1. Accumulate the selected questions $1$ The number of Ministers
2. obtain Kri The predicted answer
3. 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$ Right integer , And for each pair of positive integers $z=x\times y\times \gcd (x,y)$.

But naughty Zay eureka Kri Draft paper , Each group of $y$ Wipe them all off , There may also be some changes $z$ .

Now? Kri I'd like to ask you to help restore each group's $y$ , In particular , For each group $x$ and $z$ , You need to output the smallest positive integer $y$, bring $z=x\times y\times \gcd (x,y)$ . If so $y$ non-existent , That is to say Zay Must have changed $z$ , Then please output $-1$ .

notes ：$\gcd (x,y)$ Express $x$ and $y$ Maximum common divisor of , That is, the largest positive integer $d$ , Satisfy $d$ both $x$ The divisor of , again $y$ The divisor of .

Input format

The first line is an integer $t$ , Express $t$ Right integer $x$ and $z$ .

Next $t$ That's ok , Two positive integers per line $x$ and $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$ , Please export $-1$ , Otherwise, the minimum positive integer satisfying the condition is output $y$ .

Examples

The sample input 1

1
10 240

Sample output 1

12

Sample explanation 1

$x\times y\times \gcd (x,y)=10\times 12\times \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\%$ The data of ,$t,x,z\le 10^3$ .

about $40\%$ The data of ,$t\le 10^3,x\le 10^6,z\le 10^9$ .

For another $30\%$ The data of ,$t\le 10^4$ .

For another $20\%$ The data of ,$x\le 10^6$ .

about $100\%$ The data of ,$1\le t\le 5\times 10^5,1\le x\le 10^9,1\le z\le 2^{63}$ .

NOI Official explanation

Make $d=\gcd (x,y),x=pd,y=qd$,

be $z=x\times y\times \gcd (x,y)=pd\cdot qd\cdot d=pq{d}^3$.

From the definition of the greatest common divisor ：$p$、$q$ Coprime .( Reduction to absurdity : if $p$、$q$ Not mutual , be $d$ No $\gcd (x,y)$)

$\therefore p^2$、$q$ Coprime .

$\therefore d^2=\gcd (p^2{d}^2,q{d}^2)$, namely $d^2=\gcd (x^2,\frac{z}{x})$

Immediate :$d=\sqrt{\gcd (x^2,\frac{z}{x})}$

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$ Group string study .

The first $i$ In this study , Kri Prepared two strings $S$ and $R$, among $S$ The length is $n$ , And only by 0、1、- Three characters make up （ notes ： The third character here is the minus sign ）,$R$ Initially empty .

Each study ,Zay Will carry a beautiful length of $m$ String $T$ Come looking for Kri play ,Kri Very envious Zay Have such a beautiful string , I also want to use string $S$ and $R$ Change the string $T$.

In particular ,Kri There will be $n$ operations . In every operation ,Kri Will take out $S$ First character of （ Write it down as $c$）, And take it from $S$ Delete from . If $c=$-, be Kri To delete $R$ The beginning or end of a character （ After the data guarantee is deleted $R$ Not empty ）. otherwise ,Kri Will $c$ Add to $R$ At the end of .

When all operations are completed ,Kri Will check the $R$ Whether and $T$ equal . If $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$ The first character of . In this operation of another scheme ,Kri Delete $R$ The ending character of .

Because the answer can be big , You just need to output the answer divided by $1,000,000,007$（ namely $10^9+7$） The remainder of .

Input format

First line a positive integer .

Next there is $t$ Groups of data represent $t$ Research on sub string , For each set of data ：

The first line has two positive integers $n,m$, Each represents a string $S,T$ The length of .

The second line is the string $S$.

The third line is the string $T$.

Output format

common $t$ That's ok , The first $i$ Line representation $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$ The beginning of , the second - Delete $R$ The beginning of .

first - Delete $R$ Ending , the second - Delete $R$ The beginning of .

Data range and tips
about $20\%$ The data of ,$n,m\le 15$ .

about $30\%$ The data of ,$n,m\le 30$ .

about $70\%$ The data of ,$n,m\le 80$ .

For another $10\%$ The data of , Make sure the answer doesn't exceed $1$.

about $100\%$ The data of ,$1\le t\le 5$ ,$1\le n,m\le 400$.

NOI Official explanation

First we have to make sure that , Each character added determines its result at the beginning ： From $R$ On the left, delete （ be called l）、 From $R$ Right delete （ be called r）、 Become $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$ Part of when , It's in $T$ The subscript of is also uniquely determined .

because $S$ Determine the operation of , character string $R$ The length must also be determined .

For strings $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$ 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$ The length must be , middle o The quantity of is also determined .

Set this time $R$ The length is len, State transition is ：

When $S_i$ yes ‘-’ when ：

$$d{p}_{i,j,k}=d{p}_{i-1,j+1,k}+d{p}_{i-1,j+1,k}$$

（ At this time, select Delete left or delete right ）.

When $S_i$ Not ‘-’ when ：

$$d{p}_{i,j,k}=d{p}_{i-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\ge 1$）.

$$d{p}_{i,j,k}=d{p}_{i,j,k}+d{p}_{i-1,j,k}$$

（ Can be added to the back and match , namely ：$k=0$ And $T_{len-j}=s_i$）.

$$d{p}_{i,j,k}=d{p}_{i,j,k}+d{p}_{i-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;
}