A - Peer Review
Water.
#include <bits/stdc++.h>
using namespace std; int t, n; int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = ; i <= n; ++i) printf("0%c", " \n"[i == n]);
}
return ;
}
B - Boring Game
Unsolved.
C - Enigma Machine
Unsolved.
D - Number Theory
Unsolved.
E - Chasing
Solved.
题意：两个人在一个二维平面上，刚开始两个人在第二象限或者第三象限，A跑到Y轴B就不能追了，B的速度是A的K倍，求B能否追到B
思路：k < 0 那么必然不行
k == 0 判断是不是在同一高度，如果是判断起始位置
k > 0 假设y轴上存在某个点 使得A B 能够在该点相遇，列方程求解
#include<bits/stdc++.h> using namespace std; double xa, xb, ya, yb, k; int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%lf %lf %lf %lf %lf", &xa, &ya, &xb, &yb, &k);
if(k < 1.0)
{
puts("N");
}
else if(k == 1.0)
{
if(ya != yb) puts("N");
else if(xb < xa) puts("N");
else puts("Y");
}
else
{
double a = k * k - 1.0;
double b = -2.0 * k * k * ya + 2.0 * yb;
double c = k * k * xa * xa - xb * xb + k * k * ya * ya - yb * yb;
double d = b * b - 4.0 * a * c;
if(d >= ) puts("N");
else puts("Y");
}
}
return ;
}
F - Carrot Gathering
Unsolved.
G - Virtual Singers
Upsolved.
题意：
H - How Many Palindromes
Unsolved.
题意：
有$n个A数和m个B数 m <= n，对每个B数都匹配一个A数，使得\sum_{i = 1}^{i = m} |B[i] - A[i]| 最小$
思路：
考虑费用流的思想，维护三个堆
将$A、B 数放在一起排序，然后从左往右枚举$
$如果当前数是A$
如果左边有未匹配的$B_1数，那么与之匹配即可，此操作不用考虑反悔操作$
$因为假如有另一个B_2，使得B_2 与 这个A匹配更优$
那么后面必然要有另一个$A_2 来匹配这个B_1 $
$贡献是 A_2 - B_1 + B_2 - A_1 这个式子显然小于 A_2 - B_2 + A_1 - B_1$
因为这四个数字存在大小关系
$A_2 - B_1 大于 A_2 - B_2 + A_1 - B_1$
如果左边没有未匹配的$B_1数，那么考虑B的反悔操作是否更优$
$更优的话就反悔并且将代价取反并算上A往右匹配的贡献放入堆Q_A中， 相当于反悔操作$
$如果当前数是B$
$如果左边有未匹配的A数，那么与之匹配，并且将代价取反并且算上B往右匹配的贡献放入堆Q_C中$
否则放入堆$Q_B$中表示还未匹配
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 100010
int t, n, m; ll x;
struct node
{
ll v; int Type;
node () {}
node (ll v, int Type) : v(v), Type(Type) {}
bool operator < (const node &r) const { return v < r.v; }
}arr[N << ];
priority_queue <ll, vector <ll> , greater <ll> > A, B, C; int main()
{
scanf("%d", &t);
while (t--)
{
while (!A.empty()) A.pop();
while (!B.empty()) B.pop();
while (!C.empty()) C.pop();
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i)
{
scanf("%lld", &x);
arr[i] = node(x, );
}
for (int i = ; i <= m; ++i)
{
scanf("%lld", &x);
arr[n + i] = node(x, );
}
sort(arr + , arr + + n + m);
ll res = ;
for (int i = ; i <= n + m; ++i)
{
if (arr[i].Type == )
{
if (!A.empty())
{
x = A.top(); A.pop();
res += arr[i].v + x;
C.push(-x - * arr[i].v);
}
else
B.push(-arr[i].v);
}
else
{
if (!B.empty())
{
x = B.top(); B.pop();
res += arr[i].v + x;
}
else if (!C.empty())
{
x = C.top();
if (arr[i].v + x < )
{
C.pop();
res += arr[i].v + x;
A.push(-x - * arr[i].v);
}
else
A.push(-arr[i].v);
}
else
A.push(-arr[i].v);
}
}
printf("%lld\n", res);
}
return ;
}
I - District Division
Solved.
题意：给出一棵树，求能不能分成$\frac{n}{k}$ 个连通块，使得每块个数为k
思路：如果存在合法分法，那么必然存在某个子树大小为k，DFS下去，再回溯上来判断即可，遇到大小为k的子树就分块
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + ; int n, k; int val[maxn];
int fa[maxn];
int vis[maxn];
int cnt;
vector<int>root;
vector<int>G[maxn]; void Init()
{
cnt = ;
root.clear();
for(int i = ; i <= n; ++i)
{
val[i] = vis[i] = ;
fa[i] = i;
G[i].clear();
}
} void DFS(int u, int pre)
{
val[u] = ;
fa[u] = pre;
for(int i = , len = G[u].size(); i < len; ++i)
{
int v = G[u][i];
if(v == pre) continue;
DFS(v, u);
val[u] += val[v];
}
if(val[u] == k)
{
cnt++;
val[u] = ;
root.push_back(u);
}
} void DFS2(int u, int pre)
{
if(vis[u]) return ;
vis[u] = ;
printf("%d%c", u, " \n"[cnt == k]);
cnt++;
for(int i = , len = G[u].size(); i < len; ++i)
{
int v = G[u][i];
if(v == pre) continue;
DFS2(v, u);
}
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n, &k);
Init();
for(int i = ; i < n; ++i)
{
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
DFS(, -);
if(cnt != n / k)
{
puts("NO");
continue;
}
puts("YES");
for(int i = , len = root.size(); i < len; ++i)
{
cnt = ;
DFS2(root[i], fa[root[i]]);
}
}
return ;
}
J - Good Permutation
Solved.
题意：每次能够交换相邻两个数，求最少交换次数使得满足题目给出的序列条件
思路：通过枚举每次在第一位的数，从而递推下一种状态，比如12345推出51234即加上5移到第一位的步数再减去5带来的贡献
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + ; int n;
int arr[maxn];
int pos[maxn];
int a[maxn]; int lowbit(int p)
{
return p & (-p);
} void update(int p)
{
while(p <= n)
{
a[p]++;
p += lowbit(p);
}
} int query(int p)
{
int res = ;
while(p)
{
res += a[p];
p -= lowbit(p);
}
return res;
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
ll ans = ;
for(int i = ; i <= n; ++i) a[i] = ;
for(int i = ; i <= n; ++i)
{
scanf("%d", arr + i);
pos[arr[i]] = i;
}
for(int i = n; i >= ; --i)
{
ans += query(arr[i] - );
update(arr[i]);
}
ll tmp = ans;
for(int i = ; i <= n; ++i)
{
tmp = tmp + n - pos[i] - (pos[i] - );
ans = min(ans, tmp);
}
printf("%lld\n", ans);
}
return ;
}