題目鏈接：點擊查看

題目大意：給出一個n*m的農場，其中'.'代表空地，'R'代表大米，現在有k只雞需要分布在這個農場之中，需要滿足以下條件：

每個方格都要被雞占領

每只雞至少占領一個方格

每只雞占領的方格必須連通，并且設所占領的大米數為cnt

要求每只雞占領的cnt最大值與最小值差值最小

用0~9，a~z以及A~Z代表62只雞，要求構造合適的占領方案

題目分析：因為要求每只雞占領的方格連通，所以我們直接連通的跑完整個矩陣就好了，可以選擇S形遍歷，也可以選擇回字形遍歷，不管怎么樣，只要保證前后連通即可，既然題目要求占有大米的值最大值與最小值差值最小，我們讓其差值為0或1就可以了，0或1主要取決于大米的數量能否整除雞的數量，合理分配就好了

注意一下，我一開始寫的代碼在test2WA掉了，想了半天找不到錯誤，去cf拿數據看了一眼，這里放上來可以調試一下吧：

2 9 3 .R..R..R. .R..R..R.

ans:

000001111 222222211

別的就沒什么注意的了，我用的S形遍歷，自認為寫的還是比較清晰簡單的吧

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;const string ss="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";char maze[N][N],ans[N][N];int target,sum,cnt1,cnt2,pos;void solve(int x,int y)//處理每個方塊 {ans[x][y]=ss[pos];if(maze[x][y]=='R')sum++;if(cnt1)//如果target+1的方塊還沒處理完，優先處理{if(sum==target+1){cnt1--;pos++;sum=0;}}else if(sum==target&&cnt2)//最后處理target的方塊{cnt2--;if(cnt2)//注意這里特判，到了最后一個方塊后pos就不再加一了{pos++;sum=0;}} } int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n,m,k;memset(ans,0,sizeof(ans));//記得初始化scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)scanf("%s",maze[i]+1);int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(maze[i][j]=='R')cnt++;target=cnt/k;//記錄每個雞需要占領的米，分別為target和target+1cnt1=cnt%k;//cnt1個雞有target+1個R cnt2=k-cnt1;//cnt2個雞有target個Rpos=0;//記錄字符下標 sum=0;//記錄當前的雞占有多少米了 for(int i=1;i<=n;i++){if(i&1){for(int j=1;j<=m;j++)solve(i,j);}else{for(int j=m;j>=1;j--)solve(i,j);}} for(int i=1;i<=n;i++)printf("%s\n",ans[i]+1);}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1255D Feeding Chicken(贪心+构造+模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。