智算之道2020第二场初赛参考代码

￡神魔★判官ぃ 2023-02-28 12:58 32阅读 0赞

# T1 #

#include <iostream>
    using namespace std;
    
    int main()
    { 
        int t;
        cin >> t;
        while(t--)
        { 
            int n, m;
            cin >> n >> m;
            int a[m + 1];
            for(int i = 1; i <= m; i++)
            { 
                cin >> a[i];
            }
    
            if(m == 3)
            { 
                cout << a[2];
            }
            else if(m == 2)
            { 
                if(n > 2)
                { 
                    if(a[2] == 2)
                    { 
                        cout << 1;
                    }
                    else if(a[1] == n - 1)
                    { 
                        cout << n;
                    }
                    else
                    { 
                        cout << -1;
                    }
                }
                else
                { 
                    cout << -1;
                }
            }
            else if(m == 1)
            { 
                if(n == 1)
                { 
                    cout << a[1];
                }
                else
                { 
                    cout << - 1;
                }
            }
            cout << endl;
        }
    
        return 0;
    }

# T2 #

## 解法一：30分代码 ##

#include <iostream>
    using namespace std;
    
    int a[27];
    
    int main()
    { 
        int n;
        cin >> n;
        for(int i = 1; i <= 26; i++)
        { 
            cin >> a[i];
        }
    
        cout << a[1] / n;
    
        return 0;
    }

## 解法二：AC代码 ##

每个字符均分到不同的字符串中，这样得到的公共前缀子串最长。

#include<bits/stdc++.h>
    #define int long long
    using namespace std;
    
    signed main()
    { 
        ios::sync_with_stdio(0);
        cin.tie(0);
        
        int n,a,ans=0;
        cin>>n;
        
        for(int i=1;i<=26;i++)
        { 
            cin>>a;
            ans+=a/n;
        }
        
        cout<<ans<<endl;
    
        return 0;
    }

# T3 #

## 解法一：20分代码 ##

#include <bits/stdc++.h>
    using namespace std;
    
    int main()
    { 
        int n, m;
        cin >> n >> m;
    
        int t, number;
        set<int> s;
        while(m--)
        { 
            cin >> t >> number;
            s.insert(number);
            cout << s.size() << endl;
        }
    
        return 0;
    }

## 解法二：AC代码 ##

#include <cstdio>
    using namespace std;
    
    const int N = 300010;
    int fa[N], vis[N], cnt[N];
    
    int find(int x)
    { 
        return x == fa[x] ? x : find(fa[x]);
    }
    
    int main()
    { 
        //freopen("T3.in", "r", stdin);
    
        int n, m;
        scanf("%d%d", &n, &m);
    
        for (int i = 1; i <= n; i++)
        { 
            fa[i] = i;
            cnt[i] = 1;
        }
    
        int op, x, y, ans = 0;
        for (int i = 0; i < m; i++)
        { 
            scanf("%d", &op);
    
            if (op == 1)
            { 
                scanf("%d", &x);
                int fx = find(x);
                if (!vis[fx])
                { 
                    ans += cnt[fx];
                    vis[fx] = true;
                }
            }
            else if (op == 2)
            { 
                scanf("%d%d", &x, &y);
                if(x == y) //如果x与y是同一个数，那么这个数是和的一半
                { 
                    int fx = find(x);
                    if (!vis[fx])
                    { 
                        ans += cnt[fx];
                        vis[fx] = true;;
                    }
                }
                else
                { 
                    int fx = find(x), fy = find(y);
                    if(fx != fy)
                    { 
                        if (!vis[fx] && vis[fy])
                        { 
                            ans += cnt[fx];
                        }
                        else if(vis[fx] && !vis[fy])
                        { 
                            ans += cnt[fy];
                            vis[fy] = true;
                        }
    
                        cnt[fy] += cnt[fx];
                        fa[fx] = fy;
                    }
                }
            }
    
            printf("%d\n", ans);
        }
    
        return 0;
    }

了解信息学竞赛请加微信307591841邀请入群