社区讨论
(非代码)这道题贪心错在哪里?
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 条回复,欢迎继续交流。
正在加载回复...