题面：http://codeforces.com/contest/805/problems
A. Fake NP
题面：给定左右边界$l$和$r$，找出所有的数中出现次数最多的约数。
解法：显然每隔一次就会出现一次2，所以2肯定是出现次数最多的约数。
但还需要考虑只有一个数且为奇数的情况，这时候输出自己就可以了。1
2
3
4
5
6
7
8
9
10
11
12
13
using namespace std;
const int maxn = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int l, r;
cin >> l >> r;
if(l == r) cout << l << endl;
else cout << 2 << endl;
return 0;
}
B. 3-palindrome
题意：需要你使用$a,b,c$三种字符构造一个长度为n且不出现长度为3的回文串的字符串，要求尽量使用a和b.
解法：其实是个脑洞题。由于是不出现长度为3的回文串而不是长度大于3的回文串，所以只需要
$ab-ba-ab-ba…$或者$aa-bb-aa-bb-aa-bb$一直循环写下去就可以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
using namespace std;
const int maxn = 2e5 + 10;
string a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n / 2; i++)
if(i % 2)cout << "ab";
else cout << "ba";
if(n % 2)
{
if((n / 2) % 2)
cout << "b";
else
cout << "a";
}
cout << endl;
return 0;
}
C. Find Amir
题意：有$n$个学校(indexed from $1$)，要访问完所有的n个学校，从i到j需要花费$(i + j) \% (n + 1)$，问最少的花费是多少。
解法：随便尝试一下就知道了，尽量要使得$(i + j)$的值靠近$(n + 1)$，首位不停的访问即可 凑个结论出来就好了1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace std;
const int maxn = 2e5 + 10;
string a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
cout << (n + 1) / 2 - 1 << endl;
return 0;
}
D. Minimum number of steps
题意：给定一个字符串，在这个字符串中每遇到一个$ab$就将其变换为$bba$，问最少会进行几次这样的变换。
解法：规律 & 思维
当时这道题是跑了个暴力硬生生找规律找出来的，发现每次遇到一个$ab$，观察前面有几个$a$，后面有几个$b$，然后每次会把这个权重(权重为$2^i$)乘以$b$的数量，且$a$的数量会一直累计。跑一个快速幂就可以。
其实后来发现做复杂了。我们仔细观察发现，最后的字符串一定是$bbb…aaaa$的形式，即做的是一个将$a$移动至最右边的操作。$”aab” → “abba” → “bbaba” → “bbbbaa”$
发现每个a后有几个b就做了几次操作，且每次操作会使得b的数量翻倍。
所以只需要从后向前处理，记录b的个数，不断的累加即可。
快速幂解法：
1 |
|
思维解法
1 |
|
E. Ice cream coloring
题意：有一棵树，树上的每个结点都有一定数量的ice，现在要根据这些结点构建一个新的图，要求每个结点上的ice都是互相可以到达的(即强连通)，现在要对这个构造出来的子图进行染色，要求相连的两个结点必须染成不同的颜色，问最少需要几种颜色。
解法：
对于原图：
如果任意2点有相同的ice,那2点之间有边
又因为原图为树，所以，任意一种ice，最多只可能出现2次
原图中u点有{a,b,c}ice
那图G中a,b,c的颜色互不相同
SO：
从原图任意一点开始dfs
对点u中的雪糕按从1开始，从小到大标颜色
由于每个结点上的ice构成一个强连通图，所以必然每个结点都是不同的颜色。但是会存在之前这个结点已经被染上色的情况，这种情况下，预处理该结点上所有已经染上的颜色，跳过这些颜色从小到大染色即可。细节见代码。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
using namespace std;
const int maxn = 3e5 + 10;
vector<int> tree[maxn];
vector<int> ice[maxn];
bool vis[maxn];
int col[maxn];
void dfs1(int node)//用map存储 稍慢
{
vis[node] = 1;
int s = 1;
map<int, int> q;
for(auto idx: ice[node])
{
if(col[idx])
q.insert(make_pair(col[idx], 1));
}
for(auto idx: ice[node])
{
while(q[s])
s++;
if(!col[idx])
col[idx] = s++;
}
for(auto idx: tree[node])
{
if(!vis[idx])
dfs1(idx);
}
}
void dfs2(int node)//去掉那个map的log的复杂度
{
vis[node] = 1;
int s = 1, ii = 0;
vector<int> q;
for(auto idx: ice[node])
if(col[idx])
q.push_back(col[idx]);
q.push_back(INT_MAX);
sort(q.begin(), q.end());
for(auto idx: ice[node])
{
while(s == q[ii])
{
s++;ii++;
}
if(!col[idx])
col[idx] = s++;
}
for(auto idx: tree[node])
{
if(!vis[idx])
dfs2(idx);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
int t; cin >> t;
ice[i].resize(t);
for(auto &idx: ice[i])
cin >> idx;
}
for(int i = 1; i < n; i++)
{
int a, b; cin >> a >> b;
tree[a].push_back(b);
tree[b].push_back(a);
}
dfs2(1);
for(int i = 1; i <= m; i++)
if(!col[i])col[i] = 1;
set<int> t;
for(int i = 1; i <= m; i++)
t.insert(col[i]);
cout << t.size() << endl;
for(int i = 1; i <= m; i++)
cout << col[i] << ' ';
cout << endl;
return 0;
}