题目描述
任务一
给定 \(n\) 个 \(32\) 位无符号整数，将它们从小到大排序。
任务二
有 \(2n\) 个人玩 "石头剪刀布" 游戏，他们分成两排，每排 \(n\) 个人， \(a_{i,j}=0/1/2\) 分别表示第 \(i\) 排第 \(j\) 人出石头、剪刀、布。
\(q\) 次询问，每次给定 \(x,y,l\) ，询问第一排第 \(x\sim x+l-1\) 人和第二排第 \(y\sim y+l-1\) 人比赛后，第一排有多少人会赢。
任务三
给点一个由 ( 、 ) 、 ? 组成的字符串，询问有多少种方法将每个 ? 替换为 ( 和 ) 中的一个，使其变成一个合法的括号串，对 \(2^{32}\) 取模。
数据范围
任务一
- \(n=10^5\) ，时间限制 \(\texttt{3s}\) 。
- \(n=10^8\) ，时间限制 \(\texttt{4s}\) 。
- \(n=2\cdot 10^8\) ，时间限制 \(\texttt{6s}\) 。
任务二
- \(n=q=10^3\) ，时间限制 \(\texttt{3s}\) 。
- \(n=q=3\cdot 10^5\) ，时间限制 \(\texttt{3s}\) 。
任务三
- \(n=120000\) ，时间限制 \(\texttt{3s}\) 。
- \(n=225000\) ，时间限制 \(\texttt{3s}\) 。
- \(n=266666\) ，时间限制 \(\texttt{3s}\) 。
分析
任务一
基数排序
基数排序（\(\texttt{Radix sort}\)）是一种稳定的排序方法，即两个相同元素在排序后的顺序与排序前相同。
先看单关键字基数排序，其实和桶排序没有区别。
for(int i=1;i<=n;i++) c[a[i]]++;
for(int i=1;i<=V;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) rk[i]=c[a[i]]--;
如果 a[i] 相同，靠后的元素会分到较大的排名，因此基数排序是稳定的。
再看双关键字基数排序，操作流程如下：
- 对第一关键字求前缀和。
- 对第二关键字做基数排序，求出每个元素的排名。
- 按照上述排名的倒序枚举所有元素，该元素的真实排名为其第一关键字所在桶中的剩余元素数量。
for(int i=1;i<=n;i++) c[a[i].x]++,d[a[i].y]++;
for(int i=1;i<=V;i++) c[i]+=c[i-1],d[i]+=d[i-1];
for(int i=n;i>=1;i--) tmp[d[a[i].y]--]=i;
for(int i=n;i>=1;i--) rk[tmp[i]]=c[a[tmp[i]].x]--;
正确性如何保证？
- 如果两个元素的第一关键字不同，根据
c数组为的含义，第一关键字较小的元素排名较小。 - 如果两个元素的第一关键字相同，第二关键字不同，第二关键字较大的元素在
tmp数组中分到了较大的编号，在第四行中先被枚举到，从而获得更大的排名。 - 如果两个元素一二关键字都相同，我们认为靠后的元素第二关键字较大，分析方法与第二种情况类似。
多关键字排序操作流程和双关键字类似。
如果用基数排序对数字排序，将 \(B\) 进制下的每一位看成一个关键字，时间复杂度 \(\mathcal O\big(n\log _B(\max a_i)\big)\) 。一般取 \(B\) 为 \(2\) 的幂次（以 \(2^8\) 或 \(2^{16}\) 为主），从而可以用位运算优化。
在代码实现的过程中，由于我们已经按照优先级较高的关键字排好序了，所以只需对当前位（优先级较低的关键字）做一遍桶排。
for(int u=0;u<32;u+=8)
{
memset(c,0,4*256);
for(int i=1;i<=n;i++) c[a[i]>>u&255]++;
for(int i=1;i<256;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) tmp[c[a[i]>>u&255]--]=a[i];
memcpy(a+1,tmp+1,4*n);
}
缓存
这需要我们对计算机读取数据的原理有一定了解。
由于博主对此了解并不深入，如有错误烦请指出。
计算机优先从缓存中读取数据，如果没有读到再从内存中读取。缓存容量小但读取快，内存容量大但读取慢。
缓存也分一级、二级、三级，其中一级缓存速度最快，容量一般为 \(\texttt{128KB}\sim\texttt{2MB}\) 。
在基数排序中取 \(B=2^8\) ，则足以将桶塞进一级缓存，从而提高读取效率。
namespace task1
{
ui c[256];
void main()
{
ui n=read(),seed=read();
ui *a=new ui[n+5],*tmp=new ui[n+5];
for(int i=1;i<=n;i++) seed=next_integer(seed),a[i]=seed;
for(int u=0;u<32;u+=8)
{
memset(c,0,4*256);
for(int i=1;i<=n;i++) c[a[i]>>u&255]++;
for(int i=1;i<256;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) tmp[c[a[i]>>u&255]--]=a[i];
memcpy(a+1,tmp+1,4*n);
}
output_arr(a+1,4*n);
}
}
任务二
暴力 \(\mathcal O(nq)\) ，接下来两条路可走。
样例二第 \(9\) 行为
2 3 3。
循环展开
\(\texttt{CPU}\) 运算特点：如果不同运算之间相互独立，可以并行完成。
以求和为例，暴力写法如下：
for(int i=1;i<=n;i++) sum+=a[i];
但是如果用 \(8\) 个变量分别统计下标 \(\bmod 8\) 位置的数之和，可以刺激 \(\texttt{CPU}\) 并行。
for(i=1;i+7<=n;i+=8)
{
s1+=a[i],s2+=a[i+1],s3+=a[i+2],s4+=a[i+3];
s5+=a[i+4],s2+=a[i+5],s3+=a[i+6],s4+=a[i+7];
}
sum=s1+s2+s3+s4+s5+s6+s7+s8;
for(;i<=n;i++) sum+=a[i];
以下数据为做 \(10^5\) 次对长为 \(10^5\) 的数组求和所用时间，在 noi linux 2.0 系统下通过运行 \(20\) 次求平均值得到。
- 不循环展开：7.45 秒。
- 步长为 \(2\) ：4.31 秒。
- 步长为 \(4\) ：4.24 秒。
- 步长为 \(6\) ：3.66 秒。
- 步长为 \(8\) ：3.84 秒。
当然，步长并不是越大越好，因为寄存器数量有限，而且码量会大幅增长，一般选择步长为 \(6\) 或 \(8\) 。
对于本题，步长选择 \(6\) 或 \(8\) 用时均为 2.13 秒，下面是步长为 \(6\) 的代码。
namespace task2
{
const int maxn=3e5+5;
int n,q;
char a[maxn],b[maxn];
int c[maxn],d[maxn],f[3][3];
ui res[maxn];
void main()
{
scanf("%d%d%s%s",&n,&q,a,b);
for(int i=0;i<n;i++) c[i]=a[i]-'0',d[i]=b[i]-'0';
f[0][1]=f[1][2]=f[2][0]=1;
for(int i=1,j=0,l=0,x=0,y=0;i<=q;i++)
{
scanf("%d%d%d",&x,&y,&l);
ui s1=0,s2=0,s3=0,s4=0,s5=0,s6=0,sum=0;
for(j=0;j+5<l;j+=6)
{
s1+=f[c[x+j]][d[y+j]];
s2+=f[c[x+j+1]][d[y+j+1]];
s3+=f[c[x+j+2]][d[y+j+2]];
s4+=f[c[x+j+3]][d[y+j+3]];
s5+=f[c[x+j+4]][d[y+j+4]];
s6+=f[c[x+j+5]][d[y+j+5]];
}
sum=s1+s2+s3+s4+s5+s6;
for(;j<l;j++) sum+=f[c[x+j]][d[y+j]];
res[i]=sum;
}
output_arr(res+1,4*q);
}
}
bitset 优化
每场比赛产生贡献有三种情况：第一排为 \(0/1/2\) ，第二排为 \(1/2/0\) 。
用 \(3\) 个 bit 保存每个人的信息，第一排存储是否为 \(0/1/2\) ，第二排存储是否为 \(1/2/0\) 。
这样我们得到了两个长为 \(3n\) 的 \(\texttt{01}\) 串，询问等价于将其分别左移 \(3x,3y\) 位后，求按位与中前 \(3l\) 位的 popcount 。
时间复杂度 \(\mathcal O(\frac {nq}w)\) ，有 \(3\) 倍常数。
namespace task2
{
const int maxn=3e5+5;
int n,q;
char s[maxn];
ull a[2][maxn],b[2][maxn];
ui res[maxn];
void set(ull *b,int x)
{
b[x>>6]|=1ull<<(x&63);
}
void shift(ull *a,ull *b,int x,int len)
{
int h=x>>6,l=x&63;
ull lst=a[h]>>l;
for(int i=0;i<=len>>6;i++) b[i]=lst|(l?a[i+h+1]<<(64-l):0),lst=a[i+h+1]>>l;
b[len>>6]&=(1ull<<(len&63))-1;
}
void main()
{
n=read(),q=read();
for(int i=0;i<=1;i++)
{
scanf("%s",s);
for(int j=0;j<n;j++) set(a[i],3*j+(s[j]-'0'+!i)%3);
}
for(int i=0;i<q;i++)
{
ui x=read(),y=read(),l=3*read();
shift(a[0],b[0],3*x,l),shift(a[1],b[1],3*y,l);
for(int j=0;j<=(l>>6);j++) res[i]+=__builtin_popcountll(b[0][j]&b[1][j]);
}
output_arr(res,4*q);
}
}
任务三
数组寻址
假如我们要访问数组 a 中的第 \(5\) 个元素，有两种写法：a[5] 和 *(a+5) 。
第一种写法很好理解，对于第二种写法，a 表示数组头指针，a+5 表示指向数组中第五个元素的指针，再用 * 解除引用即可。
一句话总结：数组名即为数组的头指针，数组中的元素被连续存储在内存（或缓存）中。
回到本题，记 \(f_{i,j}\) 表示考虑前 \(i\) 个字符，左括号层数为 \(j\) 的方案数，容易写出转移方程：
\[\begin{cases} f_{i,j}=f_{i-1,j-1} & if(s_i=\texttt{(})\\ f_{i,j}=f_{i-1,j+1} & if(s_i=\texttt{)})\\ f_{i,j}=f_{i-1,j-1}+f_{i-1,j+1} & if(s_i=\texttt{?})\\ \end{cases} \]暴力时间复杂度\(\mathcal O(n^2)\) ，显然过不去。
对于前 \(2\) 种转移，常规的转移需要扫描整个数组。但是如果我们开一个长为 \(2n+\mathcal O(1)\) 的内存池，并将头指针指向内存池中间，那么前两种转移可以通过移动头指针的方式 \(\mathcal O(1)\) 完成，注意要将数组边界（新访问到的位置）设为零。
对于第三种转移，先令头指针减一（即完成左括号的转移），再令 \(f_j\gets f_{j+2}\) 即可。
还有两个明显而重要的优化：
- 若 \(2\not\mid (i-j)\) ，则 \(f_{i,j}\) 一定为零。
- 数组上界为 \(\min(i,n-i)\) 。
namespace task3
{
const int maxn=266671;
int n;
char s[maxn];
ui buf[2*maxn],*f=buf+maxn;
void main()
{
scanf("%d%s",&n,s+1),f[0]=1;
for(int i=1;i<=n;i++)
{
if(s[i]=='(') f--,f[0]=0;
if(s[i]==')') f++;
if(s[i]=='?')
{
f--,f[0]=0;
for(int j=i&1,len=min(i,n-i);j<=len;j+=2) f[j]+=f[j+2];
}
}
printf("%u\n",f[0]);
}
}
以下是完整代码，把上面三个 namespace 贴进来即可：
#include<bits/stdc++.h>
#define ui unsigned int
#define ull unsigned long long
using namespace std;
int id;
ui read()
{
int q=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) q=10*q+ch-'0',ch=getchar();
return q;
}
ui next_integer(ui x)
{
x^=x<<13,x^=x>>17,x^=x<<5;
return x;
}
void output_arr(ui *a, ui sz)
{
ui blocks=sz/4,res=sz;
for (ui i=0,x=23333333;i<blocks;i++) res^=a[i]+x,x=next_integer(x);
printf("%u\n",res);
}
int main()
{
scanf("%d",&id);
if(id==1) task1::main();
if(id==2) task2::main();
if(id==3) task3::main();
return 0;
}