| A | Heavy Rotation |
水题
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n;
inline void solve()
{
cin >> n;
puts((n
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
| B | Trapezoid Sum |
水题
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n;
unsigned ll ans;
unsigned ll f(unsigned ll x) { return x * (x + 1) / 2; }
inline void solve()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
ll l, r;
cin >> l >> r;
ans += f(r) - f(l - 1);
}
cout << ans << '\n';
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
| C | Collinearity |
水题。用叉积判一下就行。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n;
pair<ll, ll> p[N];
bool check(int i, int j, int k)
{
pair<ll, ll> v1 = mp(p[i].first - p[j].first, p[i].second - p[j].second);
pair<ll, ll> v2 = mp(p[j].first - p[k].first, p[j].second - p[k].second);
if(v1.first * v2.second - v1.second * v2.first == 0)
return 1;
return 0;
}
inline void solve()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> p[i].first >> p[i].second;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
for (int k = j + 1; k <= n; ++k)
{
if(check(i,j,k))
return puts("Yes"), void();
}
puts("No");
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
| D | Hachi |
注意到 $1000 \bmod 8 = 0$，那么实际上我们只需要注重最后三位的数字就可以了。只需要枚举 8 的倍数，直到这个数大于 3 位为止就行。
不过要注意 $n\le 2$ 的时候特判一下。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n;
char s[N];
int cnt[15];
inline void solve()
{
scanf(
n = strlen(s);
for (int i = 0; i < n; ++i)
cnt[s[i] - '0']++;
if (n == 1)
{
return puts((cnt[8]) ? "Yes" : "No"), void();
}
if (n == 2)
{
for (int d = 2;; ++d)
{
int now = d * 8;
if (now > 100)
break;
int need[15] = {0};
while (now)
{
need[now
now /= 10;
}
bool yes = 1;
for (int i = 0; i <= 9; ++i)
if (need[i] > cnt[i])
yes = 0;
if (yes)
return puts("Yes"), void();
}
return puts("No"), void();
}
if (n >= 3)
{
for (int d = 13;; ++d)
{
int now = d * 8;
if (now > 1000)
break;
int need[15] = {0};
while (now)
{
need[now
now /= 10;
}
bool yes = 1;
for (int i = 0; i <= 9; ++i)
if (need[i] > cnt[i])
yes = 0;
if (yes)
return puts("Yes"), void();
}
return puts("No"), void();
}
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
| E | Transformable Teacher |
首先把 h 从小到大排序，显然最优解就是相邻两个人配对。将自己插进队之后方案是唯一的，接下来就观察答案的贡献部分。因为是相邻两个人配对，我们插进去之后实际上只会改变相邻的贡献，插入位置之前以及之后的配对情况不会改变，但是前面与后面的奇偶性不一样。所以我们记录两个前缀和，一个是偶数坐标的，一个是奇数坐标的，然后二分查找当前 $W_i$ 对应的应该插入的位置，之后三个部分分别计算即可。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n, m;
int h[N], w[N];
int ans = inf;
int sum1[N], sum2[N];
inline void solve()
{
scanf(
for (int i = 1; i <= n; ++i)
scanf(
for (int i = 1; i <= m; ++i)
scanf(
sort(h + 1, h + n + 1);
for (int i = 1, j = 2; i <= n; i += 2, j += 2)
{
sum1[i] = sum1[max(i - 2, 0)] + h[i + 1] - h[i];
sum2[j] = sum2[j - 2] + h[j + 1] - h[j];
}
for (int i = 1; i <= m; ++i)
{
int pos = lower_bound(h + 1, h + n + 1, w[i]) - h;
int tmp = 0;
if (pos & 1)
{
tmp += h[pos] - w[i];
tmp += sum1[pos - 2];
tmp += sum2[n - 1] - sum2[pos - 1];
}
else
{
tmp += w[i] - h[pos - 1];
tmp += sum1[pos - 3];
tmp += sum2[n - 1] - sum2[pos - 2];
}
ans = min(ans, tmp);
}
cout << ans << '\n';
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
| F | Silver Woods |
套路题。显然答案是有单调性的，我们二分当前答案 $r$，接下来考虑怎么 check。
可以发现，两点的距离如果大于等于这个圆的直径的话，那么这个圆就可以穿过这两个点中间。而对于点到边界的话就是做一条垂线即可。
假设两点之间的距离小于直径，可以认为这两个点之间有一堵“墙”，总之圆是无法穿过去的。那么我们枚举所有的点对，如果这个点对间的距离小于直径，就将这两个点放入一个集合内。以及把上下边界分别看成两个点，距离就是垂线长度。如果上下边界在一个集合内的话，就相当于有一堵连续的墙连接了上下边界，这样这个圆就永远过不去了。上面就是check过程。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n;
pair<double, double> p[N];
int f[N];
int Find(int x) { return x == f[x] ? x : f[x] = Find(f[x]); }
void Union(int x, int y)
{
int fx = Find(x), fy = Find(y);
if (fx != fy)
f[fy] = fx;
}
bool check(double r)
{
for (int i = 1; i <= n + 2; ++i)
f[i] = i;
for (int i = 1; i <= n; ++i)
{
if (fabs(p[i].second - 100) < r * 2)
Union(i, n + 1);
if (fabs(p[i].second + 100) < r * 2)
Union(i, n + 2);
}
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
{
if (hypot(p[i].first - p[j].first, p[i].second - p[j].second) < 2 * r)
{
Union(i, j);
}
}
return Find(n + 1) != Find(n + 2);
}
inline void solve()
{
scanf(
for (int i = 1; i <= n; ++i)
scanf(
double l = 0, r = 100.0;
int cnt = 0;
while ((cnt++) < 50)
{
double mid = (l + r) / 2;
if (check(mid) == 0)
r = mid;
else
l = mid;
}
printf(
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
Comments NOTHING