C.Constructive Problems Never Die

Question meaning:
Given a sequence A of length n, Ai<=n.
Please find a permutation P such that for all i, Pi!=Ai.
If possible, output YES and output the permutation.
Otherwise, output NO.

Ideas:
The input is an array of a, and the b array is preprocessed first, b[i]=i.
When i The previous ones have been processed to meet the requirements.
Next, consider b[n].
If b[n]==a[n],
Find the previous b[i] and b[n] to exchange,
If b[n]!=a[n]&&The exchanged a[i]!=b[i],
means that it works and exits the loop.
If that doesn't work, revert to the way it was before.
If no feasible ones are found after traversing the previous ones,
will output NO.

Code:

#include using namespace std;const int N = 1e5+10;int n,a[N],b[N];int main(){int t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);b[i]=i;}for(int i=1;i

F.Candies

Question meaning:
Given a series of circular numbers, each time you can choose adjacent equal numbers or numbers that add = x
and eliminate them to get a candy,Ask how many candies you can get.

Thinking:
Double pointer.
First, the candies that satisfy the elimination while processing the input,
ans++,j– after each elimination.
If it is not satisfied, it is j++. When j==0, because j-1 cannot be realized,
So it can only be j++.
Because it is circular, the last input may be eliminated with the first
input, so the last two pointers are used, and
handles the first and last.
The first i=0, the last j–.
Because each input will go to the next digit of the last existing digit
, so you need j-go back to the last digit first.

Code:

#include using namespace std;const int N = 1e5+10;int a[N];int n,x,ans,i,j;int main(){scanf("%d%d",&n,&x);for(i=0;i0){if(a[j]==a[j-1]||a[j]+a[j-1]==x){ans++;j--;}else j++;}else j++;}i=0;j--;while(j>i&&(a[j]==a[i]||a[j]+a[i]==x)){j--;i++;ans++;}printf("%d\n",ans);return 0;}

G.Regular Expression

Question meaning:
Give q queries, each query gives a string consisting of lowercase letters.
Please output the length and number of the shortest regular expression matched by this string.

Ideas:
After analyzing the examples given and testing with test sites,
learned that only .* + can shorten the string length.
. Can be used in any position, indicating an arbitrary letter, * and + cannot be used in the first position,
* means copy the preceding letter any number of times (can be 0 times), + means inAdd any string of any length (>1) after it.
Then each regular expression can only start with a letter or ..

(1) When the string length is 1,
matches itself and .
(2) When the string length is 2,
1> All characters in the string are the same, such asaa
Then the matching cases are:
Starting with the letter a:
aa
a+
a*
a.
Starting with .:
…
.+
.*
.a
There are 8 types in total.
2> Not all characters are the same: such as ab
ab
a+
a.
…
.+
.b
(3) When length>=3
We found that .+ must match any string.
Therefore, when length>=3, the shortest length must be 2.
1> When all letters are the same, such as aaa
Start with a letter:
a+
a*
Start with a dot:
.+
.*
Totalfour.

2>Not all letters are the same:
Then you can't use *
that means copying, so only
a+
.+
There are two cases in total

As for the modulo mentioned in the title, it's pure scaring!

Code:

#include using namespace std;int main(){int q;string s;scanf("%d",&q);while(q--){cin>>s;if(s.size()==1) puts("1 2");else{bool f=1;for(int i=1;i