T1 队列变换
Description
FJ打算带他的N(1 <= N <= 30,000)头奶牛去参加一年一度的“全美农场主大奖赛”。在这场比赛中，每个参赛者都必须让他的奶牛排成一列，然后领她们从裁判席前依次走过。
今年，竞赛委员会在接受队伍报名时，采用了一种新的登记规则：他们把所有队伍中奶牛名字的首字母取出，按它们对应奶牛在队伍中的次序排成一列（比如说，如果FJ带去的奶牛依次为Bessie、Sylvia、Dora，登记人员就把这支队伍登记为BSD）。登记结束后，组委会将所有队伍的登记名称按字典序升序排列，就得到了他们的出场顺序。
FJ最近有一大堆事情，因此他不打算在这个比赛上浪费过多的时间，也就是说，他想尽可能早地出场。于是，他打算把奶牛们预先设计好的队型重新调整一下。
FJ的调整方法是这样的：每次，他在原来队列的首端或是尾端牵出一头奶牛，把她安排到新队列的尾部，然后对剩余的奶牛队列重复以上的操作，直到所有奶牛都被插到了新的队列里。这样得到的队列，就是FJ拉去登记的最终的奶牛队列。
接下来的事情就交给你了：对于给定的奶牛们的初始位置，计算出按照FJ的调整规则所可能得到的字典序最小的队列。Input
* 第1行: 一个整数：N
* 第2..N+1行: 第i+1行仅有1个'A'..'Z'中的字母，表示队列中从前往后数第i头奶牛名字的首字母Output
* 第1..??行: 输出FJ所能得到的字典序最小的队列。每行（除了最后一行）输出恰好80个'A'..'Z'中的字母，表示新队列中每头奶牛姓名的首字母
Sample Input
6 A C D B C BSample Output
ABCBCDData Constraint
Hint
【样例解释】
操作数 原队列 新队列 #1 ACDBCB #2 CDBCB A #3 CDBC AB #4 CDB ABC #5 CD ABCB #6 D ABCBC #7 ABCBCD
题目很简单，就是：
输出FJ所能得到的字典序最小的队列。每行（除了最后一行）输出恰好80个'A'..'Z'中的字母，表示新队列中每头奶牛姓名的首字母
QWQ！！！
考试时想到了暴力做法，即两端判断，取比较小的一端，这样就可以保证字典序最小，可是当遇到如题目样例一样的出现了两个 C 的话，就要往下再判断一位了。（题目的样例输入）例如当前考虑到第2位与第 5 位，这两个都是 C，那我们往下一位，判断第 3 位和第 4 位，第 4 位的 B 大一点，我们选择它。
这样的做法最坏是 \(O(n^2)\) ，例如 30000 个 A。我考试时想到了 记忆化，也就是往下判断一位时把这个结果用 hash 储存，最后就可以节省时间。同时，我考试时写了把相同且重复的部分储存起来。
正解是优化 “当两端是一致时，往下判断一位” 。能否把两端相同的部分跳过呢？跳过就是先二分相同区间长度，然后判断是否相同（二分条件）。
怎么判是否相同呢？还是 hash，建一个正向 hash 和反向 hash ，然后跑一遍字符串哈希判断就行了，哈希不多叙述。
这样一看真的很简单，主要是要认真读题！！！
#include <cstdio>
#define P 98244353
#define ll long long
#define base 131
ll n;
char ch[10];
char s[500010];
char ans[500010];
ll hash1[500010];
ll hash2[500010];
ll bas[500010];
bool check(ll l, ll r, ll len) {
ll x = (hash1[l + len - 1] - hash1[l - 1] * bas[len] %P+P)%P;
ll y = (hash2[r - len + 1] - hash2[r + 1] * bas[len]%P+P)%P;
return x==y;
}
ll solve(ll x, ll y) {
ll l = 1, len = 1;
ll r = (y - x + 1) >> 1;
while(l <= r) {
ll mid = (l + r) >> 1;
if(check(x, y, mid)) {
len = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return len;
}
int main() {
// freopen("data.in", "r", stdin);
scanf("%lld", &n);
for(ll i = 1; i <= n; i ++) {
scanf("%s", ch+1);
s[i] = ch[1];
}
bas[0] = 1;
for(ll i = 1; i <= n; i++) {
hash1[i] = (hash1[i - 1] * base + s[i])%P;
bas[i] = (bas[i - 1] * base)%P;
}
for(ll i = n; i >= 1; i--) {
hash2[i] = (hash2[i + 1] * base + s[i])%P;
}
ll l = 1, r = n;
for(ll i = 1; i < n; i++) {
if (s[l] < s[r]) {
ans[i] = s[l++];
} else if (s[r] < s[l]) {
ans[i] = s[r--];
} else {
ll len = solve(l, r);
if(s[l + len] < s[r - len]) {
ans[i] = s[l++];
} else {
ans[i] = s[r--];
}
}
}
ans[n] = s[l];
for(ll i = 1; i <= n; i++) {
putchar(ans[i]);
if(i % 80 == 0) {
putchar('\n');
}
}
}
T2 挑剔的美食家
Description
与很多奶牛一样，Farmer John那群养尊处优的奶牛们对食物越来越挑剔，随便拿堆草就能打发她们午饭的日子自然是一去不返了。现在，Farmer John不得不去牧草专供商那里购买大量美味多汁的牧草，来满足他那N(1 <= N <= 100,000)头挑剔的奶牛。
所有奶牛都对FJ提出了她对牧草的要求：第i头奶牛要求她的食物每份的价钱不低于A_i(1 <= A_i <= 1,000,000,000)，并且鲜嫩程度不能低于B_i(1 <= B_i <= 1,000,000,000)。商店里供应M(1 <= M <= 100,000)种不同的牧草，第i种牧草的定价为C_i(1 <= C_i <= 1,000,000,000)，鲜嫩程度为D_i (1 <= D_i <= 1,000,000,000)。
为了显示她们的与众不同，每头奶牛都要求她的食物是独一无二的，也就是
说，没有哪两头奶牛会选择同一种食物。
Farmer John想知道，为了让所有奶牛满意，他最少得在购买食物上花多少
钱。Input
* 第1行: 2个用空格隔开的整数：N 和 M
* 第2..N+1行: 第i+1行包含2个用空格隔开的整数：A_i、B_i
* 第N+2..N+M+1行: 第j+N+1行包含2个用空格隔开的整数：C_i、D_iOutput
* 第1行: 输出1个整数，表示使所有奶牛满意的最小花费。如果无论如何都无法满足所有奶牛的需求，输出-1
Sample Input
4 7 1 1 2 3 1 4 4 2 3 2 2 1 4 3 5 2 5 4 2 6 4 4Sample Output
12Data Constraint
Hint
输出说明:
给奶牛1吃价钱为2的2号牧草，奶牛2吃价钱为4的3号牧草，奶牛3分到价钱
为2的6号牧草，奶牛4选择价钱为4的7号牧草，这种分配方案的总花费是12，为
所有方案中花费最少的。
比赛时想到了贪心，肯定是给要求最高的先挑，这很显然（其实就是不会证）。
然后我们把草和牛放在一起排序，这里以鲜嫩值排序，如果是草，那就放进一个地方，如果是牛，那么就获取比它要价的后继草（就是比这头牛的要价高且距离最近的草），因为鲜嫩值不影响答案，所以没有限制条件。
为什么不能按价格排序，因为价格影响最小值，所以我们搜索后继时要把价格和鲜嫩值一起搜索，这个……我不会！
那么有什么数据结构能找到后继呢？我们想到了两个：
- 平衡树，这里不多叙述。
- 权值线段树，我们找到最左边那个草就可以了。
数据结构要学好。
#include <bits/stdc++.h>
#define solve(l, r) sort(c + l, c + l + r, cmp)
std::multiset<long long> s;
using namespace std;
#define ll long long
struct node {
ll a, b;
bool isCow;
} c[200010];
ll n, m;
ll ans;
bool cmp(node x, node y) {
if(x.b == y.b) return x.a > y.a;
return x.b > y.b;
}
int main() {
scanf("%lld %lld", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%lld %lld", &c[i].a, &c[i].b);
c[i].isCow = true;
}
for(int i = 1; i <= m; i++) {
scanf("%lld %lld", &c[i + n].a, &c[i + n].b);
c[i + n].isCow = false;
}
solve(1, n + m);
for(int i = 1; i <= n + m; i++) {
if(c[i].isCow) {
auto it = s.lower_bound(c[i].a);
if(s.empty() || it == s.end()) {
printf("-1");return 0;
}
ans += *it;
s.erase(it);
} else {
s.insert(c[i].a);
}
}
printf("%lld", ans);
}
T3 三角形计数
Description
给定n个点的坐标(0<=xi,yi<=10000)求选出任意三个点能组成的三角形的总面积。
Input
第一行n表示点数。接下来每行两个数xi,yi表示点的坐标。
Output
一行一个浮点数保留一位小数表示面积和。
Sample Input
5 0 0 1 2 0 2 1 0 1 1Sample Output
7.0Data Constraint
Hint
比赛时框的一下：海伦公式！
……我谢谢你。
前置芝士：向量的叉积
我们知道二维叉积的绝对值表示两个向量张成的平行四边形的面积。即：
\[S=\frac{1}{2}\vec{AB}\times\vec{AC} \]为什么要用叉积呢？因为：叉积的公式：
\[\vec{AB}\times\vec{AC}=x_1y_2-x_2y_1 \]假如我们添加点 \(D\) ，如：
\[\vec{AB}\times\vec{AC} + \vec{AB}\times\vec{AD}=x_1y_2-x_2y_1+x_1y_3-x_3y_1 \]欸，因为 \(\vec{AB}\) 是确定的那个的边，所以我们可以很容易计算出这个算式的结果：
\[\vec{AB}\times\vec{AC} + \vec{AB}\times\vec{AD}=x_1y_2-x_2y_1+x_1y_3-x_3y_1=x_1(y_2+y_3)-y1(x_2+x_3) \]说完了叉积的优点，我们来说怎么做这道题：
我们先要枚举上面的 \(A\) 点，在枚举前，我们先给 \(A\) 点排序。原因下面再说（问题1）。
现在我们选择一个 \(A\) 点，然后选择比它高的第二个点 \(B\) 点。因为排过序，我们就可以确保 $B_y \ge A_x $，两点之间的关系就可以确定了（为什么要确定，因为叉积有正负性，如果不确定关系，你不知道是正还是负），同时可以防止重复计算。问题1解决。
这是就会有人说了，加个绝对值(abs)不就好了？！这个问题之后再说（问题2）。
我们枚举 \(B\) 点做什么？！当然是把它位移到以 \(A\) 为原点的中心啦。因为叉积中的坐标都是以 \(A\) 为基准的。
怎么位移？\(B_{\text{新}x}=B_x-A_x\)
枚举 \(B\) 点还有一件事，就是计算出斜率，按斜率排序（问题3）
枚举完 \(B\) 点后再枚举 \(C\) 点，做什么？当然是计算面积了。因为再问题3中我们按斜率排序了，那么 \(\vec{AB}\) 和 \(\vec{AC}\) 的关系也就找到了，不会出现负数。同时可以防止重复计算。问题3解决。我们定义 \(S_x=x_2,S_y=y_2\) ，因为叉积是可以通过乘法分配律累加的，所以我们可以用 \(S\) 累加。
因为为了防止重复计算，我们枚举 \(C\) 到下标 \(i\) 时，点 \(B\) 只能从下标 1 到 \(i-1\) 。即我们有下表：
| 枚举到点C | 点B计算 | 叉积和 | 叉积和化简 |
|---|---|---|---|
| 2 | 1 | \(x_1y_2-x_2y_1\) | \(x_1y_2-x_2y_1\) |
| 3 | 1，2 | \(x_1y_2-x_2y_1+x_1y_3-x_3y_1\) | \(x_1(y_2+y_3)-y_1(x_2+x_3)\) |
| 4 | 1，2，3 | \(x_1y_2-x_2y_1+x_1y_3-x_3y_1+x_1y_4-x_4y_1\) | \(x_1(y_2+y_3+y_4)-y_1(x_2+x_3+x_4)\) |
我们枚举完点 \(C_i\) 时，我们就可以给 \(S\) 累加上这一轮的结果
最后再说问题2，因为我们需要累加 \(S\) ，有可能这一轮的 \(x\) 或 \(y\) 有负，那么会给 \(S\) 进行抵消，就混乱了。
#include <cstdio>
#include <cmath>
#define ll long long
ll n;
long double ans;
struct POINT {
ll x, y;
} a[3010], a_[3010]; // 归并用，下同
struct VEC {
ll x, y;
long double k; // 斜率，按斜率排序，防止算多
} g[3010], g_[3010];
// 排序
void solve_a(ll l, ll r) {
if(l == r) return;
ll mid = (l + r) >> 1;
solve_a(l, mid);
solve_a(mid + 1, r);
ll pos1 = l, pos2 = mid + 1;
for(ll i = l; i <= r; i++) {
if(pos2 > r || (pos1 <= mid && a[pos1].y > a[pos2].y)) {
a_[i] = a[pos1];
pos1++;
} else {
a_[i] = a[pos2];
pos2++;
}
}
for(ll i = l; i <= r; i++) {
a[i] = a_[i];
}
}
void solve_g(ll l, ll r) {
if(l == r) return;
ll mid = (l + r) >> 1;
solve_g(l, mid);
solve_g(mid + 1, r);
ll pos1 = l, pos2 = mid + 1;
for(ll i = l; i <= r; i++) {
if(pos2 > r || (pos1 <= mid && g[pos1].k < g[pos2].k)) {
g_[i] = g[pos1];
pos1++;
} else {
g_[i] = g[pos2];
pos2++;
}
}
for(ll i = l; i <= r; i++) {
g[i] = g_[i];
}
}
int main() {
scanf("%lld", &n);
for(int i = 1; i <= n; i++) {
scanf("%lld %lld", &a[i].x, &a[i].y);
}
solve_a(1, n);
for(ll i = 3; i <= n; i++) {
for(ll j = 1; j < i; j++) {
g[j].x = a[j].x - a[i].x;
g[j].y = a[j].y - a[i].y;
g[j].k = atan2(g[j].y, g[j].x);
}
solve_g(1, i - 1);
POINT sum;
sum.x = g[1].x, sum.y = g[1].y;
for(ll j = 2; j < i; j++) {
ans += sum.x * g[j].y - sum.y * g[j].x;
sum.x += g[j].x;
sum.y += g[j].y;
}
}
ans /= 2.0;
printf("%.1Lf", ans);
}
T4 ZCC loves Isaac
Description
表箱关有一个房间非常可怕，它由n个变异天启组成。
每个天启都会在进入房间后吐出绿弹并炸向某一个位置且范围内只有一个天启。若该位置的天启已经死亡则没有事情发生，否则该位置的天启会死亡。每个天启只能且必须吐一次绿弹（除非在它吐弹以前他就挂了）。
绿弹的飞行速度很快，在某个绿弹落地之前不会有新的绿弹被吐出。
虽然房间的天启位置和吐弹位置固定，但是吐弹顺序是随机的，所以ZCC不能很好地制定策略。
现在ZCC想知道，最少和最多有几个天启被干掉。Input
第一行n表示天启个数。
第二行n个数ai表示i号天启的目标是ai。
注意：行末有一个空格。Output
一行两个数表示最少和最多有几个天启被干掉。
Sample Input
8 2 3 2 2 6 7 8 5Sample Output
3 5Data Constraint
Hint
比赛时其实想到了最大值的正解，因为最大值确实简单。
我们分类讨论：
-
单独的环（mermaid打钱）
graph LR a((1)) --> b((2)) --> c((3)) --> d((4)) --> a那么最大的杀伤过程为：
graph LR a((1)) --开炮--> b((2)) --> c((3)) --> d((4)) --> a graph LR a((1没炮)) --> b((2死)) --> c((3)) --> d((4)) --开炮--> a graph LR a((1死)) --> b((2死)) --> c((3)) --> d((4没炮)) --> a graph LR a((1死)) --> b((2死)) --> c((3)) --开炮--> d((4没炮)) --> a graph LR a((1死)) --> b((2死)) --> c((3没炮)) --> d((4死)) --> a也就是最终最多活 1 个。
-
链和环
graph LR a((1)) --> b((2)) --> c((3)) --> d((4)) --> c那么最大的杀伤过程为：
graph LR a((1)) --> b((2)) --> c((3)) --开炮--> d((4)) --> c graph LR a((1)) --> b((2)) --> c((3没炮)) --> d((4死)) --> c graph LR a((1)) --> b((2)) --开炮--> c((3没炮)) --> d((4死)) --> c graph LR a((1)) --> b((2没炮)) --> c((3死)) --> d((4死)) --> c graph LR a((1)) --开炮--> b((2没炮)) --> c((3死)) --> d((4死)) --> c graph LR a((1没炮)) --开炮--> b((2死)) --> c((3死)) --> d((4死)) --> c也就是最终最多活 1 个。
那么就是说，无论如何，一个 单独的环 或者一个 链和环 都是活 1 个。
问题就来了，怎么判断一个 单独的环 或者一个 链和环？
没错！dfs！！！！！
我们直接暴力跑一遍，跑的时候进行标记，如果跑到一个有标记的点，就结束，并把 mx-- 。
这样就可以实现这个最简单的部分了。
emm……最小值就有点麻烦了。
我们先看一下 链 的情况。
graph LR a((1)) --> b((2)) --> c((3)) --> d((4)) graph LR a((1)) --开炮--> b((2)) --> c((3)) --> d((4)) graph LR a((1没炮)) --> b((2死)) --> c((3)) --> d((4)) graph LR a((1没炮)) --> b((2死)) --> c((3)) --开炮--> d((4)) graph LR a((1没炮)) --> b((2死)) --> c((3没炮)) --> d((4死))也就是说我们让没东西杀的天启先放，因为这些天启是一定会活下来的，这样可以节约很多个炮。
那么就是一个拓扑了。
我们把链全部跑完后，剩下就只有 单独的环 了：
graph LR a((1)) --> b((2)) --> c((3)) --> d((4)) --> a懒得弄mermaid了。
我们会发现，当一个环有 \(n\) 个天启时，一个环最多活 \(\lfloor (n + 1)\div2\rfloor\) 个。
那么像跑最大值一样再跑一遍dfs即可。
#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
#define ll long long
ll n;
ll to[1000010];
ll rd[1000010]; // 入度
ll rd2[1000010];
ll cd[1000010]; // 出度
bool v[1000010];
bool v2[1000010];
bool zs[1000010];
ll q[1000010];
ll h, t;
ll mx, mn;
void dfs(ll x) {
if(v[x] == 1) {
return;
}
rd[x]--;
v[x] = 1;
dfs(to[x]);
}
void dfs2(ll x, ll tot = 1) {
if(v2[x]) {
mn += tot / 2;
} else {
v2[x] = 1;
dfs2(to[x], tot + 1);
}
}
int main() {
scanf("%lld", &n);
mx = n;
mn = 0;
for(ll i = 1; i <= n; i++) {
scanf("%lld", &to[i]);
if(to[i] == i) {
v[to[i]] = 1;
zs[i] = 1;
} else {
rd[to[i]]++;
}
cd[i]++;
rd2[to[i]]++;
}
// 跑最大值
for(ll i = 1; i <= n; i++) {
if(!rd[i] && !v[i]) {
mx--;
v[i] = 1;
dfs(to[i]);
}
}
for(ll i = 1; i <= n; i++) {
if(rd[i] && !v[i]) {
mx--;
v[i] = 1;
dfs(to[i]);
}
}
// 跑最小值
for(ll i = 1; i <= n; i++) {
if(!rd2[i]) {
q[++t] = i;
}
}
while(h < t) {
h++;
ll x = q[h];
v2[x] = 1;
if(v2[to[x]]) continue;
v2[to[x]] = 1;
mn++;
rd2[to[to[x]]]--;
if(rd2[to[to[x]]] == 0 && !v2[to[to[x]]] && !zs[to[to[x]]]) {
q[++t] = to[to[x]];
}
}
for(ll i = 1; i <= n; i++) {
if(!v2[i]) {
if(zs[i]) {
v2[i] = 1;
mn++;
}
dfs2(i, 1);
}
}
printf("%lld %lld", mn, mx);
}