CF::GYM 100203D / Different vectors

Posted on By 二价氢

题目:CF::GYM 100203D

我们发现,数字本身并没有什么特别的含义,含义在于数字与数字之间的联系

换而言之,就是石头门数字与数字之间的距离决定了一切

于是我们处理出每个数下一次出现的位置,并将它当作新的字符串

因为是循环同构,所以要跑一遍最小表示法

最后用哈希判重即可

AC-Code (原谅我用了模\(2^{64}\)的哈希)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
const int maxn = 10000 + 5 , maxk = 100 + 5;
const long long md = 101;
unsigned long long ha[maxn];
int s[maxn][maxk];
int rs[maxk];
int n , k;
map<int , int> app;
void work()
{
    memset(ha , 0 , sizeof(ha));
    scanf("%d%d" , &n , &k);
    for (int i = 0 ; i < n ; i++)
    {
        for (int j = 0 ; j < k ; j++)
        {
            scanf("%d" , &s[i][j]);
            rs[j] = 0;
        }
        app.clear();
        for (int j = 1 ; j <= k ; j++)
        {
            if (app[s[i][j - 1]])
                rs[app[s[i][j - 1]] - 1] = j;
            app[s[i][j - 1]] = j;
        }
        for (int j = 1 ; j <= k ; j++)
        {
            if (app[s[i][j - 1]])
                rs[app[s[i][j - 1]] - 1] = j;
            app[s[i][j - 1]] = j;
        }
        for (int j = 0 ; j < k ; j++)
            rs[j] = ((rs[j] - 1 - j) % k + k) % k;
        int mi = 0 , mj = 1 , mk = 0 , mt = 0;
        while (mi < k && mj < k && mk < k)
        {
            mt = rs[(mi + mk) >= k ? mi + mk - k : mi + mk] - 
                rs[(mj + mk) >= k ? mj + mk - k : mj + mk];
            if (!mt)
                mk++;
            else
            {
                if (mt > 0) mi = mi + mk + 1;
                else mj = mj + mk + 1;
                if (mi == mj) mj ++;
                mk = 0;
            }
        }
        mk = (mi < mj) ? mi : mj;
        for (int p = 0 ; p < k ; p++)
            ha[i] = ha[i] * md + rs[( mk + p ) % k] + 1;
    }
    sort(&ha[0] , &ha[n]);
    int ans = unique(&ha[0] , &ha[n]) - &ha[0];
    printf("%d\n" , ans);
}
int main()
{
    int t;
    scanf("%d" , &t);
    while (t--)
        work();
    return 0;
}