最近感觉自己越来越摆了，看到各位大佬洛谷的月通过量都 100 以上感到十分震惊，不像我这个废物月通过量只有 30 。
T1 无限之环
考虑互为子串的两个字符串，容易发现两个串的 \(B\) 部分字母所组成的集合一定完全相同，考虑两个串的 \(A\) 部分，如果 \(A\) 部分的末尾字符属于 \(B\) 部分字母所组成的集合，那么这个字符显然可以和 \(B\) 部分进行匹配，可以直接将这样的末尾字符删去，不难发现两个串剩余的 \(A\) 部分一定完全相等。
比较显然的做法是将所有串按照 \(B\) 部分字母所组成的集合以及剩余的 \(A\) 部分进行分组，直接输出每组内包含的字符串即可。
code
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <cstring>
#include <vector>
using namespace std;
const int max1 = 1e6;
const int base = 29, mod1 = 998244353, mod2 = 20051107;
int n;
char A[max1 + 5], B[max1 + 5];
struct Hash
{
int h1, h2;
Hash () {}
Hash ( int __h1, int __h2 )
{ h1 = __h1, h2 = __h2; }
Hash operator + ( const Hash &A ) const
{ return Hash(( h1 + A.h1 ) % mod1, ( h2 + A.h2 ) % mod2); }
Hash operator * ( const Hash &A ) const
{ return Hash(1LL * h1 * A.h1 % mod1, 1LL * h2 * A.h2 % mod2); }
bool operator == ( const Hash &A ) const
{ return h1 == A.h1 && h2 == A.h2; }
bool operator < ( const Hash &A ) const
{
if ( h1 != A.h1 )
return h1 < A.h1;
return h2 < A.h2;
}
};
struct Data
{
int s; Hash h;
Data () {}
Data ( int __s, Hash __h )
{ s = __s, h = __h; }
bool operator < ( const Data &A ) const
{
if ( s != A.s )
return s < A.s;
return h < A.h;
}
};
map <Data, int> Map;
vector <int> id[max1 + 5];
int total;
int main ()
{
freopen("infty.in", "r", stdin);
freopen("infty.out", "w", stdout);
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
{
scanf("%s%s", A + 1, B + 1);
int len;
int s = 0;
if ( B[1] != '=' )
{
len = strlen(B + 1);
for ( int k = 1; k <= len; k ++ )
s |= 1 << B[k] - 'a';
}
Hash h = Hash(0, 0);
if ( A[1] != '=' )
{
len = strlen(A + 1);
while ( len && ( s >> ( A[len] - 'a' ) & 1 ) )
--len;
for ( int k = 1; k <= len; k ++ )
h = h * Hash(base, base) + Hash(A[k] - 'a' + 1, A[k] - 'a' + 1);
}
if ( Map.find(Data(s, h)) == Map.end() )
Map[Data(s, h)] = ++total;
id[Map[Data(s, h)]].push_back(i);
}
printf("%d\n", total);
for ( int i = 1; i <= total; i ++ )
{
printf("%lu ", id[i].size());
for ( auto v : id[i] )
printf("%d ", v);
printf("\n");
}
return 0;
}
T2 变化多端
考虑按照从内到外的顺序依次枚举每个马槽，从这个马槽开始 Bfs ，找到最近的马后将其移动到这个马槽即可，马的数量较多的时候可以改为移动空格（显然几乎没有优化）。
code
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#include <utility>
#include <iostream>
using namespace std;
const int lim = 8, sum = 64;
const int inf = 0x3f3f3f3f;
int n;
bool block[sum + 5], vis[sum + 5], koi[sum + 5], done[sum + 5], rev;
int point[sum + 5], dis[sum + 5], pre[sum + 5];
queue <int> que;
vector < pair <int, int> > ans;
bool Bfs ( int s )
{
if ( block[s] )
{ done[s] = true; return true; }
memset(vis, 0, sizeof(bool) * sum);
memset(dis, 0x3f, sizeof(int) * sum);
memset(pre, -1, sizeof(int) * sum);
while ( !que.empty() )
que.pop();
dis[s] = 0; vis[s] = true; que.push(s);
while ( !que.empty() )
{
int now = que.front();
que.pop();
int x = now >> 3, y = now & 7;
int v;
if ( x > 0 && y > 1 )
{
v = ( x - 1 ) << 3 | ( y - 2 );
if ( !done[v] && !vis[v] )
{
dis[v] = dis[now] + 1;
que.push(v);
vis[v] = true;
pre[v] = now;
if ( block[v] )
break;
}
}
if ( x > 0 && y < 6 )
{
v = ( x - 1 ) << 3 | ( y + 2 );
if ( !done[v] && !vis[v] )
{
dis[v] = dis[now] + 1;
que.push(v);
vis[v] = true;
pre[v] = now;
if ( block[v] )
break;
}
}
if ( x < 7 && y > 1 )
{
v = ( x + 1 ) << 3 | ( y - 2 );
if ( !done[v] && !vis[v] )
{
dis[v] = dis[now] + 1;
que.push(v);
vis[v] = true;
pre[v] = now;
if ( block[v] )
break;
}
}
if ( x < 7 && y < 6 )
{
v = ( x + 1 ) << 3 | ( y + 2 );
if ( !done[v] && !vis[v] )
{
dis[v] = dis[now] + 1;
que.push(v);
vis[v] = true;
pre[v] = now;
if ( block[v] )
break;
}
}
if ( x > 1 && y > 0 )
{
v = ( x - 2 ) << 3 | ( y - 1 );
if ( !done[v] && !vis[v] )
{
dis[v] = dis[now] + 1;
que.push(v);
vis[v] = true;
pre[v] = now;
if ( block[v] )
break;
}
}
if ( x > 1 && y < 7 )
{
v = ( x - 2 ) << 3 | ( y + 1 );
if ( !done[v] && !vis[v] )
{
dis[v] = dis[now] + 1;
que.push(v);
vis[v] = true;
pre[v] = now;
if ( block[v] )
break;
}
}
if ( x < 6 && y > 0 )
{
v = ( x + 2 ) << 3 | ( y - 1 );
if ( !done[v] && !vis[v] )
{
dis[v] = dis[now] + 1;
que.push(v);
vis[v] = true;
pre[v] = now;
if ( block[v] )
break;
}
}
if ( x < 6 && y < 7 )
{
v = ( x + 2 ) << 3 | ( y + 1 );
if ( !done[v] && !vis[v] )
{
dis[v] = dis[now] + 1;
que.push(v);
vis[v] = true;
pre[v] = now;
if ( block[v] )
break;
}
}
}
for ( int i = 0; i < sum; i ++ )
{
if ( block[i] && dis[i] != inf )
{
int now = i;
while ( now != s )
{
ans.push_back(make_pair(now, pre[now]));
now = pre[now];
}
block[i] = false;
block[s] = true;
done[s] = true;
break;
}
}
return true;
}
void Update ()
{
if ( !rev )
{
for ( int y = 0; y < lim; y ++ )
{
for ( int x = 0; x < lim; x ++ )
{
int p = x << 3 | y;
if ( koi[p] && !done[p] && Bfs(p) )
return;
}
}
}
else
{
for ( int y = lim - 1; y >= 0; y -- )
{
for ( int x = lim - 1; x >= 0; x -- )
{
int p = x << 3 | y;
if ( koi[p] && !done[p] && Bfs(p) )
return;
}
}
}
return;
}
int main ()
{
freopen("changeful.in", "r", stdin);
freopen("changeful.out", "w", stdout);
scanf("%d", &n);
char s[5];
for ( int i = 1; i <= n; i ++ )
{
scanf("%s", s);
point[i] = ( s[0] - 'a' ) << 3 | ( s[1] - '1' );
block[point[i]] = true;
}
for ( int i = 0; i < ( n >> 3 ); i ++ )
{
for ( int j = 0; j < lim; j ++ )
{
int x = j << 3 | i;
koi[x] = true;
}
}
for ( int j = 0; j < ( n & 7 ); j ++ )
{
int x = j << 3 | ( n >> 3 );
koi[x] = true;
}
if ( n > ( sum >> 1 ) )
{
rev = true; n = 0;
for ( int i = 0; i < sum; i ++ )
{
if ( !block[i] )
point[++n] = i;
block[i] ^= 1;
koi[i] ^= 1;
}
}
for ( int i = 1; i <= n; i ++ )
Update();
if ( rev )
for ( auto &p : ans )
swap(p.first, p.second);
printf("%lu\n", ans.size());
for ( auto p : ans )
{
putchar('a' + ( p.first >> 3 ));
putchar('1' + ( p.first & 7 ));
putchar('-');
putchar('a' + ( p.second >> 3 ));
putchar('1' + ( p.second & 7 ));
putchar('\n');
}
return 0;
}
T3 活罪难赦
考虑分析平衡串的性质，对于 \(x\) ，我们从高向低依次考虑每一位，如果最高位为 \(0\) ，显然平衡串的前后两个部分完全相同，如果最高位为 \(1\) ，显然平衡串的前后两个部分完全相反。
考虑到每次操作为区间取反，这并不好实现，比较套路的想法是对原串进行异或差分，因此分析平衡串的差分数组的性质，设 \(t_i=s_{i-1}\oplus s_i\) ，由于平衡串前后完全相同或者完全相反，因此前后做差分实际上完全相同，特殊的，差分数组中间位置取值任意。
注意到题目给定 \(b\) ，表示对平衡串整体取反不会产生代价，因此我们只需要考虑平衡串一些位置上的值相等，而不需要考虑其具体的取值。
一个比较显然的 \(O(nq)\) 暴力是取出所有满足取值相等的位置，统计这些位置中 \(0,1\) 的个数，然后将 \(\min(cnt_0,cnt_1)\) 统计入答案中。
观察这些取值相等的位置的特点，发现这些位置的 lowbit 相等，因此可以预处理每个位置 \(i\) 到 \(n\) 的子串内，满足下标 lowbit 为 \(2^k\) 的差分数组中 \(1\) 的个数 \(sum_{i,k}\) ，查询时枚举每个 lowbit 统计贡献即可，复杂度 \(O((n+q)\log n)\) 。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 3e5;
int n, q, a[max1 + 5];
char s[max1 + 5];
int sum[max1 + 5][20];
int main ()
{
freopen("sins.in", "r", stdin);
freopen("sins.out", "w", stdout);
scanf("%d%s", &n, s);
for ( int i = 0; i < n; i ++ )
a[i] = s[i] - '0';
for ( int i = n - 1; i >= 1; i -- )
a[i] = a[i] ^ a[i - 1];
for ( int k = 0; ( 1 << k ) <= n; k ++ )
{
for ( int i = n - 1; i >= 0; i -- )
{
if ( i + ( 1 << k ) < n )
{
sum[i][k] = sum[i + ( 1 << k )][k];
sum[i][k] += a[i + ( 1 << k )];
}
}
}
for ( int i = 0; i <= n - 1; i ++ )
for ( int k = 0; ( 1 << k ) <= n; k ++ )
sum[i][k] -= sum[i][k + 1];
scanf("%d", &q);
int L, R, ans;
while ( q -- )
{
scanf("%d%d", &L, &R);
ans = 0;
for ( int k = 0; ( 1 << k + 1 ) <= R - L + 1; k ++ )
ans += min(sum[L][k] - sum[R + 1][k], ( R - L + 1 ) / ( 1 << k + 1 ) - ( sum[L][k] - sum[R + 1][k] ));
printf("%d\n", ans + 1 >> 1);
}
return 0;
}