头像

wjl




离线:4个月前


活动打卡代码 AcWing 846. 树的重心

wjl
6个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int ans = N;
bool st[N];

void add_edge(int x, int y)
{
    e[idx] = y; ne[idx] = h[x]; h[x] = idx;
    idx++;
}



int n, x, y;

int dfs(int u)
{
    st[u] = true;
    int res = 0, s, sum=1;

    for (int i=h[u]; i!=-1; i=ne[i])
    {
        int j = e[i];

        if (!st[j])
        {
            st[j] = true;
            s = dfs(j);
            res = max(res, s);
            sum += s;
        }
    }

    res = max(res, n-sum);

    ans = min(ans, res);
    return sum;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n;

    memset(h, -1, sizeof(h));
    memset(st, false, sizeof(st));

    for (int i=0; i<n-1; i++)
    {
        cin>>x>>y;
        add_edge(x, y); add_edge(y, x);
    }


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


活动打卡代码 AcWing 845. 八数码

wjl
6个月前
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
string st, ed;
int depth;
int hfunc(string st) {
    int ans = 0;
    for (register int i = 0; i < st.size(); ++i) {
        if (st[i] == '0') continue;
        int j = ed.find(st[i]), r = i / 3, c = i % 3;
        int x = j / 3, y = j % 3;
        ans += abs(r - x) + abs(c - y);
    }
    return ans;
}
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
bool dfs(int now, int pre) {
    int cnt = hfunc(st);
    if (!cnt) return 1;
    if (now + cnt > depth) return 0;
    int pos = st.find('0'), x = pos / 3, y = pos % 3;
    for (register int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx > 2 || ny < 0 || ny > 2 || nx * 3 + ny == pre) continue;
        swap(st[pos], st[nx * 3 + ny]);
        if (dfs(now + 1, pos)) return 1;
        swap(st[pos], st[nx * 3 + ny]);
    }
    return 0;
}
int main() {
    for (register int i = 1; i <= 9; ++i) {
        char s[2];
        scanf("%s", s);
        st += s[0] == 'x' ? '0' : s[0];
    }
    int cnt = 0;
    for (register int i = 0; i < st.size(); ++i)
        if (st[i] != '0')
            for (register int j = 0; j < i; ++j)
                if (st[j] != '0') cnt += st[i] > st[j];
    if (cnt & 1) {
        puts("-1");
        return 0;
    }
    ed = "123456780";
    for (depth = hfunc(st); !dfs(0, -1); ++depth);
    cout << depth;
}



活动打卡代码 AcWing 844. 走迷宫

wjl
6个月前
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 107;
int g[N][N], d[N][N];


queue<PII> q;

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

int bfs()
{
    PII node;
    q.push({0,0});
    while(!q.empty())
    {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i=0; i<4; i++)
        {
            int x1 = x + dx[i], y1 = y + dy[i];
            if (x1>=0 & x1<n && y1>=0 && y1<m && d[x1][y1]==-1 && g[x1][y1]==0)
            {
                d[x1][y1] = d[x][y] + 1;
                q.push({x1, y1});
            }
        }
    }

    return d[n-1][m-1];
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>m;

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

    memset(d, -1, sizeof(d));
    cout<<bfs()+1<<endl;

}


活动打卡代码 AcWing 843. n-皇后问题

wjl
6个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 11;

int n;
char output[N][N];

bool col[N], dg[2*N], udg[2*N];

void dfs(int u)
{
    if (u>n)
    {
        for (int i=1; i<=n; i++)
        {
            for (int j=1; j<=n; j++)
                cout<<output[i][j];
            cout<<endl;
        }
        cout<<endl;

        return;
    }

    for (int i=1; i<=n; i++)
     if(!col[i] && !dg[u+i] && !udg[n+u-i])
     {
         col[i]=true; dg[u+i]=true; udg[n+u-i]=true;
         output[u][i]='Q';
         dfs(u+1);
         col[i]=false; dg[u+i]=false; udg[n+u-i]=false;
         output[u][i]='.';
     }
}

int main()
{
    cin>>n;
    for (int i=1; i<=n; i++)
    for (int j=1; j<=n; j++)
        output[i][j] = '.';    

    dfs(1);

    return 0;
}


活动打卡代码 AcWing 842. 排列数字

wjl
6个月前
#include<iostream>
using namespace std;

const int N = 8;
int path[N];
bool st[N];
int n;

void dfs(int u)
{
    if (u==n)
    {
        for (int i=1; i<=n; i++)
            cout<<path[i]<<" ";
        cout<<endl;
        return;
    }

    for (int i=1; i<=n; i++)
        if (!st[i])
        {
            st[i]=true;
            path[u+1]=i;
            dfs(u+1);
            st[i]=false;
        }
}

int main()
{
    cin>>n;
    dfs(0);
    return 0;
}


活动打卡代码 AcWing 841. 字符串哈希

wjl
6个月前
#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
const int N = 1E5 + 10;
int pp = 131;
ULL h[N], p[N];
ULL geth(int l, int r)
{
    return h[r] - h[l-1]*p[r-l+1];
}

int main()
{
    std::ios::sync_with_stdio(false);
    int n,m,l1,r1,l2,r2;
    string str;
    cin>>n>>m;
    cin>>str;

    p[0] = 1;
    for (int i=1; i<=n; i++) 
    {
        p[i]=p[i-1]*pp;
        h[i]=h[i-1]*pp + str[i-1]; 
    }

    while(m--)
    {
        cin>>l1>>r1>>l2>>r2;
        if (geth(l1,r1)==geth(l2,r2)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }

}


活动打卡代码 AcWing 840. 模拟散列表

wjl
6个月前
#include<bits/stdc++.h>
using namespace std;

unordered_map<int, int> h;
int n;
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n;
    char ch; 
    int x;
    while(n--)
    {
        cin>>ch>>x;
        if (ch=='I')
        {
            h[x] = 1;
        }else
        {
            if (h.find(x)==h.end()) cout<<"No"<<endl;
            else cout<<"Yes"<<endl;
        }
    }
}


活动打卡代码 AcWing 839. 模拟堆

wjl
6个月前
#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+10;
int h[N];   //堆
int ph[N];  //存放第k个插入点的下标
int hp[N];  //存放堆中点的插入次序
int cur_size;   //size 记录的是堆当前的数据多少

//这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
//从而我们需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换 
//h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void heap_swap(int u,int v)
{   
    swap(h[u],h[v]); 
     swap(hp[u],hp[v]);     
     swap(ph[hp[u]],ph[hp[v]]);            

}

void down(int u)
{
    int t=u;
    if(u*2<=cur_size&&h[t]>h[u*2]) t=u*2;
    if(u*2+1<=cur_size&&h[t]>h[u*2+1])  t=u*2+1;
    if(u!=t)
    {
        heap_swap(u,t);
        down(t);
    }
}
void up(int u)
{
    if(u/2>0&&h[u]<h[u/2]) 
    {
        heap_swap(u,u/2);
        up(u>>1);
    }
}

int main()
{
    int n;
    cin>>n;
    int m=0;      //m用来记录插入的数的个数
                //注意m的意义与cur_size是不同的 cur_size是记录堆中当前数据的多少
                //对应上文 m即是hp中应该存的值
    while(n--)
    {
        string op;
        int k,x;
        cin>>op;
        if(op=="I")
        {
            cin>>x;
            m++;
            h[++cur_size]=x;
            ph[m]=cur_size;
            hp[cur_size]=m;
            //down(size);
            up(cur_size);
        }
        else if(op=="PM")    cout<<h[1]<<endl;
        else if(op=="DM")
        {
            heap_swap(1,cur_size);
            cur_size--;
            down(1);
        }
        else if(op=="D")
        {
            cin>>k;
            int u=ph[k];                //这里一定要用u=ph[k]保存第k个插入点的下标
            heap_swap(u,cur_size);          //因为在此处heap_swap操作后ph[k]的值已经发生 
            cur_size--;                    //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
            up(u);
           down(u);
        }
        else if(op=="C")
        {
            cin>>k>>x;
            h[ph[k]]=x;                 //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以
            down(ph[k]);                //所以可直接传入ph[k]作为参数
            up(ph[k]);
        }

    }
    return 0;
}



活动打卡代码 AcWing 838. 堆排序

wjl
6个月前
#include<bits/stdc++.h>
using namespace std;

priority_queue<int, vector<int> > q;

int n,m,x;

int main()
{
    std::ios::sync_with_stdio(false);

    cin>>n>>m;
    for (int i=0; i<n; i++)
    {
        cin>>x;
        if (q.size()<m) q.push(x);
        else
        {
            if (q.top()>x)
            {
                q.pop();
                q.push(x);
            }
        }
    }

    vector<int> res;
    while(!q.empty()) 
    {
        res.push_back(q.top());
        q.pop();
    }

    int len = res.size();
    for (int i=len-1; i>=0; i--)
    cout << res[i] <<" ";
}


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

wjl
6个月前
// CreateTime: 2019-11-10 15:54:36
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>

using namespace std;

int n;
int k;

int D;
int x;
int y;

const int N = 5e4 + 10;
const int M = 3;

int parent[N];
int d[N];

void init() {
    for (int i = 0; i <= n; i++) {
        parent[i] = i;
        d[i] = 0;
    }
}

int find(int x) {
    if (x != parent[x]) {
        int oldParent = parent[x];
        parent[x] = find(parent[x]);
        d[x] = (d[x] + d[oldParent]) % M;
    }
    return parent[x];
}

bool D1(int x, int y) {
    int p1 = find(x);
    int p2 = find(y);

    // 如果 x 和 y 已经处理过了
    if (p1 == p2) {
        return d[x] % M == d[y] % M;
    }

    parent[p2] = p1;
    d[p2] = ((d[x] - d[y]) + M) % M;
    return true;
}

bool D2(int x, int y) {
    int p1 = find(x);
    int p2 = find(y);

    // 如果 x 和 y 已经处理过了
    if (p1 == p2) {
        return d[x] % M == (d[y]+1) % M;
    }

    parent[p2] = p1;
    d[p2] = ((d[x]-d[y]-1) + M) % M;
    return true;
}

int main(void) {
    int res = 0;

    cin >> n;
    init();

    cin >> k;
    while (k--) {
        cin >> D >> x >> y;
        if (x > n || y > n) {
            res += 1;
        } else {
            if (D == 1) {
                if (D1(x, y) == false) {
                    res += 1;
                }
            }
            if (D == 2) {
                if (D2(x, y) == false) {
                    res += 1;
                }
            }
        }
    }

    cout << res << endl;

    return 0;
}