20191015测试总结

T1:WOJ4218

就是一个大暴力。忘记了判断一个是否存在了导致得分很低,以后大暴力还是不能对自己的正确性太自信,要多检查啊。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int t, top, s[10], row[10][10], col[10][10], squ[10][10], a[10][10][105];
char ss[20][20];
int find(int x, int y)
{
if (x <= 3)
{
if (y <= 3)
return 1;
if (y <= 6)
return 2;
if (y <= 9)
return 3;
}
if (x <= 6)
{
if (y <= 3)
return 4;
if (y <= 6)
return 5;
if (y <= 9)
return 6;
}
if (x <= 9)
{
if (y <= 3)
return 7;
if (y <= 6)
return 8;
if (y <= 9)
return 9;
}
return 0;
}
int main()
{
for (int i = 1; i <= 19; ++i)
{
scanf("%s", ss[i]);
if (!(i & 1))
for (int j = 1; j < 19; j += 2)
a[i >> 1][(j >> 1) + 1][0] = ss[i][j] ^ 48;
}
for (int i = 1; i <= 9; ++i)
for (int j = 1; j <= 9; ++j)
if (a[i][j][0])
{
int k = a[i][j][0];
row[i][k] = 1;
col[j][k] = 1;
squ[find(i, j)][k] = 1;
}
scanf("%d", &t);
for (int tt = 1; tt <= t; ++tt)
{
char type[10];
scanf("%s", type);
if (type[0] == 'I')
{
for (int i = 1; i <= 9; ++i)
for (int j = 1; j <= 9; ++j)
a[i][j][tt] = a[i][j][tt - 1];
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
if (a[x][y][tt])
{
puts("Error!");
continue;
}
if (row[x][k])
{
puts("Error:row!");
continue;
}
if (col[y][k])
{
puts("Error:column!");
continue;
}
if (squ[find(x, y)][k])
{
puts("Error:square!");
continue;
}
a[x][y][tt] = k;
row[x][k] = 1;
col[y][k] = 1;
squ[find(x, y)][k] = 1;
puts("OK!");
}
if (type[0] == 'D')
{
for (int i = 1; i <= 9; ++i)
for (int j = 1; j <= 9; ++j)
a[i][j][tt] = a[i][j][tt - 1];
int x, y;
scanf("%d%d", &x, &y);
if (!a[x][y][tt])
{
puts("Error!");
continue;
}
int k = a[x][y][tt];
a[x][y][tt] = 0;
row[x][k] = 0;
col[y][k] = 0;
squ[find(x, y)][k] = 0;
puts("OK!");
}
if (type[0] == 'Q')
{
for (int i = 1; i <= 9; ++i)
for (int j = 1; j <= 9; ++j)
a[i][j][tt] = a[i][j][tt - 1];
int x, y;
scanf("%d%d", &x, &y);
if (a[x][y][tt])
{
puts("Error!");
continue;
}
top = 0;
for (int i = 1; i <= 9; ++i)
if (!row[x][i] && !col[y][i] && !squ[find(x, y)][i])
s[++top] = i;
printf("%d\n", top);
for (int i = 1; i <= top; ++i)
printf("%d\n", s[i]);
}
if (type[0] == 'M')
{
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
memset(squ, 0, sizeof(squ));
int x, y, ans[2] = {0};
scanf("%d%d", &x, &y);
for (int i = 1; i <= 9; ++i)
for (int j = 1; j <= 9; ++j)
{
if (a[i][j][x])
{
int k = a[i][j][x];
if (!row[i][k] && !col[j][k] && !squ[find(i, j)][k])
{
a[i][j][tt] = k;
row[i][k] = 1;
col[j][k] = 1;
squ[find(i, j)][k] = 1;
++ans[0];
}
}
if (!a[i][j][tt] && a[i][j][y])
{
int k = a[i][j][y];
if (!row[i][k] && !col[j][k] && !squ[find(i, j)][k])
{
a[i][j][tt] = k;
row[i][k] = 1;
col[j][k] = 1;
squ[find(i, j)][k] = 1;
++ans[1];
}
}
}
if (x == y)
ans[1] = ans[0];
printf("%d %d\n", ans[0], ans[1]);
}
if (type[0] == 'P')
{
for (int i = 1; i <= 9; ++i)
for (int j = 1; j <= 9; ++j)
a[i][j][tt] = a[i][j][tt - 1];
for (int i = 1; i <= 9; ++i)
{
for (int j = 1; j <= 19; ++j)
if (j & 1)
putchar('+');
else
putchar('-');
putchar('\n');
for (int j = 1; j <= 9; ++j)
printf("|%d", a[i][j][tt]);
putchar('|');
putchar('\n');
}
for (int i = 1; i <= 19; ++i)
if (i & 1)
putchar('+');
else
putchar('-');
putchar('\n');
}
}
return 0;
}

T2:WOJ4219

题目其实就是Johnson不等式的标准式子,不过我忘了qwq(虽然好像大家都忘了)

这种贪心当时直接从一些直接的值来考虑了, 但是套路应该是两两比较,看哪个更优。果然我做过的题还是太少。

PS:注意比较相等的时候的状况
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int t, n;
long long c[50005], sum[50005];
struct node
{
int a;
int b;
} a[50005];
bool cmp(node aa, node bb)
{
if (min(aa.a, bb.b) == min(bb.a, aa.b))
return aa.a < bb.a;
return min(aa.a, bb.b) < min(bb.a, aa.b);
}
int main()
{
scanf("%d", &t);
for (int tt = 1; tt <= t; ++tt)
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &a[i].a, &a[i].b);
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; ++i)
{
sum[i] = sum[i - 1] + a[i].a;
c[i] = max(c[i - 1], sum[i]) + a[i].b;
}
printf("%lld\n", c[n]);
}
return 0;
}

T3:WOJ4220

非常恶心的期望题目,细节太多这里就不详细说了,自己看题解。

果然我的数学板块非常短板,需要恶补啊。
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
long long n, k;
int num;
double pp, ans[2], an;
int main()
{
scanf("%lld%lf", &n, &pp);
k = n - 1;
while (k)
{
k >>= 1;
++num;
}
for (int i = num; i >= 1; --i)
{
double p = (double)(n - ((n >> i) * (1LL << (i - 1)) + min(n - (n >> i) * (1LL << i), 1LL << (i - 1)))) / (double)n;
ans[0] += 2.0 * (1.0 - p) * p * (1LL << (i - 1));
}
if (n != 1)
{
long long sum, cnt;
double tot = 0.0;
--n;
k = 1;
while (k <= n)
k <<= 1;
sum = k - 1;
k >>= 1;
tot += (double)sum * (n - k + 1);
tot += (double)k * k;
cnt = k;
sum >>= 1;
while (k != 1)
{
k >>= 1;
sum >>= 1;
if (n & k)
{
tot += (double)cnt * k;
tot += (double)(cnt >> 1) * sum;
cnt >>= 1;
}
else
tot += (double)(cnt >> 1) * k;
}
ans[1] = tot / (double)(n + 1);
}
an = (1.0 - pp) * ans[0] + pp * ans[1];
num = 0;
while (an >= 10.0)
{
an /= 10.0;
++num;
}
while (an > 0.0 && an < 1.0)
{
an *= 10.0;
--num;
}
printf("%.5f %d", an, num);
return 0;
}

 

评论

此博客中的热门博文

min-max反演