题面：https://codeforces.com/contest/1082/problems
总共就A了3题，还FST了。最后居然还涨了15分。我之前到底是怎么掉分的
A. Vasya and Book
题意：给定共有$n$页一本书，每次只能翻连续$d$页，现在要从$x$翻到$y$，问最少需要翻几次。注意，如果翻的索引小于$1$或者大于$n$，则认为是翻到第一页或是最后一页。
解法：
- 直接从第$x$页翻到第$y$页
- 先翻到第$1$页再翻到第$y$页
- 先翻到最后一页再翻到第$y$页
wa了好多次是因为判断能不能$x$到$y$的时候出了问题ummm只要$x$和$y$差的绝对值能整除d就可以。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
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, x, d, y, t;
cin >> t;
while(t--)
{
cin >> n >> x >> y >> d;
int ans = INT_MAX;
if(abs(y - x) % d == 0)
ans = abs(y - x) / d;
if((y - 1) % d == 0)
{
int t = (y - 1) / d + (x - 1) / d;
if((x - 1) % d)
t++;
ans = min(ans, t);
}
if((n - y) % d == 0)
{
int t = (n - y) / d + (n - x) / d;
if((n - x) % d)
t++;
ans = min(ans, t);
}
if(ans == INT_MAX)
ans = -1;
cout << ans << endl;
}
return 0;
}
B. Vova and Trophies
题意：给定一个字符串，G表示黄金，现在可以任意交换两个字符，问最多的连续的G有多少个
解法：先预处理每个位置连续的G的数量有多少个并记录下来。然后遍历字符串遇到S字符的时候看是不是能够将这个S替换为不是左右连续的G中的一个G使之长度变长（通过G的个数来判断是否有多余的G）否则的话就将其中一个替换过来使之长度变为左右的和。
More details is in the code.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
using namespace std;
const int maxn = 2e5 + 10;
int l[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
string s;
cin >> n >> s;
int num = 0;
if(n == 1)
{
if(s[0] == 'G')
cout << 1 << endl;
else
cout << 0 << endl;
return 0;
}
for(int i = 0; i < n; i++)
if(s[i] == 'G')
num++;
for(int i = 0; i < n; i++)
{
if(s[i] == 'G')
{
int j = i, temp = 0;
while(s[j] == 'G' && j < n)
{
temp++;
j++;
}
for(int k = i; k < j; k++)
l[k] = temp;
i = j - 1;
}
}
int ans = 0;
for(int i = 0; i < n; i++)
ans = max(ans, l[i]);
for(int i = 0; i < n; i++)
{
if(s[i] == 'S')
{
if(l[i - 1] + l[i + 1] < num)
ans = max(ans, l[i - 1] + l[i + 1] + 1);
else
ans = max(ans, l[i - 1] + l[i + 1]);
}
}
cout << ans << endl;
return 0;
}
C. Multi-Subject Competition
题意：有$n$个学生，$m$门课，每个学生擅长某一门课，并且有一个擅长值（擅长值可能为负）。现在需要选出一些学生，所有的学科数量必须相等（可以不选某个学科）求最大的擅长值的和。
解法：考虑前缀和。
先将每一门课的擅长值记录并排序，从小到大处理所有学科，考虑每个学科的贡献。如果累加出来的前缀和是正的，那么就将其加上。用一个数组存每门学科各取了几节的和即可。$sum[i]$表示学科取了$i$节的和，因为只要是正的就一定能使得值变大并且这个值是不断更新的。最后取一个max即可。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
const int maxn = 2e5 + 10;
using namespace std;
vector<ll> p[maxn];
ll sum[maxn];
bool cmp(ll a, ll b)
{
return a > b;
}
ll ans;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
p[a].push_back(b);
}
for(int i = 1; i <= m; i++)
{
sort(p[i].begin(), p[i].end(), cmp);
ll temp = 0;
int len = (int)p[i].size();
for(int j = 0; j < len; j++)
{
temp += p[i][j];
if(temp > 0)
{
sum[j] += temp;
ans = max(ans, sum[j]);
}
else
break;
}
}
cout << ans << endl;
return 0;
}
D. Maximum Diameter Graph
题意：给定$n$个点和$a_i$，构造出一个图使得没有重边没有环且任意两个点都要可达。要使得这个图上最远的两点的距离最大。要求点$i$的度数不能超过$a_i$。
解法：图论太菜。写到自闭。其实是水题
一开始读错题理解成要使最远的两个点最短。然后发现读错题是要找最长。
首先确定肯定是需要构造出一棵树来。
那么构造一条链并使得这条链尽可能的长即可。在构造的过程中会有很多细节。
而且昨天又写到2点多，思路都混乱了。
首先将度数从大到小排序，然后前$n-2$个点依次判断看能否成链（度数大于2即可）
然后再把剩下的度数为1的点挂在链上度数还有剩余的点即可。
我这里的做法是开一个vector存剩下的还有度数的点，有多少个就塞多少个。然后依次连即可
但后来因为这wa了还查不出来，忘记考虑链头的点还需要减去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
62
63
64
65
66
67
68
69
70
71
const int maxn = 2e3 + 10;
using namespace std;
pair<int, int> a[maxn];
vector<int> g[maxn];
vector<int> toru;
int len, ii;
bool cmp(pii a, pii b)
{
return a.se > b.se;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, sum = 0;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i].se;
a[i].fi = i;
sum += a[i].se;
}
if(sum / 2 < n - 1)
{
cout << "NO" << endl;
return 0;
}
sort(a + 1, a + n + 1, cmp);
int head = a[1].fi, tail = a[1].fi, i;
for(i = 1; i < n - 1; i++)
{
if(a[i + 1].se < 2)//大于2的成链
break;
g[a[i].fi].push_back(a[i + 1].fi);
len++;
tail = a[i + 1].fi;
a[i].se--; a[i + 1].se--;
}
for(int j = 1; j <= i; j++)
{
for(int k = 0; k < a[j].se; k++)
toru.push_back(a[j].fi);
if(j == 1)
toru.pop_back();//链头的度还要减1
}
for(int j = n; j > i; j--)
{
if(j == n)
{
g[head].push_back(a[j].fi);
len++;
}
else if(j == n -1)
{
g[tail].push_back(a[j].fi);
len++;
}
else
g[toru[ii++]].push_back(a[j].fi);
}
cout << "YES" << ' ' << len << endl << n - 1 << endl;
for(int i = 1; i <= n; i++)
for(auto idx: g[i])
cout << i << ' ' << idx << endl;
return 0;
}