社区讨论

(非代码)这道题贪心错在哪里?

P6499[COCI 2016/2017 #2] Burza参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mdel7f9y
此快照首次捕获于
2025/07/22 21:45
8 个月前
此快照最后确认于
2025/11/04 03:55
4 个月前
查看原帖
写了1个类似次短路的做法,原理是Daniel每次封的应该是当前能走的最深的子节点,也就是每次走的是能走的最大深度次深的子节点。
至于这个深度就是1路走次好的走上来,DP求答案的时候可以顺便解决,时间复杂度O(N)。
所以这样做哪里出了问题?
代码写得比较清楚:
CPP
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <string>
#include <map>
#include <string>
#include <set>
#include <queue>
#include <cmath>
#include <tuple>
#include <stack>
#include <numeric>
#include <climits>
#include <deque> 
#include <chrono>
#include <unordered_map>
#include <cstring>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#define systemwait system("read -p \"Press Enter to continue...\"");
#else
#define debug(x...) 
#define systemwait
#endif

#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define sqsq(x) (x)*(x)
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>

const int INF=1e9+7;
const int MOD=1e9+7;
//const int MOD=998244353;
const int maxn=405;

vi mp[maxn];
int f[maxn],deg[maxn],N,K;

int DFS(int x,int fa) {
    int mx1=0,mx2=0;
    for(auto v:mp[x]) {
        if(v==fa)
            continue;
        f[v]=DFS(v,x);
        if(f[v]>mx1) {
            mx2=mx1;
            mx1=f[v];
        } else if(f[v]>mx2) {
            mx2=f[v];
        }
    }
    if(deg[x]>2 || (x==1 && deg[x]>=2)) {
        return (mx2+1);
    } else {
        return mx2;
    }
}

void solve() {
//--------Initiallize Boundless--------
//--------Input--------
    cin>>N>>K;
    for(int i=1;i<N;i++) {
        int uu,vv;
        cin>>uu>>vv;
        mp[uu].push_back(vv);
        mp[vv].push_back(uu);
        deg[uu]++;
        deg[vv]++;
    }
//--------Initiallize Bounded--------
//--------No fluff real stuff--------
    f[1]=DFS(1,-1);
    for(int i=1;i<=N;i++) {
        debug(f[i]);
    }
    if(f[1]<K) {
        cout<<"DA"<<endl;
    } else {
        cout<<"NE"<<endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int TT=1;
    //cin>>TT;
    for(int i=1;i<=TT;++i) {
        solve();
    }
    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...