洛谷 P4503 [CTSC2014]企鹅QQ

暴力枚举不同的一位即可。。

主要是常数问题

1.统计答案时用sort速度快于用tr1/unordered_map，后者又快于map

（tr1/unordered_map完全达不到理论复杂度上的O(1)一次操作）（虽然复杂度一样，sort后统计比map要快得多）

2.幸好没卡自然溢出...双模hash直接T飞

 1 #pragma GCC optimize(3)
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<vector>
 6 using namespace std;
 7 #define fi first
 8 #define se second
 9 #define mp make_pair
10 #define pb push_back
11 typedef long long ll;
12 typedef unsigned long long ull;
13 typedef pair<int,int> pii;
14 namespace Hash
15 {
16 typedef ull Hdata;
17 #define N 1000000
18 const int X=131;
19 Hdata pwx[N+100];
20 void init()
21 {
22     pwx[0]=1;
23     for(int i=1;i<=N;i++)    pwx[i]=pwx[i-1]*X;
24 }
25 struct H
26 {
27     Hdata h;int sz;
28     H():h(),sz(0){}
29     H(const Hdata &a,int b):h(a),sz(b){}
30 };
31 H operator+(const H &a,const H &b)
32 {
33     H ans;ans.sz=a.sz+b.sz;
34     ans.h=a.h+b.h*pwx[a.sz];
35     return ans;
36 }
37 bool operator==(const H &a,const H &b)
38 {
39     return a.sz==b.sz&&a.h==b.h;
40 }
41 }
42 using Hash::Hdata;
43 using Hash::H;
44 using Hash::X;
45 using Hash::pwx;
46 
47 
48 int n,l,s;ll ans;
49 struct S
50 {
51     Hdata hs[201];
52     S& operator=(const char *s)
53     {
54         for(int i=1;i<=l;i++)
55         {
56             hs[i]=hs[i-1]*X+s[i];
57         }
58         return *this;
59     }
60     H gett(int l,int r)
61     {
62         if(l>r)    return H();
63         return H(hs[r]-hs[l-1]*pwx[r-l+1],r-l+1);
64     }
65 }ss[30100];
66 char tmp[2010];
67 Hdata tta[30100];
68 int main()
69 {
70     int i,j,ttt,tt2;
71     Hash::init();
72     scanf("%d%d%d",&n,&l,&s);
73     for(i=1;i<=n;i++)
74     {
75         scanf("%s",tmp+1);
76         ss[i]=tmp;
77     }
78     for(j=1;j<=l;j++)
79     {
80         ttt=0;
81         for(i=1;i<=n;i++)
82             tta[++ttt]=(ss[i].gett(1,j-1)+ss[i].gett(j+1,l)).h;
83         sort(tta+1,tta+ttt+1);tt2=0;
84         for(i=1;i<=ttt;i++)
85         {
86             tt2++;
87             if(i==ttt||tta[i+1]!=tta[i])
88             {
89                 //printf("%d %d
",j,tt2);
90                 ans+=tt2*(tt2-1)/2;
91                 tt2=0;
92             }
93         }
94     }
95     printf("%lld",ans);
96     return 0;
97 }