codeforces C. Valera and Tubes

2023-09-10 阅读 20 评论 0

摘要：http://codeforces.com/contest/441/problem/C 题意：有nm个方格，然后把这些方格分成k部分，每个部分内的方格的坐标满足|xi - xi + 1| + |yi - yi + 1| = 1，且每一个部分内的方格数>=2，输出其中的一种方

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个方格，依次按照蛇形划分，剩余划分到最后一个内。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cmath>
 4 #include <vector>
 5 #include <cstring>
 6 #include <algorithm>
 7 #define maxn 1000100
 8 #define ll long long
 9 using namespace std;
10 
11 int n,m,k;
12 struct node
13 {
14     int x,y;
15 } st;
16 
17 int main()
18 {
19     cin>>n>>m>>k;
20     vector<node>g[100000];
21     int cnt=0;
22     int x=0;
23     for(int i=1; i<=n; i++)
24     {
25         if(i%2)
26         {
27             for(int j=1; j<=m; j++)
28             {
29                 cnt++;
30                 st.x=i;
31                 st.y=j;
32                 g[x].push_back(st);
33                 if(x<k-1)
34                 {
35                     if(cnt%2==0)
36                     {
37                         x++;
38                     }
39                 }
40             }
41         }
42         else
43         {
44             for(int j=m; j>=1; j--)
45             {
46                 cnt++;
47                 st.x=i;
48                 st.y=j;
49                 g[x].push_back(st);
50                 if(x<k-1)
51                 {
52                     if(cnt%2==0)
53                     {
54                         x++;
55                     }
56                 }
57             }
58         }
59     }
60     for(int i=0; i<k; i++)
61     {
62        printf("%d ",(int)g[i].size());
63        for(int j=0; j<(int)g[i].size(); j++)
64        {
65            st=g[i][j];
66            printf("%d %d ",st.x,st.y);
67        }
68        printf("\n");
69     }
70     return 0;
71 }