洛谷 P3498 [POI2010]KOR-Beads 题解

每日一题 day71 打卡

之前家里出了点事，托福学习日记和编程题解都咕了几天，请大家见谅

Analysis

这道题是我学 hash 以来第一道没看题解代码做出来的，只借鉴了思路。

首先既然要实现字符串判重，那我们已知的方法中只有 hash ，所以我们考虑如何用 hash 来解决这道题。

题目中说“and so the substrings can be reversed”，所以字符串是可以反转的，于是我们先初始化两遍 hash ：从前到后和从后到前。

那么现在有两个思路上的问题：一是如何用哈希判重，二是时间可能会超限。

先解决第一个问题，哈希值是很大的，所以 book 数组是肯定开不下的，所以我想到了前不久刚学的 map 来代替 book 数组的功能。

而在枚举时如果想取区间 [ i , j ]（包含 i 和 j ）的哈希值， 可以用 hash [ j ] - hash [ i - 1 ] * power [ i ] 来计算。

接下来是第二个问题，我们需要一些必要的剪枝来让我们的程序在时间复杂度上没有问题。

1. 如果以当前枚举的 k 所形成的段数要比已知的最大不同的段的个数要大，那么这种情况一定不是最优解。

2. 如果已知的不同的段的数量加上之后所有段的数量比已知的最大不同的段的个数要大，那么这种情况也一定不是最优解。

（建议与代码共同理解）

以下是代码实现：

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #define int long long
 7 #define ull unsigned long long
 8 #define maxn 200010
 9 #define rep(i,s,e) for(register int i=s;i<=e;++i)
10 #define dwn(i,s,e) for(register int i=s;i>=e;--i)
11 using namespace std;
12 inline int read()
13 {
14     int x=0,f=1;
15     char c=getchar();
16     while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
17     while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();}
18     return f*x;
19 }
20 inline void write(int x)
21 {
22     if(x<0){putchar('-');x=-x;}
23     if(x>9)write(x/10);
24     putchar(x%10+'0');
25 }
26 int n,base=13131;
27 int num,cnt;
28 int a[maxn],ans[maxn];
29 ull power[maxn];
30 struct node
31 {
32     ull x,y;
33 }hash[maxn];
34 map<int,bool> book;
35 void init()
36 {
37     power[0]=1;
38     rep(i,1,n) power[i]=power[i-1]*base;
39     rep(i,1,n) hash[i].x=hash[i-1].x*base+a[i];
40     dwn(i,n,1) hash[i].y=hash[i+1].y*base+a[i];
41 }
42 signed main()
43 {
44     n=read();
45     rep(i,1,n) a[i]=read();
46     init();
47     rep(i,1,n)
48     {
49         if(n/ibreak;
50         int r=0;
51         book.clear();
52         for(int j=i;j<=n;j+=i)
53         {
54             if(r+(n-j+i)/ibreak;
55             ull hash1=hash[j].x-hash[j-i].x*power[i];
56             if(book[hash1]==true) continue;
57             ull hash2=hash[j-i+1].y-hash[j+1].y*power[i];
58             if(book[hash2]==true) continue;
59             ++r;
60             book[hash1]=book[hash2]=true;
61         }
62         if(r==num) ans[++cnt]=i;
63         else if(r>num) 
64         {
65             cnt=0;
66             ans[++cnt]=i;
67             num=r;
68         }
69     }
70     write(num);
71     putchar(' ');
72     write(cnt);
73     putchar('\n');
74     rep(i,1,cnt)
75     {
76         write(ans[i]);
77         putchar(' ');
78     }
79     return 0;
80 }

如有失误请各位大佬斧正（反正我不认识斧正是什么意思）

STL-map字符串哈希

相关

P3370 【模板】字符串哈希

luogu P3370 【模板】字符串哈希

13 | 字符串哈希(字符串的哈希判等、前缀和的思想)

标签