首页 > 代码库 > Codeforces 758C：Unfair Poll（思维+模拟）
Codeforces 758C：Unfair Poll（思维+模拟）
http://codeforces.com/problemset/problem/758/C
题意：教室里有n列m排，老师上课点名从第一列第一排开始往后点，直到点到第一列第m排，就从第二列第一排开始点，当点完第n列的名之后，接着点第n-1列的名。以此类推，就是从列上来看的话：1,2,3,4，……，n，n-1，n-2，……，1 ，2，……。这样的顺序点名。老师上课总共点k次名，问该课堂最多可以点同一个同学多少次，最少可以点同一个同学多少次，点了位置为（x，y）的同学多少次名。
思路：一遇到这种题目就有点血崩。确信以为是一条公式可以做出来的题目，然后写了一页草稿纸，连样例都过不了，不知所措。赛后想看看别人的公式，结果看过的都是通过计算+模拟的。既然用计算机了，在符合时间复杂度的情况下用模拟帮助计算，好像没什么问题啊。（为什么我就直接确信直接去推公式了，而且好像也不是第一次犯这种错误了啊）。
首先要注意点名的列顺序，好像挺多人都没看懂题目（就算我看懂了然并卵），假设n是4，那么顺序是1,2,3,4,3,2,1,2,3，……。这样的，所以从列来看一个周期是（n+n-2），因为当n = 1的时候这条式子等于0，所以要特判n = 1的情况。如果n = 1的话，那么每次都是点这一排了，最多的人是算了k / m次，剩下的用k % m从第一排去模拟加上，直到那个余数变成0为止。如果n > 1的话，那么每个周期点第1列和第n列的次数是只有一次，而点2~n-1列的次数是有两次，那么可以点的周期数 = k / m / (n+n-2），然后剩下的用k % （m * （n+n-2））去模拟。因为初始是从第一列开始的，所以从第一列开始扫起。
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <queue> 8 #include <vector> 9 #include <map>10 #include <set>11 #include <stack>12 using namespace std;13 #define INF 0x3f3f3f3f14 #define N 10001015 typedef long long LL;16 LL mp[105][105];17 18 int main() {19 int x, y, n, m;20 LL k;21 cin >> n >> m >> k >> x >> y;22 LL mi = -1, ma = -1;23 if(n == 1) {24 LL yu = k % m;25 LL cnt = k / m;26 for(int i = 1; i <= m; i++) mp[1][i] += cnt;27 for(int i = 1; i <= m; i++)28 if(yu) mp[1][i]++, yu--;29 } else {30 LL num = (n + n - 2) * m;31 LL cnt = k / num; // 周期数32 LL yu = k % num;33 for(int i = 1; i <= n; i++)34 for(int j = 1; j <= m; j++)35 if(i == 1 || i == n) mp[i][j] += cnt;36 else mp[i][j] += cnt * 2;37 for(int i = 1; i <= n; i++)38 for(int j = 1; j <= m; j++)39 if(yu) mp[i][j]++, yu--;40 for(int i = n - 1; i >= 1; i--)41 for(int j = 1; j <= m; j++)42 if(yu) mp[i][j]++, yu--;43 }44 for(int i = 1; i <= n; i++) {45 for(int j = 1; j <= m; j++) {46 if(ma < mp[i][j]) ma = mp[i][j];47 if(mi == -1 || mi > mp[i][j]) mi = mp[i][j];48 }49 }50 printf("%I64d %I64d %I64d\n", ma, mi, mp[x][y]);51 return 0;52 }
Codeforces 758C：Unfair Poll（思维+模拟）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。