D1. All are Same
同余题 求所有数加上k*x之后的值相等时k的最大值 即所有数同余k相等 我们可以找到最小值 所有数减去这个最小值然后求gcd所得值即为k的最大值
为什么是减去最小值呢？ 有 a ≡ b(mod k) 等价于 (a - b) % k = 0 所有我们必须使序列所有数减去一个序列之中的数字来求gcd 减去最小值是为了使得处理后的序列中不包含负数
代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i ++ )
using namespace std;
typedef pair<int, int> PII;
const int N = 100, INF = 1e8;
inline int read()
{
register int x = 0, k = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-') k = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x * k;
}
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
void solve()
{
int n; n = read();
vector<int> a(n);
rep(i, n) a[i] = read();
vector<int> dif;
int tmp = *min_element(a.begin(), a.end());
rep(i, n) if (a[i] != tmp) dif.push_back(a[i] - tmp);
if (dif.size() == 0) {puts("-1"); return;}
int ans = dif[0];
rep(i, dif.size()) ans = gcd(ans, dif[i]);
printf("%d\n", ans);
}
int main()
{
int t;
t = read();
while (t -- )
{
solve();
}
return 0;
}
D2 - Half of Same
D2和D1相似 是要去找k使得一半以上的序列元素减去 k * x 可以相等 我们可以想到 在这个序列中随便取两个数 这两个数均是在减去最大k * x后的相等序列的可能性为四分之一 我们可以用1e3次寻找 寻找后验证是否满足题意 这一千次寻找均不满足题意的可能性为四分之三的一千次方 能看出很小了 担心会wa的话可以再搞大一点
验证是每次找到的两数之差的因数都有可能是k 所以再遍历一次k就好 如果当前k满足题意 则记录 每次求最大值
代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i ++ )
using namespace std;
typedef long long ll;
const int N = 110, INF = 1e6;
inline int read()
{
register int x = 0, k = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-') k = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x * k;
}
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int n;
int a[N];
bool check(int k)
{
map<int, int> mp;
for (int i = 1; i <= n; i ++ )
{
mp[(a[i] + (ll)k * INF) % k] ++ ;
if (mp[(a[i] + (ll)k * INF) % k] * 2 >= n) return true;
}
return false;
}
void solve()
{
n = read();
for (int i = 1; i <= n; i ++ ) a[i] = read();
sort(a + 1, a + 1 + n);
int sum = 1, flag = 0;;
for (int i = 2; i <= n; i ++ )
if (a[i] == a[i - 1])
{
sum ++ ;
if (sum * 2 >= n) flag = 1;
}
else sum = 1;
if (flag) {puts("-1"); return;}
srand(time(0));
int ans = -1;
int t = 1e3;
while (t -- )
{
int x = rand() % n + 1, y = rand() % n + 1;
int tmp = abs(a[x] - a[y]);
for (int i = 1; i * i <= tmp; i ++ )
if (tmp % i == 0)
{
if (check(i)) ans = max(ans, i);
if (check(tmp / i)) ans = max(ans, tmp / i);
}
}
printf("%d\n", ans);
}
int main()
{
int t;
t = read();
while (t -- )
{
solve();
}
return 0;
}
E. Gardener and Tree
题目为给一棵无根树 每切割一次会把所有树的最外面一圈给割掉 即把所有叶子结点全给删掉 我们可以将它看成一张拓扑图 用一个优先队列来维护每次入度为1的点 与k相比查看是否删掉
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 4e5 + 10, M = N * 2;
inline int read()
{
register int x = 0, k = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-') k = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x * k;
}
int n, k;
int h[N], e[M], ne[M], idx;
int d[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void solve()
{
n = read(), k = read();
memset(h, -1, sizeof h); idx = 0;
for (int i = 0; i < n - 1; i ++ )
{
int a, b; a = read(), b = read();
add(a, b), add(b, a);
d[a] ++, d[b] ++ ;
}
if (n == 1)
{
if (k >= 1) puts("0");
else puts("1");
return;
}
priority_queue<PII, vector<PII>, greater<PII>> Q;
for (int i = 1; i <= n; i ++ ) if (d[i] == 1) Q.push(make_pair(1, i));
int sum = 0;
while (Q.size())
{
auto t = Q.top(); Q.pop();
int from = t.second, step = t.first;
if (step > k) continue;
sum ++ ;
for (int i = h[from]; ~i; i = ne[i])
{
int to = e[i];
if ( -- d[to] == 1)
Q.push(make_pair(step + 1, to));
}
}
printf("%d\n", n - sum);
for (int i = 1; i <= n; i ++ ) d[i] = 0;
}
int main()
{
int t;
t = read();
while (t -- )
{
solve();
}
return 0;
}