题解：P12414 「YLLOI-R1-T3」一路向北

TJB_LHY · 2025-07-29 14:58:25 · 题解

这是一篇暴力题解！

思路

我们直接考虑模拟操作的过程，先枚举在哪里放，然后直接模拟每次操作的过程，如果很久都没有拿到 0，那说不定就是在循环了。那我们要操作多少次，答案才是正确的呢？若能将 0 取出，我们最多只用先取出其他的 n\times m 个数，重新放入队列中，因为我们不会把数放在 0 前面。反之，0 就取不出来了。是不是很神奇？？？

#include<bits/stdc++.h>
#define FOR(i,u) for(ll i=G.head[u];i;i=G.nex[i])
#define lc (d<<1)
#define rc (d<<1|1)
#define ll long long
#define C const
using namespace std;
void read(int &x) {
    x=0;
    char y=getchar_unlocked();
    bool flag=0;
    while(y<'0' || y>'9') {
        if(y=='-')flag=1;
        y=getchar_unlocked();
    }
    while((y>='0' && y<='9')) {
        x=(x<<1)+(x<<3)+(y-'0');
        y=getchar_unlocked();
    }
    if(flag)x=-x;
}
void write(int x) {
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(x<10)putchar(x+'0');
    else {
        write(x/10);
        putchar(x%10+'0');
    }
}
int t,n,m,a,id,cnt[100005];
bool flag;
queue<int>Q[100005];
bool check(int id){
    Q[id].push(0);
    int i=m*n,k;
    while(i--){
        k=Q[id].front();
        Q[id].pop();
        if(k==0)return 0;
        id=k;
        Q[id].push(k);
    }
    return 1;//模拟 
}
void run(){
    for(int i=1;i<=n;i++){
        if(check(i)){
            puts("Yes");
            return;
        }
    }
    puts("No");//输出 
    return;
}
signed main() {
    read(t);
    while(t--){
        read(n);read(m);
        flag=1;
        for(int i=1;i<=n;i++){
            while(Q[i].size())Q[i].pop();
            for(int j=1;j<=m;j++){
                read(a);
                Q[i].push(a);
            }
        }
        run();
    }
    return 0;
}

自信提交：听取 WA 声一片。为什么呢？我们会发现有一种情况：操作 n\times m 次后，0 还在对头，所以我们多操作一次就可以快乐的 AC 了。时间复杂度为 O(tn^2m)。足以通过此题。

#include<bits/stdc++.h>
#define FOR(i,u) for(ll i=G.head[u];i;i=G.nex[i])
#define lc (d<<1)
#define rc (d<<1|1)
#define ll long long
#define C const
using namespace std;
void read(int &x) {
    x=0;
    char y=getchar_unlocked();
    bool flag=0;
    while(y<'0' || y>'9') {
        if(y=='-')flag=1;
        y=getchar_unlocked();
    }
    while((y>='0' && y<='9')) {
        x=(x<<1)+(x<<3)+(y-'0');
        y=getchar_unlocked();
    }
    if(flag)x=-x;
}
void write(int x) {
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(x<10)putchar(x+'0');
    else {
        write(x/10);
        putchar(x%10+'0');
    }
}//快读快写
int t,n,m,a,id;
queue<int>Q[100005];
bool check(int id){
    Q[id].push(0);
    int i=m*n+1,k;
    while(i--){
        k=Q[id].front();
        Q[id].pop();
        if(k==0)return 0;
        id=k;
        Q[id].push(k);
    }
    return 1;//模拟 
}
void run(){
    for(int i=1;i<=n;i++){
        if(check(i)){
            puts("Yes");
            return;
        }
    }
    puts("No");//输出 
    return;
}
signed main() {
    read(t);
    while(t--){
        read(n);read(m);
        for(int i=1;i<=n;i++){
            while(Q[i].size())Q[i].pop();//多测清空！！！
            for(int j=1;j<=m;j++){
                read(a);
                Q[i].push(a);//入队
            }
        }
        run();
    }
    return 0;
}

完结撒花！