把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。
题目大意：
CF1534D lost tree
交互题，有一棵大小为n的树（2000），一次询问一个点将会得到每个点对于这个点的距离，最多询问n/2（向上取整）次，要求出这棵树。
解：
可以知道，当询问一个点时，只要是距离为1的点就一定是和他链接的。而开局的时候问哪个点都一样，所以我们问“1”。
画几张图可以发现，无论我们怎么取点询问，除非是通过将距离与被询问点为1的点和被询问点连边或者只剩一个节点没问过的时候将它连到最后一个没有问过的点（这个概率太小而且非常麻烦），我们是无法获取整棵树的。
也就是说无论如何对于一对连通的点，我们至少要询问其中的一个。
那么问题就很简单了，这些点最好是互相间隔的，无论如何我们都不想询问一对连通点中的两个点，因为这毫无意义，于是一开始想到了multiset的方法，只要问过的点，都不再去与它连接的点，但是直接被样例1卡了，只能说是高质量样例啊。
为什么呢？因为这个方法实际上是把所有点一分为二，然后取其中的一个集合，但我们必须保证自己取的是更小的那个集合，而不是随便取一个，显然，更小的那个集合里面的点数一定是小于n/2的。
那么怎么得到这个集合呢？通过一开始问的那个1，因为信息除了距离为1的点还有其他的点，依靠距离有没有什么能够直接把点集一分为二的方法呢？有，距离的奇偶，既然连接的节点距离只能为1，那么奇数节点就只能和相邻的偶数节点连接，反之亦然，所以只要询问奇偶节点里数量小的那部分即可。
至于为什么是n/2向上取整，就是因为第一个问的那个1了，卡的非常死啊。
遇到n/2的时候要首先想到把整个集合分成两个部分，这是非常关键的，也是在思维题中可以积累出来的技巧。
代码
代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 400005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
#define endl '\n'
using namespace std;
int n;
vector<pll> ans;
multiset<int> st;
int qr[2005];
map<pll, int> vi;
int vis[2001];
vector<int> dis[2005];
void add_edge(int a, int b) {
pll p;
p.first = a;
p.second = b;
if (vi[p] == 0)ans.push_back(p);
vi[p] = 1;
p.first = b;
p.second = a;
vi[p] = 1;
}
int main() {
cfast;
cin >> n;
cout << "? 1" << endl;
cout.flush();
int od = 0, ev = 0;
inc(i,1,n+1){
cin >> qr[i];
if (qr[i] == 1) {
add_edge(1, i);
}
if (i == 1)continue;
if (qr[i] % 2 == 1) {
od++;
}
else {
ev++;
}
}
int cas = 0;
if (od < ev)cas++;
inc(i, 2, n + 1) {
if (qr[i] % 2 == cas) {
cout << "? " << i << endl;
cout.flush();
inc(j, 1, n + 1) {
int tmp;
cin >> tmp;
if (tmp == 1)add_edge(i, j);
}
}
}
cout << "!" << endl;
inc(i, 0, n-1) {
cout << ans[i].first << " " << ans[i].second << endl;
}
cout.flush();
}
|
Copyright Notice: 此文章版权归EmiteInna所有，多看看吧。
