头像

我呼吸了




离线:9小时前


最近来访(86)
用户头像
Linclon
用户头像
77777777777
用户头像
AcWing2AK
用户头像
冰之韵
用户头像
怀旧经典
用户头像
ccj
用户头像
paul2008
用户头像
大雪莱
用户头像
acwing_1054
用户头像
本人和硕
用户头像
用户头像
潘潘_the_panda
用户头像
带带人家嘛
用户头像
今晚太阳不错
用户头像
coderFS
用户头像
爱驴脸爱世界
用户头像
Sweet.L
用户头像
呜噜噜
用户头像
WangJY
用户头像
slight


#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int,int> pii;

const int N = 25;

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,-1,0,1};

unordered_map<char,bool> st;
char g[N][N];
int n, m;
int cnt,res;

void dfs(int x, int y)
{
    st[g[x][y]] = true;
    cnt++;

    res = max(res,cnt);

    for(int k = 0; k < 4; k++)
    {
        int nx = x + dx[k], ny = y + dy[k];

        if(nx >= 0 && nx < n && ny >= 0 && ny < m)
        {
            if(!st[g[nx][ny]]) dfs(nx,ny);
        }
    }

    cnt--;
    st[g[x][y]] = false;
}

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

    for(int i = 0; i < n; i++) cin >> g[i];

    dfs(0,0);

    cout << res << endl;

    return 0;
}



#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int,int> pii;

const int N = 310;

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,-1,0,1};

char g[N][N];
bool st[N][N];
int d[N][N];
int n, m;
int sx, sy, gx, gy;

int bfs()
{
    memset(st,0,sizeof st);
    memset(d,0x3f,sizeof d);
    d[sx][sy] = 1;
    st[sx][sy] = true;
    queue<pii> q;
    q.push({sx,sy});

    while(q.size())
    {
        pii t = q.front();
        q.pop();

        for(int k = 0; k < 4; k++)
        {
            int nx = t.x + dx[k], ny = t.y + dy[k];

            if(nx == gx && ny == gy) return d[t.x][t.y];

            if(nx >= 0 && nx < n && ny >= 0 && ny < m)
            {
                if(!st[nx][ny] && g[nx][ny] == '.')
                {
                    q.push({nx,ny});
                    st[nx][ny] = true;
                    d[nx][ny] = d[t.x][t.y] + 1;
                    q.push({nx,ny});
                }
            }
        }
    }
    return -1;
}

int main()
{
    while(cin >> n >> m && n && m)
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                cin >> g[i][j];
                if(g[i][j] == '@') sx = i, sy = j;
                if(g[i][j] == '*') gx = i, gy = j;
            }
        }

        cout << bfs() << endl;
    }

    return 0;
}


活动打卡代码 AcWing 4420. 连通分量

#pragma GCC optimize(2)

#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = N * N;

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,-1,0,1};

int p[M],s[M];
int n, m;
char g[N][N];

int get(int x,int y)
{
    return x * m + y;
}

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void merge(int a,int b)
{
    int pa = find(a), pb = find(b);

    p[pa] = pb;
    s[pb] += s[pa];
}

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

    for(int i = 0; i < n * m; i ++) 
    {
        p[i] = i;
        s[i] = 1;
    }

    for(int i = 0; i < n; i++) cin >> g[i];

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(g[i][j] == '.')
            {
                for(int k = 0; k < 4; k++)
                {
                    int nx = i + dx[k], ny = j + dy[k];

                    if(nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == '.')
                    {
                        int a = get(i,j), b = get(nx,ny);
                        int pa = find(a), pb = find(b);

                        if(pa != pb) merge(a,b);
                    }
                }
            }
        }
    }




    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(g[i][j] == '.') cout << ".";
            else
            {
                unordered_set<int> h;
                int res = 1;

                for(int k = 0; k < 4; k++)
                {
                    int nx = i + dx[k], ny = j + dy[k];
                    if(nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == '.')
                    {
                        h.insert(find(get(nx,ny)));
                    }
                }

                for(auto t : h) res += s[t];
                cout << res % 10;

            }
        }
        cout << endl;

    }
    return 0;
}


活动打卡代码 AcWing 238. 银河英雄传说

#include <bits/stdc++.h>
using namespace std;

const int N = 30010;
int p[N],s[N],d[N];
int T;

int find(int x)
{
    if(x != p[x])
    {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}


void merge(int a,int b)
{
    int pa = find(a), pb = find(b);

    if(pa != pb)
    {
        p[pa] = pb;
        d[pa] = s[pb];
        s[pb] += s[pa];
    }
}

int main()
{
    cin >> T;

    for(int i = 0; i < N; i++)
    {
        s[i] = 1;
        p[i] = i;
    }

    char op;
    int a, b;

    while(T -- )
    {
        cin >> op >> a >> b;

        int pa = find(a), pb = find(b);

        if(op == 'M') merge(a,b);


        else 
        {
            if(pa != pb) cout << -1 << endl;
            else cout << max(0,abs(d[a]-d[b])-1) << endl;

        }
    }
    return 0;
}


活动打卡代码 AcWing 239. 奇偶游戏

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;

unordered_map<int,int> h;
int p[N],d[N];
int n, k;

int get(int x)
{
    if(!h.count(x)) h[x] = n++;
    return h[x];
}

int mod(int a, int b)
{
    return (a % b + b) % b;
}

int find(int x)
{
    if(p[x] != x)
    {
        int root = find(p[x]);
        d[x] = mod(d[x]+d[p[x]],2);
        p[x] = root;
    }
    return p[x];
}

void merge(int a,int b,int t)
{
    int pa = find(a), pb = find(b);

    d[pa] = mod(t + d[b] - d[a], 2);
    p[pa] = pb;
}

int main()
{
    cin >> n >> k;
    n = 0;

    for(int i = 0; i < N; i++) p[i] = i;

    for(int i = 1; i <= k; i++)
    {
        int a, b;
        string op;

        cin >> a >> b >> op;

        a = get(a-1), b = get(b);

        int pa = find(a), pb = find(b);



        //偶数
        if(op[0] == 'e')
        {
            if(pa != pb) merge(a, b, 0);

            else if(mod(d[a]-d[b], 2) != 0)
            {
                cout << i - 1 << endl;
                return 0;
            }
        }

        //奇数
        else
        {
            if(pa != pb) merge(a, b, 1);

            else if(mod(d[a]-d[b], 2) != 1)
            {
                cout << i - 1 << endl;
                return 0;
            }
        }
    }

    cout << k << endl;

    return 0;
}


活动打卡代码 AcWing 240. 食物链

#include <bits/stdc++.h>
using namespace std;

const int N = 50010;

int p[N],d[N];

int n, k;
int res;

int mod(int a, int b)
{
    return (a % b + b) % b;
}

int find(int x)
{
    if(p[x] != x)
    {
        int root = find(p[x]);
        d[x] = mod(d[x] + d[p[x]], 3);
        p[x] = root;
    }

    return p[x];
}

void merge(int a,int b,int t)
{
    int pa = find(a), pb = find(b);
    d[pa] = mod(t + d[b] - d[a], 3);
    p[pa] = pb;

}

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

    for(int i = 1; i <= n; i++) p[i] = i;

    for(int i = 1; i <= k; i++)
    {
        int op, a, b;

        cin >> op >> a >> b;

        if(a > n || b > n)
        {
            res ++;
            continue;
        }

        int pa = find(a), pb = find(b);

        //同类
        if(op == 1)
        {
            if(pa != pb) merge(a, b, 0);

            else if(mod(d[a]-d[b], 3) != 0) res ++;
        }

        //a吃b
        else
        {
            if(pa != pb) merge(a, b, 1);

            else if(mod(d[a]-d[b], 3) != 1) res ++;
        }
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1540. 主导颜色

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 610, M = 810;

int n, m;
ll g[N][M];
unordered_map<ll,int> h;

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

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> g[i][j];
            h[g[i][j]] ++;
        }
    }

    int maxn = -1, res = -1;

    for(auto t : h)
    {
        if(t.second > maxn)
        {
            maxn = t.second;
            res = t.first;
        }
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1531. 课程学生列表

#include <bits/stdc++.h>
using namespace std;

const int N = 40010, M = 2510;

struct Student{
    char name[100];
    int cnt;
    vector<int> CourseId;
}s[N];

struct Course{
    int cnt;
    vector<string> name;
}c[M];

int n, k;

int main()
{
    //cin >> n >> k;
    scanf("%d%d",&n,&k);

    for(int i = 0; i < n; i++)
    {
        //cin >> s[i].name >> s[i].cnt;
        scanf("%s%d",s[i].name,&s[i].cnt);
        for(int j = 0; j < s[i].cnt; j ++)
        {
            int id;
            //cin >> id;
            scanf("%d",&id);
            s[i].CourseId.push_back(id);
            c[id].cnt++;
            c[id].name.push_back(s[i].name);
        }
    }

    for(int i = 1; i <= k; i++)
    {
        //cout << i << ' ' << c[i].cnt << endl;
        printf("%d %d\n",i,c[i].cnt);
        sort(c[i].name.begin(),c[i].name.end());

        for(auto t : c[i].name)
        //cout << t << endl;
         printf("%s\n",t.c_str());
    }

    return 0;
}


活动打卡代码 AcWing 1525. 独一无二

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int a[N];
int cnt[N];

int n;

int main()
{
    cin >> n;

    int x;

    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        cnt[a[i]] ++;
    }

    int res = 0;

    for(int i = 1; i <= n; i++)
    {
        if(cnt[a[i]] == 1)
        {
            res = a[i];
            break;
        }
    }

    if(res == 0) puts("None");
    else cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 166. 数独

#include <bits/stdc++.h>
using namespace std;

const int N = 9;

int ones[1 << N], pos[1 << N];

int col[N],row[N],g[3][3];

string s;

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

int get(int i, int j)
{
    return row[i] & col[j] & g[i / 3][j / 3];
}

bool dfs(int cnt)
{
    if(cnt == 0) return true;

    int minv = 10;
    int sx, sy;

    for(int i = 0, k = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++, k++)
        {
            if(s[k] == '.')
            {
                if(ones[get(i,j)] < minv)
                {
                    minv = ones[get(i,j)];
                    sx = i;
                    sy = j;
                }
            }
        }
    }

    //从(sx,sy)开始
    for(int i = get(sx,sy); i; i -= lowbit(i))
    {

        int t = pos[lowbit(i)];

        s[sx * 9 + sy] = '1' + t;
        row[sx] -= (1 << t);
        col[sy] -= (1 << t);
        g[sx / 3][sy / 3] -= (1 << t);

        if(dfs(cnt - 1)) return true;

        g[sx / 3][sy / 3] += (1 << t);
        col[sy] += (1 << t);
        row[sx] += (1 << t);
        s[sx * 9 + sy] = '.';
    }

    return false;
}

void init()
{
    for(int i = 0; i < N; i++) col[i] = row[i] = (1 << N) - 1;

    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            g[i][j] = (1 << N) - 1;
        }
    }
}

int main()
{
    for(int i = 0; i < N; i++) pos[1 << i] = i;

    for(int i = 0; i < 1 << N; i++)
    {
        int k = 0;
        for(int j = i; j; j -= lowbit(j)) k++;
        ones[i] = k;
    }


    while(cin >> s && s[0] != 'e')
    {
        init();
        int cnt = 0;
        for(int i = 0,k = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++,k++)
            {
                if(s[k] != '.')
                {
                    int t = s[k] - '1';

                    row[i] -= (1 << t);
                    col[j] -= (1 << t);
                    g[i / 3][j / 3] -= (1 << t);

                }
                else cnt ++;
            }
        }

        dfs(cnt);

        cout << s << endl;

    }
    return 0;
}