题面：http://codeforces.com/contest/782/problems
A. Andryusha and Socks
题意：有n双袜子，现在要从袋子里取袜子放到柜子，每次取一只，如果取出的袜子是一双中的第一只则把它放在外面，否则就一起放入柜子中。求同一时刻最多有多少只袜子在外面。
解法：模拟一下就好了。标记一下该种袜子是不是被取出来过。随便维护一下最大值就好了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
using namespace std;
const int maxn = 2e5 + 10;
int put[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int ans = 0, cnt = 0;
for(int i = 0; i < 2 * n; i++)
{
int t;
cin >> t;
if(put[t] == 0)
{
ans++;
put[t] = 1;
}
else if(put[t] == 1)
{
ans--;
put[t] = 2;
}
cnt = max(ans, cnt);
}
cout << cnt << endl;
}
B. The Meeting Place Cannot Be Changed
题意：有n个人位于给定x轴上的若个位置，现在要把他们聚集到x轴上的某个位置。每个人有一个速度，问你最短聚集的时间是多少。他们相遇的点可以不是整点。
解法：二分答案。二分时长。由于每个人都有一个速度，相当于此人可以向左或者向右走一段路的距离，如果所有人的这段区间有一个共同的交点，则说明满足条件。
这样就把问题转换为如果判断区间相交了，思考了一下发现只需要最小的右端点大于最大的左端点就一定可以满足条件。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
using namespace std;
const int maxn = 1e5 + 10;
double x[maxn], v[maxn];
int n;
bool C(double mid)
{
double lr = INT_MAX, rl = 0;
for(int i = 0; i < n; i++)
{
double a = x[i] - v[i] * mid, b = x[i] + v[i] * mid;
rl = max(rl, a);
lr = min(lr, b);
}
if(rl < lr)
return true;
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++)
cin >> x[i];
for(int i = 0; i < n; i++)
cin >> v[i];
double l = 0, r = 0;
for(int i = 1; i < n; i++)
r = max(r, fabs(x[i] - x[0]) / (1.0 * v[i]));
// cout << l << ' ' << r << endl;
for(int i = 0; i < 100; i++)
{
double mid = (l + r) / 2;
if(C(mid))
r = mid;
else
l = mid;
}
cout << fixed << setprecision(7) << r << endl;
//要设置输出小数位数，否则会wa
}
C. Andryusha and Colored Balloons
题意：染色问题。相邻的三个结点必须是不同的颜色，要求你输出最少需要的颜色。
解法：DFS。首先对于一个结点而言，所有的儿子必须染成不同的颜色。其次由于需要满足相邻的三个结点不能同色，所以dfs时需要传入父结点及再上一层结点的颜色。
这里给出两种写法，熟悉一下链式前向星写法。
- vector写法
1 |
|
- 链式前向星写法
1 |
|
D. Innokenty and a Football League
题意：题意稍微有点复杂。就是你需要给每个球队取一个简称的名字，每个球队会给你两个字符串，你有以下两种取名的规则。
- 选取第一个字符串的前三个字符
- 选取第一个字符串的前两个字符和第二个字符串的第一个字符
显然每个队的队名都是unique的。此外，如果一个队伍以第二种方式命名，那么也不能有一个队起这个队伍的第一种规则组成的名字。
举例来说：如果一个队两个字符串是ABC DEF。如果取名为ABD，则ABC也不能作为名字。
这是针对另一个队的第一种规则而言的，如果第二个规则能构成ABC，认为是可行的。
总之就是有一些奇怪的规则。需要仔细考虑。
解法：乱搞（贪心）。由于n的范围很小。
一开始想的是直接取第一个名字，要是不行取第二个。
（因为觉得取了第二个会导致第一个也不可用）
但这样会出现一个问题，可能之前第一个名字可以，但后面由于出现了选取了第二种规则导致第一个名字不可用的情况出现。
用map标记每一个字符串的状态。用1表示该名字已经被使用，用2表示该字符串不能出现在以第一种规则命名的名字。
同时用一个数组记录每次的规则是第一个还是第二个。
每次优先取第二个，同时看之前有没有第一种规则的字符串被作为以第一种规则命名的名字。如果有就说明肯定不可行直接break。因为已经尽量保证取第二个了，所以不行就是肯定不行。如果可以，则取第二个字符串，同时将第一个名字的字符串置为2（如果还没被使用）
如果第二个字符串已经被使用，那么考虑第一个，如果其值为1或者2，则不行break否则记录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
using namespace std;
const int maxn = 2e3 + 10;
map<string, int> T;
pair<string, string> a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
string s, t;
cin >> s >> t;
a[i] = make_pair(s.substr(0, 3), s.substr(0, 2) + t[0]);
}
vector<string> ans;
vector<int> seq;
bool f = 1;
for(int i = 0; i < n; i++)
{
if(T[a[i].second] != 1)
{
bool res = 1;
for(int j = 0; j < i; j++)
{
if(seq[j] == 1 && ans[j] == a[i].first)
{
res = 0;
break;
}
}
if(res == 0)
{
f = 0;
break;
}
ans.push_back(a[i].second);
T[a[i].second] = 1;
if(T[a[i].first] != 1)
T[a[i].first] = 2;
seq.push_back(2);
}
else
{
if(T[a[i].first])
{
f = 0;
break;
}
ans.push_back(a[i].first);
T[a[i].first] = 1;
seq.push_back(1);
}
}
if(f)
{
cout << "YES" << endl;
for(auto idx: ans)
cout << idx << endl;
}
else
cout << "NO" << endl;
return 0;
}
E. Underground Lab
题意：给定一个联通图。给定n, m, k分别表示定点个数和边的个数。现在要求你从k个点出发，每个点可以走$\lceil\frac{2n}{k}\rceil$个点，要求你遍历图上的所有结点，给出这k个点的路径。
解法：DFS & 思维
这是一道难点在想法上的题目。一开始可能会无从下手。共k个点，每个点$\lceil\frac{2n}{k}\rceil$次，我们可以把它们乘起来看看发现是大于等于$2n$的。考虑从某一点DFS整个图，每条边会被走两次（回溯也算）由于是一棵生成树，所以共经过结点$2*(n - 1) + 1$小于$2n$然后把这个序列分配给这k个点即可。如果分配完了，剩下的输出1 1即可。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
using namespace std;
const int maxn = 4e5 + 10;
int n, m, k;
vector<int> g[maxn];
vector<int> path;
bool vis[maxn];
void dfs(int node)
{
vis[node] = 1;
path.push_back(node);
for(auto idx: g[node])
{
if(vis[idx]) continue;
dfs(idx);
path.push_back(node);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
while(m--)
{
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1);
int res = (int)path.size();
int len = (2 * n) / k;
if(2 * n % k) len++;
for(int i = 0, j = 0; i < k; i++)
{
if(res <= 0)//之前写了等于0 re了好久
{
cout << "1 1" << endl;
continue;
}
if(res >= len)
{
int t = len;
cout << t << ' ';
res -= t;
while(t--)
cout << path[j++] << ' ';
cout << endl;
}
else
{
cout << res << ' ';
while(res--)//要注意这里res是会减到小于0的
cout << path[j++] << ' ';
cout << endl;
}
}
return 0;
}