11.1纪中DAY4_分队问题 & 数字对 & 高级打字机
noip2019…counting down three weeks
纪中day4
（头发日益益益益稀少）
11.1纪中B组notes
- 分队问题（洛谷 p2062）
- 数字对（洛谷 p2090）
- 高级打字机（洛谷 p1383）
仍旧是蒟蒻的悲惨一天o(╥﹏╥)o
keys & notes 部分来源于纪中题解
T1 分队问题（洛谷 p2062）
CEOI 2011 team简化…
题目描述
给定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
题目描述
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）
题目描述
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。
请为这种高级打字机设计一个程序，支持如下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;
}
上一篇： Day4_列表基础