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 <stdio.h>
#include <string.h>
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 <stdio.h>
#include <string.h>
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 <stdio.h>
#include <string.h>
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 <stdio.h>
#include <string.h>
#include <algorithm>
#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 <stdio.h>
#include <string.h>
#include <algorithm>
#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;
}
