题解 CF1082A 【Vasya and Book】
史上最难A题，没有之一
从题意可以看出，翻到目标页只有三种办法
-
先从(x)到(1),再从(1)到(y)
-
先从(x)到(n),再从(n)到(y)
-
直接从(x)到(y)
三种的必要条件分别是
-
((y-1)mod d equiv 0)
-
((n-y)mod d equiv 0)
-
(|x-y|mod d equiv 0)
所以如果上面三种都不满足的话就输出(-1)
不然就取最小的输出
# include <bits/stdc++.h>
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int n, x, y, d;
scanf("%d%d%d%d", &n, &x, &y, &d);
int ans = 0x7f7f7f7f;
if(abs(x - y) % d == 0)
ans = abs(x - y) / d;
if((y - 1) % d == 0)
ans = std::min(ans, (x - 1) / d + bool((x - 1) % d) + (y - 1) / d);
if ((n - y) % d == 0)
ans = std::min(ans, (n - x) / d + bool((n - x) % d) + (n - y) / d);
if(ans == 0x7f7f7f7f)
{
printf("-1
");
continue;
}
printf("%d
", ans);
}
return 0;
}
题解 CF1082B 【Vova and Trophies】
(B)比(A)水qwq
这题，对每一个''(G)''，求它这一块的左边界和右边界
然后对于每一个''(S)''，求一下他左边那块的大小，右边那块的大小，再判断一下他能不能把两块连在一起，不能就取大的那块，做完了
#include <bits/stdc++.h>
using std::string;
const int MaxN = 100010;
int a[MaxN];
int l[MaxN], r[MaxN];
int main()
{
int n;
string s;
scanf("%d", &n);
std::cin >> s;
int len = s.length();
int sum = 0, ans = 0;
for (int i = 0; i < len; i++)
a[i + 1] = s[i] == 'S' ? 0 : 1, sum += a[i + 1];
if (sum == 0)
return printf("0") * 0;
if (sum == n)
return printf("%d
", n) * 0;
for (int i = 1; i <= n; i++)
{
if (a[i] == 1 && a[i - 1] == 1)
l[i] = l[i - 1];
else
l[i] = i;
}
for (int i = n; i >= 1; i--)
{
if (a[i] == 1 && a[i + 1] == 1)
r[i] = r[i + 1];
else
r[i] = i;
}
for (int i = 1; i <= n; i++)
{
if (a[i] == 0)
{
int tmp = 0;
if (a[i - 1])
tmp += r[i - 1] - l[i - 1] + 1;
if (a[i + 1])
tmp += r[i + 1] - l[i + 1] + 1;
if(tmp == sum)
ans = std::max(ans, tmp);
if (tmp < sum)
ans = std::max(ans, tmp + 1);
if (a[i - 1] && r[i - 1] - l[i - 1] + 1 < sum)
ans = std::max(r[i - 1] - l[i - 1] + 2, ans);
if (a[i + 1] && r[i + 1] - l[i + 1] + 1 < sum)
ans = std::max(r[i + 1] - l[i + 1] + 2, ans);
}
}
printf("%d
", ans);
return 0;
}
题解 CF1082C 【Multi-Subject Competition】
这个(C)好难啊
这是道前缀和好题
首先，读入后，把每一个分数扔进相应学科的桶
然后贪心地对每个桶排序
然后对于每一个桶，求前缀和，如果大于(0)，就加到对应的(ans[i])中((ans[i])记录的是每个学科(i)个人的最大得分)
最后输出
[max_{1<=i<=n}{ans[i]}
]
#include <bits/stdc++.h>
# define int long long
using std::vector;
const int MaxN = 100010;
int ans;
int sum[MaxN];
vector<int> v[MaxN];
int s[MaxN], rank[MaxN];
int cmp(int a, int b) { return a > b; }
signed main()
{
int n, m, maxn = 0;
scanf("%I64d%I64d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%I64d%I64d", &s[i], &rank[i]);
v[s[i]].push_back(rank[i]);
maxn = std::max(rank[i], maxn);
}
if (maxn == 0)
return 0 * printf("0
");
for (int i = 1; i <= m; i++)
{
if (v[i].size())
std::sort(v[i].begin(), v[i].end(), cmp);//排序
}
for(int i = 1; i <= m; i++)
{
int tmp = 0;
for(int j = 0; j < v[i].size(); j++)
{
tmp += v[i][j];
if(tmp <= 0)
break;
sum[j + 1] += tmp;//前缀和
}
}
printf("%d", *std::max_element(sum + 1, sum + n + 1));
return 0;
}