链接：https://www.jisuanke.com/contest/2346?view=challenges
第一题
需要删除的骨牌满足的条件为：
[1]:出度最大；
[2]:出度相同判断有无入度；
vector<int >out[maxn];///out[x]:存x指出去的点 int in[maxn];///in[x]:x的入度 #include<bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define ll long long const int maxn=5e3+50; int n; vector<int >out[maxn]; int in[maxn]; bool vis[maxn]; void Update() { int t=0; for(int i=1;i <= n;++i) { if(vis[i] || out[i].size() < out[t].size()) continue; if(t == 0) t=i; if(out[i].size() > out[t].size() || in[i] > 0) t=i; } for(int i=0;i < out[t].size();++i) in[out[t][i]]--; vis[t]=true; } int Solve() { mem(vis,false); if(n <= 2) return 0; Update(); Update(); int ans=0; for(int i=1;i <= n;++i) if(!vis[i] && in[i] == 0) ans++; return ans; } int main() { scanf("%d",&n); for(int i=1;i < n;++i) { int x,y; scanf("%d%d",&x,&y); out[x].push_back(y); in[y]++; } printf("%d\n",Solve()); return 0; }额，真没想到贪心居然能过。
算了顺便写一下窝WA了的解法：额，跑联通块居然WA了，忒惨了
#include<iostream> #include<algorithm> #include<vector> #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100005; const ll mod = 1e9+7; const ll INF = 0x3f3f3f3f; const double eps = 1e-9; vector<int>v[maxn]; bool vis[maxn]; int ans=0; void dfs(int x){ vis[x]=true; for(int i=0;i<v[x].size();i++) { int next=v[x][i]; if(!vis[next]) dfs(next); } } int main(){ int n; scanf("%d",&n); for(int i=0;i<n-1;i++){ int x,y; scanf("%d %d",&x,&y); v[x].push_back(y); } v[1].clear(); int num=0;int flag=0; for(int i=2;i<=n;i++){ if(num<v[i].size()){ num=v[i].size(); flag=i; } } v[flag].clear();int ans=0; for(int i=2;i<=n;i++){ if(!vis[i]){ dfs(i); ans++; } } cout<<ans<<endl; return 0; }第二题 未补完
第三题 未补完
第四题 未补完
