当前位置: 首页 > news >正文

[BalticOI 2002] Tennis Club (Day1) 解题报告

构造题

解题思路

贪心。优先满足想交朋友数最多的人。每次排序,让能交朋友多的人分别和第二,第三,……,交朋友。

代码实现

循环进行贪心分配。每次循环先排序,再分配朋友并更新需求。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
bool f[1010][1010];
struct node{int v,id;friend bool operator <(node a,node b){return a.v>b.v;}
}a[1010];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i].v,a[i].id=i;for(int i=1;i<=n;i++){sort(a+1,a+n+1);for(int j=2;j<=a[1].v+1;j++){if(!a[j].v)return cout<<"NO SOLUTION"<<endl,0;a[j].v--;f[a[1].id][a[j].id]=1;f[a[j].id][a[1].id]=1;}a[1].v=0;}cout<<"SOLUTION\n";for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(f[i][j])cout<<j<<' ';}cout<<endl;}return 0;
} 

发散思考

线性的问题能不能转化到树上?
考虑下列问题:

  • 给定 \(n\) 个点的树,问能选出多少点对 \((u,v)\),满足 \(u,v\) 互相不为祖先,每个点只能被包含在一个点对中。
    这个问题将线性转化到了树上。
    由调整法,若所有子树的大小均不超过它们总大小的一半,根据经典的结论可知,匹配数能够达到上界。
    否则,记大小最大的子树是 \(v\),由调整法可知,存在一种最优方案使所有子树之间的匹配,存在于 \(v\) 和其它子树之间。那么我们只需优先在 \(v\) 的子树内部匹配,之后将剩余节点与其它子树匹配。
http://www.hskmm.com/?act=detail&tid=26118

相关文章:

  • 党徽
  • ZKEACMS:基于ASP.Net Core开发的开源免费内容管理系统
  • MySQL面试题汇总
  • 穷人的中国象棋打谱程序
  • 文件系统的层次结构
  • oracle 19c学习笔记2
  • 文件保护
  • 一些数数杂题
  • AI元人文:规则与人文的统一之路
  • 10.7
  • qmd 模拟赛的一道题
  • 四元数:从理论基础到实际应用的深度探索 - 教程
  • Day12
  • HoneyWell(霍尼韦尔)1450g扫码枪说明书
  • 课上动手东脑问题
  • 箭头函数的疑问
  • 文件共享
  • 【万字长文】让面试没有难撕的JS基础题
  • Java总览
  • PCoT: Persuasion-Augmented Chain of Thought for Detecting Fake News and Social Media Disinformation
  • 博客地址
  • 宏定义中,为什么使用:do{}while(0)这种模式是最安全的
  • 20251007J赛合订本
  • XML 元素:基础、应用与优化 - 教程
  • Educational Codeforces Round 183 (Rated for Div. 2) A~D
  • Cisco vManage漏洞分析:未授权RCE与权限提升完整攻击链
  • QBXT2025S刷题 Day6题
  • 硅芯片创新如何成为云计算成功的关键
  • 东萍象棋 DhtmlXQ UBB 转 中国象棋云库查询 FEN
  • 斑马ZT210碳带及纸张安装教程