HG 2018.10.28 模拟题
hicc0305
2018-10-28 14:46:43
今天三道题就放一起了，因为前两题实在没什么好讲的。第一题入门模拟题，第二题很简单的二分图染色（但我只输出了方案，忘输出YES了orz，然后又爆了）
## 第二题
这题就不概括题意了，因为题目一共就一句话orz
给定M个二元组$(A_i, B_i)$，求$X_1, ..., X_N$满足：对于任意$(A_i, B_i)$，有$|X_{A_i} - X_{B_i}| = 1$成立。
然后，随便想一想，其实就是一道二分图染色，染成0,1即可，染出来有矛盾，就不行。
代码：
```
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,cnt=0;
int head[200100],nxt[200100],to[200100];
int vis[100100];
void addedge(int x,int y)
{
cnt++;
nxt[cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
}
void dfs(int u,int k,int fa)
{
vis[u]=k;
for(int i=head[u];i!=-1;i=nxt[i])
{
int v=to[i];
if(v==fa) continue;
if(vis[v]!=-1 && vis[v]!=(vis[u]^1))
{
printf("NO");
exit(0);
}
if(vis[v]==-1) dfs(v,vis[u]^1,u);
}
}
int main()
{
memset(vis,-1,sizeof(vis));
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for(int i=1;i<=n;i++)
if(vis[i]==-1) dfs(i,0,-1);
printf("YES\n");
for(int i=1;i<n;i++)
printf("%d ",vis[i]);
cout<<vis[n]<<endl;
return 0;
}
```
## 第三题
### 题意
给你一个n*m的矩阵，n、m小于等于5
上面有数字0~9和X，X代表墙，0~9每种数字代表一种动物,你要给同种动物进行两两配对，配对的价值为连线的最短距离。规则类似于连连看，连线不能穿墙，不能穿过还没消掉的动物，一开始没有空格子，只能消相邻的，消相邻的花费为0。消掉之后就会留下空格子。最后输出要求配对组数最大，花费尽量小
### 样例
#### 输入
3 4
XX0X
X11X
X0XX
#### 输出
2 2
要先消1 1，然后才能消0 0，组数2，花费2
然后。。。正解是bfs+哈希表orz
然后贴一段题解：
本题最难，是用宽度优先搜索加上哈希表处理的。首先状态的表示有难度，其实每一状态只与消去动物的位置(空白位置)有关，未消去部分与初始状态相同，因此无需记录。由于动物总数不超过mn=25个，所以任一状态只要用一个mn位二进制数(程序中用一个长整型数)表示，每一位二进制表示一个动物的状态，1表示该位二进制位对应的动物已消去，0表示该位二进制位对应的动物还未消去，初始状态(所有动物都健在)用0表示。另外障碍物'X'不用记录，可以通过预处理将'X'去掉，具体来说就是将棋盘看作一个图，每个动物即为图的一个顶点，顶点编号即为动物在输入文件中的序号(不计'X')，输入文件中的第一个动物序号为1(即程序中的下标)，第i个动物的类别记录在board[i]中，其位置记录在row[i]和col[i]中，第i个动物的状态对应二进制数的从最高位往后数的第i位，第1个动物的状态对应最高位。两个动物所在的格子在棋盘上相邻则表示图中有一条对应的边，程序中用邻接表link表示，只有直接相邻或通过空白位置(消去动物后的格子)间接相邻的同类动物才能被消去。hash表len记录到达相应状态(下标对应的二进制数)的最优解(消去动物的最小代价)。从初始状态出发，用队列依次生成所有状态，队列用链表存储，链表结点的data域对应的二进制数代表棋盘状态，而该状态的最优解记录在hash表len中，len[i]=255表示状态i不在链表中，len[i]<255表示状态i在链表中，这样判断一个状态前面有没有出现过且是否最优就很方便了。由于每次总是只消去两个动物，即只改变状态(二进制数)中的某两位，所以程序中用了位运算操作shl、shr和and等。本程序仅一个hash表就用了2^(m*n)B≈33MB的内存，如果动物总数真的达到或接近25个且均为同种动物的话，程序将要超时，其它情况均能在规定时限内出解，我认为在题目中加上动物总数不超过20个的限制会更好一些，当然上述情况也可能可以通过预处理解决，如若干个同种动物聚集在一起时，可以先单独处理一下，即先消这一块，再消其它动物，但这样做不一定划算，因为在增加编程复杂度的同时你所假想数据并没有出现，会令你很失望，这种情况在比赛中经常遇到，一些高手总会为之惆怅良久并扼腕叹息(没选上)，所以对24个以上同种动物用个if语句输出12 0，其它情况用随机化算法亦不失为一种高效投机算法。由于本算法对每个结点仅扩展一次，且扩展过的结点立刻从链表中释放以节约内存，本算法应该是最快的完备算法了，也许用记忆化搜索(沿用同样的状态表示)加上剪枝会更快些。实际上用随机化算法简单写一个程序也行，数据实在太弱了。
然后正解代码：
```
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int read() {
int tot=0,fh=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') fh=-1;c=getchar();}
while (c>='0'&&c<='9') {tot=tot*10+c-'0';c=getchar();}
return tot*fh;
}
const int maxn=34000000;
short n,m,f[maxn],g[maxn];
int qx[100],qy[100];
char mp[7][7];
int tx[]={0,0,1,-1},ty[]={1,-1,0,0};
int calc(int x,int y) {return (x-1)*m+y-1;}
bool valid(int x,int y) {if (x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]!='X') return true;else return false;}
void solve(int x);
void bfs(int x,int y,int zt) {
int l=1,r=1;qx[1]=x,qy[1]=y;
short step[7][7];
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
step[i][j]=100;
step[x][y]=0;
while (l<=r) {
for (int i=0;i<4;i++)
if (valid(qx[l]+tx[i],qy[l]+ty[i])&&(zt&(1<<calc(qx[l]+tx[i],qy[l]+ty[i])))!=0
&&step[qx[l]][qy[l]]+1<step[qx[l]+tx[i]][qy[l]+ty[i]]) {
step[qx[l]+tx[i]][qy[l]+ty[i]]=step[qx[l]][qy[l]]+1;
r++;
qx[r]=qx[l]+tx[i];
qy[r]=qy[l]+ty[i];
}
l++;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (step[i][j]!=100) {
for (int k=0;k<4;k++) {
int dx=i+tx[k],dy=j+ty[k];
if (dx==x&&dy==y) continue;
if (valid(dx,dy)&&mp[dx][dy]==mp[x][y]&&(zt&(1<<calc(dx,dy)))==0) {
int tmp=zt+(1<<calc(x,y))+(1<<calc(dx,dy));
solve(tmp);
if (f[tmp]+1>f[zt]) {
f[zt]=f[tmp]+1;
g[zt]=g[tmp]+step[i][j];
} else {
if (f[tmp]+1==f[zt]&&g[zt]>g[tmp]+step[i][j]) g[zt]=g[tmp]+step[i][j];
}
}
}
}
}
void solve(int x) {
if (f[x]!=-1) return;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (((1<<calc(i,j))&x)==0&&mp[i][j]!='X') bfs(i,j,x);
if (f[x]==-1) f[x]=g[x]=0;
}
int main() {
freopen("pair.in","r",stdin);
freopen("pair.out","w",stdout);
n=read();m=read();
for (int i=1;i<=n;i++) {
char c=getchar();int len=0;
while ((c<'0'||c>'9')&&c!='X') c=getchar();
while ((c>='0'&&c<='9')||c=='X') {mp[i][++len]=c;c=getchar();}
}
bool flag=true;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (mp[i][j]!=mp[1][1]) flag=false;
if (flag) {
if (mp[1][1]=='X') cout<<"0 0"<<"\n";
else cout<<n*m/2<<" 0"<<"\n";
return 0;
}
for (int i=0;i<(1<<(n*m));i++) f[i]=g[i]=-1;
solve(0);
cout<<f[0]<<" "<<g[0]<<"\n";
return 0;
}
```
然后。。。我打了一个错的bfs，成功骗到了80分。
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,cnt=0,sum=0,pre;
int f[15],vis[10][10];
int det[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int a[10][10];
struct PPP
{
int x,y,s;
}q[100100],u,v;
void bfs(int x,int y)
{
memset(vis,0,sizeof(vis));
int l=0,r=1;
q[1].x=x,q[1].y=y,q[1].s=0;vis[x][y]=1;
while(l<r)
{
u=q[++l];
for(int i=0;i<4;i++)
{
v.x=u.x+det[i][0],v.y=u.y+det[i][1],v.s=u.s+1;
if(vis[v.x][v.y]) continue;
if(a[v.x][v.y]!=0 && a[v.x][v.y]!=a[x][y]) continue;
if(a[v.x][v.y]==a[x][y]) {cnt++;sum+=v.s-1;a[v.x][v.y]=a[x][y]=0;return;}
vis[v.x][v.y]=1;
q[++r]=v;
}
}
}
int main()
{
memset(a,-1,sizeof(a));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
char tmp[10];
scanf("%s",tmp+1);
for(int j=1;j<=m;j++)
if(tmp[j]>='0' && tmp[j]<='9') a[i][j]=tmp[j]-'0'+1;
}
while(1)
{
pre=cnt;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]>0) bfs(i,j);
if(cnt==pre) break;
}
printf("%d %d",cnt,sum);
return 0;
}
```
然后某大佬的记忆化搜索，成功地弄到了100分，其实也是卡时间的orz，鉴于数据比较水，所以也过了
```
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define R(i,s,t) for(int i=s;i<=t;i++)
#define GN(x,y) ((x)*m+(y))
using namespace std;
typedef pair<int,int> pii;
int n,m,ans,low;
char s[6][6];
void update(int p,int l) {
if(p>ans) {ans=p; low=l;}
else if(p==ans) low=min(low,l);
}
int cnt,vis[34000000];
void dfs(int p,int l,int state) {
if(++cnt>1e6) return;
if(vis[state]<=l) return;
vis[state]=l;
update(p,l);
R(i,0,n-1) R(j,0,m-1) if(isdigit(s[i][j])) {
char rec=s[i][j];
queue<pii> q;
q.push(make_pair(GN(i,j),0));
bool vis[5][5]; memset(vis,0,sizeof vis);
while(!q.empty()) {
int cur=q.front().first,step=q.front().second;
q.pop(); int r=cur/m,c=cur%m,rc=GN(i,j);
if(c>0) {
if(s[r][c-1]==s[i][j]&&(r!=i||c-1!=j)) {
s[r][c-1]=s[i][j]='*';
dfs(p+1,l+step,state|1<<rc|1<<GN(r,c-1));
s[r][c-1]=s[i][j]=rec;
}
if(s[r][c-1]=='*'&&!vis[r][c-1])
{vis[r][c-1]=true; q.push(make_pair(GN(r,c-1),step+1));}
}
if(c<m-1) {
if(s[r][c+1]==s[i][j]&&(r!=i||c+1!=j)) {
s[r][c+1]=s[i][j]='*';
dfs(p+1,l+step,state|1<<rc|1<<GN(r,c+1));
s[r][c+1]=s[i][j]=rec;
}
if(s[r][c+1]=='*'&&!vis[r][c+1])
{vis[r][c+1]=true; q.push(make_pair(GN(r,c+1),step+1));}
}
if(r>0) {
if(s[r-1][c]==s[i][j]&&(r-1!=i||c!=j)) {
s[r-1][c]=s[i][j]='*';
dfs(p+1,l+step,state|1<<rc|1<<GN(r-1,c));
s[r-1][c]=s[i][j]=rec;
}
if(s[r-1][c]=='*'&&!vis[r-1][c])
{vis[r-1][c]=true; q.push(make_pair(GN(r-1,c),step+1));}
}
if(r<n-1) {
if(s[r+1][c]==s[i][j]&&(r+1!=i||c!=j)) {
s[r+1][c]=s[i][j]='*';
dfs(p+1,l+step,state|1<<rc|1<<GN(r+1,c));
s[r+1][c]=s[i][j]=rec;
}
if(s[r+1][c]=='*'&&!vis[r+1][c])
{vis[r+1][c]=true; q.push(make_pair(GN(r+1,c),step+1));}
}
}
}
}
int main() {
#ifdef LOCAL
freopen("pair.in","r",stdin);
#endif
cin>>n>>m;
R(i,0,n-1) cin>>s[i];
memset(vis,0x3f,sizeof vis);
dfs(0,0,0);
cout<<ans<<' '<<low<<endl;
return 0;
}
```