Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意是说用 k 种颜色填充 nm 的方格，第 i 种颜色要用 c[i] 次，保证 c[i]（i 属于 1..k）的和为 nm，问是否有可行解，若有，输出任意一种。 第一感觉是 dfs，而且数据范围还那么小。但是鉴于我上次 dfs 写成汪的经历……嗯，不过群里有学长说似乎剪枝不太好想？ 我一开始分了四类：o 行 o 列、e 行 e 列、e 行 o 列、o 行 e 列（o 是 odd，e 是 even），然后将 c[i] 排序，先填大的 c[i]，感觉这样应该更容易找到解。交了一发，WA 掉了。发现当 k 较小的时候，也就是 c[i] 都相对较大的时候，先填大的 c[i] 的策略会出现错误。于是我换了下，按 c[i] 的大小从两边往中间填。然后我还发现其实 o 行 o 列和 e 行 e 列可以归为一类，同理，后两种也可以归为一类。又交，又 WA 2333333。然后想了好久，发现对于上面说的两类的处理顺序不同会得到不同的结果，只有一种是对的。于是加了个 judge 函数判断冲突，如果冲突就换个顺序。再交，A 了。
过程中出现了两个语法上的错误。一个是 = 写成了 ==（从来都是把 == 写成 =），另一个是无参数的函数依然要写 ()。
确实不难……的确是我生疏了。
代码实现
1
2
3 /* ***********************************************
4 Author :111qqz
5 Created Time :2016年02月19日 星期五 16时20分07秒
6 File Name :code/hdu/5113.cpp
7 ************************************************ */
8
9 #include <iostream>
10 #include <algorithm>
11 #include <cstring>
12
13 using namespace std;
14
15 int c[100],cc[100];
16 int ans[10][10];
17 int colorid[100];
18 int n,m,k;
19 void look();
20 bool judge();
21
22
23 int main()
24 {
25 int tt;
26 int t;
27 int kk;
28
29 cin>>t;
30 tt=t;
31
32
33 int i,j;
34 int head;
35 int flag;
36 while (t--)
37 { head=1;
38 flag=1;
39 memset(ans,0,sizeof(ans));
40 cin>>n>>m>>k;
41 kk=k;
42 for (i=1;i<=k;i++)
43 cin>>c[i];
44
45 for (i=1;i<=k;i++)
46 colorid[i]=i;
47 for (i=1;i<k;i++)
48 for (j=i+1;j<=k;j++)
49 if (c[i]>c[j])
50 {
51 swap(c[i],c[j]);
52 swap(colorid[i],colorid[j]);
53 }
54 for (i=1;i<=k;i++)
55 cc[i]=c[i];
56
57
58
59 if (c[k]>(n*m+1)/2) { cout<<"Case #"<<tt-t<<":"<<endl;cout<<"NO"<<endl;continue;}
60
61 for (i=1;i<=n;i++)
62 for (j=1;j<=m;j++)
63 if ((i%2+j%2)%2==1)
64 {
65 if (flag%2==1)
66 {
67
68
69 ans[i][j]=colorid[k];
70 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
71
72 c[k]--;
73 if (c[k]==0)
74 {
75 k--;
76 flag++;
77
78 }
79 }
80 else
81 {
82 ans[i][j]=colorid[head];
83
84 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
85 c[head]--;
86 if (c[head]==0)
87 {
88 head++;
89 flag++;
90
91 }
92 }
93 // look();
94 }
95
96
97 for (i=1;i<=n;i++)
98 for (j=1;j<=m;j++)
99 if ((i%2+j%2)%2==0)
100 {
101
102
103 if (flag%2==1)
104 {
105
106
107 ans[i][j]=colorid[k];
108 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
109 c[k]--;
110 if (c[k]==0)
111 {
112 k--;
113 flag++;
114 }
115 }
116 else
117 {
118 ans[i][j]=colorid[head];
119 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
120 c[head]--;
121 if (c[head]==0)
122 {
123 head++;
124 flag++;
125 }
126 }
127 // look();
128 }
129 cout<<"Case #"<<tt-t<<":"<<endl;
130 cout<<"YES"<<endl;
131
132 if (!judge())
133 look();
134 else
135 {
136
137
138 k=kk;
139 head=1;
140 flag=1;
141 for (i=1;i<=k;i++)
142 c[i]=cc[i];
143 memset(ans,0,sizeof(ans));
144
145 for (i=1;i<=n;i++)
146 for (j=1;j<=m;j++)
147 if ((i%2+j%2)%2==0)
148 {
149 if (flag%2==1)
150 {
151 ans[i][j]=colorid[k];
152 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
153
154 c[k]--;
155 if (c[k]==0)
156 {
157 k--;
158 flag++;
159
160 }
161 }
162 else
163 {
164 ans[i][j]=colorid[head];
165
166 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
167 c[head]--;
168 if (c[head]==0)
169 {
170 head++;
171 flag++;
172
173 }
174 }
175 // look();
176 }
177 for (i=1;i<=n;i++)
178 for (j=1;j<=m;j++)
179 if ((i%2+j%2)%2==1)
180 {
181
182
183 if (flag%2==1)
184 {
185
186
187 ans[i][j]=colorid[k];
188 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
189 c[k]--;
190 if (c[k]==0)
191 {
192 k--;
193 flag++;
194 }
195 }
196 else
197 {
198 ans[i][j]=colorid[head];
199 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
200 c[head]--;
201 if (c[head]==0)
202 {
203 head++;
204 flag++;
205 }
206 }
207 // look();
208 }
209 look();
210
211 }
212
213
214
215 }
216 return 0;
217 }
218
219
220 void look()
221 {
222 // cout<<"lookkkkkkkkkkkkkkkkkkkkk"<<endl;
223 int i,j;
224 for (i=1;i<=n;i++)
225 for (j=1;j<=m;j++)
226 if (j!=m)
227 cout<<ans[i][j]<<" ";
228 else cout<<ans[i][j]<<endl;
229
230 }
231 bool judge()
232 {
233 int i,j;
234 for (i=1;i<=n;i++)
235 for (j=1;j<m;j++)
236 if (ans[i][j]==ans[i][j+1])
237 return true;
238 for (i=1;i<n;i++)
239 for (j=1;j<=m;j++)
240 if (ans[i][j]==ans[i+1][j])
241 return true;
242 return false;
243 }