目录
按照训练赛AC先后顺序来
F
题目陈述
大意：构造一个 p e r m u t a t i o n permutation permutation，使得 p i ≡ 0 ( m o d ( p i − p i − 2 ) ) p_i \equiv 0 \pmod {(p_i - p_{i-2})} pi≡0(mod(pi−pi−2))
算法思路
- 一个数 m o d − 1 mod-1 mod−1或 1 1 1总是为0
- 构造
1，n， 2， {n - 1}， 3 ，{n - 2} ……
代码实现
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define debug(x) cerr << #x << ": " << x << '\n'
#define bd cerr << "----------------------" << el
#define el '\n'
#define cl putchar('\n')
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define loop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define ceil(a, b) (a + (b - 1)) / b
#define ms(a, x) memset(a, x, sizeof(a))
#define inf 0x3f3f3f3f
#define db double
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<db, db> PDD;
typedef vector<int> vci;
const int N = 1e5 + 10, M = 2e6 + 10, E = 1e3 + 10, md = 1e9 + 7;
const double PI = acos(-1), eps = 1e-8;
int T, n, m;
int a[N], cnt;
int main()
{
cin.tie(0);
cout.tie(0);
int c, d;
cin >> T;
while(T -- )
{
cin >> n;
cnt = 0;
c = 1, d = n;
//构造1 n 2 {n - 1} 3 {n - 2} ……
while(cnt < n)
{
cout << c << " ";
cnt ++ ;
c ++ ;
if(cnt == n)
break;
cout << d << " ";
cnt ++;
d -- ;
}
cl;
}
}
H
题目陈述
大意：给定若若干堆石头，每堆石头个数为 b i b_i bi，每次可以将一颗石头从一堆移动到另一堆，问使得所有堆的 g c d ( ) > 1 gcd()>1 gcd()>1的最小步骤，其中约定 g c d ( a , 0 ) = a gcd(a,0)=a gcd(a,0)=a
算法思路
- 设所有堆的和为 s u m sum sum
- 设最后所有的堆都是 t t t的倍数，那么 t t t一定是 s u m sum sum的约数，所以需要先质因数分解（后续也只需要判断质因数即可）
- 某个常理有， 1 e 10 1e10 1e10中拥有最多的质因子的数的 质 因 子 的 个 数 < 2 e 3 质因子的个数<2e3 质因子的个数<2e3
- 显然我们可以发现，我们调整一堆到最接近 t t t的倍数只可能取上下（刚好就不动它）
- 如果跨越了两个 t t t的倍数显然是不可能的，因为多出来的一个 t t t属于浪费的代价，完全可以在除了这一堆石头外的其他堆内调整，且代价不会更劣
- 我们设 c [ j ] = b [ j ] m o d t , s = ∑ c [ j ] c[j]=b[j] \bmod t,s=\sum c[j] c[j]=b[j]modt,s=∑c[j]，显然 s s s也是 t t t的倍数，我们现在是将所有的数字看做一堆取模后的正数，但是我们现在要把某些数字翻转掉，就是减去 t t t，即变成 c [ j ] − t c[j]-t c[j]−t
- 每有一个元素翻转一次， s s s就会减去 t t t,我们可以确定有 s / t s / t s/t 个数字需要翻转,那么剩下的和，就一定是一组合法方案
- 即选择 n − s / t n - s / t n−s/t 个数字的和，我们需要让和最小，所以我们选择翻转掉最大的
代码实现
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define debug(x) cerr << #x << ": " << x << '\n'
#define bd cerr << "----------------------" << el
#define el '\n'
#define cl putchar('\n')
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define loop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define ceil(a, b) (a + (b - 1)) / b
#define ms(a, x) memset(a, x, sizeof(a))
#define inf 0x3f3f3f3f
#define db double
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<db, db> PDD;
typedef vector<int> vci;
const int N = 1e5 + 10, M = 2e6 + 10, E = 1e3 + 10, md = 1e9 + 7;
const double PI = acos(-1), eps = 1e-8;
int T, n, m;
int b[N], cnt;
LL a[N], sum; //储存质因数
LL c[N];
void divide(LL x) //质因数分解
{
rep(i, 2, x / i)
{
if (x % i == 0) //如果是质因子
{
while (x % i == 0)
x /= i;
a[++cnt] = i;
}
}
if (x > 1) //如果x是个质数
a[++cnt] = x;
return;
}
int main()
{
cin.tie(0);
cout.tie(0);
cin >> T;
LL t;
LL s = 0, k = 0, ans = LLONG_MAX;
while (T--)
{
ans = LLONG_MAX;
sum = 0;
cin >> n;
rep(i, 1, n)
{
cin >> b[i];
sum += b[i];
}
cnt = 0;
divide(sum); //质因数分解
rep(i, 1, cnt)
{
t = a[i];
s = 0;
k = 0;
rep(j, 1, n)
{
c[j] = b[j] % t;
s += c[j];
}
sort(c + 1, c + n + 1);
//我们可以确定s一定是t的倍数
//每个数字翻转一次，s就会减去t
//我们可以确定有 s / t 个数字需要翻转
//那么剩下的和，就一定是一组合法方案
//即选择n - s / t 个数字的和
//我们需要让和最小，所以我们选择翻转掉最大的
for (int j = 1; j <= n - s / t; j++)
{
k += c[j];
}
ans = min(ans, k);
}
cout << ans << el;
}
}
M
题目陈述
- 大意：给定平面上面若干个点，求解一个圆，使得有 ⌈ N 2 ⌉ \lceil \cfrac{N}{2}\rceil ⌈2N⌉的点在该圆上（且保证一定有，多种方案输出任一）
算法思路
- 众所周知，三点确定一个圆（外接圆）
- 随机选择一个点 1 / 2 1/2 1/2的概率落在这个圆上，随机三个点都落在圆上的概率是 1 / 8 1/8 1/8，所以多 r a n d rand rand几十次几百次就行了
- 因为 r a n d o m random random只到 3 3 3万多，所以记得用 m t 19937 mt19937 mt19937
- n < = 4 n<=4 n<=4的时候，四点共线会死循环，记得特判边界，还有 n = 1 n=1 n=1的时候特判随便一个半径
- （VP的时候我身为队内唯一一个计算几何选手还是在两个队友的帮助下A的，队内吉祥物无疑了，我tcl）
代码实现
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define debug(x) cerr << #x << ": " << x << '\n'
#define bd cerr << "----------------------" << el
#define el '\n'
#define cl putchar('\n')
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define loop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define ceil(a, b) (a + (b - 1)) / b
#define ms(a, x) memset(a, x, sizeof(a))
#define inf 0x3f3f3f3f
#define db double
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<db, db> PDD;
typedef vector<int> vci;
typedef map<int, int> mii;
typedef mii::iterator mii_it;
const int N = 1e5 + 10, M = 2e6 + 10, E = 1e3 + 10, md = 1e9 + 7;
const double PI = acos(-1), eps = 1e-6;
int T, n, m;
struct Circle {
PDD p;
db r;
};
PDD q[N];
int sign(db x) {
if (fabs(x) < eps)
return 0;
if (x < 0)
return -1;
return 1;
}
db dcmp(db x, db y) {
if (fabs(x - y) < eps)
return 0;
if (x < y)
return -1;
return 1;
}
PDD operator-(PDD a, PDD b) {
return {a.x - b.x, a.y - b.y};
}
PDD operator+(PDD a, PDD b) {
return {a.x + b.x, a.y + b.y};
}
db operator*(PDD a, PDD b) {
return a.x * b.y - a.y * b.x;
}
db operator&(PDD a, PDD b) {
return a.x * b.x + a.y * b.y;
}
db get_dist(PDD a, PDD b) {
db dx = a.x - b.x;
db dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
PDD operator*(PDD p, db t) {
return {p.x * t, p.y * t};
}
PDD operator/(PDD a, db t) {
return {a.x / t, a.y / t};
}
PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w) {
auto u = p - q;
db t = w * u / (v * w);
return p + v * t;
}
PDD rotate(PDD a, db t) {
return {a.x * cos(t) + a.y * sin(t), -a.x * sin(t) + a.y * cos(t)};
}
pair<PDD, PDD> get_line(PDD a, PDD b) {
return {(a + b) / 2, rotate(b - a, PI / 2)};
}
Circle get_circle(PDD a, PDD b, PDD c) {
auto u = get_line(a, b), v = get_line(a, c);
auto p = get_line_intersection(u.x, u.y, v.x, v.y);
return {p, get_dist(p, a)};
}
int main() {
Circle p ;
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed); // 大随机数
cin.tie(0);
cout.tie(0);
int i1, i2, i3, cnt;
cin >> T;
int k;
while (T--) {
cin >> n;
rep(i, 1, n)
cin >> q[i].x >> q[i].y;
if(n == 1)
{
p.p = {q[1].x + 1,q[1].y};
p.r = 1;
printf("%.6lf %.6lf %.6lf\n", p.p.x, p.p.y, p.r);
continue;
}
else if(n <= 4){ //四点共线的情况
p = {(q[1] + q[2]) / 2, get_dist(q[1], q[2]) / 2};
printf("%.6lf %.6lf %.6lf\n", p.p.x, p.p.y, p.r);
continue;
}
//每个点在圆上的概率是1 / 2
// 1 / 8的概率可以三个点都在圆上
// 多随机几次总会有一发
while (1) {
//每次随机选取三个点
//有
i1 = rnd() % n + 1;
do {
i2 = rnd() % n + 1;
} while (i2 == i1);
do {
i3 = rnd() % n + 1;
} while (i3 == i1 || i3 == i2);
p = get_circle(q[i1], q[i2], q[i3]);
//三点确定一个外接圆
//三点共线，叉积为0，重新选择
if(sign((q[i1] - q[i2]) * (q[i1] - q[i3])) == 0)
continue;
cnt = 0;
rep(i, 1, n) {
if(dcmp(get_dist(p.p, q[i]),p.r) == 0) {
cnt ++ ;
}
}
if(cnt >= (n + 1) / 2) {
printf("%.6lf %.6lf %.6lf\n", p.p.x, p.p.y, p.r);
break;
}
}
}
}
B
题目陈述
- 将 a [ ] a[] a[]数组中，任意一个长度大于 k k k的子串，的第 k k k大的数放入 b [ ] b[] b[]数组中(不去重)，求解 b b b数组中第 m m m大的数
算法思路
- 尺取法+二分答案
- 二分第 m m m大的数的值 m i d mid mid，如果 b [ ] b[] b[]数组中比 m i d mid mid大的值 < m <m <m则说明 m i d mid mid比答案大需要减小右边界，反之增大
- 那接下来的问题就是如何用尺取法计算 b [ ] b[] b[]数组中比 m i d mid mid大的值
- 定义左边界 i i i和右边界 j j j， s u m sum sum记录当前区间比 m i d mid mid大的数的个数， a n s ans ans记录函数的答案
- 先将长度达到
k
k
k，再继续增加
s
u
m
sum
sum，直至
s
u
m
=
k
sum=k
sum=k，此时后面的所有区间的
[
i
,
k
]
,
k
∈
[
j
+
1
,
n
]
[i,k],k\in [j + 1, n]
[i,k],k∈[j+1,n]，取出的第
k
k
k大的数字都
>
m
i
d
>mid
>mid，所以这些数在
b
[
]
b[]
b[]中一定大于
m
i
d
mid
mid，此时
ans+=n-j+1 - 注意枚举右指针时， j < n j<n j<n，且增加 i i i时候，记得根据 a [ i ] a[i] a[i]是否 > m i d >mid >mid来判断 s u m sum sum是否需要减1
代码实现
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define debug(x) cerr << #x << ": " << x << '\n'
#define bd cerr << "----------------------" << el
#define el '\n'
#define cl putchar('\n')
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define loop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define ceil(a, b) (a + (b - 1)) / b
#define ms(a, x) memset(a, x, sizeof(a))
#define inf 0x3f3f3f3f
#define db double
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<db, db> PDD;
typedef vector<int> vci;
typedef map<int, int> mii;
typedef mii::iterator mii_it;
const int N = 1e5 + 10, M = 2e6 + 10, E = 1e3 + 10, md = 1e9 + 7;
const double PI = acos(-1), eps = 1e-6;
LL a[N], n, k, m;
LL check(int mid) //尺取法判断
{
LL j = 0, sum = 0, ans = 0;
// j代表右指针，sum代表当前区间中大于mid的元素个数
for (int i = 1; i <= n; i++)
{
//如果区间长度<k，并且下标还没有越界
while (j - i + 1 < k && j < n)
{
j++;
if (a[j] > mid)
sum++; //比 mid大的数加一
}
while (sum < k && j < n) //区间长度从k继续增加
{
j++;
if (a[j] > mid)
sum++;
}
if (sum < k) //说明j==n的时候sum都<k
break;//则接下来没有任何一个区间会有贡献
ans += (n - j + 1); //[i,k], 其中k in [j + 1, n]
//这些区间的k th 都必然 > mid
if (a[i] > mid) //下一个区间不包括这个i位置
sum--;
}
return ans; //比mid大的b数组元素个数
}
int main()
{
cin.tie(0);
cout.tie(0), cin.sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
cin >> n >> k >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
int str = 0, end = 1e9;
while (str <= end) //二分答案
{
int mid = (str + end) / 2;
if (check(mid) < m) //长度大于k的区间中，比mid大元素的数量<m
{//这样的方案才合法,才有可能是答案
end = mid - 1;
}
else
{
str = mid + 1;
}
}
cout << str << endl;
}
}