头像

Pipipapi

英雄协会




在线 


最近来访(156)
用户头像
王创
用户头像
朱柏霖
用户头像
-Acwing-
用户头像
嘉然
用户头像
小JAVA千
用户头像
ding-zk
用户头像
tryflow
用户头像
山有扶苏_0
用户头像
acwing_zfw
用户头像
AcWing_Umbrella
用户头像
陆诚
用户头像
卓杯
用户头像
艾特玖
用户头像
konkayy
用户头像
qujunyi
用户头像
湿漉漉
用户头像
滚筒洗衣机
用户头像
moreexcellent
用户头像
Aurora丶
用户头像
QL_GI


Pipipapi
12小时前

题目在这里

题目描述

屏幕截图 2021-09-26 225033.jpg

大致意思就是给你n个点n-1条边,然后依次求出每个点到其他所有点的距离和

样例

Sample Input 1 
3
1 2
2 3
Sample Output 1 
3
2
3
Sample Input 2 
2
1 2
Sample Output 2 
1
1
Sample Input 3 
6
1 6
1 5
1 3
1 4
1 2
Sample Output 3 
5
9
9
9
9
9

算法:推公式加dfs求解

O(n)

我们先求一个点的$$\sum_j^Ndist(i,j)$$
首先dfs出1的结果,记录为dist[1];
我们考察1的儿子节点s们的dist[]值会有什么区别:
对于1的儿子s和i;
如果i是不是s的儿子结点,那么 len(1,i)=len(s,i)+1;
如果i是s的结点,那么len(1,i)=len(s,i)-1;
因此我们假设所有i都不是s的儿子,那么dist[s]需要加上n(n个点),但是我们可以求出来s的儿子们的个数son[s],因此这些被多加了,原本应该减去,因此就是减去两倍,即:
$$dist[s]=dist[j]+n-s*son[s]$$

因此做法就是:
1.做一遍深搜搜出dist[1],并且记录以1为根的树的所有结点的儿子结点个数
2.再做一遍深搜,按照由近到远的顺序,先求儿子结点的答案,再递归求儿子的儿子的答案即可

C++ 代码

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

using namespace std;
//================================
#define debug(a) cout << #a": " << a << endl;
#define N 200010
//================================
typedef pair<int,int> pii;
#define x first
#define y second
typedef long long LL; typedef unsigned long long ULL; typedef long double LD;
inline LL read() { LL s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(LL x, int op = 10) { if (!x) { putchar('0'); if (op)  putchar(op); return; }  char F[40]; LL tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op) putchar(op); }
//================================= 

int n;
int e[2*N],ne[2*N],h[N],idx=0;
long long son[N],dist[N];

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

void dfs(int u,int pre,int len){
    dist[1]+=len;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==pre) continue;
        dfs(j,u,len+1);
        son[u]+=son[j];
    }
}

void dfs(int u,int pre){
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==pre) continue;
        dist[j]=dist[u]+n-2ll*son[j];
        dfs(j,u);
    }
}

//=================================
int main(){
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    for(int i=1;i<=n;i++) son[i]=1;
    dfs(1,-1,0);

    dfs(1,-1);

    for(int i=1;i<=n;i++)
        printf("%lld\n",dist[i]);

    return 0;
}


活动打卡代码 AcWing 1262. 鱼塘钓鱼

Pipipapi
20小时前
#include<bits/stdc++.h>
using namespace std;
const int M = 210;
const int N = 1010;

int n,T,m;
int f[N][N];
int a[N],t[N],sub[N],s[N],sum[N][N];

int main(){
    cin >> n;
    for(int i=1;i<=n;i++)
        cin >> a[i];
    for(int i=1;i<=n;i++)
        cin >> sub[i];
    for(int j=2;j<=n;j++)
        cin >> t[j];
    for(int i=2;i<=n;i++)
        s[i]+=s[i-1]+t[i];
    cin >> m;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            sum[i][j]=sum[i][j-1]+max(0,a[i]-(j-1)*sub[i]);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            f[i][j]=f[i-1][j-t[i]];
            if(j>=s[i]) 
                for(int k=s[i-1];k<=j-t[i];k++){
                        int tt=j-k-t[i];
                        f[i][j]=max(f[i][j],f[i-1][k]+sum[i][tt]);
                    }
        }

    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i][m]);
    cout << ans << endl;
}



#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010

int lf[N],rt[N],q[N],st[N],hh=0,f[N];
int n;

signed main(){
    while(scanf("%lld",&n),n){
        for(int i=1;i<=n;i++)
            scanf("%lld",&q[i]);
        q[0]=q[n+1]=-1;

        hh=-1;
        st[++hh]=0;
        for(int i=1;i<=n;i++){
            while(q[st[hh]]>=q[i]) hh--;
            lf[i]=i-st[hh];
            st[++hh]=i;
        }

        hh=-1;
        st[++hh]=n+1;
        for(int i=n;i;i--){
            while(q[st[hh]]>=q[i]) hh--;
            rt[i]=st[hh]-i;
            st[++hh]=i;
        }
        int ans=0;
        for(int i=1;i<=n;i++)
            ans=max(ans,q[i]*(rt[i]+lf[i]-1));
        printf("%lld\n",ans);
    }
    return 0;
}


活动打卡代码 AcWing 3990. 砍树

#include<bits/stdc++.h>

using namespace std;

#define N 100010

int n,d[N];
int e[2*N],ne[2*N],h[N],idx=0;
int ans=0;

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

int dfs(int u,int pre){
    int res=1,son=0;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==pre) continue;

        son=dfs(j,u);
        if(son%2==0) ans++;
        res+=son;
    }
    return res;
}

int main(){
    memset(h,-1,sizeof h);

    scanf("%d",&n);
    if(n&1){puts("-1");return 0;}
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
        d[a]++,d[b]++;
    }
    dfs(1,-1);
    cout << ans << endl;
    return 0;
}


活动打卡代码 LeetCode 456. 132模式

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> S;
        int second_big=-0x3f3f3f3f;

        if(nums.size()<3) return false;

        for(int i=nums.size()-1;i>=0;i--){

            if(nums[i]<second_big) return true;
            while(S.size()&&nums[i]>S.top()){
                second_big=S.top();
                S.pop();
            }
            S.push(nums[i]);
        }

        return false;
    }
};


活动打卡代码 AcWing 1497. 树的遍历

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

#define N 100010

const int M = 35;

int n,m,root;
int mid_ord[M],back_ord[M];
unordered_map<int,int> pos,l,r;

int build(int ml,int mr,int bl,int br){  //返回当前树的根
    int u=back_ord[br];
    int k=pos[u]; //找到根节点的位置
    if(ml<k) l[u] = build(ml,k-1,bl,bl+k-1-ml);
    if(mr>k) r[u] = build(k+1,mr,bl+k-ml,br-1);
    return u;
}

void bfs(int root){
    queue<int> Q;
    Q.push(root);

    while(Q.size()){
        auto u =Q.front();
        Q.pop();

        cout << u << " " ;

        if(l.count(u)){
            Q.push(l[u]);
        }
        if(r.count(u)){
            Q.push(r[u]);
        }
    }
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++)
        cin >> back_ord[i];

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

    root=build(1,n,1,n);
    bfs(root);

    return 0;
}



dfs

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */

class NestedIterator {
public:
    vector<int> q;
    int k=0;

    NestedIterator(vector<NestedInteger> &nestedList) {
        k = 0;
        for(auto &l:nestedList){
            dfs(l);
        }
    }

    void dfs(NestedInteger& l){        
        if(l.isInteger()) q.push_back(l.getInteger());
        else{
            for(auto& j:l.getList())
                dfs(j);
        }
    }

    int next() {
        return q[k++];
    }

    bool hasNext() {
        return k < q.size();
    }
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */


活动打卡代码 AcWing 276. I-区域

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

using namespace std;

const int N =16;

//状态1表示扩张,0表示收缩
int f[N][226][N][N][2][2],a[N][N],b[N][N],n,m,t,i,j,k,l,r,x,y,p,q,ans,now,ai,al,ar,ax,ay;
char cl[N][226][N][N][2][2],cr[N][226][N][N][2][2],dx[N][226][N][N][2][2],dy[N][226][N][N][2][2];

inline void update(int dat,int L,int R,int X,int Y){ //传入权值之和,左边界、右边界列号,左边界轮廓状态,右边界轮廓状态
    if(dat<f[i][j][l][r][x][y]) return ;
    f[i][j][l][r][x][y]=dat;
    //记录方案,分别是左边右边
    cl[i][j][l][r][x][y]=L,cr[i][j][l][r][x][y]=R; //分别记录上一层转移的左边界、右边界
    dx[i][j][l][r][x][y]=X,dy[i][j][l][r][x][y]=Y; //分别记录上一层转移的左边界状态。右边界状态
}

void print(int i,int j,int l,int r,int x,int y){  //递归方式记录方案
    if(!j) return;
    print(i-1,j-(r-l+1),cl[i][j][l][r][x][y],cr[i][j][l][r][x][y],dx[i][j][l][r][x][y],dy[i][j][l][r][x][y]);
    for(j=l;j<=r;j++) printf("%d %d\n",i,j);
}


int main(){
    cin >> n >> m >> t;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            b[i][j]=b[i][j-1]+a[i][j];
        }

    memset(f,0xcf,sizeof f); //0xcf直接赋值成负数

    for( i=1;i<=n;i++) //枚举行数
        for( j=1;j<=t;j++) //枚举防止的方块数
            for( l=1;l<=m;l++) //枚举左边界
                for(r=l;r<=m;r++) //枚举右边界
                { 
                    if((k=r-l+1)>j) break;
                    now=b[i][r]-b[i][l-1];
                    for( x=0;x<2;x++)
                        for(y=0;y<2;y++)
                            update(now,m,0,x,y);

                    x=y=1; //左右扩张
                    for(p=l;p<=r;p++) //枚举每一行
                        for(q=p;q<=r;q++)
                            update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1); //左右都递增只能由递增的状态转移过去

                    x=y=0; //左右收缩
                    for(p=1;p<=l;p++)
                        for(q=r;q<=m;q++){
                            update(f[i-1][j-k][p][q][0][0]+now,p,q,0,0);
                            update(f[i-1][j-k][p][q][1][0]+now,p,q,1,0);
                            update(f[i-1][j-k][p][q][0][1]+now,p,q,0,1);
                            update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
                        }

                    x=1,y=0; //左收缩右收缩
                    for(p=l;p<=r;p++)
                        for(q=r;q<=m;q++){
                            update(f[i-1][j-k][p][q][1][0]+now,p,q,1,0);
                            update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
                        }

                    x=0,y=1;
                    for(p=1;p<=l;p++)
                        for(q=l;q<=r;q++){
                            update(f[i-1][j-k][p][q][0][1]+now,p,q,0,1);
                            update(f[i-1][j-k][p][q][1][1]+now,p,q,1,1);
                        }
                }

    for(i=1;i<=n;i++)
        for(l=1;l<=m;l++)
            for(r=l;r<=m;r++)
                for(x=0;x<2;x++)
                    for(y=0;y<2;y++)
                        if(f[i][t][l][r][x][y]>ans){
                            ans=f[i][t][l][r][x][y];
                            ai=i,al=l,ar=r,ax=x,ay=y;
                        }

    cout << "Oil : " << ans << endl;
    print(ai,t,al,ar,ax,ay);

    return 0;
}



活动打卡代码 AcWing 257. 关押罪犯

相当于带权并查集

#include<bits/stdc++.h>
using namespace std;
#define N 20010
#define M 100010

int n,m;
int fa[N],oppo[N];
struct Edge{
    int a,b,v;
    bool operator<(const Edge &W){
        return W.v < v;
    }
}edge[M];

int find(int x){
    return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}

void join(int a,int b){
    a=find(a),b=find(b);
    if(a!=b){
        fa[a]=b;
    }
}

int main(){
    scanf("%d%d",&n,&m);

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

    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].v);

    sort(edge+1,edge+1+m);

    for(int i=1;i<=m+1;i++){
        int a=edge[i].a,b=edge[i].b,v=edge[i].v;
        int pa=find(a),pb=find(b);
        if(pa==pb){
            printf("%d\n",v);
            exit(0);
        }
        else{
            if(!oppo[a]) oppo[a]=b;
            else join(oppo[a],b);
            if(!oppo[b]) oppo[b]=a;
            else join(oppo[b],a);
        }
    }

    puts("0");

    return 0;
}


活动打卡代码 AcWing 503. 借教室

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

int a[N],d[N],s[N],t[N],diff[N];
int n,m;

inline bool check(int x){
    memset(diff,0,sizeof diff);
    for(int i=1;i<=x;i++)
        diff[s[i]]+=d[i],diff[t[i]+1]-=d[i];
    int need=0;
    for(int i=1;i<=n;i++){
        need+=diff[i];
        if(a[i]<need) return false;
    }
    return true;
}

int main(){
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&d[i],&s[i],&t[i]);
    }

    if(check(m)){
        puts("0");
        return 0;
    }
    int l=1,r=m;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) l=mid+1;
        else r=mid;
    }
    puts("-1");
    printf("%d\n",l);
    return 0;
}