首页 > 其他分享 >C - Removing Coins

C - Removing Coins

时间:2024-07-31 15:51:28浏览次数:11  
标签:Removing ll Coins dfs depth maxs now root

原题链接

题解

对于硬币数变为零的点,由于既不能穿越,也不能选取,所以等于删掉了

所以操作就变成了,选取一个点,删除以其为根的树的所有叶子节点

先将树退化成链,考虑链上操作的情况,如果选取链上端点,总节点数只减一,否则减二

因此对于树上任意一条链,每次选取会导致要么减一要么减二,因此只考虑最长链的长度

当链的长度剩2的时候,只能减一,所以先手输,其他情况先手赢

code

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll inf=1e18;
const ll mod=1e9+7;
vector<ll> G[200005];


ll depth[200005]={0};
ll root,maxs=0;
void dfs(ll now,ll fa)
{
    depth[now]=depth[fa]+1;
    if(depth[now]>maxs)
    {
        maxs=depth[now];
        root=now;
    }
    for(auto next:G[now])
    {
        if(next==fa) continue;
        dfs(next,now);
    }
}

void solve()
{
    ll n;
    cin>>n;

    for(ll i=1;i<n;i++)
    {
        ll x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1,1);
    maxs=0;
    depth[root]=0;
    dfs(root,root);

    if(depth[root]%3==2) cout<<"Second\n";
    else cout<<"First\n";
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TT=1;
    //cin>>TT;
    while(TT--) solve();
    return 0;
}


标签:Removing,ll,Coins,dfs,depth,maxs,now,root
From: https://www.cnblogs.com/pure4knowledge/p/18334814

相关文章

  • Solution - Atcoder AGC028B Removing Blocks
    因为贡献的方法是相加,一种想法就是拆开,对每一项单独贡献。不难发现这题目中的贡献其实只涉及到两点之间。即删除\(x\)时\(y\)也产生了贡献。考虑这个贡献会在多少种排列中出现。令\(d=|x-y|+1\),即\(x,y\)中的点数。能发现排列需要满足除\(x\)外的\(d-1\)......
  • Solution - Atcoder ARC150D Removing Gacha
    考虑到每次操作都比定会选上一个点,于是答案可以表示为每个点被选中的次数之和。即令\(c_i\)为\(i\)点被选中的次数,答案即为\(E(\sum\limits_{i=1}^nc_i)\)。根据期望的线性性,考虑把答案的\(E\)拆到每个\(c_i\)上,即变为\(\sum\limits_{i=1}^nE(c_i)\)的形式。......
  • Topcoder SRM616-Div1-Lv2 ColorfulCoins
    涉及知识点:奇妙Ad-hoc前言一道很不常规的题目,思维难度大代码简单,而且这种思路很难在赛时想到,故记录一下。题意某国的货币系统硬币有\(n\(\leq60)\)种面额\(val_i\(\leq10^{18})\),其中最小的面额为\(1\),并且所有的面额之间都保证两两有倍数关系,每种面额的硬币有独一无......
  • 518_coins_changeII_找零钱II
    问题描述链接:https://leetcode.com/problems/coin-change-ii/Youaregivenanintegerarraycoinsrepresentingcoinsofdifferentdenominationsandanintegeramountrepresentingatotalamountofmoney.'Returnthenumberofcombinationsthatmakeupthat......
  • CF1385F Removing Leaves 题解
    看到题,感觉像树形DP,遂设计DP式子。\(dp_u\)表示以\(u\)为根的子树内最多能删多少次(不删\(u\))。那么每次子节点到父节点增加的贡献就是\(\lfloor\frac{子树大小为1的子节点个数}{k}\rfloor\)。得出式子\(dp_u=\sum_{v\inson_u}dp_v+(\sum_{v\inson_u}[dp_v\times......
  • cf gym101981e Eva and Euro coins
     20182019-acmicpc-asia-nanjing-regional-contest-en.pdf(codeforces.com) 这类字符串的能否从s状态到达t状态的题。还可以删除若干子串后然后比较。感觉是一种套路。 100↔111↔001011↔000↔110 01001↔10010可以移动 用栈,如果找到k个连续相同,然后栈删掉这k......
  • CF875B Sorting the Coins 题解
    题面。算是比较简单的题目了,自己多手出几个样例就可以发现规律了。强烈建议多读几遍题目!!!!思路设0表示硬币朝上,1表示硬币朝下,则第\(0\)次与第\(n\)操作一定输出\(1\)。因为没有可以操作的对象,前者是由于全部硬币朝上,后者是由于全部硬币朝下,即使没有操作也要遍历一遍。注......
  • [论文阅读] Domain generalization by learning and removing domain-specific featur
    1Introduction最近的研究发现,DNNs倾向于以与人类不同的方式学习决策规则[17,21,16]。例如,在基于ImageNet的图像分类任务中,卷积神经网络(CNNs)倾向于学习局部纹理以区分对象,而我们人类则可能使用全局对象形状的知识作为线索。DNNs学到的特征可能只属于特定的领域,对其他领域不具......
  • AGC018C Coins 题解
    模拟费用流。传送门题意:共\(n=x+y+z\)个人,每个人可以选择获得\(a_i\)个金币或\(b_i\)个银币或\(c_i\)个铜币。要选\(x\)个人拿金币,\(y\)个人拿银币,\(z\)个人拿铜币。问币数总和最大是多少。\(n\le10^5\)。先建出费用流模型:把一个人的选择视作一个人流到了金币/......
  • Codeforces Round 656 (Div. 3) F. Removing Leaves
    ProblemDescription给出一棵\(n\)个节点的无根树。你可以进行以下操作:选择\(k\)个共同父节点的叶子节点,将\(k\)个节点和与父节点相连的边删去。求最大操作次数。Input第一行输入一个整数\(t\)\((1\let\le2\times10^4)\),表示测试组数。接下来每组测试数据第......