A - Beginning
签到.
#include <bits/stdc++.h>
using namespace std; int main()
{
int a[];
while (scanf("%d", a) != EOF)
{
for (int i = ; i < ; ++i) scanf("%d", a + i);
sort(a, a + );
int res = ;
for (int i = ; i < ; ++i) res = res * + a[i];
puts(res == ? "YES" : "NO");
}
return ;
}
B - KEYENCE String
签
#include <bits/stdc++.h>
using namespace std; string s; string get(int pos)
{
string res = "";
for (int i = ; i <= pos; ++i) res += s[i];
int len = s.size();
for (int i = len - ( - pos - ); i < len; ++i) res += s[i];
return res;
} bool work()
{
for (int i = ; i < ; ++i)
{
string tmp = get(i);
if (tmp == "keyence") return ;
}
return ;
} int main()
{
while (cin >> s) puts(work() ? "YES" : "NO");
return ;
}
C - Exam and Wizard
Solved.
题意：
给出些个数字$A_i, 和 B_i$
要求构造$C_i 使得 C_i >= B_i 并且 \sum A_i = \sum C_i$
并且使得变动的数字个数最少
思路：
先弄出不足的部分，然后取差值最大的$A_i > B_i$ 的部分用堆维护，每次取最大的贡献出来补充
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define ll long long
int n, a[N], b[N]; int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", a + i);
for (int i = ; i <= n; ++i) scanf("%d", b + i);
ll need = ;
priority_queue <int, vector <int>, less <int> > pq;
int res = ;
for (int i = ; i <= n; ++i)
{
if (b[i] > a[i]) need += b[i] - a[i], ++res;
else if (b[i] < a[i]) pq.push(a[i] - b[i]);
}
while (!pq.empty() && need > )
{
int top = pq.top(); pq.pop();
need -= top; ++res;
}
if (need > ) puts("-1");
else printf("%d\n", res);
}
return ;
}
D - Double Landscape
Upsolved.
题意：
在$n * m的矩阵中填数，每行中最大的数为a_i, 每列中最大的数为b_i$
求填数方案
思路：
对于某个数$x$
如果它存在于多个$a_i 中 或者多个 b_i 中 $
那么无解
再考虑
它既存在于$a_i 也存在于 b_i 中
那么它的位置是确定的$
它只存在于某个$a_i或者某个b_i中$
那么它的方案数就是那一列或者那一行的$a_i$比它大的数的个数
它不存在于某个$a_i或者某个b_i中$
那么它的方案数是 $a_i > a_x 的个数 \cdot b_i > b_x的个数$
但是要减去比它大的数的个数
因为它能填的位置，比它大的数都能填，而且是子集关系
所以要让出一位
但是对于第二种情况不用考虑，因为第二种情况的那个数肯定是当前行或者当前列最大的
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 1100
const ll MOD = (ll)1e9 + ;
int n, m, a[N], b[N]; bool check()
{
for (int i = ; i <= n; ++i) for (int j = i + ; j <= n; ++j)
if (a[i] == a[j]) return false;
for (int i = ; i <= m; ++i) for (int j = i + ; j <= m; ++j)
if (b[i] == b[j]) return false;
return true;
} int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", a + i);
for (int i = ; i <= m; ++i) scanf("%d", b + i);
sort(a + , a + + n);
sort(b + , b + + m);
if (!check()) puts("");
else
{
a[n + ] = n + ;
b[m + ] = m + ;
int l[] = {, };
ll res = ;
for (int i = ; i <= n * m; ++i)
{
while (l[] <= n && a[l[]] < i) ++l[];
while (l[] <= m && b[l[]] < i) ++l[];
ll d = ;
if (a[l[]] == i && b[l[]] == i)
d = ;
else if (a[l[]] == i && b[l[]] != i)
d = m - l[] + ;
else if (b[l[]] == i && a[l[]] != i)
d = n - l[] + ;
else
d = (m - l[] + ) * (n - l[] + ) - (n * m - i);
res = (res * d) % MOD;
}
printf("%lld\n", res);
}
}
return ;
}
E - Connecting Cities
Upsolved.
题意：
$n个城市，两个城市之间的边权是 |i - j| \cdot D + A_i + A_j$
求最小生成树
思路：
考虑将区间分成两部分
分别为$[l, mid] 和 [mid +1, r]$
考虑
左区间为$f[i] = a[i] - d * i$
右区间为$g[i] = a[i] + d * j$
令$f[0] 和 g[0] 为 Min(f[i]), g[0] 为 Min(g[i])$
那么我们将$(i, j_0), (i_0, j), (i_0, j_0) 连边$
我么考虑$(i, j)这种边一定比上面三种边的边权要大$
那么假设我们需要$(i, j)这种边来增加连通性，那么上面那三种边必定能满足$
所以分治建边 一共有$NlogN级别的边数 $
再做MST
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 200010
#define INFLL 0x3f3f3f3f3f3f3f3f
int n, m;
ll d, a[N];
struct Edge
{
int u, v; ll w;
Edge() {}
Edge(int u, int v, ll w) : u(u), v(v), w(w) {}
bool operator < (const Edge &other) const { return w < other.w; }
}edge[N * ]; void add(int l, int r)
{
if (l == r) return;
int mid = (l + r) >> ;
ll Min = INFLL; int pos = -;
for (int i = l; i <= mid; ++i)
{
ll f = a[i] - d * i;
if (f < Min)
{
Min = f;
pos = i;
}
}
for (int i = mid + ; i <= r; ++i)
edge[++m] = Edge(pos, i, a[pos] + a[i] + d * (i - pos));
Min = INFLL; pos = -;
for (int i = mid + ; i <= r; ++i)
{
ll f = a[i] + d * i;
if (f < Min)
{
Min = f;
pos = i;
}
}
for (int i = l; i <= mid; ++i)
edge[++m] = Edge(pos, i, a[pos] + a[i] + d * (pos - i));
add(l, mid);
add(mid + , r);
} int pre[N];
int find(int x) { return pre[x] == ? x : pre[x] = find(pre[x]); }
ll Kruskal()
{
memset(pre, , sizeof pre);
sort(edge + , edge + + m);
int cnt = ;
ll res = ;
for (int i = ; i <= m; ++i)
{
int u = edge[i].u, v = edge[i].v; ll w = edge[i].w;
int fu = find(u), fv = find(v);
if (fu == fv) continue;
pre[fu] = fv;
res += w;
++cnt;
if (cnt == n) return res;
}
return res;
} int main()
{
while (scanf("%d%lld", &n, &d) != EOF)
{
m = ;
for (int i = ; i <= n; ++i) scanf("%lld", a + i);
add(, n);
printf("%lld\n", Kruskal());
}
return ;
}
法二：
按$a_i大小排序$
每次对于当前$x, 在所有a_j <= a_x的 城市当中，对于在它两侧的，各选出一条最短边连边$
为什么这样贪心是对的
我们考虑假如存在一个城市$z\; a_z < a_i, 并且假设最短边的城市是y$
那么$(x, y) 和 (y, z) 都小于 (x, z)$
所以$(x, z)这条边一定不在MST中$
考虑这样证明
$dist(x, y) < dist(x, z) 非常显然$
考虑$dist(y, z) < dist(x, z)$
首先假设$z < y < x$
$dist(y, z) = a_y +a_z + d * (y - z)$
$dist(x, z) = a_x + a_z + d * (x - z)$
$dist(x, z) - dist(y, z) = a_x - a_y + d * (x - y) >= 0$
得证
再考虑$y < z < x$
$dist(x, y) = a_x + a_y + d * (x - y)$
$dist(z, y) = a_z + a_y + d * (z - y)$
$dist(x, y) - dist(z, y) = a_x - a_z + d * (x - z) >= 0$
又因为 $dist(x, y) <= dist(x, z)$
所以$dist(x, z) >= dist(x, y) >= dist(z, y)$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 200010
#define INFLL 0x3f3f3f3f3f3f3f3f
int n, m;
ll d;
struct node
{
int id; ll v;
void scan(int id)
{
this->id = id;
scanf("%lld", &v);
}
bool operator < (const node &other) const { return v < other.v; }
}a[N];
struct Edge
{
int u, v; ll w;
Edge () {}
Edge (int u, int v, ll w) : u(u), v(v), w(w) {}
bool operator < (const Edge &other) const { return w < other.w; }
}edge[N << ]; struct SEG
{
struct node
{
ll Min; int pos;
node () {}
node (ll Min, int pos) : Min(Min), pos(pos) {}
void init() { Min = INFLL, pos = -; }
node operator + (const node &other) const
{
node res; res.init();
if (Min < other.Min)
{
res.Min = Min;
res.pos = pos;
}
else
{
res.Min = other.Min;
res.pos = other.pos;
}
return res;
}
}a[N << ], res;
void build(int id, int l, int r)
{
a[id].init();
if (l == r) return;
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
}
void update(int id, int l, int r, int pos, ll v)
{
if (l == r)
{
a[id] = node(v, pos);
return;
}
int mid = (l + r) >> ;
if (pos <= mid) update(id << , l, mid, pos, v);
else update(id << | , mid + , r, pos, v);
a[id] = a[id << ] + a[id << | ];
}
void query(int id, int l, int r, int ql, int qr)
{
if (qr < ql) return;
if (l >= ql && r <= qr)
{
res = res + a[id];
return;
}
int mid = (l + r) >> ;
if (ql <= mid) query(id << , l, mid, ql, qr);
if (qr > mid) query(id << | , mid + , r, ql, qr);
}
}seg[]; int pre[N];
int find(int x) { return pre[x] == ? x : pre[x] = find(pre[x]); }
ll Kruskal()
{
memset(pre, , sizeof pre);
sort(edge + , edge + + m);
int cnt = ;
ll res = ;
for (int i = ; i <= m; ++i)
{
int u = edge[i].u, v = edge[i].v; ll w = edge[i].w;
int fu = find(u), fv = find(v);
if (fu == fv) continue;
pre[fu] = fv;
++cnt;
res += w;
if (cnt == n) return res;
}
return res;
} int main()
{
while (scanf("%d%lld", &n, &d) != EOF)
{
m = ;
for (int i = ; i <= n; ++i) a[i].scan(i);
for (int i = ; i < ; ++i) seg[i].build(, , n);
sort(a + , a + + n);
for (int i = ; i <= n; ++i)
{
int u = a[i].id, v;
for (int j = ; j < ; ++j)
seg[j].res.init();
seg[].query(, , n, , u - );
seg[].query(, , n, u + , n);
for (int j = ; j < ; ++j) if (seg[j].res.pos != -)
{
v = seg[j].res.pos;
edge[++m] = Edge(u, v, a[i].v + 1ll * (j ? - : ) * d * u + seg[j].res.Min);
}
seg[].update(, , n, u, a[i].v - d * u);
seg[].update(, , n, u, a[i].v + d * u);
}
printf("%lld\n", Kruskal());
}
return ;
}