MMOI Round 2 题目总结
2026-07-06 12:19:03
发布于：重庆
前言 & 闲话
比赛质量还行，但是出了很多搞笑的状况，比如 T3 的空间莫名其妙变成了 2048MB，大概是4点多吧，反正我打的时候准备看 T3 的时候来了个提示说 T3 空间限制修改了。
莫名其妙，而且有一个比较好玩的情节。
不会重复提及某题题意，请自行观看。
T1
红，没什么好说的，注意一张饼需要操作 次，同时有 面需要操作，答案就是 。
懒得给代码。
T2
构造可能有点创人，但是我觉得还好。这个扩展有一个特性：加入一个格子水域周长不会增多。原因很显然，因为规则中指出格子四联通周围有两格及以上才会扩展，一个格子就四边。最好的情况相当于有两面接壤，然后有两面补上了原来接壤的那个空缺，周长不变。
然后我们发现最终状态整个网格都被填满，水域边长为 。也就是说答案的下界一定是 ，相当于一个格子周长为 。下界也不难得到，构造如下：
-
在左上角 上方的 和 放水，把这块区域填满。（出题人巧思不错，这就是 MC 里面无限水的做法）
-
然后我们发现可以隔着两个放一桶，比如填满列就填充 ，这样我们可以让第一行都被填满，第一列同理。
-
然后我们发现此时整个过程相当于说逐渐从边缘扩展，逐步的水会扩展每个格子。
还有一些特殊情况，这样的方案无法覆盖到末短是奇数格子的情况。比如 为奇数时，格 就无法被覆盖到，此时加进去就可以了，如果 是奇数同理。需要注意的是，当 均为奇数时只需要填充 即可，不然会有冗余。从这里也可以看出构造是严格达到下界的。
时间复杂度 ，总体而言还行。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define mkp make_pair
const int N=2e2+5;
int cid,t,n,m;
char a[N][N];
void work(){
cin >> n >> m;
for(int i = 1;i <= n;i++)for(int j = 1;j <=m;j++)a[i][j]='0';
a[1][2]=a[2][1]='1';
for(int i = 4;i <= n;i+=2)a[i][1]='1';
for(int i =4;i <= m;i+=2)a[1][i]='1';
if((n&1)&&(m&1))a[n][m]='1';
else if(n&1)a[n][1]='1';
else if(m&1)a[1][m]='1';
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++)cout << a[i][j];
cout << "\n";
}
}
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> cid >> t;
while(t--)work();
return 0;
}
这是这位同学你 @消失的AC与写不完的UKE 要的代码。
下次记得晚点发hhh。
T3
有点意思，这是一个比较新颖的题，但其实也比较简单。首先其他数出现两次这个性质启示我们想办法对这些数作区分，一个运算能很好的体现这个区分性：异或。
因为 ，原序列的异或和就是要求的那两个数 的异或值 。并且我们发现 至少有一位非零，因为 。然后此刻某一位为 的意思就是这两个数二进制下这一位不同，随便找到一个为 的位，如果 针对这一位为 的再做异或就可以得到 的某一个，然后再和 异或一次就得到两组解了。
到正解其实和 没什么区别，二进制位一共就 位左右，每次读入的时候开一个大小为 的数组 表示第 位为 的所有数的异或和，然后直接查表就可以了。
时间复杂度 ，空间复杂度 。当时是写了个模拟过的（2G空间），后面觉得有点不地道然后写了个正解，反正场上两种都过了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128
#define mkp make_pair
int cid,t,n,d,p[61],ansx,ansy,sum;
void work(){
cin >> n >> d;sum=0;
memset(p,0,sizeof(p));
for(int i = 1,x;i <= n;i++){
cin >> x;sum^=x;
for(int j = 0;j <= 60;j++)
if(x&(1ll<<j))
p[j]^=x;
}
if(d==2){
for(int i = 1,x;i <= n;i++)cin >>x;
}int id = 0;
for(int i = 0;i <= 60;i++){
if(sum&(1ll<<i)){
id=i;
break;
}
}ansx=p[id],ansy=sum^ansx;
if(ansx>ansy)swap(ansx,ansy);
cout << ansx << " " << ansy << "\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> cid >> t;
while(t--)work();
return 0;
}
T4
思考了 10 分钟，有一个细节有点意思，其他没什么难度。
首先一个经典的观察是每个数最多经历过 次开根操作就变成 了，所以这一部分是可以对每个数暴力做的。然后观察数变成 后的特殊性质：
-
如果目前操作是 ，那开根后向下取整还是 。
-
如果目前操作是 ，那直接就是 。
同时， 怎么操作都一定会变成 ，所以每个数最终的归宿 或 可以批量维护，我们只在意个数。如果操作是 就没影响，否则就交换 和 的个数。查询就是 的个数加上其他数的和。
重点是合并操作，由于这个 太大了不能直接启发式合并，但其实有一个很聪明的方法规避暴力合并：使用链表维护所有大于 的数，再做合并。（开头提到的有点意思的点）
链表合并的方式很简单，记录链表的头指针和尾指针，合并时把一边的尾指针的后继改成一边的头指针就行了。这个过程时间复杂度是 的，然后很经典的用并查集维护集合。
处理开根操作的时候遍历链表，每个数暴力处理，更新总和并且看看操作后能否规约到 。这一点可以使用两个变量维护头指针和尾指针，具体实现看代码，没什么好说的。
开根反而是时限瓶颈，这里卡常使用了一个值域分治技巧，如果数 查表即可，这一点可以简单预处理。默认开根为 则总时间复杂度为 。
const int N=1e7+5;
int c,n,q,a[N],maxn=1e7,siz[N],f[N],head[N],tail[N],tot,cnt[N][2],d[N];
long long sum[N];
struct Point{
int nxt,val;
}e[N];
void init(){
for(int i = 1;i*i <= maxn;i++)d[i*i]=i;
for(int i = 1;i <= maxn;i++)if(!d[i])d[i]=d[i-1];
for(int i = 1;i <= n;i++){
f[i]=i,siz[i]=1;
if(a[i]>1){
sum[i]=a[i];
e[++tot].val=a[i],head[i]=tail[i]=tot;
}
else cnt[i][a[i]]++;
}
}
int getf(int u){
if(f[u]==u)return u;
return f[u]=getf(f[u]);
}
void merge(int x,int y){
x=getf(x),y=getf(y);
if(x==y)return;
if(siz[x]<siz[y])swap(x,y);
siz[x]+=siz[y],f[y]=x;
cnt[x][0]+=cnt[y][0],cnt[x][1]+=cnt[y][1];sum[x]+=sum[y];
if(head[y]){//实际这样实现是什么意味呢
//因为x可能是空的，里面的数都规约到了0/1，然后不如先把x接到y后面，然后把x的头指针改成y的头指针
//然后如果x不存在尾指针就可以直接复制y的，如果你直接把y接到x后面需要注意x不存在，需要写两个case
//不过也行，我写代码就是当时想实现就写了，可能比较猎奇。
e[tail[y]].nxt=head[x];
head[x]=head[y];
if(!tail[x])tail[x]=tail[y];
}
}
void update(int x,int y){
x=getf(x);
if(y==1)swap(cnt[x][0],cnt[x][1]);
int fx=0,fy=0;//维护指针用，实际就是动态看首和尾，遇到变成0/1的数不加就是了
for(int i = head[x];i;){
int lt=e[i].nxt;
sum[x]-=e[i].val;
int val = abs(e[i].val-y);//撤销
if(val<=maxn)e[i].val=d[val];//<=1e7查表
else e[i].val=sqrt(val);//直接开根
if(e[i].val<=1){//更新
cnt[x][e[i].val]++;
}else{
sum[x]+=e[i].val;//更新和
if(!fx)fx=fy=i;
else e[fy].nxt=i,fy=i;
}i=lt;
}if(fy)e[fy].nxt=0;
head[x]=fx,tail[x]=fy;
}
long long query(int x){
x=getf(x);
return cnt[x][1]+sum[x];
}
有帮助，赞一个