hustwinter1-A - Black And White

题意是说用k重颜色填充n*m的方格,第i种颜色要用ci次,保证ci(i属于1..k)的和为n"m,问是否有可行解,若有,输出任意一种。
第一感觉是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列可以归为一类,同理,后两种也可以归为一类。又交,又WA2333333  然后想了好久。。。 发现对于上面说的两类的处理顺序不同会得到不同的结果.......只有一种是对的。于是加了个judge函数判断冲突...如果冲突就换个顺序.....再交,A了。

 过程中出现了两个语法上的错误....一个是=写成了==(从来都是把==写成=。。。) 
                            另一个是无参数的函数依然要写()。。。。。。

确实不难....的确是我生疏了。hustwinter1-A - Black And White 

001 #include <iostream>
002 #include <algorithm>
003 #include <cstring>
004 
005 using namespace std;
006 
007     int c[100],cc[100];
008     int ans[10][10];
009     int colorid[100];
010     int n,m,k;
011     void look();
012 bool judge();
013 
014 
015 int main()
016 {
017     int tt;
018     int t;
019     int kk;
020 
021     cin>>t;
022     tt=t;
023 
024 
025     int i,j;
026     int head;
027     int flag;
028    while (t--)
029     {  head=1;
030     flag=1;
031          memset(ans,0,sizeof(ans));
032         cin>>n>>m>>k;
033         kk=k;
034         for (i=1;i<=k;i++)
035             cin>>c[i];
036 
037         for (i=1;i<=k;i++)
038             colorid[i]=i;
039         for (i=1;i<k;i++)
040             for (j=i+1;j<=k;j++)
041             if (c[i]>c[j])
042             {
043               swap(c[i],c[j]);
044               swap(colorid[i],colorid[j]);
045             }
046              for (i=1;i<=k;i++)
047                 cc[i]=c[i];
048 
049 
050 
051         if (c[k]>(n*m+1)/2)  { cout<<"Case #"<<tt-t<<":"<<endl;cout<<"NO"<<endl;continue;}
052 
053         for (i=1;i<=n;i++)
054             for (j=1;j<=m;j++)
055                 if ((i%2+j%2)%2==1)
056                 {
057                   if (flag%2==1)
058                   {
059 
060 
061                      ans[i][j]=colorid[k];
062                     // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
063 
064                      c[k]--;
065                      if (c[k]==0)
066                         {
067                             k--;
068                             flag++;
069 
070                         }
071                   }
072                   else
073                     {
074                         ans[i][j]=colorid[head];
075 
076                     //    cout<<"i:"<<i<<"j:"<<j<<"  "<<colorid[head]<<endl;
077                         c[head]--;
078                         if (c[head]==0)
079                         {
080                             head++;
081                             flag++;
082 
083                         }
084                     }
085                   //  look();
086                 }
087 
088 
089                 for (i=1;i<=n;i++)
090             for (j=1;j<=m;j++)
091                 if ((i%2+j%2)%2==0)
092                 {
093 
094 
095                     if (flag%2==1)
096                   {
097 
098 
099                      ans[i][j]=colorid[k];
100                   //   cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
101                      c[k]--;
102                      if (c[k]==0)
103                         {
104                             k--;
105                               flag++;
106                         }
107                   }
108                   else
109                     {
110                         ans[i][j]=colorid[head];
111                       // cout<<"i:"<<i<<"j:"<<j<<"  "<<colorid[head]<<endl;
112                         c[head]--;
113                         if (c[head]==0)
114                         {
115                             head++;
116                            flag++;
117                         }
118                     }
119                  //   look();
120                 }
121                cout<<"Case #"<<tt-t<<":"<<endl;
122                cout<<"YES"<<endl;
123 
124                 if (!judge())
125                      look();
126                else
127                {
128 
129 
130                    k=kk;
131                    head=1;
132                    flag=1;
133                    for (i=1;i<=k;i++)
134                        c[i]=cc[i];
135                    memset(ans,0,sizeof(ans));
136 
137                    for (i=1;i<=n;i++)
138                     for (j=1;j<=m;j++)
139                         if ((i%2+j%2)%2==0)
140                     {
141                         if (flag%2==1)
142                         {
143                      ans[i][j]=colorid[k];
144                    //  cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
145 
146                      c[k]--;
147                      if (c[k]==0)
148                         {
149                             k--;
150                             flag++;
151 
152                         }
153                   }
154                   else
155                     {
156                         ans[i][j]=colorid[head];
157 
158                      //   cout<<"i:"<<i<<"j:"<<j<<"  "<<colorid[head]<<endl;
159                         c[head]--;
160                         if (c[head]==0)
161                         {
162                             head++;
163                             flag++;
164 
165                         }
166                     }
167                   //  look();
168                 }
169                 for (i=1;i<=n;i++)
170             for (j=1;j<=m;j++)
171                 if ((i%2+j%2)%2==1)
172                 {
173 
174 
175                     if (flag%2==1)
176                   {
177 
178 
179                      ans[i][j]=colorid[k];
180                     // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
181                      c[k]--;
182                      if (c[k]==0)
183                         {
184                             k--;
185                               flag++;
186                         }
187                   }
188                   else
189                     {
190                         ans[i][j]=colorid[head];
191                      //  cout<<"i:"<<i<<"j:"<<j<<"  "<<colorid[head]<<endl;
192                         c[head]--;
193                         if (c[head]==0)
194                         {
195                             head++;
196                            flag++;
197                         }
198                     }
199                  //   look();
200                 }
201                   look();
202 
203                }
204 
205 
206 
207     }
208     return 0;
209 }
210 
211 
212 void look()
213 {
214     //  cout<<"lookkkkkkkkkkkkkkkkkkkkk"<<endl;
215     int i,j;
216     for (i=1;i<=n;i++)
217         for (j=1;j<=m;j++)
218             if (j!=m)
219           cout<<ans[i][j]<<" ";
220          else cout<<ans[i][j]<<endl;
221 
222 }
223 bool judge()
224 {
225     int i,j;
226     for (i=1;i<=n;i++)
227         for (j=1;j<m;j++)
228          if (ans[i][j]==ans[i][j+1])
229            return true;
230     for (i=1;i<n;i++)
231         for (j=1;j<=m;j++)
232         if (ans[i][j]==ans[i+1][j])
233           return true;
234       return false;
235 }

hustwinter1-A - Black And White

上一篇:利用.htaccess隐藏html和php后缀


下一篇:转:vs发布window应用程序时出错:未能签名 ...\setup.exe