CodeforcesRound#231(Div.2)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#231(Div.2)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4878字，纯文字阅读大概需要7分钟。
内容图文
Problems # Name A Counting Sticks standard input/output 1 s, 256 MB x2326 B Very Beautiful Number standard input/output 1 s, 256 MB x856 C Dominoes standard input/output 2 s, 256 MB x803 D Physical Education and Buns standard input/output
Problems
| # | Name | ||
|---|---|---|---|
| A |
Counting Sticks
standard input/output 1 s, 256 MB |
|
|
| B |
Very Beautiful Number
standard input/output 1 s, 256 MB |
|
|
| C |
Dominoes
standard input/output 2 s, 256 MB |
|
|
| D |
Physical Education and Buns
standard input/output 2 s, 256 MB |
|
|
| E |
Lightbulb for Minister
standard input/output 1 s, 256 MB |
|
|
A题：先处理字符串把3个位置的数字保存下来，在去判断相等或者差值为2，去移动即可。
B题：枚举最后一位数字，模拟往前推数字，推到第一位判断是不是和一开始枚举的数字相同。
C题：贪心，10和01其实是一样的，所以先保存下11，10和01的总数，00的个数，先从左往右放11，放完之后，在从右边往左边去放10,01，每行交替着放即可，剩下的就是00。
D题：从小到大排序后，先枚举公差d，先变化后的序列A1是0，然后求出整个需要去向上移动的最大值和最小值（可能是负的），那么变化后的序列其实可以看成一条斜率k是d，b是A1的直线，然后这条直线无论上移下移，那么对于最大值和最小值肯定还是原来那2个位置，那么只要保证移动到最大值和最小值中的最大值尽可能小，那么就是去中间肯定是最优的，为(up + down + 1)/2 （要向上取整所以+1），最后维护ans的最小值即可。
D题：还有一种解法，二分答案，然后去判断，判断的方式先枚举公差，在用O(n)的方法去维护每个上下区间从大到小。
代码：
A题：
#include#include char c; int main() { int num[3], s = 0; memset(num, 0, sizeof(num)); while ((c = getchar()) != EOF && c != '\n') { if (c == '+' || c == '=') s++; else num[s]++; } if (num[0] - 1 + num[1] == num[2] + 1) { if (num[0] == 1) num[1]--; else if (num[1] == 1) num[0]--; else if (num[0] != 1 && num[1] != 1) num[0]--; num[2]++; } else if (num[0] + num[1] == num[2]) { } else if (num[0] + 1 + num[1] == num[2] - 1) { if (num[2] == 1) { printf("Impossible\n"); return 0; } num[2]--; num[0]++; } else { printf("Impossible\n"); return 0; } int i; for (i = 0; i < num[0]; i++) printf("|"); printf("+"); for (i = 0;i < num[1]; i++) printf("|"); printf("="); for (i = 0; i < num[2]; i++) printf("|"); printf("\n"); return 0; }
B题：
#include#include int p, x, ans[1000005]; int main() { scanf("%d%d", &p, &x); int yu = 0; for (int i = 0; i <= 9; i++) { int s = i; int j; yu = 0; for (j = 0; j < p; j++) { ans[j] = s; int ji = s * x + yu; s = ji % 10; yu = ji / 10; } if (s == i && j == p && ans[p - 1] != 0 && yu == 0) { for (int j = p - 1; j >= 0; j--) printf("%d", ans[j]); printf("\n"); return 0; } } printf("Impossible\n"); return 0; }
C题：
#include#include int n, m, i, j; int num10, num00, num11; char str[10], ans[1005][1005][4]; int main() { num10 = num00 = num11 = 0; scanf("%d%d", &n, &m); for (i = 0; i < n; i++) for (j = 0; j < m; j++) { scanf("%s", str); if (strcmp(str, "00") == 0) num00++; if (strcmp(str, "01") == 0 || strcmp(str, "10") == 0) num10++; if (strcmp(str, "11") == 0) num11++; } for (i = 0; i < n; i++) for (j = 0; j < m; j++) strcpy(ans[i][j], "00"); i = 0; j = 0; while (num11) { strcpy(ans[i][j], "11"); j++; if (j == m) { j = 0; i++; } num11--; } int jj = m - 1; while (num10) { strcpy(ans[i][jj], "10"); num10--; if (jj == j) break; jj--; } i++; jj = m - 1; while (num10) { strcpy(ans[i][jj], "01"); num10--; if (jj == j) break; jj--; } int flag = 0; j--; if (j == -1) { j = m - 1; i++; } while (num10) { if (flag == 0) strcpy(ans[i][j], "01"); else strcpy(ans[i][j], "10"); j--; if (j == -1) { j = m - 1; i++; flag = 1 - flag; } num10--; } for (i = 0; i < n; i++) { for (j = 0; j < m - 1; j++) { printf("%s ", ans[i][j]); } printf("%s\n", ans[i][j]); } return 0; }
D题1：
#include#include #include #define INF 0x3f3f3f3f #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; const int N = 1005; int n, num[N]; void solve() { int ans = INF, start, dd; sort(num, num + n); for (int d = 0; d <= 20000; d++) { int up = -INF, down = INF; for (int i = 0; i < n; i++) { up = max(up, i * d - num[i]); down = min(down, i * d - num[i]); } int res = (up - down + 1) / 2; if (ans > res) { ans = res; start = -up + res; dd = d; } } printf("%d\n%d %d\n", ans, start, dd); } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &num[i]); solve(); return 0; }
D题2：
#include#include #include #define INF 0x3f3f3f3f #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; const int N = 1005; const int M = 10005; int n, num[N], start, dd; bool judge(int Max) { for (int d = 0; d <= 20000; d++) { int up = num[n - 1] + Max, down = num[n - 1] - Max; for (int i = n - 2; i >= 0; i--) { up = min(num[i] + Max, up - d); down = max(num[i] - Max, down - d); } if (down <= up) { start = down; dd = d; return true; } } return false; } void solve() { int l = 0, r = M; sort(num, num + n); while (l < r) { int mid = (l + r) / 2; if (judge(mid)) r = mid; else l = mid + 1; } printf("%d\n%d %d\n", l, start, dd); } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &num[i]); solve(); return 0; }
内容总结
以上是互联网集市为您收集整理的CodeforcesRound#231(Div.2)全部内容，希望文章能够帮你解决CodeforcesRound#231(Div.2)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。