2022牛客蔚来杯第七场CFGJ(K)

2022牛客蔚来杯第七场CFGJ(K)
2022牛客蔚来杯第七场
文章目录
- 2022牛客蔚来杯第七场
- [C.Constructive Problems Never Die](https://ac.nowcoder.com/acm/contest/33192/C)
  F.Candies
  [G.Regular Expression](https://ac.nowcoder.com/acm/contest/33192/G)
  [J.Melborp Elcissalc](https://ac.nowcoder.com/acm/contest/33192/J)
  [K.Great Party](https://ac.nowcoder.com/acm/contest/33192/K)
C.Constructive Problems Never Die
- 题意
  - 给长度为n的数组a，所有ai<=n
  - 请你构造一个n的排列b，使得任意ai != bi
- 题解
  - 当a所有数都相等时，即所有数都是x(1<=x<=n)，不可能构造出n的排列符合要求
  - 只要a不全相等，就一定存在排列b符合要求。只需要贪心的放，直接构造一个ans=1,2,…n的排列，某个位置不符合要求直接扫一遍，找到符合要求的交换
  - 可以先把所有相等的位置存放起来，只需要把这些位置两两交换就行，算是优化
- 代码
打表
```
#include 
#include 
#include 

using namespace std;

const int N=1e5+10;
int t,n,a[N],ans[N];
map cnt;

void solve() {
    cnt.clear();//清空计数哈希表
    
    cin>>n;
    vector tmp;
    
    bool f=true;
    for(int i=1;i<=n;i++) {
        ans[i]=i; cin>>a[i];
        if(ans[i]==a[i]) tmp.push_back(i);//存储不合法的位置(值)
        
        cnt[a[i]]+=1;
        if(cnt[a[i]]>=n) f=false;//判断是否全为一个数
    }
    if(!f) {
        cout<<"NO"<<'\n';
        return ;
    }
    cout<<"YES"<<'\n';
    
    for(int i=0;i>t;
    while(t--) solve();
    
    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
47
48
49
50
51
52
53
54
55
56
57
58
59
```
F.Candies
- 题意
  - 给一个长度为n的循环数组，以及特定值x
  - 如果相邻两个元素相等或者两者之和为x，那么就把这两个元素消除，每消除一次ans++，问ans最大值
- 题解
  - 可证得，随意消除都只能消除一样的数量，所以最大消除数就是答案。
  - 只需维护一个双端队列，暴力遍历消除并计数即可
- 代码
```
#include 
#include 

using namespace std;

int main() {
    int n,x,res=0;
    deque q;
    
    cin>>n>>x;
    for(int i=0;i>t;
        if(q.empty()) q.push_back(t);//空的，先加入
        else if(t==q.back() || t+q.back()==x) {//符合要求则消除且计数
            res++;
            q.pop_back();
        }
        else q.push_back(t);//不符合要求直接加入
    }
    while(q.size()>=2 && (q.back()+q.front()==x || q.back()==q.front())) {//把循环的相邻进行消除处理
        res++;
        q.pop_back();
        q.pop_front();
    }
    cout<
```
- 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
G.Regular Expression
- 题意
  - 给定一个字符串s，问可以匹配s的最短正则表达式长度len，以及长度为len能表达s的正则表达式数量
- 题解
  - 前置知识，正则表达式
```
'.'点：是一个元符号，可以表达任意一个字符

'+'加：表示把前一个标记重复一次或者多次

'*'乘：表示把前一个标记重复零次或者多次



于是，".*"可以表达任何字符串

1. s.len=1;假设s="a"，那么符合要求的正则表达式为，'a','.'
2. s.len=2;
   1. 两字符相等，假设s="aa"，那么方程要求的正则表达式为，'aa','a.','a+','a*','.a','..','.+','.*'
   2. 两字符不等，假设s="ab"，那么方程要求的正则表达式为，'ab','a.','.b','..','.+','.*'
3. s.len>=3;
	 1. 字符全相等，假设s="aa..aa",那么符合要求的正则表达式为，'a+','a*','.+','.*'
	 1. 字符不全相等，假设s="aa..ba",那么符合要求的正则表达式为，'.+','.*'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
```
- 代码
```
#include 
#include 

using namespace std;
const int N=1e5+10;

void solve() {
    string s;
    cin>>s;
    int n=s.length();
    
    if(n>=3){
        bool f=false;
        for(int i=1;i>t;
    while(t--) solve();
    
    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
```
J.Melborp Elcissalc
- 题意
  - 给定k，若区间和是k的倍数，那么数组的优度+1
  - 长度为n，所有数在[0,k)之间，优度为t的数组有多少个
- 题解
  - 首先简化问题来更好理解题目。若给定一个长度为n的在[0,k-1]的数组，那么其优度为多少？由于优度与区间和相关，枚举区间不如转换为前缀和去看端点，计算出数组前缀和pre模余k情况下，注意数组所有数在[0,k-1]，所以前缀和即使在模余k意义下也是和原数组一一对应的。那么区间[i,j]和是k的倍数条件转换为，pre[i]=pre[j] (mod k)，即pre中每两个相同的点都能构成一个优度区间，可以枚举i \in[0,k-1]出现的次数cnt_i那么总优度为\sum \plus^{2}_{cnt_i}
  - 回到原问题，我们可以dp构造所有的pre(模余k意义)前缀和，由于前缀和和原数组一一对应，那么符合条件的pre数量即为答案。
    
    定义：f[i,len,v]考虑放i个[0,k-1]这些数，总共放了len个数，优度为v的pre数量
    
    始态终态：f[0,0,0]=1，ans=f[k,n,t]
    
    转移：前i-1数字已经放入l总共en个，优度为v。现在考虑放数字i，同时放入num个。当i>1时，此时状态为f[i,len+num,v+c(2,num)] (长度变为len+num,优度增加c(2,num),因为这num个数都相同，挑两个就行)，转移其实就是在原先放着的len个数里面再丢进num个数，所以即为上一状态*c(num,len+num)；当i=1时，即考虑放前1一个，即考虑放数字0，由于前缀和数组第一个一定为0，所以此时状态为f[i,len+num,v+c(2,num+1)] (优度变化为c(2,num+1)是因为加上本身含有的0及新加入的num个0，总共有num+1个0，从中挑两个)
    
    ${\begin{cases} f [i, l e n + n u m, v + C_{n u m + 1}^{2}] & + = & f [i - 1, l e n, v] \times C_{n u m + l e n}^{n u m} & , i = 1 \\ f [i, l e n + n u m, v + C_{n u m}^{2}] & + = & f [i - 1, l e n, v] \times C_{n u m + l e n}^{n u m} & , i \neq 1 \end{cases}$ ${f [i, l e n + n u m, v + C_{n u m + 1}^{2}] f [i, l e n + n u m, v + C_{n u m}^{2}] + = + = f [i - 1, l e n, v] \times C_{n u m + l e n}^{n u m} f [i - 1, l e n, v] \times C_{n u m + l e n}^{n u m}, i = 1, i \neq = 1$
- 代码
```
#include 

using namespace std;
const int N=70,mod=998244353;

int n,k,t;
int c[N][N];
int f[N][N][N*N];//注意开的范围，优度可以取到c(n,n)，即n^2级别

int main() {
    cin>>n>>k>>t;
    for(int i=0;i<=n+1;i++) //预处理组合数
        for(int j=0;j<=i;j++) {
            if(!j) c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    
    f[0][0][0]=1;
    for(int i=1;i<=k;i++) {//dp符合要求的前缀和数组数量
        for(int len=0;len<=n;len++) {
            for(int v=0;v<=t;v++) {
                if(!f[i-1][len][v]) continue;//剪枝，此时已经为0了，那么转移到下一状态乘组合数之后，下一状态的值还是0，等于没用，直接剪掉
                
                if(i==1) {
                    for(int num=0;num+len<=n;num++)
                        f[i][len+num][v+c[num+1][2]]=(f[i][len+num][v+c[num+1][2]]+1LL*f[i-1][len][v]*c[len+num][num])%mod;
                }
                else {
                    for(int num=0;num+len<=n;num++)
                        f[i][len+num][v+c[num][2]]=(f[i][len+num][v+c[num][2]]+1LL*f[i-1][len][v]*c[len+num][num])%mod;
                }
            }
        }
    }
    
    cout<
```
- 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
K.Great Party
- 题意
  - 有意思的nim游戏变形，但是没学莫队，学完来补qwq
- 题解
  - 依次枚举不同堆数，可以发现奇数堆先手必胜；偶数堆时可以类比经典nim游戏，只不过此时的必败态为所有堆数都只含1个石子，可以偷懒把所有堆事先-1，就变成必败态为全0，完全变成经典nim游戏，异或和为0先手必败，否则必胜。
- 代码
```
1
```

2022牛客蔚来杯第七场

文章目录

C.Constructive Problems Never Die

F.Candies

G.Regular Expression

J.Melborp Elcissalc

K.Great Party