Ah, it's another day to brush questions~~

Friends who want to see questions 1 to 5 can Kangkang here~~

In order to facilitate understanding, I made some questions a little more popular, and some of the original questions really can't go on

OK, no more waste words brush questions~~

Question 6: Sushi タワワ - Luogu

Title Description:

A sushi consists of a rice and a dish. Now I want to make sushi tower with n sushi. (including n rice and N dishes)

There are three ways to pack a sushi.

1. Intact: in the order of rice and vegetables.

2. Turn over: according to the order of dishes and rice.

3. Unpacking: separate the rice and vegetables and pack them separately.

For example, if you want to install three sushi towers into "dish, rice, dish, dish, rice and rice" from the bottom, you can do it in the following order.

1. Take a sushi apart and serve it.

2. Put a sushi directly.

3. Turn a sushi upside down.

4. Put on the left white rice. Because it takes a lot of time to open sushi, I want to reduce the number of open sushi as much as possible.

Find the minimum number of sushi to be disassembled to complete the target sushi tower.

Input format: two lines. The first line gives the number of sushi N. The second line gives the string s with a length of 2N, indicating the stacking order of sushi towers (from bottom to top). S is a string consisting of 0 and 1, where 0 represents rice and 1 represents vegetables.

Output format: one line. The minimum number of sushi to be disassembled to complete the target sushi tower. Add a newline at the end of the output.

Example 1

Input:

3
101100

Output:

1

Example 2

Input:

5
0000111011

Output:

3

Idea:

Violence is impossible. It is impossible to be violent in this life;

We can adopt the following ideas:

1. Count the sushi that has not been split

2. Subtract the whole sushi from the total

Code:

#include<bits/stdc++.h>
using namespace std;
string s;
int n,t;
int main() {
	scanf("%d",&n);
	cin>>s;
	int len=s.size();
	for(int i=0;i<len;i++){
		if((s[i]=='0'&&s[i+1]=='1')||(s[i]=='1'&&s[i+1]=='0')){//If it's full sushi 
			i++;//a key! i + +, which means that the whole sushi has been "taken away". Don't walk again 
			t++;//Number of complete sushi plus 1 
		}
	}
	printf("%d\n",n-t); 
	return 0;
}

Question 7: おとぎのののの Gaoqiao Jun Luogu

Title Description:

AtCoder, where Takahashi lives, like us, also commonly uses 10 Arabic numerals (0-9) (0 − 9) in decimal system.

However, the relationship between the size of the numbers in AtCoder country and the size of the numbers we commonly useDifferent. For example: when the number of AtCoder countries increases from small to largeIn AtCoder, 8 is bigger than 9, and 72 is bigger than 97.

Give the size relationship of each Arabic numeral in the AtCoder country. Please arrange some numbers in the AtCoder country in ascending order.

In addition, like the numbers we commonly use, the smallest number in AtCoder must be 0

Example 1

Input:

0 8 1 3 5 4 9 7 6 2
10
1
2
3
4
5
6
7
8
9
10

Output:

8
1
3
5
4
9
7
6
2
10

Example 2

Input:

0 9 8 7 6 5 4 3 2 1
3
13467932
98738462
74392

Output:

74392
98738462
13467932

Idea:

In this problem, we need to convert the numbers in the AtCoder kingdom into normal numbers, and then use the structure to record two elements: one is the number in the AtCoder Kingdom and the other is the normal number.

Code:

#include<bits/stdc++.h>
using namespace std;
struct yin {
	int a;//Figures in the kingdom of AtCoder 
	int b;//Normal number 
} yy[77777];
int a[10],n,k;
int woc(int aa) {//Convert the numbers in the AtCoder kingdom into normal numbers 
	int ans=0;
	int k=1;
	while(aa) {
		int h=aa%10;
		ans+=a[h]*k;
		aa/=10;
		k*=10;
	}
	return ans;
}
bool cmp(yin x,yin y) {//Sort from small to large according to the normal value 
	return x.b<y.b;
}
int main() {
	for(int i=0; i<=9; i++)
		scanf("%d",&k),a[k]=i;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&yy[i].a);
		yy[i].b=woc(yy[i].a);
	}
	sort(yy+1,yy+1+n,cmp);//sort 
	for(int i=1;i<=n;i++) printf("%d\n",yy[i].a);
 	return 0;
}

Question 8: (iwi) - Los Angeles Valley

Title Description:

Symmetry is defined as follows:

1. Empty string
2. One letter 'i'
3. One letter 'w'
4. Contain a symmetrical string in two letters ('i 'or' w '), such as "iwi", "wiw", "ii", "www"
5. Contain a symmetrical string in parentheses. Note that there are two forms of parentheses: 1 "()" 2, ") (", that is, "(i)" and ") i(", are legal symmetric strings.

Make at least several changes to make a string symmetrical.

Enter a string consisting of 'i','w', 'and' ('and') '.

Output a positive integer, that is, the minimum number of changes.

Example 1

Input:

(iwi)

Output:

0

Example 2

Input:

ii(((((ww

Output:

5

Idea:

This problem is a simulation!

Suppose the length of the string is N,

If the firstIf the bit is' i ', then NoThe bit should also be 'i';

If the firstIf the bit is' w ', then NoThe bit should also be 'w';

If the firstIf the bit is' (', then theBit is') ';

If the firstIf the bit is') ', then the second bitBit is' (');

Code

#include<bits/stdc++.h>
using namespace std;
string s;
bool yin(char x,char y) {
	if(x=='i'&&y=='i') return 1;
	if(x=='w'&&y=='w') return 1;
	if(x=='('&&y==')') return 1;
	if(x==')'&&y=='(') return 1;
/*	
regulations: 
If bit I is' I ', then bit n-i-1 is also' I ';
If bit I is' w ', then bit n-i-1 is also' w ';
If bit I is' (', then bit n-i-1 is')';
If bit I is') ', then bit n-i-1 is' (';
	
*/ 
	return 0;
}
int k=0;
int main() {
	cin>>s;
	int si=s.size();
	for(int i=0;i<(si+1)/2;i++) {
		if(!yin(s[i],s[si-i-1])) k++;//If not, k++ 
	}
	printf("%d\n",k);
	return 0;
}

Question 9: And が N の interval - Luogu

Title Description:

I'll give you an arrangement of n and write it down as, ask how many pairs of L,R, satisfy

Example 1

Input:

7
7 6 5 4 3 2 1

Output:

2

Example 2

Input:

20
19 11 10 7 8 9 17 18 20 4 3 15 16 1 5 14 6 2 13 12

Output:

3

Idea:

This problem is done with prefix and, and then simulate the left and right endpoints

Code:

#include<bits/stdc++.h>
using namespace std;
int n,a[100010];
int ans=0;
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);//input 
		a[i]=a[i-1]+a[i];//Prefix and 
	}
	for(int i=1;i<=n;i++) {//Simulated left endpoint 
		for(int j=i;j<=n;j++){//Simulate right endpoint 
			if(a[j]-a[i-1]>n)//Explain that a[j]-a[i-1] is from a[i] to a[j] 
			//If the sum is greater than n, there is no need to add it. The sum will only become larger and larger 
			    break;
			if(a[j]-a[i-1]==n)//If sum equals n 
			    ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Question 10: [ARC076A] Reconciled? - Luogu

Title Description

He has N dogs and M monkeys. すぬけ Jun wants to line up these N+M animals.

すぬけけけけけけけけけけけけけけけけけけけ.

How many such permutations are there? Please output the answerThe result of taking the mold. However, there are differences between dogs and monkeys.

Example 1

Input:

2 2

Output:

8

Example 2

Input:

100000 100000

Output:

530123477

Idea:

This question

The arrangement of monkeys and dogs is undoubtedly cross arrangement;

We can divide them into a team full of dogs and a team full of monkeys

There are teams full of dogs! N (factorial of n)

A team full of monkeys! M (factorial of M)

The whole team has! N*! M arrangement

We can find that:

1. First, the absolute values of N and M cannot be greater than 1;

2. If N-M==1, there are two possibilities:

(1) monkey dog monkey dog... Monkey (starts with monkey and ends with monkey)

(2) dog monkey dog monkey dog monkey... Dog (starts with dog and ends with dog)

The whole team has! N  *  ! M arrangement

3. If N==M, there are two arrangements for the arrangement of dogs and monkeys in one case:

(1) monkey dog, monkey dog, monkey dog... Monkey dog (starts with monkey and ends with dog)

(2) dog monkey dog monkey... Monkey dog (starts with dog and ends with monkey)

Because there are two arrangements for one situation

The whole team has! N  *  ! M * 2 arrangements

Code:

#include<bits/stdc++.h>
using namespace std;
const int Mod=1000000007;
long long n,m;
long long jc(int x) {//Factorial 
	long long ans=1;
	for(int i=1; i<=x; i++)
		ans*=(i%Mod),ans%=Mod;//Touch every step 
	return ans;
}
int main() {
	scanf("%lld%lld",&n,&m);
	if(abs(n-m)>=2) {//n. If the absolute value of M is greater than 2 
		printf("%d\n",0);//There is no arrangement method 
		return 0;
	}
	n=jc(n),m=jc(m); 
	if(n==m)//If N==M, the whole team has! N * ! M * 2 arrangements
		printf("%lld\n",m*n%Mod*2%Mod);
	else//If N-M==1, the whole team has! N * ! M arrangement
		printf("%lld\n",m*n%Mod);
	return 0;
}

Oh, finally, don't forget --