题解 | #第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛I,K,L题解#
大学期末现状
https://ac.nowcoder.com/acm/contest/27302/A
大部分题解楼上的巨巨已经给出了,这里补充下I,K,L的题解
I 最大公约数(简单数论)
思路:
对任意x,若x为序列的因数,即有:
, , ..... . 那么令; 显然有
即最多可能产生的序列的因数的数量即为的不同因数个数。直接对序列求和,计算和的不同因数的个数即可。
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
void solve(ll sum)
{
ll ans = 0;
for (ll i = 1; i <= sum / i; i++)
if (sum % i == 0)
if (i * i == sum)
ans++;
else
ans += 2;
cout << ans << endl;
}
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef ak
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n;
cin >> n;
ll sum = 0;
for (int i = 1; i <= n; i++)
{
ll t;
cin >> t;
sum += t;
}
solve(sum);
return 0;
}
K 金牌厨师(二分答案+差分维护)
思路:
二分最大化可行答案,对于每次mid,差分维护判断是否存在连续长度不小于mid且人数也不小于mid的区间即可。
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
const int N = 3e5 + 10;
pll a[N];
int sum[N], n, m;
bool check(int mid)
{
memset(sum, 0, sizeof sum);
for (int i = 1; i <= m; i++)
{
int len = a[i].second - a[i].first + 1;
if (len >= mid)
{
sum[a[i].first + mid - 1]++;
sum[a[i].second + 1]--;
}
}
for (int i = 1; i <= n; i++)
{
sum[i] += sum[i - 1];
if (sum[i] >= mid)
return 1;
}
return 0;
}
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef ak
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
cin >> n >> m;
for (int i = 1; i <= m; i++)
cin >> a[i].first >> a[i].second;
int l = 1, r = n;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (check(mid))
l = mid;
else
r = mid - 1;
}
cout << l << endl;
return 0;
}
L WireConnection(最小生成树裸题)
思路:
三维上求最小生成树即可,这里给出prim算法实现
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const double eps = 1e-9;
const int N = 1e4 + 10;
ll dis[N], ans = 0, n, st[N];
struct electric
{
ll x, y, z;
} el[N];
ll calcu(int a, int b)
{
ll w = ceil(sqrt((el[a].x - el[b].x) * (el[a].x - el[b].x) + (el[a].y - el[b].y) * (el[a].y - el[b].y) + (el[a].z - el[b].z) * (el[a].z - el[b].z)));
return w;
}
void prim()
{
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
for (int i = 1; i <= n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dis[t] > dis[j]))
t = j;
ans += dis[t];
st[t] = 1;
for (int j = 1; j <= n; j++)
if (!st[j])
dis[j] = min(dis[j], calcu(j, t));
}
}
int main()
{
std::ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef ak
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
cin >> n;
for (int i = 1; i <= n; i++)
{
ll a, b, c;
cin >> a >> b >> c;
el[i] = {a, b, c};
}
prim();
cout << ans << endl;
return 0;
}