USACO 5.5 章节
Picture
题目大意
IOI 1998
求n (<=5000)个矩形 覆盖的图形 的周长(包括洞), 坐标范围[-10000,10000]
题解
一眼离散化+2维线段树，但仔细一想 空间不太够,时间勉强接受
然后目测可能1维线段树+扫描线了?
然后 竟然 裸的扫描线可以过，如下面代码
总数量级上来讲，输入O(n),排序O(n log n),扫描过程O(sum(len周长)) 约5000*20000*4的上限[ 不过USACO给过了，
所以还是线段树好?
从实现来讲，把矩形拆分成x和y方向，靠计算每个块的累计层数 来判断边界
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
using namespace std;
const string filename = "picture";
void usefile(){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
int N,ans=0;
// OX向和OY向的 线段分离处理，互不影响
tuple<int,bool,int,int> Lx[10010],Ly[10010]; // {位置idx坐标,结束边bool?,st->end}
int level[20010];
void Scan(tuple<int,bool,int,int> *L) {
sort(L,L+N);
rep(i,0,20001)
level[i]=0;
rep(i,0,N){
rep(j,get<2>(L[i]),get<3>(L[i])){
if (!get<1>(L[i])){
ans += level[j+10000]==0;
level[j+10000]++;
} else {
level[j+10000]--;
ans += level[j+10000]==0;
}
}
}
}
int main(){
usefile();
scanf("%d",&N);
rep(i,0,N){
int x1,x2,y1,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
// OX 方向边
Lx[i*2] = {y1,false,x1,x2};
Lx[i*2+1] = {y2,true,x1,x2};
// OY 方向边
Ly[i*2] = {x1,false,y1,y2};
Ly[i*2+1] = {x2,true,y1,y2};
}
N*=2;
Scan(Lx);
Scan(Ly);
printf("%d\n",ans);
return 0;
}Hidden Password
ACM South Eastern Europe -- 2003
题目大意
字符串L(长度<=100’000)
求 以该字符串，平移后的， 所有字符串中 字典序最小的字符串的首字母在原字符串中的下标
如cba
所有字符串 acb bac cab, (排序后),第一个字符串首字母对应原来字符串位置为2 (从0计数)
题解
枚举！
这样 我们首先找到最小字母 扫一遍O(n)
然后找到这些开始的坐标
逐步增加长度
那么我们由递归关系，保证每次增加长度后，当前还剩余的坐标只有最小的留下，
因此当增加长度到l时，我们 的维持的起始坐标是 整个字符串里，长度从1到l都是字典序最小的
那么我们有两种长度改变方式
- +1
假设所有点按照长度扩充 都不属于当前维护的点，那么，长度加1，保留，增加字符最小的点
例子 abcabdzzzabc
初始所有a的坐标[0,3,9]，长度1
扩充，扩充目标分别为[1,4,10]，都不是当前维护的点([0,3,9])
所以比较元素，全为b，长度=1+1=2
接下来，扩充目标为[2,5,11],也都不是维护的点
比较字符，两个abc,一个abd,所以维护的点变为[0,9],长度变为=2+1=3
再扩充，扩充目标为[3,0],注意到0是我们当前维护的[0,9]中的元素，所以不采取+1的方案
- 倍增
假设字符aabbabbb，
那么在找完最小字符后，起始坐标还剩下[0,1,4],一旦发现任意一个扩充的下一步([1,2,5]) 是一个维持的点，那么长度翻倍，后一个点删除，在这种情况下，扩充的位置不是最小坐标的点直接移除。
因为我们维持的点 == 从1到该长度下，每个长度 都是字典序最小的，所以没有在维护中的点，都是非字典序最小的,所以 可以倍增
删除右边的点是因为 扩充右边的维护点的字典序一定大于等于 左边的点，等于的情况由判环处理
如上在一次扩充后发现0的下一个扩充是1，而1是我们维持着的点，所以长度=1*2,1点删除，4扩充是5，那么5没有被维持，所以4点也被删除，综上最后剩下0
以上描述存在的问题：起始点是哪个点？
假设字符串 aaazzaaza,
显然在初始操作后 需要维护的点有[0,1,2,5,6,8]
注意到，如果从左向右来处理，按照上面的算法会 变成[0,6,8???],而实际 从环的性质来看，期望的应该是得到[1,6,8]，也就是8位置的看做[8,0,1,2]这一段的起始点。
这里加一个父节点的查找，找到环意义上该点所对应的最左的点即可，在下方函数看的话就是circle,
同时，circle这里如果发现，整个保存的点构成了环,那么也就是 这些点仅对于环上字典序的等价了，根据题目期望这种情况下最小index，就取出即是答案
空间复杂度，emmmm没啥好说，看变量即可，维持在O(n)
时间复杂度,
每一次倍增会让点数至少除以2，因为一个点要留下来，那么首先它的扩展点要在原来的维护里，并且下一次维护需要消失，所以每次要留一个点，就一定要删一个点，还有的点不会被留下，所以留下的一定小于等于上一次的一半
O(n+n/2+n/4) = O(2n) = O(n)
考虑对任意长度，都是执行+1，那么每次能执行+1的限度为
sum(n*(1+1/2+...1/n))
众所周知这是一个无穷级数，所以时间复杂度无穷大
大自也是O(12n)=O(n)的复杂度，
下面就是实际上，是这两种穿插 ，那么一定小于等于O(2n+12n)=O(n), (数学的习惯懒得分类讨论不等的情况 能用就行，所以留一个等于)
综上 时间空间均满足
char s[100010];
int sz=0;
bool pos[100010];
vector<int>p;
vector<int>q;
int L;
bool circle(int idx,int len,int &newidx){
newidx = (idx+L-len)%L;
while(newidx != idx){
if(!pos[newidx]){
(newidx+=len)%=L;
return false;
}else{
newidx = (newidx+L-len)%L;
}
}
while(newidx - L > 0){
newidx -= L;
}
printf("%d\n",newidx);
return true;
}
int main(){
usefile();
// 同步增长，冲突取前，倍增 其余删除(因为保证最小)
scanf("%d",&L);
while(sz<L){
scanf("%s",s+sz);
sz+=strlen(s+sz);
}
char minch = s[0];
rep(i,1,L){
minch = min(minch,s[i]);
}
rep(i,0,L){
if(s[i] == minch){
p.push_back(i);
pos[i]=true;
}
}
int l = 1;
while(p.size() > 1){
int state = 0; // 0 for +1, 1 for *2
minch = s[(p[0]+l)%L];
for(auto idx : p){
if(pos[(idx+l)%L] == true){
state = 1;
break;
}
minch = min(minch,s[(idx+l)%L]);
}
if(state == 0){
q.clear();
for(auto idx:p){
if(!pos[idx])continue;
if(s[(idx+l)%L] == minch){
q.push_back(idx);
}else{
pos[idx]=false;
}
}
p=q;
l++;
}else{
q.clear();
int startidx ;
int ret = circle(p[0],l,startidx);
if(ret){
return 0;
}
int pidx = 0;
for(pidx=0;pidx<p.size();pidx++){
if(p[pidx] == startidx){
break;
}
}
rep(i,pidx,p.size()){
int idx = p[i];
if(!pos[idx])continue;
if(pos[(idx+l)%L]){
q.push_back(idx);
pos[(idx+l)%L] = false;
}else{
pos[idx]=false;
}
}
rep(i,0,pidx){
int idx = p[i];
if(!pos[idx])continue;
if(pos[(idx+l)%L]){
q.push_back(idx);
pos[(idx+l)%L] = false;
}else{
pos[idx]=false;
}
}
p=q;
l*=2;
}
}
printf("%d\n",p[0]);
return 0;
}Twofive
题目大意
IOI 2001
A到Y构成的排列，满足 把这25个字母排成 5*5矩阵后 每行每列，单调递增，则为合法的
所有合法的排列，按照字典序 排序
请编写 字典序序号 到字符串 和 字符串反向转换为字典序序号的程序
尝试思路
看数据量，我自己也估计不到实际大小于是先写了一个打表，(上界 是25!但是有限制所以不知道是否会降低
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
using namespace std;
const string filename = "twofive";
void usefile(){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
int chars[30];
int vis[30];
int cnt = 0;
void print(){
cout<<endl;
rep(i,0,5){
rep(j,0,5){
cout<<char(chars[i*5+j]+'a')<<" ";
}
cout<<endl;
}
}
void gen(int idx){
if(idx%5==0){
rep(i,0,25){
if(vis[i] == 0){
vis[i]=1;
chars[idx] = i;
gen(idx+1);
vis[i]=0;
return ;
}
}
}
if(idx == 24){
cnt++;
chars[24]=24;
print();
return ;
}
int sti = chars[idx-1];
if(idx>5){
sti=min(sti,chars[idx-5]);
}
rep(i,sti+1,26-(5-idx%5)*(5-idx/5)){
if(vis[i])continue;
vis[i]=1;
chars[idx] = i;
gen(idx+1);
vis[i]=0;
}
}
int main(){
// usefile();
gen(0);
cout<<cnt<<endl;
return 0;
}跑了一下大概
7951237
a b c d e
f g h l n
i m k q w
j p o r u
s t v x y 以上的改动才到i,说明 数量级上，不可能期望打表了
接下来，注意到，如果我们有方法从数字序号转换到 对应的单词，那么 可以2分法 找到对应的单词
同理，如果我们找到 单词映射到序号的方法，那么2分（如果可以，因为这里二分单词似乎没那么好做）也能反过来找数字，所以分析上，任何一个问题 都可以解决对应的一个
还有个思路是，简单的排序，计算被删掉的个数,那么序列= 总排序-被删掉比它小的个数
题解
记忆化+dp
我们如果把数从小到大填入
那么显然，新插入的数在已经插入的数的行末,也在已经插入的数的列末，如
a b e
c d f
g
h
ij可插入的位置 为g右侧或e右侧
所以 我们有dp
dp[i0][i1][i2][i3][i4] 表示 第0行i0个，第1行i1个数...第i4行个数的情况下，剩余未填部分的期望个数
不考虑具体，仅考虑题目基本限制的情况下, 满足 ij >= i(j+1),因为我们按照顺序放数字，所以上面的行的个数不小于下一行
有转移方程
dp[i0][i1][i2][i3][i4] = dp[i0-1][...]+dp[...][i1-1][...]+dp[...][i2-1][...]+dp[...][i3-1][...]+dp[...][i4-1]
其中 如果在-1时不满足 行之间个数的大小关系，那么 对应的dp直接为0
综上，我们有了在没有 具体求值下，能计算所有满足题目限制下的dp，时间复杂度 = O(空间*状态转移)=O(6^5*5),空间O(6^5)
求解
接下来是如何进行转换的问题求
因为所求的idx为实际的 合法twofive的字典序
那么我们可以按位逼近，//延伸阅读 BROP的按位枚举攻击方法
假设我们求的是
ADEFGBHIJKC...Y, 那么 它 的字典序 = AB...的所有+AC...的所有+...
简单的说，如果一个前缀小于 要求的等长前缀，那么加上该前缀的所有个数，
如果该前缀等于要求的值的等长前缀，那么前缀长度+1
外层for前缀长度，中间for字母， 时间复杂度小于 O(25*25)
以上我们可以 从 字符串转化为index
相反
同样用逼近的方法，可以O(25*25)时间复杂度内 index转化为 字符串
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
using namespace std;
const string filename = "twofive";
void usefile(){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
char s[100]; // 按位逼近的
char str[100]; // str2index
int dp[6][6][6][6][6];
int dfs(int a=0, int b=0, int c=0, int d=0, int e=0, char ch='A') {
if(ch > 'Y') return 1;
int &ret = dp[a][b][c][d][e];
if(ret) return ret;
// 每一行 一定小于等于上一行
int w = 5;
int *v[6]={&w,&a,&b,&c,&d,&e};
rep(i,1,6){
// 未填过 和 已经填过(按照 字母顺序扩展)
int idx = *v[i]+(i-1)*5;
if(*v[i] < *v[i-1] && (s[idx] == 0 || s[idx] == ch)){
(*v[i])++;
ret+=dfs(a,b,c,d,e,ch+1);
(*v[i])--;
}
}
return ret;
}
void index2word(){
int n;
scanf("%d",&n);
rep(i,0,25){
for(s[i] = 'A';; s[i]++) { // 按位逼近 时间复杂度25×25
memset(dp, 0,sizeof(dp));
int ret = dfs();
// cout<<i<<" = "<<s[i]<<"\tret = "<<ret<<endl;
if(ret >= n) break;
n -= ret;
}
}
printf("%s\n", s);
}
void word2index(){
scanf("%s", str);
int ans = 1;
rep(i, 0, 25) {
for(s[i] = 'A'; s[i] < str[i]; s[i]++) {
memset(dp, 0,sizeof(dp));
ans += dfs();
}
}
printf("%d\n", ans);
}
int main(){
usefile();
char c;
cin >> c;
if(c == 'N') { // index 2 word
index2word();
} else if(c == 'W') { // word 2 index
word2index();
}
return 0;
}上面实现中 dp过程是按照字母顺序填写，由ch保证，所以在最外层枚举dp的时候，就直接从A 到Y 了
同程旅行工作强度 19人发布