noip2019…counting down three weeks

纪中day4 （头发日益益益益稀少）

11.1纪中B组notes

分队问题（洛谷 p2062） 数字对（洛谷 p2090） 高级打字机（洛谷 p1383）

仍旧是蒟蒻的悲惨一天o(╥﹏╥)o

keys & notes 部分来源于纪中题解

T1 分队问题（洛谷 p2062）

CEOI 2011 team简化…

题目描述

jzoj 3792 分队问题 洛谷 2062 分队问题

给定n个选手，将他们分成若干只队伍。 其中第i个选手要求自己所属的队伍的人数大等于a[i]人。 在满足所有选手的要求的前提下，最大化队伍的总数。 注：每个选手属于且仅属于一支队伍。

Input 第一行一个整数n，表示人数。 以下n行，每行一个整数表示a[i]。

Output 输出队伍总数的最大值。数据保证有解。

Sample Input 5 2 1 2 2 3

Sample Output 2

Data Constraint 对于20%的数据，n <= 10 对于40%的数据，n <= 1000 对于60%的数据，n <= 10000 对于100%的数据，1 <= n <= 10^6

notes&keys

DP

令f [ i ] 表示将1~i 个人分队的最多分队数。

f [ i ] = max { f [ j ] } + 1 , j <= i - a[i] 那么只需要g [ i ] = max { f [ j ] }, j <= i 即可实现O(n)

AC代码

#include <bits/stdc++.h> using namespace std; const int maxn = 1000015; int n, a[maxn], f[maxn], g[maxn]; inline int read()//快读优化 { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int main() { n = read(); for(int i = 1; i <= n; ++i) a[i] = read(); sort(a + 1, a + n + 1); for(int i = 1; i <= n; ++i) { f[i] = g[i - a[i]] + 1; //预留出后边儿a[i]个，后边儿最多成一组，前面的 i - a[i]个数的最大分队数+1 g[i] = max(g[i - 1], f[i]); //预处理前面的（类似最大前缀和）分队数，求出转移最大值 } printf("%d", f[n]); //不知为啥输出f？？ return 0; }

↑ 别看上边儿的注释都是水…

··另一十分神奇的写法+特判… 在洛谷AC了的代码…

#include<bits/stdc++.h> using namespace std; #define INF 1<<30 #define maxn 1000010 int read() { char ch = getchar(); int ret = 0, flag = 1; while(ch < '0'|| ch > '9') { if(ch == '-') flag = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ret = ret * 10 + ch - '0'; ch = getchar(); } return ret * flag; } int a[maxn],n,f[maxn]; int main() { n = read(); memset(a,0,sizeof(a)); memset(f,0,sizeof(f)); for(int i = 1; i <= n; i ++) a[i] = read(); sort(a + 1,a + n + 1); for(int i = 1; i <= n; i ++) { if(i - a[i] >= 0) f[i] = max(f[i - 1],f[i - a[i]]+ 1); } if(n - a[n] == 0)//特判！！ { f[n] = 1; } printf("%d\n",f[n]); return 0; }

附：艰难爆肝一上午的艰难秃头过程… 也可直接：

f[i] = max ( f[ i - 1], f[i - a[ i] ] + 1) //f[ i - 1]第i个人不开新队，最大分队数不变 //f[i - a[ i] ] + 1第i个人开新队，最少保证后边儿还有a[i]个人 sum = max(sum, f[i])

↑错的！！！

改为：

g[n] = f[i - a[ i] ] + 1 f[i] = max ( f[ i - 1], g[i]) 输出f[i]

**↑还是错的！！ **

f[n]相当于标程中的g（预处理效果？？），最后应输出g[n]！！

再改：（对于加了一位反而所有加在一起都只能分一组的特判（？）

(循环内) if(i - a[i] >= 0) { g[n] = f[i - a[ i] ] + 1 f[i] = max ( f[ i - 1], g[i]) } (循环外) if(n - a[n] == 0) f[n] = 1; 输出f[n]

T2 数字对（洛谷 p2090）

题目出处 CodeForces 134 B

题目描述

jzoj 3793 数字对 洛谷 p2090 数字对

Description 对于一个数字对(a, b)，我们可以通过一次操作将其变为新数字对**(a+b, b)或(a, a+b)。** 给定一正整数n，问最少需要多少次操作可将数字对(1, 1)变为一个数字对，该数字对至少有一个数字为n。

Input 第一行一个正整数 n

Output 一个整数表示答案。

Sample Input 5

Sample Output 3 【样例解释】 (1,1)  →  (1,2)  →  (3,2)  →  (5,2)

Data Constraint 对于30%的数据， 1 <= n <= 1000 对于60%的数据， 1 <= n <= 20000 对于100%的数据，1 <= n <= 10^6

notes&keys

来自某不知名巨佬的讲解…

反向考虑：（n，i）如何变为（1,1）？

↓ i 一定小于等于（？）n ↓每次变为（n - i，i）×—复杂度会太高！

→类似辗转相除： gcd（i， n % i ） + n / i ；

枚举1~（n + 1）/ 2（余下状态都是可以对应转移过来的）

枚举 改版gcd跑，找操作次数最少

附上蒟蒻的AC代码

#include <bits/stdc++.h> #define inf int(1e8) using namespace std; int n,now=inf; int gcd(int a, int b) { while (b != 0) { if(b == 1) return a - 1;//b最终=1说明一直没动，光给a加值去了 else { return gcd(b, a % b) + a / b;//like辗转相除 } } return inf; //b=0的话说明不存在，返回无限大 } inline int read()//快读优化 { int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int main() { n = read(); for(int i = 1; i <= (n + 1) / 2; i++) now = min(now, gcd(n, i)); printf("%d\n", now); return 0; }

带注释版代码（from巨佬blt~）

#include<bits/stdc++.h> using namespace std; #define INF 1<<30 int read() { char ch = getchar(); int ret = 0, flag = 1; while(ch < '0'|| ch > '9') { if(ch == '-') flag = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ret = ret * 10 + ch - '0'; ch = getchar(); } return ret * flag; } int magic(int a, int b) { if(!b)//要是b等于零，b显然不可能为零嘛 //最小都是(1,1)，之后又一直加的，怎么会有零 //要是说是后面取模取到整除的话，那也是不可能的，手动模拟一下就知道了 //e.g.:最简单，(2,2)，一看就知道，根本是行不通的嘛 return INF; if(b == 1) //要是b等于1，那就一直加另一边啊，因为另一边本来就有1，所以操作数要减1 return a - 1; return magic(b, a % b) + a / b; //这个其实挺好理解的，就是 n * b + a % b = a //e.g.:(8,3) = (3,2) + 2 也就是说，把 3 往 2 那里加两次，就可以得到(8,3)了 } int n; int now = INF; int main() { n = read(); for(int i = 1; i <= (n + 1) / 2; i ++) //只用到一半就好啦，因为前一半和后一半的结果是可以由同一个状态转移过去的 { now = min(now, magic(n,i)); //然后枚举，看看最后一步要从哪转移才能让之前的步数最小，并记录最小步数 } printf("%d\n",now); return 0; }

T3 高级打字机（洛谷 p1383）

题目描述

jzoj 3794 高级打字机 洛谷 p1383 高级打字机

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。 请为这种高级打字机设计一个程序，支持如下3种操作： T x：在文章末尾打下一个小写字母x。(type操作) U x：撤销最后的x次修改操作。（Undo操作）（注意Query操作并不算修改操作） Q x：询问当前文章中第x个字母并输出。（Query操作） 文章一开始可以视为空串。

Input 第1行：一个整数n，表示操作数量。 以下n行，每行一个命令。保证输入的命令合法。

Output 每行输出一个字母，表示Query操作的答案。

Sample Input 7 T a T b T c Q 2 U 2 T c Q 2

Sample Output b c

Data Constraint 对于40%的数据 n<=200; 对于100%的数据 n<=100000；保证Undo操作不会撤销Undo操作。 <高级挑战> 对于200%的数据 n<=100000；Undo操作可以撤销Undo操作。 <IOI挑战> 必须使用在线算法完成该题。

notes&keys

某不知名巨佬： “这道题不就是用下数据结构就好了吗？” 我：“？？？？” 巨佬： 不是道板子题么？就是用主席树维护一下，就没了啊，有什么好讲的吗？ 我： “？？？？？？？？？？？？？？？？？？？？？”（目瞪狗呆）

啊主席树… awsl… 居然两百分儿一道题(＃￣～￣＃)…

100分做法…

线段树 每个节点记录区间中有多少字母， 查询：like权值线段树查第k大。

200分做法…

可持久化线段树… 可持久化线段树再加上前面的做法。

纪中提供题解

这道题的意思是，你的程序就像一台打字机，有3种操作方法： T x：在末尾加上x U x：撤销x次操作（100分以上的点还会撤销Undo操作） Q x：输出这个字符串的第x个字符 总共有n次操作，输出每次Q询问的结果

100分：像一个栈一样，T就插入x，U就删除栈顶-x到栈顶个字符

180分：建立一个[1…100000]的ansistring数组，用来保存每一个版本的文章，再用ans记录总共有多少个版本，T的话就版本数+1，并且新的版本就等于上一个版本的末尾+x，如果是U的话，其实就是取第ans-x-1个版本，Q就是输出当前的版本的第k个字符，

200分：很明显，因为是1~100000，而且是ansistring，所以会空间超限，因此，我用了一个循环数组（也就是滚动数组）来优化空间，这个滚动数组空间是20000，为什么呢，因为小了的话就会答案错误（U x中的x），大了的话就容易空间超限，Q操作一样，就是ans=ans mod 20000+1，T操作ans-1要进行特殊处理，ans=1到数组的末尾，U操作ans-x-1也要特殊操作，转到a[20000-x-1+ans],然后就AC了。

由于没有学过主席树而改题失败的某蒟蒻…o(╥﹏╥)o 此处只能附上纪中大佬的标程~

#include <cstdio> #include <cstring> const int N = 100007; int q, t, cnt = 0, tot = 0; char c; int len[N]; struct Tree { int rt[N], lson[N << 5], rson[N << 5]; char val[N << 5]; void build(int &rt, int fa, int l, int r, int po) { if (!rt) rt = ++tot; //??????? if (l == r) { val[rt] = c; //?????????? return; } int mid = (l + r) >> 1; if (po <= mid) rson[rt] = rson[fa], build(lson[rt], lson[fa], l, mid, po); if (mid + 1 <= po) lson[rt] = lson[fa], build(rson[rt], rson[fa], mid + 1, r, po); } char qry(int rt, int l, int r, int po) { if (l == r) return val[rt]; //??????????? int mid = (l + r) >> 1; if (po <= mid) return qry(lson[rt], l, mid, po); if (mid + 1 <= po) return qry(rson[rt], mid + 1, r, po); } } tree; int main() { scanf("%d", &q); while (q--) { scanf(" %c", &c); if (c == 'T') { scanf(" %c", &c); len[++cnt] = len[cnt - 1] + 1; //??????????????????? tree.build(tree.rt[cnt], tree.rt[cnt - 1], 1, N, len[cnt]); } else if (c == 'U') { scanf("%d", &t); len[++cnt] = len[cnt - t - 1]; //?????cnt - t - 1??????? tree.rt[cnt] = tree.rt[cnt- t - 1]; } else { scanf("%d", &t); printf("%c\n", tree.qry(tree.rt[cnt], 1, N, t)); //?????????? } } return 0; }