头像

ox_xo




离线:8天前


最近来访(18)
用户头像
Passer
用户头像
失败尽常态
用户头像
小胖熊
用户头像
辣辣溜溜梅
用户头像
up_79
用户头像
Zoiwen
用户头像
星辰带海带
用户头像
吁鱼羽御
用户头像
小妹妹送我的郎啊
用户头像
jzz2002
用户头像
努力刷leetcode
用户头像
Dylan_0

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

ox_xo
4个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
const int M = 2*N;

int h[N]; //邻接表存储树,有n个节点,所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入,n个节点
int ans = N; //表示重心的所有的子树中,最大的子树的结点数目

bool st[N]; //记录是否被访问,访问过则标记为true



////a所对应的单链表中插入b  a作为根 
void add(int a, int b)
{
    e[idx] = b ; ne[idx] = h[a]; h[a] = idx++;
}


//返回以u为根节点的子树中的个数,包括u节点
int dfs(int u) 
{
    int sum = 1;//当前节点
    int res = 0; //表示删掉某个节点后,最大的连通子块
    st[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            int s = dfs(j);
            res = max(s,res);//记录最大联通子图的节点数
            sum += s; //记录了以j为节点的树的节点数

        }

    }

     res = max(res, n-sum);
     ans = min(ans, res);

    return sum;

}
int main()
{
    memset(h,-1,sizeof h); //初始化数组,-1表示尾节点
    cin >> n ;

    for(int i = 0 ; i<n-1; i ++ )
    {
        int a,b;

        cin >> a >> b;
        add(a,b), add(b,a); //无向图
    }

    dfs(1);

    cout << ans << endl;


    return 0;
}


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

ox_xo
5个月前
#include <bits/stdc++.h>
#define  x first
#define  y second
using namespace std;
int n,m;
const int N = 110;
int g[N][N],d[N][N];
int ans;


typedef pair<int, int > PII;

PII q[N*N];

int bfs()
{
    int hh = 0 , tt = 0;
    q[0]={0,0};
    memset(d , -1 ,sizeof d);

    d[0][0] = 0; //表示走过{0,0}点了 从0 开始计算

    //偏移量
    int dx[]={-1,0,1,0}, dy[] ={0,-1,0,1};

    while(hh<=tt)
    {
        auto t = q[hh++];//取队头 hh++细节

        for(int i = 0; i<4; i++)
        {
            int x = t.x + dx[i] , y = t.y+dy[i];
            if( x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                q[++tt] = {x,y}; // ++tt 细节
                d[x][y] = d[t.x][t.y] + 1;
            }
        }

    }

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


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

    cout << bfs() << endl;

    return 0;
}


活动打卡代码 AcWing 4400. 玩游戏

ox_xo
5个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int a[N];

int n,m;


int main()
{
    queue<int> q;

    cin >> n >> m ;

    for(int i=1; i<=n; i++)
    {
        q.push(i);
    }
     for(int i=0; i<m; i++)
    {
            int a ;
            cin >> a;
            a %= q.size();
         for(int i=0; i<a; i++)
         {
             q.push(q.front());//妙a
             q.pop();
         }

       cout << q.front() << " ";
       q.pop();//记得干掉
    }

    return 0;
}


活动打卡代码 AcWing 830. 单调栈

ox_xo
6个月前
#include <iostream>
using namespace std;
const int N = 100010;
int stk[N], tt;

int n;



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

    while(n--)
    {


        cin >> x;

        while( tt && stk[tt] >= x ) 
                tt--;

        if(!tt) cout<< "-1" << " ";
        else cout << stk[tt] << " ";

        stk[++tt] = x;

    }


    return 0;

}


活动打卡代码 AcWing 3302. 表达式求值

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

stack<int> num;
stack<char> op;
string s ;

unordered_map<char,int> h={
    {
        '+',1
    },
    {
        '-',1
    },
    {
        '*',2
    },
    {
        '/',2
    }
};

void eval()//求值
{
    int a = num.top();//第二个操作数
    num.pop();

    int b = num.top();//第一个操作数
    num.pop();

    char p = op.top();//运算符
    op.pop();

    int r = 0;//结果 

    //计算结果
    if (p == '+') r = b + a;
    if (p == '-') r = b - a;
    if (p == '*') r = b * a;
    if (p == '/') r = b / a;

    num.push(r);//结果入栈


}



int main()
{   
    cin >> s;
     for (int i = 0; i < s.size(); i++)
    {
        if (isdigit(s[i]))//数字入栈
        {
            int x = 0, j = i;//计算数字
            while (j < s.size() && isdigit(s[j]))
            {
                x = x * 10 + s[j] - '0';
                j++;
            }
            num.push(x);//数字入栈
            i = j - 1;
        }
        //左括号无优先级,直接入栈
        else if (s[i] == '(')//左括号入栈
        {
            op.push(s[i]);
        }
        //括号特殊,遇到左括号直接入栈,遇到右括号计算括号里面的
        else if (s[i] == ')')//右括号
        {
            while(op.top() != '(')//一直计算到左括号
                eval();
            op.pop();//左括号出栈
        }
        else
        {
            while (op.size() && h[op.top()] >= h[s[i]])//待入栈运算符优先级低,则先计算
                eval();
            op.push(s[i]);//操作符入栈
        }
    }
    while (op.size()) eval();//剩余的进行计算
    cout << num.top() << endl;//输出结果
    return 0;

}


活动打卡代码 AcWing 828. 模拟栈

ox_xo
6个月前
#include <bits/stdc++.h>

using namespace std;

const int N  = 100010;

// tt表示栈顶
int stk[N], tt = 0;
int m;

int main()
{
    cin >> m;
    while(m--)
    {
        string s;
        int x;
        cin >> s;
        if( s == "push"){
            cin >> x;
            // 向栈顶插入一个数
           stk[ ++ tt] = x;
        }

        if( s == "pop"){
           // 从栈顶弹出一个数
            tt -- ;
        }

        if( s == "query"){
           // 从栈顶弹出一个数
            cout << stk[tt] << endl;
        }

        if( s == "empty"){
           // 
            if(!tt)
            cout<<"YES"<<endl;
            else
            cout<<"NO"<<endl;


        }
    }
    return 0;
}


活动打卡代码 AcWing 826. 单链表

ox_xo
6个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int m;

int head, e[N], ne[N], idx;

//初始化
void init()
{
    head = -1;
    idx = 0;
}

//在链表头插入一个数
void add(int a)
{
    e[idx] = a, ne[idx] = head, head = idx , idx++;
}

//在链表中插入一个数
void insert(int k, int x)
{
    int id = k-1;
    e[idx] = x, ne[idx] = ne[id],  ne[id] = idx, idx++;
}

//将k后的结点删除
void remove(int k)
{
    int id = k-1;
    ne[id] = ne[ne[id]];
}

int main()
{
    cin >> m;
    init();
    while(m--)
    {
       char op;
       cin >> op ;
       if( op == 'H')
       {
           int x;
           cin >> x;
           add(x);
       }

       if( op == 'D')
       {
           int k;
           cin >> k;
           if( !k ) head = ne[head];
           else remove(k);
       }

        if( op == 'I')
       {
           int k,x;
           cin >> k >> x;
           insert(k,x);
       }

    }

    for(int i = head ; i != -1; i = ne[i] ) cout << e[i] << " ";

    return 0;
}


活动打卡代码 AcWing 1671. 三角形

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

#define x first
#define y second
const int N = 150;
#define PII pair<int, int> 
vector<PII> a;
int n,ans;

int main()
{
    cin >> n;
    for(int i = 0 ; i<n; i++ )
    {
        int x1,y1;
        cin >> x1 >> y1 ;
        a.push_back({x1,y1});
        // cout <<a[i].x<<a[i].y<<endl;
        // cout <<a.size() <<endl;
    }

    //看了高赞题解才知道判断三角形能不能构成,太菜了
    for(int i = 0 ; i<n ; i++ )
    {
        for(int j = 0 ; j<n; j++ )
        {
            for(int k = 0 ; k<n; k++ )
            {
                if(i==j || i==k || j==k ) continue;
                if( a[i].x==a[j].x && a[i].y == a[k].y )
                {
                    ans = max(ans, abs( (a[i].y-a[j].y) * (a[i].x-a[k].x)   ) );//注意每次都是用i点去减其他两个点
                }
            }
        }

    }

    cout << ans << endl;

    return 0;
}



ox_xo
6个月前
#include <bits/stdc++.h>

using namespace std;

int n;

int lowbit(int x)
{
    return x&(-x);
}
int main()
{
    cin >> n;
    while(n--)
    {
        int x ;
        cin >> x;
        int res = 0;
        while(x){
            x -= lowbit(x);
            res++;
        }
        cout<<res<<" ";
    }
    return 0;

}


活动打卡代码 AcWing 802. 区间和

ox_xo
6个月前

``````

include [HTML_REMOVED]

using namespace std;

typedef pair[HTML_REMOVED] PLL;

const int N = 300010;
int a[N],s[N];
vector[HTML_REMOVED] alls;
vector[HTML_REMOVED] adds,query;
int n,m;

// 二分求出x对应的离散化的值
int find(int x)// 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while( l < r)
{
int mid = (l + r) >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1 ;

}

return r+1; // 映射到1, 2, ...n

}

int main()
{
cin >> n >> m;
while(n–)
{
int x,r;
cin >> x >> r;
adds.push_back({x,r});

    alls.push_back(x);
}

for(int i = 0; i<m; i++)
{
    int l,r;
    cin >> l >> r;
    query.push_back({l,r});

    alls.push_back(l);
    alls.push_back(r);

}

//  去掉重复元素
sort(alls.begin(),alls.end() );
alls.erase(unique(alls.begin(), alls.end()), alls.end());

//处理插入
for( auto item : adds)
{
    int x = find(item.first);
    a[x] +=  item.second;
}

//预处理前缀和
for(int i = 1 ; i <= alls.size() ; i++ )
{
    s[i] = s[i-1] + a[i];
}

for( auto item : query)
{
    int l = find(item.first) , r = find(item.second);
    cout << s[r] - s[l-1] <<endl;

}

return 0;

}