“蔚来杯“2022牛客暑期多校训练营7，签到题CFGJ

题号 标题 已通过代码 通过率 团队
A Floor Tiles in a Park 点击查看 74/232
B Rotate Sum 3 点击查看 24/313
C Constructive Problems Never Die 点击查看 1253/4543
D The Pool 点击查看 3/28
E Ternary Search 点击查看 6/17
F Candies 点击查看 1127/3921
G Regular Expression 点击查看 850/1567
H Grammy Sorting 点击查看 2/20
I Suffix Sort 点击查看 24/235
J Melborp Elcissalc 点击查看 282/589
K Great Party 点击查看 177/1195
L Maximum Range 点击查看 18/270

C.Constructive Problems Never Die

链接：https://ac.nowcoder.com/acm/contest/33192/C
来源：牛客网

题目描述
Grammy has a sequence AA of length nn.

Please find a permutation PP such that P_i \neq A_iP
i
​


​
=A
i
​
for all ii.
输入描述:
There are multiple test cases.

The first line contains a single integer TT (1 \leq T \leq 100,0001≤T≤100000), denoting the number of test cases.

For each test case:

The first line contains a single integer nn (1 \leq n \leq 100, 0001≤n≤100000).

The second line contains nn integers A_1,A_2,\dots,A_nA
1
​
,A
2
​
,…,A
n
​
(1 \leq A_i \leq n1≤A
i
​
≤n).

It is guaranteed that the sum of nn does not exceed 500,000500000.
输出描述:
For each test case:

If the permutation does not exist, output “NO” in one line.

Otherwise output “YES” in the first line, then output nn integers in the second line, denoting the permutation P_1,P_2,\dots,P_nP
1
​
,P
2
​
,…,P
n
​
.
示例1
输入
复制
3
3
3 3 3
3
3 2 1
6
1 1 4 5 1 4
输出
复制
NO
YES
1 3 2
YES
4 5 1 2 3 6

题意：

• T（1e5）组数据， 给出一个长为n(1e5)的数组，构造一个排列满足每个位置上的数与该数组都不同。如果无法构造输出NO。

思路：

• 如果 𝐴_𝑖 全相同则无解，解法很多。
• 这里用的是给原数组值按大到小排序，排列存入小根堆， 每次取出来放到某个位置上，如果放不上去就放回排列。对于最后一个数， 还要判断能否与第一个数交换来满足条件。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct node{int w, id; }a[maxn];
bool cmp(node x, node y){ return x.w>y.w; }
int b[maxn];

int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        int n;   cin>>n;
        priority_queue<int,vector<int>,greater<int> >q;
        for(int i = 1; i <= n; i++){
            cin>>a[i].w;  a[i].id = i;  b[i] = 0;  q.push(i);
        }
        sort(a+1,a+n+1,cmp);
        int ok = 1, lst = 0;
        for(int i = 1; i <= n; i++){
            int  t = q.top();  q.pop();
            if(a[i].w == t ){
                if(q.size()==0){
                    if(t != a[1].w){
                        int tt = b[a[1].id];
                        b[a[1].id] = t;
                        b[a[i].id] = tt;
                    }else ok = 0;
                    break;
                }
                int tt = q.top();  q.pop();
                b[a[i].id] = tt;  q.push(t);
            }else{
                b[a[i].id] = t;
            }
        }
        if(ok==1){
            cout<<"YES\n";
            for(int i = 1; i <= n; i++)cout<<b[i]<<" \n"[i==n];
        }else{
            cout<<"NO\n";
        }
    }
    return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
 

F.Candies

链接：https://ac.nowcoder.com/acm/contest/33192/F
来源：牛客网

题目描述
Grammy has a circular array a_1, a_2,\dots,a_na
1
​
,a
2
​
,…,a
n
​
. You can do the following operations several (possibly, zero) times:

1. Choose two adjacent positions with the same number, and erase them.

2. Choose two adjacent positions such that the numbers on these positions add up to a special number xx, and erase them.

After each time you do an operation successfully, Grammy will give you a candy. Meanwhile, the remaining part of the array will be concatenated. For example, after deleting the third and fourth element of the array, the second element and the fifth element will become adjacent.

Find the maximum number of candies you can get.

Two positions u,vu,v(u<vu<v) are adjacent if and only if u+1=vu+1=v or u=1,v=Lu=1,v=L, where LL is the length of the remaining array.
输入描述:
The first line contains two integers n,xn,x (1 \leq n \leq 10^5, 1 \leq x \leq 10^91≤n≤10
5
,1≤x≤10
9
), denoting the length of the array and the special number xx.

The secons line contains nn integers a_1, a_2,\dots, a_na
1
​
,a
2
​
,…,a
n
​
(1 \leq a_i \leq 10^91≤a
i
​
≤10
9
), denoting the numbers in the circular array.
输出描述:
Output an integer, denoting the maximum number of candies you can get.
示例1
输入
复制
6 5
1 1 4 5 1 4
输出
复制
2
示例2
输入
复制
10 5
1 2 5 2 1 2 3 4 8 4
输出
复制
3

题意：

• 给出一个长为n的数组，如果相邻两个数相等或者相加=x，那么就可以消除这两个数，剩下的数接在一起。求最多可以对原数组消除多少次。

思路：

• 可以证明不管先消相邻的还是先消相等的，是不会影响结果的，所以直接无脑消除就行了，
• 用一个双端队列能消就消，维护一下即可。注意由于是环形，所以最后要把序列开头和结尾的能匹配的消掉。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, y;  cin>>n>>y;
    deque<int>q;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int x;  cin>>x;
        if(!q.empty()){
            if(x==q.back() || x+q.back()==y){
                q.pop_back();
                ans++;
            }else{
                q.push_back(x);
            }
        }else{
            q.push_back(x);
        }
    }
    while(q.size()>=2 && (q.front()+q.back()==y || q.front()==q.back())){
        q.pop_back();
        q.pop_front();
        ans++;
    }
    cout<<ans<<"\n";
    return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
 

G.Regular Expression

链接：https://ac.nowcoder.com/acm/contest/33192/G
来源：牛客网

题目描述
Grammy has recently been interested in regular expression while focusing on cases where the alphabet consists of characters from aa to zz. Today she asks NIO some questions. Each question gives string AA, asking the minimum length of expressions matching string AA according to the matching rules and the number of all shortest expressions.

To learn detailed rules about how regular expressions match strings,
you can refer to https://en.wikipedia.org/wiki/Regular_expression.

Here we only consider characters from ‘a’ to ‘z’, ‘.’, ‘?’, '', ‘+’, ‘|’, ‘(’, ‘)’. It is assumed that the asterisk, the question mark and the plus sign have the highest priority, then concatenation and then alternation. Parentheses can be used to change the priority. For example, \texttt{a(b|c)}a(b|c) can match “ab” and “ac”. If there is no ambiguity then parentheses may be omitted. For example, \texttt{(ab)c}(ab)c can be written as \texttt{abc}abc, and \texttt{a|(b(c))}a|(b(c*)) can be written as \texttt{a|bc*}a|bc*

Here are some examples of matching:

(or): \texttt{gray|grey}gray|grey can match “gray” or “grey”.

(question mark): \texttt{colou?r}colou?r matches both “color” and “colour”.

(asterisk): \texttt{abc}abc matches “ac”, “abc”, “abbc”, “abbbc”, and so on.

(plus sign): \texttt{ab+c}ab+c matches “abc”, “abbc”, “abbbc”, and so on, but not “ac”.

(wildcard): \texttt{a.b}a.b matches any string that contains an “a”, and then any character and then “b”; and \texttt{a.*b}a.*b matches any string that contains an “a”, and then the character “b” at some later point. More precisely, “ab” can be matched by \texttt{a.*b}a.*b but not \texttt{a.b}a.b.

(concatenation): Let expression R=\texttt{(ab|c)}R=(ab|c) matches { ab, c}{ab,c} and expression S=\texttt{(d|ef)}S=(d|ef) matches {d, ef}{d,ef}. Then, (RS)=\texttt{((ab|c)(d|ef))}(RS)=((ab|c)(d|ef)) matches {abd, abef, cd, cef}{abd,abef,cd,cef}
If you are not sure about whether a regular expression is valid, then you can use https://regex101.com/ to check its validity. Note that the character set we use is slightly different from the website.

输入描述:
The input contains only a single case.

The first line contains a single integer QQ (1\leq Q\leq 100,0001≤Q≤100000), denoting the number of questions. The ii-th line of the following QQ lines contain one string AA consisting of lowercase letters (1\leq |A|\leq 200,0001≤∣A∣≤200000), denoting the string AA of the ii-th question. It is guaranteed that \sum |A|\leq 1,000,000∑∣A∣≤1000000.
输出描述:
For each question, output a single line containing 2 integers - the minimum length and the number to the question. Note that the answer may be extremely large, so please print it modulo 998,244,353998244353 instead.
示例1
输入
复制
2
a
ab
输出
复制
1 2
2 6

题意：

• 给出q个询问（1e5），每个询问给出一个长为2e5的字符串，判断用正则表达式去匹配最小的正则表达式长度，以及有多少种该长度的表达式可以匹配这个字符串。

思路：

• 容易发现，“.*”可以匹配所有串，因此答案长度≤2，只需要对1和2分别讨论。
• 当输入串长度为1时，“a”和“.”可以匹配，长度为1，方案数为2。
• 当输入串长度≥2时，长度为2，方案数则分别考虑“ab”，“a+”，“a.”，“a*”，“.a”，“.+”，“…”，“.*”这几种能否匹配即可。

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    int T;  cin>>T;
    while(T--){
        string s;  cin>>s;
        int n = s.size(), ans1, ans2;
        if(n==1)ans1 = 1, ans2 = 2; //a, .
        else{
            ans1 = 2, ans2 = 0;
            ans2++;          //.*
            ans2++;          //.+
            if(n==2)ans2++;  //ab
            if(n==2)ans2++;  //a.
            if(n==2)ans2++;  //.a
            if(n==2)ans2++;  //..
            int ok = 1;
            for(int i = 0; i < n; i++)if(s[i]!=s[0])ok = 0;
            ans2 += ok;      //a*
            ans2 += ok;      //a+
        }
        cout<<ans1<<' '<<ans2<<'\n';
    }
    return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
 

J.Melborp Elcissalc

链接：https://ac.nowcoder.com/acm/contest/33192/J
来源：牛客网

题目描述
Grammy has a favorite number kk. She thinks that all the numbers divisible by kk are good.

For each array containing only numbers from 00 to k-1k−1, Grammy define its goodness as the number of non-empty consecutive subarrays that sums to a good number.

Please count the number of arrays of length nn such that its goodness is tt. Since the answer can be enormous, output the answer modulo 998,244,353998244353.
输入描述:
A single line contains three integers n,k,tn,k,t (1 \leq n, k \leq 64, 0 \leq t \leq \frac{n(n+1)}{2}1≤n,k≤64,0≤t≤
2
n(n+1)
​
).
输出描述:
Output a single number, denoting the answer modulo 998,244,353998244353.
示例1
输入
复制
2 5 1
输出
复制
12
示例2
输入
复制
7 10 15
输出
复制
2016
示例3
输入
复制
46 50 171
输出
复制
645560469

题意：

• 给出k（<64），构造一个长度为n（<64），每个数都属于[0,k-1]的数组，满足其中恰好有t个非空连续子序列的和是被k整除的。
• 求最够能构造多少个这样的数组，答案模998244353。

思路：

• 假定序列已经构造出来了，那么给定序列怎么求有多少子区间和≡0(mod 𝑘) 呢
  （𝑚𝑜𝑑 𝑘意义下）前缀和后考虑0~𝑘−1中每个数的出现次数，对于每个出现次数x，𝐶（𝑥,2）一下就是答案，最后累加即为满足条件的子区间个数。
• 又因为前缀和数组和原数组一一对应，对于原问题可以直接dp满足条件的前缀和数组有多少种 。记𝑓(𝑖,𝑗,𝑘)代表考虑完了0~𝑖的数，放进了𝑗个位置（即前缀和长度为j），对答案贡献为𝑘（C(出现次数, 2)，出现次数<j ） 的方案数，则𝑓(𝑘,𝑛,𝑡)即为答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
LL f[70][70][70*70], c[70][70]; //考虑完了0~𝑖的数，放进了𝑗个位置，对答案贡献为𝑘时的方案数
int main(){
    ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
    LL n, K, t;  cin>>n>>K>>t;
    c[0][0] = 1;
    for(LL i = 1; i <= n+1; i++){
        c[i][0] = 1;
        for(int j = 1; j <= i; j++)
            c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;
    }
    f[0][0][0] = 1;
    for(LL i = 0; i < K; i++){            //考虑[0,k-1]的数
        for(LL j = 0; j <= n; j++){       //当前前缀和长为j(放了随机的位置)
            for(LL k = 0; k <= j; k++){   //让i这个数在前缀和中出现k次
                for(LL l = c[k+(i==0)][2]; l <= t; l++){ //满足区间和整除k的子区间至少有C(k,2)个
                    //这k个数可能的位置有C(n-(j-k), k)种, f[j-k,l-c(k,2)]为不考虑数i的k次时原本的方案数
                    (f[i+1][j][l] += f[i][j-k][l-c[k+(i==0)][2]]*c[n-(j-k)][k]%mod) %= mod;
                }
            }
        }
    }
    cout<<f[K][n][t]<<"\n";
    return 0;
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/126233996