B. Brightness Begins

思路

要求最后的灯泡打开的数量，由于一开始灯泡是打开的，如果最后还需要打开，那么操作数量一定是偶数，移目至操作前提，需要灯泡的序号能整除 \(x\)，由于遍历1~x，推出最后灯泡 \(i\) 亮的条件是：\(1~i\) 中有偶数个\(i\)的因数，即 \(i\) 有偶数个因数，反之即有奇数个因数，由于因数成对存在，只有当这个数是完全平方数的时候才会有奇数个因数，所以题目转化为： \(n\) 以内至少有 \(k\) 个非完全平方数。
正难则反，我们只需反求：\(n\) 存在有 \(n-k\) 个完全平方数。第 \(n-k\) 个非完全平方数即 \((n-k)^2\) ,可得方程：\(n<=(n-k)^2\) ,变形得：
\(f(n)=n-\sqrt{n}>=k\),
由于 \(f(n)\) 单调递增，所以问题变成了：找到最小的 \(n\) ，使得 \(f(n)>=k\) 成立，二分即可；
注意：使用sqrtl代替sqrt，精度需求高；

AC代码

    #include<bits/stdc++.h>
    #define endl '\n'
    #define ll long long
    #define pb push_back
    #define bs bitset
    #define fast() ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
    using namespace std;

    typedef pair<char,int> PCI;
    typedef pair<int,int> PII;
    typedef pair<long long, long long> PLL;
    typedef priority_queue<int> PQ;
    const int N = 2e5+10, MAX = 1e9, INF = -1e9;

    ll k;

    void solve(){
        cin>>k;
        ll l=1;ll r=2e18;
        while(l<r){
            ll mid=(l+r)>>1;
            if(mid-(int)sqrtl(mid)>=k)r=mid;
            else l=mid+1;
            //cout<<l<<" "<<r<<" "<<mid<<" "<<mid-sqrt(mid)<<endl;
        }
        cout<<l<<endl;
    }

    int main()
    {
        fast();
        
        int t=1;
        cin>>t;
        while(t--){
            solve();
        }
        return 0;
    }

E. Tree Pruning

思路

每次删除一个叶子，问最少进行多少次操作使得所有叶子与根距离相同。距离就是深度，我们枚举深度，考虑DFS，对于深度大于 \(x\) 的所有节点都要被剪掉, 而深度小于 \(x\) 的节点, 如果没有子节点深度大于等于 \(x\), 那么也要被最后删掉统计一下删除点的个数。使用mxp和cntp分别用于记录特定深度的节点数量和最大的深度信息,dep数组存储每个节点的深度，mxdep记录从每个节点向下的最大深度。

AC代码

    #include<bits/stdc++.h>
    #define endl '\n'
    #define ll long long
    #define pb push_back
    #define bs bitset
    #define fast() ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
    using namespace std;

    typedef pair<char,int> PCI;
    typedef pair<int,int> PII;
    typedef pair<long long, long long> PLL;
    typedef priority_queue<int> PQ;
    const int N = 5e5+10, MAX = 1e9, INF = -1e9;

    vector<int> v[N];
    int mxp[N],cntp[N];
    int dep[N];
    bool leaf[N];
    int mxdep[N];
    int maxn;
    int n;

    void dfs(int x,int fa)
    {
        dep[x] = dep[fa] + 1;
        maxn = max(maxn,dep[x]);
        mxdep[x] = dep[x];
        for (auto y : v[x])
        {
            if (y==fa) continue;
            dfs(y,x);
            mxdep[x] = max(mxdep[x],mxdep[y]);
        }
        cntp[dep[x]]++;
        mxp[mxdep[x]]++;
    }

    void solve()
    {
        cin>>n;
        for(int i=1;i<=n;i++)v[i].clear(),mxdep[i] = mxp[i] = cntp[i] = dep[i] = maxn = 0;
        for(int i=1;i<=n-1;i++){
            int x,y;
            cin>>x>>y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        dfs(1,0);
        int res = 0;
        int ans = 0;
        for (int i = 1;i <= maxn;i++){
            res += cntp[i];
            ans = max(ans,res);
            res -= mxp[i];
        }
        cout<<n-ans<<endl;
    }

    int main()
    {
        fast();
        
        int t=1;
        cin>>t;
        while(t--){
            solve();
        }
        return 0;
    }

t.b.c.