Codeforces Beta Round #97 (Div. 2) 【完整题解】

KIDx 的解题报告
题目链接：http://codeforces.com/contest/136
以下省略头文件

前三题是超级水题，不解释；后两题是很不错的水题，详细解释

?

A题

#include <iostream>using namespace std;#define M 105int pre[M];int main(){int n, i, x;while (~scanf ("%d", &n)){for (i = 1; i <= n; i++)scanf ("%d", &x), pre[x] = i;for (i = 1; i < n; i++)printf ("%d ", pre[i]);printf ("%d\n", pre[i]);}    return 0;}

?

B题

#include <iostream>#include <cmath>using namespace std;#define M 105int a[M], c[M], b[M];int main(){int x, y, k, n, maxs, res, i;while (~scanf ("%d%d", &x, &y)){memset (a, 0, sizeof(a));memset (c, 0, sizeof(c));k = 0;while (x){a[k++] = x % 3;x /= 3;}n = 0;while (y){c[n++] = y % 3;y /= 3;}maxs = max (n, k);res = 0;for (i = 0; i < maxs; i++){if (c[i] >= a[i])b[i] = c[i] - a[i];else b[i] = c[i] + 3 - a[i];res += b[i] * pow (3.0, i);}printf ("%d\n", res);}    return 0;}

?

C题

#include <iostream>#include <algorithm>using namespace std;#define M 100005int a[M];int main(){int n, i;while (~scanf ("%d", &n)){for (i = 0; i < n; i++)scanf ("%d", a+i);sort (a, a+n);if (a[n-1] == 1)    //注意一下全部是1的情况即可a[n-1] = 2;else a[n-1] = 1, sort (a, a+n);printf ("%d", a[0]);for (i = 1; i < n; i++)printf (" %d", a[i]);printf ("\n");}    return 0;}

?

D题

#include <iostream>#include <algorithm>#include <cmath>using namespace std;#define eps 1e-8#define M 10struct point{double x, y;}p[M], tp[M];double dist (point a, point b){return sqrt ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));}double dianmulti (point a, point b, point c)    //求ab与bc的点积{double x1 = b.x - a.x;double y1 = b.y - a.y;double x2 = c.x - b.x;double y2 = c.y - b.y;return x1*x2+y1*y2;}int main(){int i, j, k, l, ind, q, v, ed, mid, snum[M], ans;bool hash[M];double maxs, a[5];while (~scanf ("%lf%lf", &p[0].x, &p[0].y)){for (i = 1; i < 8; i++)scanf ("%lf%lf", &p[i].x, &p[i].y);memset (hash, false, sizeof(hash));for (i = 0; i < 8; i++){for (j = i + 1; j < 8; j++){for (k = j + 1; k < 8; k++){for (l = k + 1; l < 8; l++){ind = ans = 0;tp[ind++] = p[i];tp[ind++] = p[j];tp[ind++] = p[k];tp[ind++] = p[l];//tp存放四边形的点snum[ans++] = i + 1;snum[ans++] = j + 1;snum[ans++] = k + 1;snum[ans++] = l + 1;    //记录组成四边形的点的编号maxs = 0;for (q = 1; q < ind; q++){//找出v使得tp[0],tp[v]组成对角线double dis = dist (tp[0], tp[q]);if (dis > maxs)maxs = dis, v = q;}ed = 0;for (q = 1; q < ind; q++){if (q != v){//找出四边形边长a[ed++] = dist (tp[0], tp[q]);a[ed++] = dist (tp[v], tp[q]);}}if (fabs (a[0]-a[1]) < eps &&fabs (a[0]-a[2]) < eps &&fabs (a[0]-a[3]) < eps){//判正方形四条边相等for (q = 1; q < ind; q++){if (q != v){mid = q;//tp[mid]是不同于tp[0]，tp[v]的点break;}}if (fabs (dianmulti (tp[0], tp[mid], tp[v])) < eps){//点积判0->mid是否垂直于mid->v//来到这里，说明i，j，k，l可以组成正方形//以下基本上同理了！ind = 0;for (q = 0; q < 8; q++){//找到非正方形的点存放到tpif (q != i && q != j && q != k && q != l)tp[ind++] = p[q];}maxs = 0;for (q = 1; q < ind; q++){double dis = dist (tp[0], tp[q]);if (dis > maxs)maxs = dis, v = q;}ed = 0;for (q = 1; q < ind; q++){if (q != v){a[ed++] = dist (tp[0], tp[q]);a[ed++] = dist (tp[v], tp[q]);}}sort (a, a+ed);    //排序方便判对边相等if (fabs (a[0]-a[1]) < eps &&fabs (a[2]-a[3]) < eps){//判长方形对边相等for (q = 1; q < ind; q++){if (q != v){mid = q;break;}}if (fabs (dianmulti (tp[0],tp[mid], tp[v])) < eps)goto end;//到这里,说明另外4点可以组成长方形}}}}}}}puts ("NO");continue;end:;puts ("YES");for (i = 0; i < ans - 1; i++)printf ("%d ", snum[i]), hash[snum[i]] = true;printf ("%d\n", snum[i]), hash[snum[i]] = true;ans = 0;for (i = 1; i <= 8; i++){if (!hash[i])snum[ans++] = i;//找出不是组成正方形的点}for (i = 0; i < ans - 1; i++)//再次输出printf ("%d ", snum[i]);printf ("%d\n", snum[i]);}    return 0;}

?

E题

思路：

设0的个数为n0，1的个数为n1，遇到？也会有n0++，n1++，因为0,1的个数完全可能由？构成

设w为？的个数

因为答案只有4种情况(00,01,10,11)，只要分别想办法试着构造即可

①n0 >?len-n0 (0的个数>1的个数)即必然可以构造出"00"

②n1 > len-n1+1 (1的个数>0的个数+1)必然可以构造出"11"

③除了①②情况外只剩下两种情况：

1.a个1,a个0(如果n0<=n1&&n0>=len/2则有可能出现此情况)：

按照游戏程序，必然要删掉a-1个1，a-1个0

2.a+1个1,a个0(n0>n1&&n1>=(len+1)/2……)：

按照游戏程序，必然要删掉a个1，a-1个0

即最后必然只剩下一个1，一个0

所以最后一个字符显然是不会被删掉的

那么

如果最后一个字符是1，显然答案01是可构造的

如果最后一个字符是0，显然10是可构造的

如果最后一个字符是？，则需分类讨论：

1.设？=1，则对于当前n0--，n1不变，然后再用上面绿色条件判定

2.设？=0，则对于当前n1--，n0不变，然后同理

#include <iostream>using namespace std;#define M 100005char s[M];int main(){int i, len, n0, n1, w;while (~scanf ("%s", s)){len = strlen (s);n0 = n1 = w = 0;for (i = 0; i < len; i++){if (s[i] == '?')n0++, n1++, w++;if (s[i] == '0')n0++;if (s[i] == '1')n1++;}if (n0 > len-n0)puts ("00");if (n0 <= n1 && n0 >= len/2 || n0 > n1 && n1 >= (len+1)/2){if (s[len-1] == '0')puts ("10");else if (s[len-1] == '1')puts ("01");else    //如果最后是?, 根据条件构造{if (n0-1 <= n1 && (n0-1) >= len/2 ||n0-1 > n1 && n1 >= (len+1)/2)puts ("01");if (n0 <= n1-1 && n0 >= len/2 ||n0 > n1-1 && (n1-1) >= (len+1)/2)puts ("10");}}if (n1 - (len-n1) > 1)puts ("11");}    return 0;}

?