2020北京ICPC网络选拔赛Round1-J

2020北京ICPC网络选拔赛Round1-J

十一月 03, 2020

Shift and Reverse

  • 题意

给出一个长度为n<1e5的序列a

可以进行如下操作任意次：

选择一个位置i

将$a_1,a_2,….a_i,a_{i+1},a_{i+2},..a_n$ 变为

$a_i,a_{i−1},…,a_1,a_n,a_{n−1},…,a_{i+1}$

问能产生多少个不同的序列

  • 题解

对于一个给定序列 如

1 2 3 4 5 6

选择{1 2 3}{4 5 6}

一次操作后得到:3 2 1 6 5 4

选择 {3 2}{1 6 5 4}

再一次操作后得到:2 3 4 5 6 1

选择{2 3 4 5}{6 1}

再一次操作后得到:5 4 3 2 1 6

发现无论如何操作得到的序列一定是

1 2 3 4 5 6 1 2 3 4 5 6 或

6 5 4 3 2 1 6 5 4 3 2 1 的某个长度为n的子段

用hash将子段映射成对应的ull型数

On遍历用map类型的vis标记 统计共有多少中不同的子串

实际上无论几次操作最多得到2n种不同结果

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,ll>
const int Max=2e5+5;
const int Mod=1e9+7;
const int inf=0x3f3f3f3f;

/*
*/
ull Hash[Max],base[Max],num_hash=0;
int num[Max],ans=0;
map<ull,int>vis;
void init(){
    base[0]=1;
    for(int i=1;i<=Max;i++)base[i]=base[i-1]*131;
}
ull get_hash(int L,int R){
    return Hash[R]-Hash[L-1]*base[R-L+1];
}
int main(){
    Turnoff;
    int n;init();
    while(cin>>n){
        vis.clear();
        num_hash=0;ans=0;
        for(int i=0;i<n;i++){
            cin>>num[i];
            num[i+n]=num[i];
        }
        for(int i=1;i<=2*n;i++)Hash[i]=Hash[i-1]*131+num[i];
        for(int i=1;i<=n;i++){
            num_hash=get_hash(i,i+n-1);
            if(!vis[num_hash])ans++;
            vis[num_hash]=1;
        }
        reverse(num,num+n*2);
        for(int i=1;i<=2*n;i++)Hash[i]=Hash[i-1]*131+num[i];
        for(int i=1;i<=n;i++){
            num_hash=get_hash(i,i+n-1);
            if(!vis[num_hash])ans++;
            vis[num_hash]=1;
        }
        cout<<ans<<endl;
    }
}