CodeforcesRound#231(Div.2)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#231(Div.2),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4878字,纯文字阅读大概需要7分钟。
内容图文
![CodeforcesRound#231(Div.2)](/upload/InfoBanner/zyjiaocheng/531/23d14c4ee5c943449181e5445d30a38a.jpg)
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 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。