首页 > 其他分享 >AtCoder Beginner Contest 378 ——F

AtCoder Beginner Contest 378 ——F

时间:2024-11-07 15:58:06浏览次数:4  
标签:AtCoder Beginner atcoder int 378 abc378 contests find define

https://atcoder.jp/contests/abc378/tasks/abc378_f
https://atcoder.jp/contests/abc378/editorial/11307

#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define lowbit(x) (x)&-(x)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int N=2e5+10,mod=1e9+7;
ll n,m,k;
int u[N],v[N],d[N],p[N],cnt[N];
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
void unit(int a,int b){
    a=find(a),b=find(b);
    p[a]=b;
}
void solve(){
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>u[i]>>v[i];
        d[u[i]]++,d[v[i]]++;
    }
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<n;i++){
        if(d[u[i]]==d[v[i]]&&d[u[i]]==3) unit(u[i],v[i]);//度是3且相邻的放入一个集合中
        else if(d[u[i]]==2&&d[v[i]]==3) cnt[v[i]]++;//记录度是3的点相邻的度是2的点有多少个
        else if(d[u[i]]==3&&d[v[i]]==2) cnt[u[i]]++;
    }
    map<int,set<int>> p;
    for(int i=1;i<n;i++){
        if(d[u[i]]==3) p[find(u[i])].insert(u[i]);
        if(d[v[i]]==3) p[find(v[i])].insert(v[i]);
    }
    //cout<<d[9]<<' '<<d[4]<<' '<<d[1]<<' '<<d[11]<<endl;
    ll res=0;
    //cout<<p.size()<<endl;
    for(auto [u,v]:p){
        ll c=0;
        for(int x:v){
            c+=cnt[x];
            //cout<<x<<endl;
        }
        //cout<<c<<endl;
        res+=c*(c-1)/2;
    }
    cout<<res<<endl;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int _=1;
    //cin>>_;
    while(_--) solve();

    return 0;
}

标签:AtCoder,Beginner,atcoder,int,378,abc378,contests,find,define
From: https://www.cnblogs.com/djhjojo/p/18532483

相关文章

  • paddleSOT beginner
    paddleSOTbeginner入门学习一个例子说明什么是动转静示例:在动态图和静态图中的简单计算假设我们有一个简单的神经网络模型,每次输入一个张量x,然后做一些数学运算并输出结果。这个过程使用PaddlePaddle框架中的动转静技术可以分为两个部分来说明。1.动态图实现在动态图模......
  • LeetCode题练习与总结:有序矩阵中第 K 小的元素--378
    一、题目描述给你一个 nxn 矩阵 matrix ,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。请注意,它是 排序后 的第 k 小元素,而不是第 k 个 不同 的元素。你必须找到一个内存复杂度优于 O(n^2) 的解决方案。示例1:输入:matrix=[[1,5,9],[10,11......
  • AtCoder Beginner Contest 284题解
    AtCoderBeginnerContest284A没有什么难点,反着输出一遍就可以了。#include<bits/stdc++.h>usingnamespacestd;stringa[2000];intmain(){ intn; cin>>n; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=n;i;i--)cout<<a[i]<<'\n';......
  • AtCoder Beginner Contest 378
    ContestLink还得加练。A&B&C&D不具备任何思维含量。SubmissionASubmissionBSubmissionCSubmissionDE注意到它计算答案的式子,每个子区间和都需要取模,否则就是沙币题了,可以对于每个位置\(O(1)\)地统计答案扫过去然后\(\bmodM\)。常规地,记\(S_i=\sum......
  • AtCoder Beginner Contest 360 - VP记录
    A-AHealthyBreakfast高桥日常出境。头一次知道getchar()的返回值是int。点击查看代码#include<cstdio>usingnamespacestd;intmain(){ chars[3]={getchar(),getchar(),getchar()}; if(s[0]=='R'&&s[1]=='M')puts("Yes"); els......
  • AtCoder Beginner Contest 378 E
    https://atcoder.jp/contests/abc378/tasks/abc378_ehttps://atcoder.jp/contests/abc378/editorial/11300#include<bits/stdc++.h>#definexfirst#defineysecond#defineall(x)(x).begin(),(x).end()#definelowbit(x)(x)&-(x)usingnamespacestd;ty......
  • ABC378 E 题解
    ABC378E题解题意给定序列\(A\),求\(\sum_{1\lel\ler\len}(\sum_{l\lei\ler}A_i\modM)\)计算所有区间和取模之后的结果再求和。注意外层是没有取模的。如果是外层也要取模的情况,那还是十分好办的,直接贡献法计算每个数字被统计了多少次就可以了。问题就在于外层没......
  • 洛谷题单指南-二叉堆与树状数组-P3378 【模板】堆
    原题链接:https://www.luogu.com.cn/problem/P3378题意解读:实现二叉堆。解题思路:二叉堆本质上一棵完全二叉树,根节点称为堆顶,根据特性不同分为有两种:大根堆:所有父节点的值大于子节点,根节点最大小根堆:所有父节点的值小于子节点,根节点最小主要作用:动态维护序列,并快速找到最大/最......
  • AtCoder Beginner Contest 378
    AtCoderBeginnerContest378总结A直接模拟,存\(1\)到\(4\)出现个数。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<queue>#include<map&g......
  • AtCoder Beginner Contest 378
    ABC378光速切掉前四题,结果倒在了第五题。A-Pairing难度:红。弱智题,不解释。#include<bits/stdc++.h>usingnamespacestd;intmain(){inta[5]={0};for(inti=1;i<=4;i++){intx;cin>>x;a[x]++;}intans=0;for(inti=1;i<=4;i++){......