开学大二补题（第二周）

whatdo / 2023-09-13 / 原文

这几天比赛发现短板很明显，写题异常慢，但是题是可以写出来的

还有就是wa的太随便动不动就是一个很简单的点给我wa了

总之，题刷少了

Problem - H - Codeforces

题意：就是给你一个棵树，这棵树分很多的叶子一共n个点然后让你对这个树进行层减

一共减k层就是一层一层的去掉，然后输出还剩点的个数

题解：这道题就是一个拓扑排序的题

很好想，一层一层搞我们发现就和这些点的边数有关边数少的绝对最最低层

所以我们可以记录每一个点连起来的边数只要出度为1那么这个点就是最底层的点我们就删除即可

然后跑一个广搜这样的首先记录现在就是1的底层点如何入队就可以了

跑队列的时候就用这些1的点因为底层的点被我们剪掉了，所以边也没了，和这些底层相连的点边数就要减减，然后减完看看这个点是不是边数只有1了

如果是那么然后减的层数不够，这点就入队，够就不入队，就行了

#include <bits/stdc++.h>
#pragma  GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
//#define endl '\n';
using namespace std;
const int N=1e6+5,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=998244353;
typedef pair<int,int> PII;
int bian[N];

int n1,k1;
int dep[N];
vector<int> a[N];
int su;
void bfs(int n,int k)
{
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(bian[i]==1)
        {
            q.push(i);
            bian[i]=0;
            su++;
            dep[i]=1;
        }
    }
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for(auto x:a[u])
        {
            bian[x]--;
            if(bian[x]==1 && dep[u]<k)
            {
                su++;
                q.push(x);
                dep[x]=dep[u]+1;
            }
        }
    }
}
void solve() {

    cin>>n1>>k1;
    for(int i=1;i<=n1;i++) bian[i]=0, dep[i]=1, a[i].clear();
    su=0;
    for(int i=1;i<n1;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
        bian[x]++;
        bian[y]++;
    }
    if(n1==1 || 2*k1>=n1)
    {
        cout<<0<<endl;
        return;
    }
        bfs(n1,k1);
        cout<<n1-su<<endl;



}


signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

Problem - E - Codeforces

题意：给你两种汤第一次就是只有第一种汤，第二次是只有第二种汤，然后后面开始就把两种汤混合就行了不断混合

就是i-2次和i-1次混合出来就是第i次，不断递推下去，然后问你第n次两种汤比例是多少

题解：　其实手推的时候就会发现越是往后越是靠近1：3的比例，所以我们就知道后面大的数输出一个固定值就行了

这个点也是我卡的点（赛时卡死了）

然后前面的我们就稍微写一下模拟即可，不断相加除2不断减半即可

#include <bits/stdc++.h>
#pragma  GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
//#define endl '\n';
using namespace std;
const int N=1e6+5,M=1e1;
const int INF = 0x3f3f3f3f;
const int mod=998244353;
typedef pair<int,int> PII;



void solve()
{
    int n;
    cin>>n;
    if(n==1)
    {
        cout<<100<<" "<<0<<endl;
        return;
    }
    if(n==2)
    {
        cout<<0<<" "<<100<<endl;
        return;
    }
    if(n==3)
    {
        cout<<50<<" "<<50<<endl;
        return;
    }
    if(n>=28)
    {
        cout<<"33.333333 66.666667"<<endl;
        return;
    }
    double a=100,b=0;
    for(int i=3;i<n;i++)
    {
        double t=a;
        a=b;
        b=t/2+b/2;
    }
    double ans=a*1.0/2+b*1.0/2;
    printf("%.6lf %.6lf",ans,100-ans);
}


signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}