每日一题5.27

XinyuLin

icpc2024沈阳~
The 3rd Universal Cup. Stage 19: Shenyang - 比赛主页 - 比赛 - QOJ.ac

铜牌题B或者D
B：Magical Palette - 题目 - QOJ.ac
银牌题M：Obliviate, Then Reincarnate - 题目 - QOJ.ac

XinyuLin

[C++] 纯文本查看 复制代码

铜牌题B
#include<bits/stdc++.h>
#define int long long
using namespace std;

int gcd(int x, int y) {
    if(y) return gcd(y, x % y);
    return x;
}

void solve() {
    int n, m;
    cin >> n >> m;
    if(gcd(n, m) != 1) {
        cout<<"No\n";
        return;
    } else cout<<"Yes\n";
    int M = n * m;
    for(int i=1; i<=n; i++) {
        cout<<(1 + i * m) % M <<" ";
    } 
    cout<<"\n";
    for(int i=1; i<=m; i++) {
        cout<<(1 + i * n) % M <<" ";
    }
    cout<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        solve();
    }
    return 0;
}

Fengyj

B题：

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
//1 2
//1 3 5 7
void solve(){
    int n,m;
    cin>>n>>m;
   
    if(gcd(n,m)!=1){
        cout<<"No\n";
        return;
    }
     
        vector<int>a(n+1),b(m+1);
        for(int i=1;i<=n;i++){
            a[i]=(m*(i)+1)%(n*m);
        }
        for(int i=1;i<=m;i++){
            b[i]=(n*(i)+1)%(n*m);
        }
    cout<<"Yes\n";
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" \n"[i==n];
    }
    for(int i=1;i<=m;i++){
        cout<<b[i]<<" \n"[i==m];
    }
    
 
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t=1;
    cin>>t;

    while(t--){
        solve();
    }


    return 0;
}

495684945

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;

void solve(){
	int a,b;
	cin>>a>>b;
	int temp=a*b;
	if(gcd(a,b)!=1){
		cout<<"No"<<endl;
		return ;
	}
	cout<<"Yes"<<endl;
	for(int i=1;i<=a;i++){
		cout<<(1+i*b)%temp<<" \n"[i==a];
	}
	for(int i=1;i<=b;i++){
		cout<<(1+i*a)%temp<<" \n"[i==b];
	}
}

signed main(){
	int t=1;ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)solve();
	return 0;
}

Fengyj

M：

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
#define int long long
void solve()
{
    int n, m, q;
    cin >> n >> m >> q;
 
    vector<vector<array<int, 2>>> adj(n + 1);
 
    auto mod = [&](int x)
    {
        return (x % n + n) % n;
    };
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        int A = mod(a);
        int B = mod(b);
        adj[A].push_back({mod(a + b), b});
    }
    vector<int> dfn(n + 1), low(n + 1), instk(n + 1), stk(n + 1), bel(n + 1), s(n + 1);
    int ts = 0, top = 0;
    int scccnt = 0;
    function<void(int)> tarjan = [&](int u) -> void
    {
        dfn[u] = low[u] = ++ts;
        instk[u] = 1;
        stk[++top] = u;
        for (auto [v, w] : adj[u])
        {
            if (!dfn[v])
            {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            }
            else if (instk[v])
            {
                low[u] = min(low[u], dfn[v]);
            }
        }
        
        if (dfn[u] == low[u])
        {
            scccnt++;
            int x;
            do
            {
                
                x = stk[top--];
                bel[x] = scccnt;
                s[scccnt] = x;
                instk[x] = 0;
            } while (x != u);
        }
    };
    
    for (int i = 0; i < n; i++)
    {
        if (!dfn[i])
        tarjan(i);
    }
    vector<vector<int>> scctox(scccnt + 1);
    vector<int> h(n), f(scccnt + 1), out(scccnt + 1);
    vector<int> vis(n + 1);
    int flag = 0;
    auto dfs = [&](auto &&self, int u) -> void
    {
        if(flag)
        return;
        vis[u] = 1;
        for (auto [v, w] : adj[u])
        {
            if (bel[v] != bel[u])
            continue;
            
            if (!vis[v])
            {
                h[v] = h[u] + w;
                self(self, v);
                
            }
            else
            {
                
                if (h[u] + w != h[v])
                {
                    flag = 1;
                    return;
                }
            }
        }
      
    };
    for (int i = 0; i < n;i++){
        scctox[bel[i]].push_back(i);
    }
        for (int i = 1; i <= scccnt; i++)
        {
            for(auto j:scctox[i])
                vis[j] = 0;
            flag = 0;
            vis[s[i]] = 1;
            h[s[i]] = 0;
            dfs(dfs, s[i]);
            f[i] = flag;
        }
    vector<vector<int>> nadj(scccnt + 1);
    for (int i = 0; i < n; i++)
    {
        for (auto [v, w] : adj[i])
        {
            if (bel[i] != bel[v])
            {
                nadj[bel[v]].push_back(bel[i]);
                out[bel[i]]++;
            }
        }
    }
 
    queue<int> Q;
    for (int i = 1; i <= scccnt; i++)
    {
        if (out[i] == 0)
        {
            Q.push(i);
        }
    }
    while (!Q.empty())
    {
        auto u = Q.front();
        Q.pop();
 
        for (auto v : nadj[u])
        {
            f[v] |= f[u];
            if (--out[v] == 0)
            {
                Q.push(v);
            }
        }
    }
 
    while (q--)
    {
        int x;
        cin >> x;
        x = mod(x);
        if (f[bel[x]] == 1)
        {
            cout << "Yes\n";
        }
        else
            cout << "No\n";
    }
}
 
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}