| 题目名称 | 2096. 不平凡的许愿树 |
|---|---|
| 输入输出 | hopetree.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 5000 ms (5 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2015-11-05加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：37， 提交：97， 通过率：38.14% | ||||
 前鬼后鬼的守护 |
100 | 0.131 s | 96.29 MiB | C++ |
 Heaven |
100 | 0.149 s | 96.04 MiB | C++ |
 xzz_233 |
100 | 0.154 s | 96.05 MiB | C++ |
|
xzz_233 |
100 | 0.161 s | 96.04 MiB | C++ |
 jhjh |
100 | 0.219 s | 96.05 MiB | C++ |
 白&夜 |
100 | 0.594 s | 1.46 MiB | C++ |
 老爹 |
100 | 0.760 s | 0.62 MiB | C++ |
 FoolMike |
100 | 0.891 s | 3.36 MiB | C++ |
 test |
100 | 0.960 s | 0.62 MiB | C++ |
 tututu |
100 | 0.974 s | 95.83 MiB | C++ |
| 本题关联比赛 | |||
| 不平凡的世界 | |||
| 不平凡的世界 | |||
| 关于 不平凡的许愿树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
需要开long long
 Shirry
2017-09-07 21:33
9楼
| ||||
|
来发玄学题解：
http://www.cnblogs.com/Yuzao/p/7192664.html Heaven
2017-07-17 08:07
8楼
| ||||
|
飞流直下三千尺，膜拜神犇lcy
| ||||
|
刚开始想到枚举点DFS或者BFS什么的了，但是脑残地认为会超时，于是就写了一个十分sabi的东西，然后评测的时候还因为奇怪的语法和评测环境不一样被卡掉了orz，把奇怪的语法一改，提交发现这么快，果然还是我太菜不会分析复杂度orz。
前鬼后鬼的守护
2015-11-06 08:14
6楼
| ||||
|
表示不知道正解。
| ||||
|
难道我幻想的1次DFS就解决问题是不可能的么。。。
 Skyo
2015-11-05 19:53
4楼
| ||||
|
longlong比int慢大概1S，还是在int大量取模的情况
| ||||
|
太慢啦。。。。
 Satoshi
2015-11-05 17:35
2楼
| ||||
|
QAQ...拍了1000组..竟然空间估算错了了..
| ||||
sxysxy
dashgua
mikumikumi
dydxh【题目描述】
noip要到了，大家来到许愿树前。这个许愿树不仅仅是许愿树，还有未卜先知的功能。众OIer问许愿树：“不平凡的许愿树，CCF告诉我们noip中会有两道题目从Openjudge上选择，你能不能告诉我是哪两道题。”
许愿树想了想直接说出答案并不妥：“中国有句古话叫‘闷声大发财’，我就什么也不说，这是最好的。但是我看到你们这么热情，一句话不说也不好，我就告诉你们点信息吧。你们看我是一个由N个结点组成的树，在树中任选着3个点，有多少种选择方案使得这三个点互相之间的距离相同？两个方案不同当且仅当一个点在第一种方案中被选择，第二种方案中没有被选择。”
“记你算出来方案数为cnt，那么第一道题的题号就是cnt%338 + 1，第二题的题目编号是(cnt+233)%338+1。”
可是OIer们手头并没有计算机，于是请你来告诉他们题目编号。
【输入格式】
第一行一个整数N，表示树有N个点。
接下来N-1行，每行两个整数u,v，表示树中有一条从u到v的边
【输出格式】
一行，两个整数，分别为预测的第一题题号和第二题题号。
【样例输入】
7 1 2 5 7 2 5 2 3 5 6 4 5
【样例输出】
6 239
【提示】
样例解释：
共有5种方案，分别是{1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}。所以第一题的编号为5%338 + 1 = 6；第二题的编号为(5+233)%338 + 1 = 239;
数据范围与约定：
对于30%的数据：1 <= n <= 100
对于60%的数据：1 <= n <= 1500
对于100%的数据：1 <= n <= 5000
胡扯：
其实Openjudge没有确切题号，第1.1节有10题，第1.2节有10题...，不如约定第16题的编号是第1.2节的第6题。如果命中我什么都不知道。
【来源】
在此键入。