codeforces C. Valera and Tubes

http://codeforces.com/contest/441/problem/C

题意：有n×m个方格，然后把这些方格分成k部分，每个部分内的方格的坐标满足|x_i - x_i + 1| + |y_i - y_i + 1| = 1，且每一个部分内的方格数>=2，输出其中的一种方案。

思路：贪心，先让k-1部分，每一部分占2个方格，依次按照蛇形划分，剩余划分到最后一个内。

 #include <cstdio>

 #include <iostream>

 #include <cmath>

 #include <vector>

 #include <cstring>

 #include <algorithm>

 #define maxn 1000100

 #define ll long long

 using namespace std;

 int n,m,k;

 struct node

 {

     int x,y;

 } st;

 int main()

 {

     cin>>n>>m>>k;

     vector<node>g[];

     int cnt=;

     int x=;

     for(int i=; i<=n; i++)

     {

         if(i%)

         {

             for(int j=; j<=m; j++)

             {

                 cnt++;

                 st.x=i;

                 st.y=j;

                 g[x].push_back(st);

                 if(x<k-)

                 {

                     if(cnt%==)

                     {

                         x++;

                     }

                 }

             }

         }

         else

         {

             for(int j=m; j>=; j--)

             {

                 cnt++;

                 st.x=i;

                 st.y=j;

                 g[x].push_back(st);

                 if(x<k-)

                 {

                     if(cnt%==)

                     {

                         x++;

                     }

                 }

             }

         }

     }

     for(int i=; i<k; i++)

     {

        printf("%d ",(int)g[i].size());

        for(int j=; j<(int)g[i].size(); j++)

        {

            st=g[i][j];

            printf("%d %d ",st.x,st.y);

        }

        printf("\n");

     }

     return ;

 }

巴特西

codeforces C. Valera and Tubes

最新文章

热门文章