【Luogu3005】槽的游戏The Trough Game

来源和评测点

USACO10 DEC
Luogu3005

题目

【题目大意】
农夫约翰在谷仓里藏起来了N(1<=N<=20)个槽,并且他已经把其中的一些装上了食物。
贝西以“在这个表里(表由贝西提供)有多少个槽里有食物?”的形式
问了M(1<=M<=100)个问题。现在,贝西想知道,哪几个槽里有食物?
【输入格式】
第一行是N、M
后面M行,
每行一个长度为N的01串,表示一个询问是否包含这个槽
然后是一个数字,表示回答
【输出格式】
如果可行,输出长度为N的01串,表示槽的状态
如果没有满足的方案,输出’IMPOSSIBLE’
如果方案不唯一,输出’NOT UNIQUE’
【输入样例】
4 4
1000 1
0110 1
1001 1
0011 1
【输出样例】
1010

分析1

这题一看数据输入输出就想到矩阵乘法
提问(m×n)(只有0、1)
真实(n×1)(只有0、1)
回答(m×1)
假如提问*真实=回答,则可行,
然后暴力搜索枚举出真实状况,然鹅这只能拿60分

代码1

这是TLE的,供参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct matrix
{
int row,col;
int a[120][120];
matrix()
{
memset(a,0,sizeof(a));
}
};
matrix cheng(matrix a,matrix b)
{
matrix c;
c.row=a.row;c.col=b.col;
for(int i=1;i<=c.row;i++)
for(int j=1;j<=c.col;j++)
for(int k=1;k<=a.col;k++)
c.a[i][j]+=a.a[i][k]*b.a[k][j];
return c;
}
bool same(matrix a,matrix b)
{
if(a.row!=b.row) return 0;
if(a.col!=b.col) return 0;
for(int i=1;i<=a.row;i++)
for(int j=1;j<=a.col;j++)
if(a.a[i][j]!=b.a[i][j])
return 0;
return 1;
}
int n,m;
matrix a,b,c,d,ans;
bool ero;
void dfs(int x)
{
if(ero) return;
if(x>n)
{
d=cheng(a,b);
if(same(c,d))
{
if(ans.row>0) ero=1;
else ans=b;
}
return;
}
b.a[x][1]=0;dfs(x+1);
b.a[x][1]=1;dfs(x+1);
}
char s[30];
int main()
{
ero=0;
scanf("%d%d",&n,&m);
a.row=m;a.col=n;
b.row=n;b.col=1;
c.row=m;c.col=1;
for(int i=1;i<=m;i++)
{
scanf("%s",s+1);
for(int j=1;j<=n;j++) a.a[i][j]=s[j]-'0';
scanf("%d",&c.a[i][1]);
}
dfs(1);
if(ero) printf("NOT UNIQUE");
else if(ans.row==0) printf("IMPOSSIBLE");
else for(int i=1;i<=n;i++) printf("%d",ans.a[i][1]);
}

分析2

接下来考虑剪枝:
根据提问中最后一个需要的槽状态排序
(所以一旦决定了那个槽,就能验证是否满足这个提问),
从而边枚举边乘,达到剪枝目的

注意因为排序内容比较多,我手写了一个二分排序

A了之后忽然想到
可以预处理出每添加一个槽状态所能多判断的提问区间,
每次判断哪些区间的提问就好了,这样时间复杂度会少灰常多。
然鹅我懒得改了,所以代码里面是从1到最后的

至于什么高斯消元……并不会

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int a[110][30],b[30],c[110];
int lt[110];//提问需要最末尾槽状态
int ans[30];bool ha=0;
bool ero;
bool cheng(int x)//被我改良后的矩阵乘法,x是确定了的槽编号
{
int i=1;
while(lt[i]<=x and i<=m)//区间限制
{
int t=0;
for(int k=1;k<=x;k++) t+=a[i][k]*b[k];
if(t!=c[i]) return 0;
i++;
}
return 1;
}
void dfs(int x)
{
if(ero) return;//多个答案
if(x>1 and !cheng(x-1)) return;//边做边判断
if(x>n)
{
if(ha>0) ero=1;
else {memcpy(ans,b,sizeof(b));ha=1;}
return;
}
b[x]=0;dfs(x+1);
b[x]=1;dfs(x+1);
}
void sort2(int l,int r)//手写二分排序
{
int x=l,y=r,mid=lt[(l+r)>>1];
while(x<=y)
{
while(lt[x]<mid and x<m) x++;
while(lt[y]>mid and y>1) y--;
if(x>y) break;
swap(lt[x],lt[y]);//都要交换
swap(a[x],a[y]);
swap(c[x],c[y]);
x++;y--;
}
if(l<y) sort2(l,y);
if(x<r) sort2(x,r);
}
char s[30];
int main()
{
ero=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%s",s+1);
for(int j=1;j<=n;j++)
{
a[i][j]=s[j]-'0';
if(a[i][j]==1) lt[i]=j;//记录
}
scanf("%d",&c[i]);
}
sort2(1,m);
dfs(1);
if(ero) printf("NOT UNIQUE");
else if(ha==0) printf("IMPOSSIBLE");
else for(int i=1;i<=n;i++) printf("%d",ans[i]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/1444.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%