期末考试当然是要学奥赛了！！！
本来想专心做几个数学题，然而被黄题虐爆了。
7.6 高一下期末考试day1
学会使用multiset!
可重集和,本质上是一个红黑树。
基本操作
定义：
multiset<int>a;
定义一个迭代器：
multiset<int> :: iterator it;
插入：
a.insert(x);
multiset内部自动排序，关键字相同的按照插入顺序从前往后排。
返回首尾迭代器：
a.begin();
a.end();
真实值的话就加一个 *, 如：
cout << *a.begin() << endl;
查询集合内一个值出现的位置，返回一个迭代器，如果目标值不存在，返回尾指针之后的位置：
a.find(x);
删除，如果删除函数的参数填的是一个集合内的类型值，则可重集内的全部元素将被删除。若想要同一个值只删除一个元素，需要往参数里填此元素所在的迭代器。
a.erase(x);
a.erase(a.find(x));
遍历：
multiset<int> :: iterator it = a.begin();
for(;;it++){
printf("%d", *it);
if(it == a.end()) break;
}
下面让我们来练习一下吧！
P1110 [ZJOI2007]报表统计
代码：
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<functional>
#define inf 0x3fffffff
using namespace std;
typedef long long ll;
#ifndef DONLINE_JUDGE
char xch, xB[1 << 15], *xS = xB, *xTT = xB;
#define getc() (xS == xTT && (xTT = (xS = xB) + fread(xB, 1, 1 << 15, stdin), xS == xTT) ? 0 : *xS++)
#endif
#ifndef DBUFFETT
#define getc() getchar()
#endif
int rd(){
int res = 0, fl = 1;
char c = getchar();
while(!isdigit(c)){
if(c == '-') fl = -1;
c = getchar();
}
while(isdigit(c)){
res = (res << 3) + (res << 1) + c - '0';
c = getchar();
}
return res * fl;
}
int n, m, st[500010], ed[500010], a[500010], pos, k, mingap, minsortgap;
string op;
multiset <int> num, delta;
int main(){
n = rd(); m = rd();
num.insert(-inf); num.insert(inf);
mingap = inf; minsortgap = inf;
for(int i = 1; i <= n; ++i){a[i] = rd(); num.insert(a[i]); st[i] = a[i]; ed[i] = a[i];}
for(int i = 1; i < n; ++i){
mingap = min(mingap, abs(a[i] - a[i + 1]));
delta.insert(abs(a[i] - a[i + 1]));
}
multiset <int> :: iterator numst = num.begin(), numlst;
while(numst != num.end()){
numlst = numst; numst++;
minsortgap = min(minsortgap, abs(*numst - *numlst));
}
multiset <int> :: iterator posk, lstk, nxtk;
for(int i = 1; i <= m; ++i){
cin >> op;
if(op == "INSERT"){
pos = rd(); k = rd();
num.insert(k);
posk = num.find(k);
posk --; lstk = posk; posk ++;
posk ++; nxtk = posk; posk --;
minsortgap = min(minsortgap, min(*posk - *lstk, *nxtk - *posk));
delta.erase(delta.find(abs(st[pos + 1] - ed[pos])));
delta.insert(abs(k - ed[pos]));
delta.insert(abs(st[pos + 1] - k));
ed[pos] = k;
mingap = *delta.begin();
}
else if(op == "MIN_GAP"){
printf("%d\n", mingap);
}
else if(op == "MIN_SORT_GAP"){
printf("%d\n", minsortgap);
}
}
return 0;
}
P1403 [AHOI2005]约数研究
1 ~ n里能被 i 整除的数共有 $\left\lfloor \frac{n} {i} \right\rfloor$个,也就是说这 $\left\lfloor\frac{n} {i} \right\rfloor$数中都含有因子 $i$,也就是说这些数每一个都对答案产生了1的贡献。
枚举 i , 累加$\left\lfloor \frac{n} {i} \right\rfloor$ 。
复杂度 $O(n)$。
注意到$\left\lfloor \frac{n} {i} \right\rfloor$单调，可以分块做到根号复杂度。
int main(){
GetPrime(1000000);
n = rd();
for(int i = 1; i <= n; ++i){
ans += n / i;
}
printf("%lld\n", ans);
return 0;
}
整体二分(初步)
整体二分是一个离线算法。当题目有多组询问时，对每个询问都进行一次二分可能会超时，整体二分的思路就是多个询问一起处理，二分答案的同时二分询问。
可以使用整体二分解决的题目需要满足以下性质：
询问的答案具有可二分性
修改对判定答案的贡献互相独立，修改之间互不影响效果
修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
贡献满足交换律，结合律，具有可加性
题目允许使用离线算法
——许昊然《浅谈数据结构题几个非经典解法》
查询第 k 小——一次二分多个询问
在一个数列中多次查询第 k 小的数。
struct Query{
int id, k;
};
int ans[maxn];
int check(int x);//原数列中小于等于x的数的个数
void solve(const int L, const int R, vector<Query> q){
int M = (L + R) / 2;
if(L == R){
for(int i = 0; i < q.size(); ++i){ans[q[i].id] = L;}
return ;
}
vector<Query> q1, q2;
for(int i = 0; i < q.size(); ++i){
if(q[i].k <= check(M))
q1.push_back(q[i]);
else{
q[i].k -= sum(m);
q2.push_back(q[i]);
}
}
solve(L, M, q1);
solve(M + 1, R, q2);
return ;
}
区间查询第 k 小——指定区间询问
在一个数列中多次给定区间查询区间第 k 小的数。
struct Num{
int p, x;
};//位于数列中第 p 项的数的值为 x
struct Query{
int l, r, k, id;
};//询问区间为[l, r], 第 k 小，编号为 id
int ans[maxn];
void add(int p, int x);//树状数组在位置 p 加上 x
int query(int p);//树状数组前缀和
void clear();//清空树状数组
void solve(const int L, const int R, vector<Num> a, vector<Query> q){//值域区间是[L, R]
int M = (L + R) / 2;
if(L == R){
for(int i = 0; i < q.size(); ++i) ans[q[i].id] = L;
return ;
}
vector<Num> a1, a2;
vector<Query> q1, q2;
for(int i = 0; i < a.size(); ++i){
if(a[i].x <= M){
a1.push_back(a[i]);
add(a[i].p, 1);
}
else{
a2.push_back(a[i]);
}
for(int i = 0; i < q.size(); ++i){
int t = query(q[i].r) - query(q[i].l - 1);
if(q[i].k <= t)
q1.push_back(q[i]);
else{
q[i].k -= t;
q2.push_back(q[i]);
}
}
}
clear();
solve(L, M, a1, q1);
solve(M + 1, R, a2, q2);
return;
}
P1338 末日的传说
转化为 n 更小的情况
观察两则数据： n = 5, m = 4 和 n = 6, m = 4。
第一组的答案是 1 3 5 4 2 ，第二组的答案是 1 2 4 6 5 3。
乍一看没什么规律，但是如果这么看第二组答案 1 (1+1) (3+1) (5+1) (4+1) (2+1) 就会发现，将第一组答案全部加1，相对大小不变，再在最开头放1，1不产生任何新的逆序对，就得到了第二组答案。
这启示我们将问题规模缩小，不难想到递归。
n = 6的排列最多能有多少逆序对？不难发现答案是 $\frac{(n-1)n}{2}$。那么也就是说如果 $m \geq \frac{(n-1)n}{2}$，答案序列的第一个数输出的一定是1，因为这样不会产生任何逆序对而且是字典序最小的。 m 不变,接着解决 n-1 的问题。反之如果 $m < \frac{(n-1)n}{2}$, 这逼着我们在答案序列的第一个数放一个足够大的数能够产生不少于$\frac{(n-1)n}{2}-m$个逆序对，然后 m 缩小，再去解决 n - 1 的问题。
于是递归算法应用而生。
用 used[i] 表示 i 这个数字有没有被使用过。 pre[i] 表示小于 i并且没有被用过的最大数字， nxt[i] 表示大于 i 并且没有被用过的最小数字。pre[]和nxt[]实现链表来缩短找寻没有使用过的数字的时间。sum[i] 表示小于 i 并且没有被用过的数字个数，即 i 的逆序对贡献。
分类讨论上述两种情况，$m \geq \frac{(n-1)n}{2}$时输出没被使用过的最小数字，否则输出最小的满足 $sum[i] \geq \frac{(n-1)n}{2} - m$的数字。递归至 $n = 1$输出唯一没被使用过的元素结束。
bool used[50010];
int pre[50010], nxt[50010], n, m, sum[50010];
void Link(int pos){
nxt[pre[pos]] = nxt[pos];
return;
}
void Prework(){
memset(used, 0, sizeof(used));
for(int i = 1; i <= n; ++i){
nxt[i] = i + 1;
pre[i] = i - 1;
sum[i] = sum[i - 1] + 1;
}
return;
}
void upd(int pos){
for(int i = pos; i <= n; i = nxt[i]){
if(!used[i]) sum[i] = sum[pre[i]] + 1;
else sum[i] = sum[pre[i]];
}
return;
}
void printmin(){
int pos = 1;
while(used[pos]){
pos = nxt[pos];
}
used[pos] = 1;
Link(pos);
upd(pos);
printf("%d ", pos);
}
void Print(int N, int M){
if(N == 1){
printmin();
return;
}
ll mostinv = 1ll * (N - 1) * (N - 2) / 2;
if(mostinv >= M){
printmin();
}
else {
int delta = M - mostinv;
for(int i = 1; i <= n; i = nxt[i]){
if(!used[i] && sum[i - 1] >= delta){
printf("%d ", i);
M -= sum[i - 1];
used[i] = 1;
Link(i);
upd(i);
break;
}
}
}
Print(N - 1, M);
}
int main(){
n = rd(); m = rd();
Prework();
Print(n, m);
cout << "\n";
return 0;
}
但是它 T 了！它 T 了呜呜呜。
观察答案性质
暴力玩小样例可以发现答案数组先升序后降序(好吧其实我没发现我看的题解)，这意味着我们可以枚举1~n，当前数字要么顺着答案序列的前几个元素往后排要么挨着后几个元素往前排。复杂度就是 O(n)了。
int n, m, ans[50010];
int lst, fst;
int main(){
n = rd(); m = rd(); lst = n;
for(int i = 1; i <= n; ++i){
ll mostinv = 1ll * (n - i) * (n - i - 1) / 2;
if(mostinv >= m) ans[++fst] = i;
else{
ans[lst--] = i;
m -= (n - i);
}
}
for(int i = 1; i <= n; ++i) printf("%d ", ans[i]);
printf("\n");
return 0;
}
逆序对为 x 的 n 的排列的数量的通式
如 n = 6, 逆序对分别为 1~15 的排列分别有 1 5 14 29 49 71 90 101 101 90 71 49 29 14 5 1 个。
不会求通项。
P2327 [SCOI2005]扫雷
我真吐了, n * 2 的话答案其实就 0、1、2 三种情况，我一开始还开了个 long long 准备累乘答案。
只要第一行确定了下面一定能确定。分别令第一行有、无雷然后判断有无解即可。
int n, b[10010], a[10010], ans;
bool check(){
for(int i = 1; i <= n; ++i){
if(a[i] + a[i - 1] > b[i]) return 0;
if(a[i] + a[i - 1] == b[i]) a[i + 1] = 0;
if(a[i] + a[i - 1] == b[i] - 1) a[i + 1] = 1;
if(a[i] + a[i - 1] + a[i + 1] != b[i]) return 0;
a[0] = 0; a[n + 1] = 0;
if(a[i] + a[i - 1] + a[i + 1] != b[i]) return 0;
}
return 1;
}
int main(){
n = rd();
for(int i = 1; i <= n; ++i) b[i] = rd();
for(int i = 1; i <= n; ++i) a[i] = -10;
a[1] = 1; a[0] = 0; a[n + 1] = 0;
if(check()) ans++;
for(int i = 1; i <= n; ++i) a[i] = -10;
a[1] = 0;
if(check()) ans++;
printf("%d\n", ans);
return 0;
}
P1620 漂亮字串
丧失思考能力...
ll cx, co, mx, mo, ans;
int main(){
while(cin >> co >> cx >> mo >> mx){
mx = min(mx, cx);
mo = min(mo, co);
if(mo == 0) cout << mx << endl;
else if(mx == 0) cout << mo << endl;
else if((co + 1) * mx < cx) cout << (co + 1) * mx + co << endl;
else if((cx + 1) * mo < co) cout << (cx + 1) * mo + cx << endl;
else cout << cx + co << endl;
}
return 0;
}