MDRC#1赛时答疑帖 & 赛后总结帖
2026-09-09 07:32:46
发布于：广东
303阅读
0回复
0点赞
本帖为 MDRC#1 赛时答疑帖& 赛后总结帖。
MDRC#1（邀请码：QrHf）
题解奖：发布的题解能获得终极主宰大神的认可即可获得本团队永久竞赛出题人或本团队任选一个职业一个月。
双平台同步开赛，可同时参赛：
- ZDZL OJ 平台：MDRC#1
- ACGO 平台：MDRC#1（邀请码：QrHf）
赛时答疑：
感谢各位参加本次比赛，关于题目有关的任何问题可以在本帖下回复。
若在比赛期间，您发现存在影响比赛的情况（如重题、样例出错等）请立即联系终极主宰大神，请勿公开讨论！
选手不允许在赛时发布无意义内容，不允许发布有关任何对比赛题目有提示性的内容。
提问前应仔细审读题目，并查看是否有人已经问过了您的问题，不允许刷屏。
在比赛开始至比赛结束的时间内，我们不允许您灌水，否则将会剥夺您获得奖励的机会。
赛时播报：
666居然退榜了
笑死😂赛况全是Lin.Zikang
最后一题很简单吗？？？那可是紫啊？？？咋这么多人过？？？
2026/8/15：
比赛提前开始了
666 Lin.Zikang在4小时内AK了，也是首AK的
赛况：
| 题目 | 用户名 |
|---|---|
| 4.FB | Lin.Zikang |
| 5.FB | Lin.Zikang |
| 首AK | Lin.Zikang |
| 1st | Lin.Zikang |
注：
首 AK：第一个完成所有题目（All Kill）。
FB：第一个完成单道题目（First Blood）。
获奖名单：
ACGO：
图例：
①AK选手 可自行选择1个团队的三年的管理员1个团队的一年的副队长或1个空白团队。
②第一~第二的人可选1个团队的半年的副队长或1个团队的一年的管理员 或 让 终极主宰大神 新创建一个团队并给选手较高的权限。
③第三~第五的人选手可自行选择本团队的三个月的管理员或 本团队的一个月的副队长或 终极主宰大神 新创建一个团队并给选手中等的权限 或让 终极主宰大神 给你永久关注 。
④题解奖：发布的题解能获得终极主宰大神的认可即可获得本团队永久竞赛出题人或本团队任选一个职业一个月。
| 用户 | 奖项(序号见上方图例) |
|---|---|
| Lin.Zikang | ①和② |
| cjj | ② |
| 𝓔𝓣𝓗𝓐𝓝 | ③ |
| 水林Watrest | ③ |
| Deepest欠揍 最深度的欠揍 | ③ |
ACGO作弊名单：
| 用户· | 作弊情况 |
|---|---|
| 徐梓轶 | 作弊 |
| 天之神_Ax·巅峰._S | 作弊 |
作弊用户可以在10月1日前申诉
MDRC#1题解：
T1：MDRC的注册验证
判断用户名是否合法：长度6到20、只能含小写字母/数字/下划线、必须以字母开头。按顺序检查三个条件，有一个不满足直接输出NO，全满足输出YES。
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int n=s.size();
if(n<6||n>20){
cout<<"NO"<<endl;
return 0;
}
if(!(s[0]>='a'&&s[0]<='z')){
cout<<"NO"<<endl;
return 0;
}
for(int i=0;i<n;i++){
if(!((s[i]>='a'&&s[i]<='z')||(s[i]>='0'&&s[i]<='9')||s[i]=='_')){
cout<<"NO"<<endl;
return 0;
}
}
cout<<"YES"<<endl;
return 0;
}
T2：MDRC 排名计算
结构体存编号和总分，总分=三题得分之和。按总分降序、第1题得分降序、编号升序排序，输出第一个。
#include<bits/stdc++.h>
using namespace std;
struct node{
int id,a,b,c,sum;
}a[1005];
bool cmp(node x,node y){
if(x.sum!=y.sum)return x.sum>y.sum;
if(x.a!=y.a)return x.a>y.a;
return x.id<y.id;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
a[i].id=i;
cin>>a[i].a>>a[i].b>>a[i].c;
a[i].sum=a[i].a+a[i].b+a[i].c;
}
sort(a+1,a+n+1,cmp);
cout<<a[1].id<<" "<<a[1].sum<<endl;
return 0;
}
T3：MDRC的树上路径统计
每次查询从 和 两个点同时往上跳，深度大的先跳，把经过的点的权值加入答案，直到两个点相遇。路径上的点权全部异或起来就是答案。修改直接把 改成 。
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,m,w[N],fa[N][20],dep[N],dfn[N],sz[N],tot;
long long bit[N],val[N];
vector<int>g[N];
void dfs(int u,int f){
fa[u][0]=f;
dep[u]=dep[f]+1;
dfn[u]=++tot;
sz[u]=1;
val[u]=val[f]^w[u];
for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:g[u]){
if(v==f)continue;
dfs(v,u);
sz[u]+=sz[v];
}
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=19;i>=0;i--){
if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
}
if(u==v)return u;
for(int i=19;i>=0;i--){
if(fa[u][i]!=fa[v][i]){
u=fa[u][i];
v=fa[v][i];
}
}
return fa[u][0];
}
void add(int x,long long v){
for(;x<=n;x+=x&-x)bit[x]^=v;
}
long long ask(int x){
long long res=0;
for(;x;x-=x&-x)res^=bit[x];
return res;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;i++){
add(dfn[i],val[i]);
add(dfn[i]+sz[i],val[i]);
}
while(m--){
int op,u,v;
cin>>op>>u>>v;
if(op==1){
int l=lca(u,v);
cout<<(ask(dfn[u])^ask(dfn[v])^w[l])<<endl;
}else{
long long delta=val[u]^v;
w[u]=v;
val[u]=v;
add(dfn[u],delta);
add(dfn[u]+sz[u],delta);
}
}
return 0;
}
T4：MDRC的动态图连通性
暴力 DFS。每次添加/删除边直接在邻接表中修改，查询时从 开始 DFS 看能否到达 。
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,q;
vector<int>g[N];
bool vis[N];
bool dfs(int u,int target){
if(u==target)return true;
vis[u]=true;
for(int v:g[u]){
if(!vis[v]&&dfs(v,target))return true;
}
return false;
}
int main(){
cin>>n>>m>>q;
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
while(q--){
int op,u,v;
cin>>op>>u>>v;
if(op==1){
g[u].push_back(v);
g[v].push_back(u);
}else if(op==2){
for(auto it=g[u].begin();it!=g[u].end();it++){
if(*it==v){
g[u].erase(it);
break;
}
}
for(auto it=g[v].begin();it!=g[v].end();it++){
if(*it==u){
g[v].erase(it);
break;
}
}
}else{
memset(vis,0,sizeof(vis));
cout<<(dfs(u,v)?"YES":"NO")<<endl;
}
}
return 0;
}
T5：MDRC的密码锁
AC自动机 + 矩阵快速幂。用 AC自动机建 Trie 图并标记危险节点，构建转移矩阵 表示从状态 走一步到状态 的方案数，矩阵快速幂求走 L 步的总方案数，累加不经过危险节点的方案数。
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=55;
struct Mat{
long long a[MAXN][MAXN];
int n;
Mat(int _n=0){
n=_n;
memset(a,0,sizeof(a));
}
Mat operator*(const Mat&x)const{
Mat res(n);
for(int i=0;i<n;i++){
for(int k=0;k<n;k++){
if(a[i][k]){
for(int j=0;j<n;j++){
res.a[i][j]=(res.a[i][j]+a[i][k]*x.a[k][j])%MOD;
}
}
}
}
return res;
}
};
Mat qpow(Mat base,long long exp){
Mat res(base.n);
for(int i=0;i<base.n;i++)res.a[i][i]=1;
while(exp){
if(exp&1)res=res*base;
base=base*base;
exp>>=1;
}
return res;
}
int ch[MAXN][10],fail[MAXN],en[MAXN],tot;
int main(){
long long L;
int k;
cin>>L>>k;
for(int i=0;i<k;i++){
string s;
cin>>s;
int u=0;
for(int j=0;j<s.size();j++){
int v=s[j]-'0';
if(!ch[u][v])ch[u][v]=++tot;
u=ch[u][v];
}
en[u]=1;
}
queue<int>q;
for(int i=0;i<10;i++){
if(ch[0][i])q.push(ch[0][i]);
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<10;i++){
if(ch[u][i]){
fail[ch[u][i]]=ch[fail[u]][i];
en[ch[u][i]]|=en[fail[ch[u][i]]];
q.push(ch[u][i]);
}else{
ch[u][i]=ch[fail[u]][i];
}
}
}
Mat trans(tot+1);
for(int i=0;i<=tot;i++){
if(en[i])continue;
for(int c=0;c<10;c++){
int v=ch[i][c];
if(!en[v]){
trans.a[i][v]=(trans.a[i][v]+1)%MOD;
}
}
}
Mat res=qpow(trans,L);
long long ans=0;
for(int i=0;i<=tot;i++){
if(!en[i]){
ans=(ans+res.a[0][i])%MOD;
}
}
cout<<ans<<endl;
return 0;
}
赛后总结：
ACGO：本次比赛共 35 人报名，10 人提交，10 人有分。
ZDZLOJ：·······
AK 人数 1 人。
感谢各位选手参加 MDRC#1。
统计信息未排除作弊者。
| 题号 | 难度 | 分值 | 通过人数 | 通过率 | 预期情况 |
|---|---|---|---|---|---|
| T1 | 入门 | 100 | 9 | 90% | 略高于预期 |
| T2 | 普及 | 140 | 6 | 60% | 略低于预期 |
| T3 | 普及+/提高 | 190 | 1 | 10% | 低于预期 |
| T4 | 提高 | 250 | 2 | 20% | 略高于预期 |
| T5 | 省选/NOI− | 320 | 3 | 30% | 高于预期 |
欢迎加入大师主宰级团队
大家要多多点赞啊！！！
有帮助，赞一个