【SinGuLaRiTy-1014】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.
对于所有的题目：Time Limit：1s | Memory：256 MB
第一题：完美序列
【题目描述】
给你一个长度为n(1<=n<=100,000)的自然数数列，其中每一个数都小于等于10亿，现在给你一个k，表示你最多可以删去k类数。数列中相同的数字被称为一类数。设该数列中满足所有的数字相等的连续子序列被叫做完美序列，你的任务就是通过删数使得该数列中的最长完美序列尽量长。
【输入】
第一行两个整数N,K。
接下来N行，每行1个整数，表示第i个数。
【输出】
最长的完美序列的长度。
【样例数据】
| 样例输入 | 样例输出 |
|
9 1 2 7 3 7 7 3 7 5 7 |
4 |
【STD Code】
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
int ans;
int kind[];
struct node
{
int value;
int pos;
};
node data[];
int cmp_value(node a,node b)
{
return a.value<b.value;
}
int cmp_origin(node a,node b)
{
return a.pos<b.pos;
}
int main()
{
int n,k;
int t,now,contain,l;
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
scanf("%d",&data[i].value);
data[i].pos=i;
}
sort(data+,data+n+,cmp_value);
now=;
t=data[].value;
for(int i=;i<=n;i++)
if(data[i].value==t)
data[i].value=now;
else
{
now+=;
t=data[i].value;
data[i].value=now;
}
sort(data+,data+n+,cmp_origin);
contain=;
l=;
for(int i=;i<=n;i++)
{
if((kind[data[i].value]==)&&(contain<=k))
{
contain+=;
kind[data[i].value]+=;
ans=max(ans,kind[data[i].value]);
}
else if((kind[data[i].value]==)&&(contain>k))
{
kind[data[i].value]+=;
kind[data[l].value]-=;
while(kind[data[l].value]!=)
{
l+=;
kind[data[l].value]-=;
}
l+=;
ans=max(ans,kind[data[i].value]);
}
else
{
kind[data[i].value]+=;
ans=max(kind[data[i].value],ans);
}
}
printf("%d",ans);
return ;
}
【题目分析】
别的先不说，看到仅有100000个数字，数据范围却是1000000000,就说明我们首先要对这个序列进行离散化。在这里，可以开一个结构体，定义两个值：value和pos，value表示值，pos表示这个数原本在序列的哪一个位置，先用一次sort对value进行排序，更改值的大小（也就是离散化的中心操作），接着再来一次sort，按pos排序，以此将序列的位置排布还原为原来的序列。
下面，我们就来看看这道题的中心思路：设置一个“移动窗口”。也就是说，定义两个变量：L，R，来记录可能答案的潜在区间。在最开始，我们将L，R初始化为0，即L，R将从序列的最左端开始向右扫描。由于题目中有要求“仅能删除k类数”，那么，当窗口刚刚开始移动时，我们可以先保持L不动，使R右移，与此同时，不断更新在该窗口内存在的数的种类（当然，你也要算出此时的最优解），当种类达到k+1种时，就说明当前区间已经塞满啦，此时要想继续使窗口移动，就要使L+=1,更新之后，再让R+=1......以此类推，不断使窗口移动下去，直到扫描至序列末端，此时的答案就是整个序列中的完美序列的最优解了。
第二题：岛屿
【题目描述】
给你一张r*c(1<=r,c<=50)的地图，有’S’,’X’,’.’三种地形，所有判定相邻与行走都是四连通的。我们设’X’为陆地，一个’X’连通块为一个岛屿，’S’为浅水，’.’为深水。其中一共有n个岛屿（n<=15）,刚开始你可以降落在任一一块陆地上，在陆地上可以行走，在浅水里可以游泳。并且陆地和浅水之间可以相互通行。但无论如何都不能走到深水。你现在要求通过行走和游泳使得你把所有的岛屿都经过一遍。问最少要经过多少次浅水区？题目保证有解。
【输入】
第一行两个整数R,C
接下来第有R行，每行C列个字符，为’X’,’S’,’.’
【输出】
一个整数，表示遍历完所有的岛屿最小要游过多少次浅水区。
【样例数据】
| 样例输入 | 样例输出 |
|
5 4 XX.S .S.. SXSS S.SX ..SX |
3 |
【STD Code】
#include<cstring>
#include<cstdio>
#include<queue> #define MAXN 55
#define Size 20
#define MAXM 400010
#define INF 0x3f3f3f3f using namespace std; int sx[]={,,,-};
int sy[]={,-,,}; int r,c,num;
char s[MAXN];
char a[MAXN][MAXN];
int land[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dist[Size][Size],dis[MAXN][MAXN]; struct hp
{
int x;
int y;
};
struct hq
{
int has_been;
int island;
};
hp st[Size][MAXN]; queue <hp> q;
queue <hq> p; int tot[Size];
int f[MAXM][Size];
int goal,ans;
bool atp[MAXM][Size]; inline void dfs(int x,int y,int num)
{
land[x][y]=num;
tot[num]+=;
st[num][tot[num]].x=x;
st[num][tot[num]].y=y;
for(int i=;i<;++i)
{
int nowx=x+sx[i];
int nowy=y+sy[i];
if(nowx>&&nowx<=r&&nowy>&&nowy<=c&&a[nowx][nowy]=='X'&&!land[nowx][nowy])
dfs(nowx,nowy,num);
}
} void spfa(int island)
{
memset(vis,,sizeof(vis));
memset(dis,0x7f,sizeof(dis));
while(!q.empty())
q.pop();
for(int i=;i<=tot[island];i++)
{
vis[st[island][i].x][st[island][i].y]=true;
dis[st[island][i].x][st[island][i].y]=;
q.push((hp){st[island][i].x,st[island][i].y});
}
while(!q.empty())
{
hp now=q.front();
q.pop();
vis[now.x][now.y]=false;
hp next;
for(int i=;i<;++i)
{
next.x=now.x+sx[i];
next.y=now.y+sy[i];
if(next.x>&&next.x<=r&&next.y>&&next.y<=c&&a[next.x][next.y]!='.')
if(a[next.x][next.y]=='S')
{
if(dis[next.x][next.y]>dis[now.x][now.y]+)
{
dis[next.x][next.y]=dis[now.x][now.y]+;
if(!vis[next.x][next.y])
{
vis[next.x][next.y]=true;
q.push((hp){next.x,next.y});
}
}
}
else
{
if(dis[next.x][next.y]>dis[now.x][now.y])
{
dis[next.x][next.y]=dis[now.x][now.y];
if(!vis[next.x][next.y])
{
vis[next.x][next.y]=true;
q.push((hp){next.x,next.y});
}
}
dist[island][land[next.x][next.y]]=min(dist[island][land[next.x][next.y]],dis[next.x][next.y]);
}
else
continue;
}
}
} int main()
{
scanf("%d%d\n",&r,&c);
for(int i=;i<=r;++i)
{
gets(s);
for(int j=;j<=c;++j)
a[i][j]=s[j-];
}
num=;
for(int i=;i<=r;++i)
for(int j=;j<=c;++j)
{
if(a[i][j]=='X'&&!land[i][j])
dfs(i,j,++num);
}
memset(dist,0x7f,sizeof(dis));
for(int i=;i<=num;++i)
spfa(i);
memset(f,0x7f,sizeof(f));
while(!p.empty()) p.pop();
for(int i=;i<num;++i)
{
p.push((hq){<<i,i+});
atp[<<i][i+]=true;
f[<<i][i+]=;
}
while(!p.empty())
{
hq now=p.front();
p.pop();
atp[now.has_been][now.island]=false;
for(int i=;i<num;i++)
if(f[now.has_been|(<<i)][i+]>f[now.has_been][now.island]+dist[now.island][i+])
{
f[now.has_been|(<<i)][i+]=f[now.has_been][now.island]+dist[now.island][i+];
if(!atp[now.has_been+(<<i)][i+])
p.push((hq){now.has_been+(<<i),i+});
}
}
for(int i=;i<num;i++)
goal+=(<<i);
ans=INF;
for(int i=;i<=num;i++)
ans=min(ans,f[goal][i]);
printf("%d\n",ans);
return ;
}
【题目分析】
这道题要用到“状态压缩DP”。
我们需要把每一个岛屿当做一个节点，求出每两个岛屿之间的最短路径distance，这样一来，我们实际上就得到了一个图。接下来，我们就可以用一个DP数组f[state][i]来表示当前的状态，其中的state为一个15位的二进制数，表示岛屿的访问标记，i表示当前停留在第几个岛屿（之前未到达过的）。
那么，我们就可以得到这么一个递推式：f[state][i]=f[state'(第i位清零)=min(state^(1<<i))][j]+distance(i,j)。
Time: 2017-03-21