头像

Moon_light

西安电子科技大学


访客:6253

在线 



Moon_light
3分钟前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    map<int,int> h;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        //前序遍历 : 中 左 右   
        //中序遍历 : 左 右 中
        //所以前序遍历中的点对应到中序遍历的位置,左侧是其左分支,右侧是其右分支
        int n = preorder.size();
        for(int i = 0; i<n; i++) h[inorder[i]] = i;
        return dfs(preorder,inorder,0,n-1,0,n-1);
    }
    TreeNode* dfs(vector<int>& pre,vector<int>& inorder,int pl,int pr,int il,int ir){
        if(pl > pr) return NULL;
        int val = pre[pl];  //根节点的值
        int id = h[val];   //根节点在中序遍历中的位置
        int len = id - il;  
        auto root = new TreeNode(val);
        root->left = dfs(pre,inorder,pl+1,pl+len,il,id-1);
        root->right = dfs(pre,inorder,pl+len+1,pr,id+1,ir);
        return root;
    }
};



Moon_light
54分钟前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> q;

        vector<vector<int>> ans;
        if(!root) return ans;
        q.push(root);
        int f = 0;  //t = 0从左向右, t = 1从右向左
        while(!q.empty()){
            int j = q.size();
            vector<int> t;

            while(j--){
                auto u = q.front();
                q.pop();
                if(u->left) q.push(u->left);
                if(u->right) q.push(u->right);
                t.push_back(u->val);
            }
            if(f==0){
                ans.push_back(t);
                f ^= 1;
            }else{
                reverse(t.begin(),t.end());
                ans.push_back(t);
                f ^= 1;
            }
        }
        return ans;
    }
};


活动打卡代码 LeetCode 101. 对称二叉树

Moon_light
1小时前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return dfs(root->left, root->right);
    }
    bool dfs(TreeNode* a, TreeNode* b)
    {
        if(!a || !b) return !a&&!b;
        return a->val == b->val && dfs(a->left,b->right) && dfs(a->right,b->left);
    }
};


活动打卡代码 AcWing 1275. 最大数

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+100;

struct{
    int l,r;
    int v;  //区间l,r的最大值
}tr[N*4];    //空间开成区间长度的四倍

int m,p,cnt;

//由子节点来更新父节点的信息
void pushup(int u){
    tr[u].v = max(tr[u<<1].v,tr[u<<1|1].v);
}

void build(int u,int l,int r){
    tr[u] = {l,r};
    if(l == r)return ;  //叶子节点
    int mid = (l+r) >> 1;
    build(u<<1,l,mid);     
    build(u<<1|1,mid+1,r);
}

int query(int u,int l,int r){
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].v;

    int mid = (tr[u].l+tr[u].r)>>1;
    int res = 0;
    if(l <= mid) res = query(u<<1,l,r);
    if(r > mid) res = max(res,query(u<<1|1,l,r));
    return res;
}

//单点修改,将x上的值修改为value
void modify(int u,int x,int value){
    if(tr[u].l == x && tr[u].r == x) tr[u].v = value;
    else{
        int mid = (tr[u].l+tr[u].r) >> 1;
        if(x <= mid) modify(u<<1,x,value);
        else modify(u<<1|1,x,value);
        pushup(u);
    }
}
int main()
{
    scanf("%d%d",&m,&p);
    build(1,1,m);
    int last,t;
    while(m--){
        char op[2];
        scanf("%s",op);
        if(op[0] == 'A'){
            scanf("%d",&t);
            modify(1,cnt+1,(last+t)%p);
            cnt++;
        }else{
            scanf("%d",&t);
            last = query(1,cnt-t+1,cnt);
            printf("%d\n",last);
            // last = t;
        }
    }

    return 0;
}


活动打卡代码 AcWing 1185. 单词游戏

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int T,n;
const int N = 30;

int p[N];
bool st[N];
int din[N],dout[N];

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

int main()
{
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        memset(st,0,sizeof st);
        memset(din,0,sizeof din);
        memset(dout,0,sizeof dout);

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

        for(int i = 0;i<n; i++){
            string s;
            cin>>s;
            int a = s[0]-'a', b = s[s.length()-1]-'a';
            st[a] = st[b] = true;  //表示这个字母用到了
            p[find(a)] = find(b);
            din[b] ++;
            dout[a] ++;
        }

        int s = 0,ed = 0;
        bool flag = true;
        for(int i = 0; i<26; i++){
            if(din[i] != dout[i]){
                if(din[i] == dout[i] + 1) ed++;
                else if(din[i] + 1 == dout[i]) s++;
                else{
                    flag = false;
                    break;
                }
            }
        }

        if(flag && !(!s && !ed || s == 1 && ed == 1)) flag = false;

        int res = -1;
        for(int i = 0; i<26; i++){
            if(!st[i]) continue;
            if(res == -1) res = find(i);
            else{
                if(res != find(i)){
                    flag = false;
                    break;
                }
            }
        }
        if(!flag){
            puts("The door cannot be opened.");
        }
        else puts("Ordering is possible.");
    }
    return 0;
}


活动打卡代码 AcWing 1124. 骑马修栅栏

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 520, M = 4000;

int g[N][N];
int F;
int ans[M],cnt;
int d[N];



void dfs(int u){
    for(int i = 1; i<=500; i++){
        if(g[u][i]){
            g[u][i]--;
            g[i][u]--;
            dfs(i);
        }   
    }
    ans[cnt++] = u;
}
int main()
{
    cin>>F;

    for(int i = 0; i<F; i++){
        int a,b;
        cin>>a>>b;
        g[a][b] ++;
        g[b][a] ++;
        d[a] ++;
        d[b] ++;
    }

    int s = 1;
    while(d[s] == 0) s++;
    for(int i = 1; i<=500; i++){
        if(d[i]&1){
            s = i;
            break;
        }
    }
    dfs(s);
    for(int i = cnt-1; i>=0; i--){
        cout<<ans[i]<<'\n';
    }
    return 0;
}



欧拉通路与欧拉回路

欧拉通路: 对于图G来说,如果存在一条通路包含G中所有的边,则该通路成为欧拉通路,也称欧拉路径。
欧拉回路: 如果欧拉路径是一条回路,那么称其为欧拉回路。
欧拉图 : 含有欧拉回路的图是欧拉图。

对有无向图G和有向图H:

图G存在欧拉路径与欧拉回路的充要条件分别是:
欧拉路径: 图中所有奇度点的数量为0或2。
欧拉回路: 图中所有点的度数都是偶数。


图H存在欧拉路径和欧拉回路的充要条件分别是:
欧拉路径: 所有点的入度等于出度 或者 存在一点出度比入度大1(起点),一点入度比出度大1(终点),其他点的入度均等于出度。
欧拉回路:所有点的入度等于出度。

下面根据这道题目记录求欧拉回路的方法:

题目描述

给定一张图,请你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。

输入格式

第一行包含一个整数 t,t∈{1,2},如果 t=1,表示所给图为无向图,如果 t=2,表示所给图为有向图。

第二行包含两个整数 n,m,表示图的结点数和边数。

接下来 m 行中,第 i 行两个整数 vi,ui,表示第 i 条边(从 1 开始编号)。

如果 t=1 则表示 vi 到 ui 有一条无向边。
如果 t=2 则表示 vi 到 ui 有一条有向边。
图中可能有重边也可能有自环。

点的编号从 1 到 n。

数据范围

$1≤n≤10^5,$
$0≤m≤2×10^5$

样例

输入
1
3 3
1 2
2 3
1 3

输出
YES
1 2 -3

算法Dfs

根据欧拉回路判断的充要条件,可以判定一个图是否是欧拉图,之后,我们可以利用dfs来找到一条欧拉回路:

以无向图为例,因为每个点的度都为偶数,所以我们从任意一个点出发,假设所有点的度数都为2,那么dfs一定会回到起点,从而形成一个回路(如果度数都为2,那么现在就是一条欧拉回路),假设度数不全为2,有4,6,8...那么在dfs过程中,当走到这些点(假设走到点u)上时,可能会走到其他环上,但是由于度数是偶数,所以如果走到其他环上,最后也会回到点u,在dfs过后,一定会形成许多环,环与环之间有一个交点(在图中两个环可能有两个交点,但在dfs过程中只会选择一条边去走,所以这个”交点”的意义要分清楚),在回溯过程中将这些点添加到答案中,就是一条欧拉回路。
有向图同理。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100100, M = 400100;

int h[N],e[M],ne[M],idx;
int ans[N*2],cnt;
bool used[M];
int din[N],dout[N];
int n,m,ver;

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void dfs(int u){
    for(int &i = h[u]; ~i; ){
        if(used[i]){  //如果这条边用过了
            i = ne[i];   //删除这条边
            continue;
        }

        used[i] = true;  //标记这条边已使用
        if(ver == 1) used[i^1] = true;   //如果是无向图,那么这条边的反向边也要标记使用过了

        int t;
        if(ver == 1){
            t = i/2 + 1;
            if(i&1) t = -t;  //(0,1) (2,3) (4,5) 奇数编号是返回的边

        }else t = i+1;

        int j = e[i];
        i = ne[i];
        dfs(j);
        ans[cnt++] = t;
    }
}
int main()
{
    scanf("%d%d%d",&ver,&n,&m);
    memset(h,-1,sizeof h);

    for(int i = 0; i<m; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        if(ver == 1) add(b,a);  //无向边
        din[b]++, dout[a]++;   
    }

    if(ver == 1){
        for(int i = 1; i<=n; i++){
            if(din[i]+dout[i] &1){
                //无向图含欧拉回路的充要条件是每个点的度都为偶数
                puts("NO");
                return 0;
            }
        }
    }else{
        for(int i = 1; i<=n; i++){
            if(din[i] != dout[i]){
                //有向图含欧拉回路的充要条件是每个点的入度等于出度
                puts("NO");
                return 0;
            }
        }
    }

    for(int i = 1; i<=n; i++){
        if(~h[i]) {
            dfs(i);
            break;
        }
    }

    if(cnt < m){
        puts("NO");
        return 0;
    }

    puts("YES");
    for(int i = cnt-1; i>=0; --i){
        cout<<ans[i]<<" ";
    }
    return 0;
}



活动打卡代码 AcWing 1184. 欧拉回路

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100100, M = 400100;

int h[N],e[M],ne[M],idx;
int ans[N*2],cnt;
bool used[M];
int din[N],dout[N];
int n,m,ver;

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void dfs(int u){
    for(int &i = h[u]; ~i; ){
        if(used[i]){
            i = ne[i];
            continue;
        }

        used[i] = true;
        if(ver == 1) used[i^1] = true;

        int t;
        if(ver == 1){
            t = i/2 + 1;
            if(i&1) t = -t;  //(0,1) (2,3) (4,5) 奇数编号是返回的边

        }else t = i+1;

        int j = e[i];
        i = ne[i];
        dfs(j);
        ans[cnt++] = t;
    }
}
int main()
{
    scanf("%d%d%d",&ver,&n,&m);
    memset(h,-1,sizeof h);

    for(int i = 0; i<m; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        if(ver == 1) add(b,a);  //无向边
        din[b]++, dout[a]++;   
    }

    if(ver == 1){
        for(int i = 1; i<=n; i++){
            if(din[i]+dout[i] &1){
                //无向图含欧拉回路的充要条件是每个点的度都为偶数
                puts("NO");
                return 0;
            }
        }
    }else{
        for(int i = 1; i<=n; i++){
            if(din[i] != dout[i]){
                //有向图含欧拉回路的充要条件是每个点的入度等于出度
                puts("NO");
                return 0;
            }
        }
    }

    for(int i = 1; i<=n; i++){
        if(~h[i]) {
            dfs(i);
            break;
        }
    }

    if(cnt < m){
        puts("NO");
        return 0;
    }

    puts("YES");
    for(int i = cnt-1; i>=0; --i){
        cout<<ans[i]<<" ";
    }
    return 0;
}


活动打卡代码 AcWing 1123. 铲雪车

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

int main()
{
    double x1,x2,y1,y2;
    cin>>x1>>x2;

    double s = 0;
    while(cin>>x1>>y1>>x2>>y2){
        double dx = x1-x2;
        double dy = y1-y2;
        s += sqrt(dx*dx + dy*dy)*2;
    }

    int m = round(s/1000/20*60);
    int h = m/60;
    m %= 60;

    printf("%d:%02d\n",h,m);
    return 0;
}



题目描述

给定一张N个点M条边的有向无环图,分别统计从每个点出发能够到达的点的数量。

数据范围

$1≤N,M≤30000$

样例

输入
10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9

输出
1
6
3
3
2
1
1
1
1
1

算法1

将这个图进行拓扑排序后,从拓扑排序数组从后向前遍历,对于每个点t来说,假设其存在两个出边ab,那么:
ans(t) = ans(e[a]) + ans(e[b]), 考虑状态表示的问题,如果使用bool数组(数组要开到N)表示某个点可以到达哪些点,因为要遍历所有边,
所以时间复杂度是O(N*M),是行不通的,而STL为我们提供了一个工具-bitset bitset百科

状态表示dp[i] 表示点i可以到达的所有点组成的二进制数,设1号点可以到2号点3号点, 那么dp[1] = 1110;
状态转移dp[i] |= dp[j]; //i->j

时间复杂度

这里,bitset每次操作时间复杂度为N/32,所以是对上述中bool数组那一块的优化,$O(N*M/32)$

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>

using namespace std;
typedef pair<int,int> PII;

const int N = 30010;

int h[N],e[N],ne[N],idx;
int q[N];
int din[N];
int n,m;
//int dp[N];
//map<PII,bool> uu;
bitset<N> dp[N];

void add(int a,int b){
    e[idx] = b,ne[idx] = h[a], h[a] = idx++;
}

void topsort(){
    int hh = 0, tt = -1;

    for(int i = 1; i<=n; i++){
        if(din[i] == 0){
            q[++tt] = i;
        }
    }
    while(hh<=tt){
        int t = q[hh++];

        for(int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if(--din[j]==0) q[++tt] = j;
        }
    }
}

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

    memset(h,-1,sizeof h);

    while(m--){
        int a,b;
        cin>>a>>b;
        //if(uu[{a,b}]) continue;
        add(a,b);
        //uu[{a,b}] = true;
        din[b]++;
    }

    topsort();


    for(int i = n-1; i>=0; i--){
        int t = q[i];
        dp[t][t] = 1;
        for(int j = h[t]; ~j; j = ne[j]){
            //cout<<e[j]<<" ";
            dp[t] |= dp[e[j]];
        }
        //cout<<endl;
    }
    for(int i = 1; i<=n; i++) cout<<dp[i].count()<<'\n';
    return 0;
}