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 |
 
|
 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 2 s, 256 MB |
|
x234 |
| E |
Lightbulb for Minister
standard input/output 1 s, 256 MB |
|
x49 |
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; }
