cf603 div2 abcd

enmmmmmm 手速快是真的很有优势，

#include <bits/stdc++.h>
//cf603 div2
using namespace std;
#define _for(i,a,b) for(int i = (a); i < (b); i++)
#define _rep(i,a,b) for(int i = (a); i <= (b); i++)
#define ll long long

void taskA(){// 可以证明当 最大数大于其他两数之和时， ans = 其他两数之和
    // 否则 ans = （r+g+b）/2  可以用数学归纳法证明
    //https://www.cometoj.com/contest/68/problem/B?problem_id=3934 有点像之前comet做的一道题，所以很快就A了
    int t; 
    cin >> t;
    while(t--) {
        int r,g,b;
        cin >> r >> g >> b;
        if(g < b) swap(g, b);
        if(r < g) swap(r, g);
        if(r >= g+b) cout << g+b << endl;
        else cout << (g+b+r)/2 << endl;
    }return;
}
void taskB(){// n <= 10 所以可以直接枚举就好， 用两个set存下已有的pin码， 如果修改后的没有冲突就加入答案
    int t; 
    cin >> t;
    while(t--) {
        int n; cin >> n;
        set<string> AA, BB;
        vector<string> ans;
        string s[12];
        _for(i,0,n) 
        {
            cin >> s[i]; 
            AA.insert(s[i]);
        }

        int cnt1 = 0;
        _for(i,0,n) {
            if(!BB.count(s[i])) {
                    ans.push_back(s[i]);
                    BB.insert(s[i]);
                    continue;
            }
            cnt1++;
            int f = 0;
            _for(j,0,4) {
                _for(k,0,10)
                {
                    char c = '0'+k;
                    swap(s[i][j], c);
                    if(!BB.count(s[i]) && !AA.count(s[i])){
                        BB.insert(s[i]);
                        ans.push_back(s[i]);
                        f = 1;
                        break;
                    }
                    swap(s[i][j], c);
                }
                if(f) break;
            }
        }
            
        cout << cnt1 << endl;
        _for(i,0,n) cout << ans[i] << "
";

    }return;
}
void taskC(){// 还是有些迷， 没看懂题  但是看样例猜到了是  i 1~sqrt(n)，  答案为 n/i的 解
    // 用个 set ，自动排序 从小到大 美滋滋    
    int t; 
    cin >> t;
    while(t--) {
        int n; cin >> n;
        set<int> ans;
        int q = sqrt(n);
    //cout << "q = " << q << endl;
        _rep(i,0,q) ans.insert(i);

        _rep(i,1,q) ans.insert(n/i);
        cout << ans.size() << endl;
        for(auto it: ans) cout << it << " ";
        cout << endl;
    }return;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    //freopen("output.txt", "w", stdout);
    //taskA();
    //taskB();
    //taskC();
    return 0;
}

C题（看了卿学姐的视频）
还可以用二分查找，每次将 i (1~n) x=n/i 压入，然后查找等于 x 的最大下标，缩小空间代码如下

#include <bits/stdc++.h>

using namespace std;

void solve(){
    vector<int> Ans;
    int n; cin >> n;
    int x = 1;
    Ans.push_back(n);
    while(x <= n) {
        int l = x, r = n+1, ans = 1;
        int d = n/l;
        while(l <= r) {
            int mid = (l+r)/2;
            if(n/mid == d) l = mid+1, ans = mid;
            else r = mid-1;
        }
        Ans.push_back(n/(ans+1));
        x = ans+1;
    }
    sort(Ans.begin(), Ans.end());
    //Ans.erase(unique(Ans.begin(), Ans.end()), Ans.end());
    cout << Ans.size() << endl;
    for(auto to : Ans)
        cout << to << " ";
    cout << endl; return;
}

int main(){
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

View Code

D题

// 有点像联想记忆，如果两个字符串中有相同的字符那他们属于一个集合
// 遍历问有几个集合，可以用DSU 并查集也可以用题解中的二维数组

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+100;
vector<int> g[N];
vector<bool> used(N, 0);
void dfs(int i){//e俄罗斯套娃
    used[i] = 1;
    _for(j,0,g[i].size()) 
    {
        if(!used[g[i][j]]) dfs(g[i][j]);
    }return; 
}
void taskD(){
    int t;
    //cin >> t;
    t = 1;
    while(t--) {
        int n; cin >> n;
        _for(i,0,n) {
            string s; cin >> s;
            _for(j,0,s.size()) {
                int a = i, b = s[j]-'a'+n;// +n 防止和前 n 个字符串下标冲突
                g[a].push_back(b);
                g[b].push_back(a);
            }
        }
        int res = 0;
        //_for(i,n,n+26) { cout << used[i]?"1
": "0
"; }
        _for(i,n,n+26) {
            if(!used[i] && !g[i].empty())
            {
                int f = 0;
                dfs(i);
                if(!f) res++;
            }
        }
        //_for(i,n,n+26) { cout << used[i]?"1
": "0
"; }
        if(n==1) res = 1;
        cout << res << endl;
    }return;
}

int main(){
    taskD();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define F(i,a,b) for(int i = (a); i < (b); i++)
const int N = 2e5;
int fa[27+N];
int find(int x){
    return fa[x]==x? x: fa[x]=find(fa[x]);
}

int main(){
    int n; cin >> n;
    F(i,0,n+27) fa[i] = i;
    F(i,0,n) {
        string s;
        cin>>s;
        F(j,0,s.size()) { 
            fa[find(i)] = fa[find(n+s[j]-'a')];
        }
    }
    int a[27] = {}, ans = 0;
    set<int> b;

    F(i,0,n) {
        if(!b.count(find(i))) ans++, b.insert(find(i));
        //cout << "  , find(i)" << find(i) << endl;
    }
    cout << ans << endl;
    return 0;   
}