M32_模拟赛总结

# 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)$ 。 ### 代码： ```cpp #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)$ 。 ### 代码： ```cpp #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 。 1. w=1，说明 $A_i!=B_i$ ， 如果 $A_i=0$ ， 那么 $B_i=1$ ；如果 $A_i=1$ ， 那么 $B_i=0$ 。 2. w=0，说明 $A_i=B_i$ ， 如果 $A_i=0$ ， 那么 $B_i=0$ ；如果 $A_i=1$ ， 那么 $B_i=1$ 。 发现这个像什么——并查集，带扩展域的并查集。 那么，对于操作二的处理就明了了： 对于给定的 A、B 两个数，考虑第 i 位，XOR值是 w 。 1. w=1，说明 $A_i!=B_i$ ， $merge(A_{i0},B_{i1})$ ， $merge(A_{i1},B_{i0})$ 。 2. 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$ 对应的数。 分情况讨论： 1. $f_0$ 在 0域 且 $y_{0i}$ 有值，说明 $x_i=y_{0i}$ 。 2. $f_0$ 在 1域 且 $y_{0i}$ 有值，说明 $x_i!=y_{0i}$ 。 3. $f_1$ 在 0域 且 $y_{1i}$ 有值，说明 $x_i!=y_{1i}$ 。 4. $f_1$ 在 1域 且 $y_{1i}$ 有值，说明 $x_i=y_{1i}$ 。 如果以上四种情况都不满足，说明 $x_i$ 取 0 或者 1 都可以。 为了使字典序最小，我们优先取 0 。 但只是 $x_i$ 赋值还不够，还要把 $y_0$ 和 $y_1$ 赋值。 赋值也需要分四种情况讨论，大体和上文一致，具体不做阐述。 最后需要注意的是，这道题卡空间，不得不采用一些~~穷凶极恶的~~办法卡空间。 时间复杂度： $O(32*nlogn)$ 。 ### 代码： ```cpp #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; } ```