KIDx 的解题报告
题目链接：http://codeforces.com/contest/136
以下省略头文件
前三题是超级水题，不解释；后两题是很不错的水题，详细解释
?
A题
?#include <iostream>
using namespace std;
#define M 105
int 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 105
int 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 100005
int 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 10
struct 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++)
{ //找到非正方形的点存放到tp
if (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 100005
char 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;
}
?
相关文章
