M32_模拟赛总结
T1:AERODROM
时空限制
Time Limit: 1000MS
Memory Limit: 32768KB
题目：
N个登机口，办理登机业务，第i个窗口的单位办理时间为Ti，M个人办理登机业务，他们可以选择最佳的方案，不考滤换人和换窗口的时间，所有窗口是同时计时的，即同时开始办理业务，请输出所有人都登机的最少时间。如样例1： 2个窗口，6个人，第一个窗口的单位时间是7,第二个是10, 一二个人分别在两个窗口办理，7秒时第三个人可在第一个窗口开始办理，10秒时，第四人开始在窗口二办理，时间14时，第五人一窗口。在时间20，窗口2可以使用，如果第六人在此办理，总时间将是30秒，如果等1秒在一窗口办理，则总时间是28秒。
输入：
第一行两个正整数 N (1 ≤ N ≤ 100 000), 窗口数,和M (1 ≤ M ≤ 1 000 000 000), 登机人数。 以下每行一个数Ti表示第i个窗口的单位办理时间 (1 ≤ Ti ≤ 10^9).
输出：
一个数，最少办理时间。
样例：
input
7 10
3 8 3 6 9 2 4
output
8
解析：
根据题意，最后的答案$ans$是耗时最长的窗口的耗时，我们要使这个最长耗时最短，显而易见的二分，签到题。
时间复杂度： $O(nlogn)$ 。
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,m;ll mp[N],mis=1e9;
ll in(){
ll x=0;char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
bool check(ll limit){
int t=0;
for(int i=1;i<=n;i++){
t+=limit/mp[i];
if(t>=m) return true;
}
return false;
}
int main(){
freopen("aerodrom.in","r",stdin);
freopen("aerodrom.out","w",stdout);
n=in(),m=in();
for(int i=1;i<=n;i++)
mp[i]=in(),mis=min(mis,mp[i]);
ll l=0,r=mis*m;
while(l<r){
ll mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%lld\n", l);
return 0;
}
T2:HERKABE
时空限制：
Time Limit: 1000MS
Memory Limit: 32768KB
题目：
给出N个由大写字母构成的名字，现在要求对名字排序，要求有相同前缀的单词要排在一起，问共有多少种排法。
输入：
第一行一个正整数 N (3 ≤ N ≤ 3000), 名字的个数。 以下N行，每行一个名字长度界于1到 3000 (inclusive) 名字无重复且按任意顺序给出。.
输出：
一行一个正整数表示方案总数。由于数据大要求输出模1 000 000 007的值.
样例：
input
5
MARICA
MARTA
MATO
MARA
MARTINA
output
24
input
4
A
AA
AAA
AAAA
output
8
解析：
字符串前缀，根据这个关键点，容易联想到字典树，我们先尝试建出字典树，看看有什么发现，如图：
容易发现，对于每一个节点，它的子树是可以任意排列的，而不同节点的子树排列方案之间是相互独立的，符合乘法原理。
所以，我们的答案呼之欲出：对于每一个节点，如果它的子树个数是 $x$ ,则 $ans*=(x!)$ 。
但是，我们发现，如果只是这样，第二组样例出现了问题，我们漏了一种情况： 对于当前节点 $s$ ,如果 $s$ 也是一个单词的结尾，那它本身也算作它的子树之一，也会参与排列。
一般情况下，这道题就可以完结撒花了，可惜这道题不一样，它卡空间。
祭出 节点压缩 Trie树,空间完全不是问题。
我们想办法规避字典树，回忆这道题的关键点：每个节点的子树个数。我们只需要得到这个信息就可以了。因此，我们选择排序+分治。
排序的话，快排大概是 $O(n^2logn)$ ，可以过。稳妥一点还有优秀的基数排序 $O(n^2)$ ,绝对不会T。
时间复杂度： $O(n^2logn)$ 。
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3005,M=1e5+5;
const ll mod=1e9+7;
int n,m;
ll ans=1,A[35];
string mp[N];
void solve(int pos,int l,int r){//pos:深度
if(l==r) return ;//只有这一个单词，返回
int sum=0,last=l;//sum:字数个数
for(int i=l;i<=r;i++){
if(mp[i][pos]!=mp[last][pos]){//遇到了新的子节点，分治
solve(pos+1,last,i-1);
last=i,sum++;
}
if(i==r) sum++,solve(pos+1,last,i);
}
ans*=A[sum],ans%=mod;
return ;
}
int main(){
freopen("herkabe.in","r",stdin);
freopen("herkabe.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
cin>>mp[i],mp[i]+='*';//处理空字符的情况
sort(mp+1,mp+1+n);
A[0]=1;
for(int i=1;i<=30;i++)
A[i]=(A[i-1]*i)%mod;//阶乘预处理
solve(0,1,n);
cout<<ans%mod;
return 0;
}T3:PROCESOR
时空限制：
Time Limit: 1000MS
Memory Limit: 32768KB
题目：
给出一个数字N表示有N个32位无符号数(0到 $2^{32}-1$ )，我们可以进行如下两个操作
操作1表示把第K个数转M位（如上图）操作2表示把第K个数和第L个数进行XOR运算。 我们最初不知道这N个数的值，但我们知道每一个操作和执行后的结果，请推出每一个数最初的值。如果有多种解，输出字典序最小的。（如果第K-1个数一样，则第K个数小的则小）
输入
第一行两个正整数: N (2 ≤ N ≤ 100 000), 变量的个数。和 E (1 ≤ E ≤ 100 000), 操作的个数。 接下来E行，按执行的顺序给出每一个操作和操作后的答案。 1 ≤ K, L ≤ N, 0 ≤ M < 32). 每次操作的答案大小 0 到 $2^{32}-1$ ,二进制异或的值是按10进制给出的。
输出：
一行，N个值，表示变量最初的可能值。 如果找不到合适的方案，则输出-1。
input
3 3 2 1 2 1 2 1 3 2 2 2 3 3
output
0 1 2
input
4 6
2 4 2
3
2 4 1
6
1 3 1
2 3 1
2
1 2 2
2 2 3
7
output
5 0 14 3
input
5 6
2 4 2
10
2 5 3
2
2 2 3
1
2 1 4
3
1 3 1
2 3 4
2147483663
output
15 6 7 12 5
解析：
操作一很好处理吧，记录一个偏移量move就可以了，难的是操作二。
我们先不考虑操作一，只看操作二。
对于给定的 A、B 两个数，考虑第 i 位，XOR值是 w 。
-
w=1，说明 $A_i!=B_i$ ， 如果 $A_i=0$ ， 那么 $B_i=1$ ；如果 $A_i=1$ ， 那么 $B_i=0$ 。
-
w=0，说明 $A_i=B_i$ ， 如果 $A_i=0$ ， 那么 $B_i=0$ ；如果 $A_i=1$ ， 那么 $B_i=1$ 。
发现这个像什么——并查集，带扩展域的并查集。
那么，对于操作二的处理就明了了：
对于给定的 A、B 两个数，考虑第 i 位，XOR值是 w 。
-
w=1，说明 $A_i!=B_i$ ， $merge(A_{i0},B_{i1})$ ， $merge(A_{i1},B_{i0})$ 。
-
w=0，说明 $A_i=B_i$ ， $merge(A_{i0},B_{i0})$ ， $merge(A_{i1},B_{i1})$ 。
操作处理完了，剩下的就是统计答案。
对于当前的数 $x$ ， 考虑第 i 位：（因为字典序最小，所以 i 从大到小考虑）
定义： $f_0$ 是 0域 的根节点，$y_0$ 是 $f_0$ 对应的数。 $f_1$ 是 1域 的根节点， $y_1$ 是 $f_1$ 对应的数。
分情况讨论：
- $f_0$ 在 0域 且 $y_{0i}$ 有值，说明 $x_i=y_{0i}$ 。
- $f_0$ 在 1域 且 $y_{0i}$ 有值，说明 $x_i!=y_{0i}$ 。
- $f_1$ 在 0域 且 $y_{1i}$ 有值，说明 $x_i!=y_{1i}$ 。
- $f_1$ 在 1域 且 $y_{1i}$ 有值，说明 $x_i=y_{1i}$ 。
如果以上四种情况都不满足，说明 $x_i$ 取 0 或者 1 都可以。
为了使字典序最小，我们优先取 0 。
但只是 $x_i$ 赋值还不够，还要把 $y_0$ 和 $y_1$ 赋值。
赋值也需要分四种情况讨论，大体和上文一致，具体不做阐述。
最后需要注意的是，这道题卡空间，不得不采用一些穷凶极恶的办法卡空间。
时间复杂度： $O(32*nlogn)$ 。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int fa[N*32*2];
//0~31是0域，32~63是1域
char mp[N*32*2],move[N];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int u,int v){
fa[find(u)]=find(v);
return ;
}
int main(){
freopen("procesor.in","r",stdin);
freopen("procesor.out","w",stdout);
// ios::sync_with_stdio(false);
int op,a,b;unsigned int c;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=0;j<32;j++){
mp[(i-1)*32*2+j]=-1;
fa[(i-1)*32*2+j]=(i-1)*32*2+j;
fa[(i-1)*32*2+j+32]=(i-1)*32*2+j+32;
}
}
for(int i=1;i<=m;i++){
cin>>op>>a>>b;
if(op==1){
move[a]+=b,move[a]%=32;
}
else{
cin>>c;
for(int j=0;j<32;j++){
int u=(j+move[a])%32;
int v=(j+move[b])%32;
if(c&1){
merge((a-1)*32*2+u,(b-1)*32*2+v+32);
merge((a-1)*32*2+u+32,(b-1)*32*2+v);
}
else{
merge((a-1)*32*2+u,(b-1)*32*2+v);
merge((a-1)*32*2+u+32,(b-1)*32*2+v+32);
}
c>>=1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=31;j>=0;j--){
int f0=find(fa[(i-1)*32*2+j]);
int f1=find(fa[(i-1)*32*2+j+32]);
int p0=f0%64,p1=f1%64;
if(f0==f1){ cout<<"-1"; return 0; }
if(p0<32&&mp[f0]>=0){
mp[(i-1)*32*2+j]=mp[f0];
continue;
}
if(p0>=32&&mp[f0-32]>=0){
mp[(i-1)*32*2+j]=(mp[f0-32]^1);
continue;
}
if(p1>=32&&mp[f1-32]>=0){
mp[(i-1)*32*2+j]=mp[f1-32];
continue;
}
if(p1<32&&mp[f1]>=0){
mp[(i-1)*32*2+j]=(mp[f1]^1);
continue;
}
mp[(i-1)*32*2+j]=0;
if(p0<32) mp[f0]=0;
if(p0>=32) mp[f0-32]=1;
if(p1>=32) mp[f1-32]=0;
if(p1<32) mp[f1]=1;
}
}
for(int i=1;i<=n;i++){
unsigned int ans=0;
for(int j=0;j<32;j++)
ans|=(mp[(i-1)*32*2+j]<<j);
cout<<ans<<" ";
}
return 0;
}