#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int vis[10];
int a[10];
int b[10];
int ans;
int answer;
int sum;
void bfs2(int cnt) {

    sum++;
    queue<int> q;
    q.push(cnt);
    vis[cnt] = 1;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        if (t == 1) {
            if (a[6] == 1&&!vis[6]) {
                q.push(6);
                vis[6] = 1;
            }
            if (a[2] == 1&&!vis[2]) {
                q.push(2);
                vis[2] = 1;
            }
        }
        else if (t == 2) {
            if (a[1] == 1 && !vis[1]) {
                q.push(1);
                vis[1] = 1;
            }
             if (a[3] == 1 && !vis[3]) {
                q.push(3);
                vis[3] = 1;
            }
             if (a[7] == 1 && !vis[7]) {
                q.push(7);
                vis[7] = 1;
            }
        }
        else if (t == 3) {
            if (a[2] == 1 && !vis[2]) {
                q.push(2);
                vis[2] = 1;
            }
             if (a[7] == 1 && !vis[7]) {
                q.push(7);
                vis[7] = 1;
            }
             if (a[4] == 1 && !vis[4]) {
                q.push(4);
                vis[4] = 1;
            }
        }
        else if (t == 4) {
            if (a[3] == 1 && !vis[3]) {
                q.push(3);
                vis[3] = 1;
            }
             if (a[5] == 1 && !vis[5]) {
                q.push(5);
                vis[5] = 1;
            }
        }
        else if (t == 5) {
            if (a[4] == 1 && !vis[4]) {
                q.push(4);
                vis[4] = 1;
            }
             if (a[7] == 1 && !vis[7]) {
                q.push(7);
                vis[7] = 1;
            }
             if (a[6] == 1 && !vis[6]) {
                q.push(6);
                vis[6] = 1;
            }
        }
        else if (t == 6) {
            if (a[5] == 1 && !vis[5]) {
                q.push(5);
                vis[5] = 1;
            }
             if (a[7] == 1 && !vis[7]) {
                q.push(7);
                vis[7] = 1;
            }
             if (a[1] == 1 && !vis[1]) {
                q.push(1);
                vis[1] = 1;
            }
        }
        else if (t == 7) {
            if (a[5] == 1 && !vis[5]) {
                q.push(5);
                vis[5] = 1;
            }
             if (a[2] == 1 && !vis[2]) {
                q.push(2);
                vis[2] = 1;
            }
             if (a[3] == 1 && !vis[3]) {
                q.push(3);
                vis[3] = 1;
            }
             if (a[6] == 1 && !vis[6]) {
                q.push(6);
                vis[6] = 1;
            }
        }
    }
    return;

}
void dfs(int num) {

    if (num > 7) {
        ans++;
        sum = 0;
        memset(vis, 0, sizeof(vis));
        memset(b, 0, sizeof(b));
        for (int i = 1; i <= 7; i++) {
            if(a[i]==1&&!vis[i])
                bfs2(i);
        }
        for (int i = 1; i <= 7; i++) {
            cout << a[i];
        }
        cout << ' ';
        cout << sum << endl;
        if (sum == 1) {
            answer++;
            //cout << answer << endl;
        }
        return;
    }
    a[num] = 1;
    dfs(num + 1);
    a[num] = 0;

    a[num] = 0;
    dfs(num + 1);
    a[num] = 1;

    return;
}
int main()
{

    dfs(1);
    cout << answer<< endl;
    return 0;
}

自己用set写的过了百分之70

单链表并查集 真的很简单

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1e5 + 10;
int p[N];
int n;
int find(int x) {
    if (x != p[x])
        p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin >> n;
    for (int i = 1; i < N; i++) {
        p[i] = i;
    }
    for (int i = 1; i <=n; i++) {
        int x;
        cin >> x;
        x = find(x);
        cout << x << ' ';
        p[x] = x + 1;
    }
    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 110, M = 1 << 20;

int n, m, k;
vector<int> col[N];
int log2[M];

int lowbit(int x)
{
    return x & -x;
}

int h(int state)  // 最少需要再选几行
{
    int res = 0;
    for (int i = (1 << m) - 1 - state; i; i -= lowbit(i))
    {
        int c = log2[lowbit(i)];
        res ++ ;
        for (auto row : col[c]) i &= ~row;
    }
    return res;
}

bool dfs(int depth, int state)
{
    if (!depth || h(state) > depth) return state == (1 << m) - 1;

    // 找到选择性最少的一列
    int t = -1;
    for (int i = (1 << m) - 1 - state; i; i -= lowbit(i))
    {
        int c = log2[lowbit(i)];
        if (t == -1 || col[t].size() > col[c].size())
            t = c;
    }

    // 枚举选哪行
    for (auto row : col[t])
        if (dfs(depth - 1, state | row))
            return true;

    return false;
}

int main()
{
    cin >> n >> m >> k;

    for (int i = 0; i < m; i ++ ) log2[1 << i] = i;
    for (int i = 0; i < n; i ++ )
    {
        int state = 0;
        for (int j = 0; j < k; j ++ )
        {
            int c;
            cin >> c;
            state |= 1 << c - 1;
        }

        for (int j = 0; j < m; j ++ )
            if (state >> j & 1)
                col[j].push_back(state);
    }

    int depth = 0;
    while (depth <= m && !dfs(depth, 0)) depth ++ ;

    if (depth > m) depth = -1;
    cout << depth << endl;

    return 0;
}

很巧妙的一题dfs
之前写dfs自己一定要用参数 如位置 步数等
这题用参数反而写不出来 不用参数更加容易理解

#include<bits/stdc++.h>
using namespace std;
string s;
int k;
int dfs()
{
    int res = 0;
    while (k < s.size()) {
        if (s[k] == '(') {
            k++;//跳过(
            res+=dfs();
            k++;//跳过 )
        }
        else if (s[k] == '|') {
            k++;//跳过 |
            res = max(res, dfs());
        }
        else if (s[k] == ')') {
            return res;
        }
        else {
            res++;
            k++;
        }
    }
    return res;
}
int main()
{
    cin >> s;
    cout << dfs() << endl;

    return 0;
}

很巧妙的一题dfs
之前写dfs自己一定要用参数 如位置 步数等
这题用参数反而写不出来 不用参数更加容易理解

#include<bits/stdc++.h>
using namespace std;
string s;
int k;
int dfs()
{
    int res = 0;
    while (k < s.size()) {
        if (s[k] == '(') {
            k++;//跳过(
            res+=dfs();
            k++;//跳过 )
        }
        else if (s[k] == '|') {
            k++;//跳过 |
            res = max(res, dfs());
        }
        else if (s[k] == ')') {
            return res;
        }
        else {
            res++;
            k++;
        }
    }
    return res;
}
int main()
{
    cin >> s;
    cout << dfs() << endl;

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL& x, LL& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    LL a, b, c, k;
    while (cin >> a >> b >> c >> k, a || b || c || k) {
        LL x, y;
        LL z = 1ll << k;
        LL d = exgcd(c, z, x, y);
        if ((b - a) % d)
            cout << "FOREVER" << endl;
        else {
            x *= (b - a) / d;
            z /= d;
            cout << (x % z + z) % z << endl;
        }
    }


    return 0;
}

学习到了辗转相减法(更相减损术)
可以用来求指数类型的最大公约数 ，分子分母分别求
最终可以得到N次方根的最简形式

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
typedef long long LL;
LL a[N],b[N],c[N];
int n;

LL gcd(LL a, LL b) {
    if (b) {
        gcd(b, a % b);
    }
    else return a;
}
LL gcd_sub(LL a, LL b) {
    if (a < b)
        swap(a, b);
    if (b == 1)return a;
    else gcd_sub(b, a / b);
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i - 1]) {
            LL d = gcd(a[i], a[0]);
            b[cnt] = a[i] / d;
            c[cnt] = a[0] / d;
            cnt++;
        }
    }
    LL up = b[0], down = c[0];
    for (int i = 1; i < cnt; i++) {
        up = gcd_sub(up, b[i]);
        down = gcd_sub(down, c[i]);
    }

    cout << up << '/' << down << endl;
    return 0;
}

学习到了辗转相除法(更相减损术)
可以用来求指数类型的最大公约数 ，分子分母分别求
最终可以得到N次方根的最简形式

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
typedef long long LL;
LL a[N],b[N],c[N];
int n;

LL gcd(LL a, LL b) {
    if (b) {
        gcd(b, a % b);
    }
    else return a;
}
LL gcd_sub(LL a, LL b) {
    if (a < b)
        swap(a, b);
    if (b == 1)return a;
    else gcd_sub(b, a / b);
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i - 1]) {
            LL d = gcd(a[i], a[0]);
            b[cnt] = a[i] / d;
            c[cnt] = a[0] / d;
            cnt++;
        }
    }
    LL up = b[0], down = c[0];
    for (int i = 1; i < cnt; i++) {
        up = gcd_sub(up, b[i]);
        down = gcd_sub(down, c[i]);
    }

    cout << up << '/' << down << endl;
    return 0;
}

自己写的暴搜 可以过百分之60

#include<bits/stdc++.h>
using namespace std;
int n, d, x, y;
const int N=1e7+10;
int vis[N];
int ans;
int dfs(int nowx,int foot){
    vis[nowx]=1;
    if(nowx==y){
        return foot;
    }
    if(nowx+d>n-1){
        if(!vis[d-(n-1-nowx)-1])
            dfs(d-(n-1-nowx)-1,foot+1);

        else return -1;
    }
    else{
        if(!vis[nowx+d]){
            dfs(nowx+d,foot+1);
        }
        else return -1;
    }    
}
int main()
{
    int t;
    cin >> t;
    while (t--) {
        memset(vis,0,sizeof(vis));
        cin >> n >> d >> x >> y;
        ans=0;
        ans=dfs(x,0);
        //int cnt = 0;
        //bool flag = false;
        //int nowx = x;
        if(ans==-1){
            cout<<"Impossible"<<endl;
        }
        else cout << ans << endl;

    }

    return 0;
}

Y总扩展欧几里得

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL& x, LL& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    int T;
    cin >> T;
    while (T--) {
        LL n, d, x, y, a, b;
        cin >> n >> d >> x >> y;
        int gcd = exgcd(n, d, a, b);
        if ((y - x) % gcd)
            puts("Impossible");
        else {
            b *= (y - x) / gcd;
            n /= gcd;
            cout << (b % n + n) % n << endl;
        }
    }

    return 0;
}