GYM102992 [2020-2021 ACM-ICPC, Asia Nanjing Regional Contest (XXI Open Cup, Grand Prix of Nanjing)](https://codeforces.com/gym/102992)
3题打铁，结论：三个人做一道题的时间是一个人写三题的时间
开场zxy签了个k和l,此期间zyj读+糊了个a题意给jyz，构造了几下wa了。
于是jyz和zyj去开f，zxy开m
过了f之后jyz接着搞a，zxy写e大力分类讨论写了200行，wa2
jyz持续搞a，中间也来写了发e，tle #2
尝试H但不清楚爆搜的复杂度，没敢写
a最后过了124组（125组算ac，xs）
A. Ah, It‘s Yesterday Once More
想了横着竖着放，还有各种仙人掌状的东西，快结束时jyz想到了斜着放的方案，但还是被卡在了#124, 赛后5min过了。
E. Evil Coordinate
考场上已经观察出了如果有解，同一个字母都连着用一定是一种解。但没有想到枚举4的全排列，而是大力分类讨论，200+行还是没有覆盖24种情况，，，
枚举排列好想又好写
// Problem: E. Evil Coordinate
// Contest: Codeforces - 2020-2021 ACM-ICPC, Asia Nanjing Regional Contest (XXI Open Cup, Grand Prix of Nanjing)
// URL: https://codeforces.com/gym/102992/problem/E
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
#define ll long long
int rd() {
int s = 0, f = 1; char c = getchar();
while (c < ‘0‘ || c > ‘9‘) {if (c == ‘-‘) f = -1; c = getchar();}
while (c >= ‘0‘ && c <= ‘9‘) {s = s * 10 + c - ‘0‘; c = getchar();}
return s * f;
}
int cnt[5], mx, my, tot, id[300], a[4];
char s[maxn], ans[maxn];
int nxt[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};//UDLR
int main() {
int T = rd();
id[‘U‘] = 0; id[‘D‘] = 1; id[‘L‘] = 2; id[‘R‘] = 3;
while (T--) {
mx = rd(), my = rd();
scanf("%s", s+1);
cnt[0] = cnt[1] = cnt[2] = cnt[3] = 0;
int n = strlen(s+1);
for (int i = 1; i <= n; i++) {
cnt[id[s[i]]]++;
}
a[0] = 0, a[1] = 1, a[2] = 2; a[3] = 3;
int x = 0, y = 0, flag = 0;//==1表示有解
do {
x = y = 0;
flag = 0;
if (x == mx && y == my) {
break;
}
for (int i = 0; i < 4; i++) {
for (int j = 1; j <= cnt[a[i]]; j++) {
x = x + nxt[a[i]][0];
y = y + nxt[a[i]][1];
if (x == mx && y == my) {
flag = -1; //经过了mx,my
break;
}
}
}
if (flag == -1) continue;
if (x != mx || y != my) {
flag = 1;
for (int i = 0; i < 4; i++) {
for (int j = 1; j <= cnt[a[i]]; j++) {
if (a[i] == 0) putchar(‘U‘);
else if (a[i] == 1) putchar(‘D‘);
else if (a[i] == 2) putchar(‘L‘);
else if (a[i] == 3) putchar(‘R‘);
}
}
printf("\n");
break;
}
if (flag == 1) break;
} while (next_permutation(a,a+4));
if (flag != 1) {
puts("Impossible");
}
}
return 0;
}
F. Fireworks
写出关于造火箭次数的函数之后jyz神奇地化了个式子出来，由于不会求导蒙了个三分的右端点（1e9），然后过了
假设最优方案是造\(k\)????个烟花，那么每造\(k\)个就放掉的总期望是
\[\begin{aligned}
&(nk+m)+(1-p)^{k}\times[nk+m+(1-p)^k\times(...)]\=&\sum_{i=0}^{\infty}(nk+m)\times{(1-p)^{ik}}\=&\frac{nk+m}{1-(1-p)^k}
\end{aligned}
\]
&(nk+m)+(1-p)^{k}\times[nk+m+(1-p)^k\times(...)]\=&\sum_{i=0}^{\infty}(nk+m)\times{(1-p)^{ik}}\=&\frac{nk+m}{1-(1-p)^k}
\end{aligned}
\]
将其记为关于\(k\)?的函数，它是单谷的，三分求解最小值即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
#define ll long long
double n, m, p, q;
int rd() {
int s = 0, f = 1; char c = getchar();
while (c < ‘0‘ || c > ‘9‘) {if (c == ‘-‘) f = -1; c = getchar();}
while (c >= ‘0‘ && c <= ‘9‘) {s = s * 10 + c - ‘0‘; c = getchar();}
return s * f;
}
double ksm(double a, ll b) {
double res = 1;
while (b) {
if (b & 1ll) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
double f(ll k) {
return (n*k+m)/(1.0-ksm(q, k));
}
int main() {
int T = rd();
while (T--) {
n = rd(), m = rd(), p = rd();
q = (10000-p) * 0.0001;
ll l = 1, r = 100000000000, lmid, rmid, k;
while (l < r) {
lmid = l + (r-l)/3ll;
rmid = r-(r-l)/3ll;
if (f(lmid) > f(rmid)) {
l = lmid + 1;
k = rmid;
} else {
r = rmid - 1;
k = lmid;
}
}
printf("%.6lf\n", f(k));
}
return 0;
}
H.[ Harmonius Rectangle](Problem - H - Codeforces)
正难则反，考虑求着色后\(n\times m\)个点中任意选俩个，都不能组成Harmonious Rectangle的方案数。
将\(2\times 2\)的网格用至多3种颜色染色，共有\(81\)种方案，其中有\(15\)种是Harmonious Rectangle. 故当网格规模大于等于\(9\times 9\)时，每一种网格图的染色方案都能找到至少一个Harmonious Rectangle.
对于小于\(9\times 9\)的情况，考虑爆搜搜出全部非法的方案数，一旦有一个合法即剪枝。
实测打表2s打完
上面的wa了。实际上若行数或列数大于等于9，它和另外一行/列就会覆盖所有的颜色搭配情况，此时答案输出\(3^{nm}\)即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
#define ll long long
const ll md = 1e9 + 7;
int n, m, k, tot, a[10][10];
int rd() {
int s = 0, f = 1; char c = getchar();
while (c < ‘0‘ || c > ‘9‘) {if (c == ‘-‘) f = -1; c = getchar();}
while (c >= ‘0‘ && c <= ‘9‘) {s = s * 10 + c - ‘0‘; c = getchar();}
return s * f;
}
ll ksm(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % md;
a = a * a % md;
b >>= 1;
}
return res;
}
ll ans;
void dfs(int cur) {
if (cur == n * m) {
ans++;
if (ans >= md) ans -= md;
return;
}
for (short col = 0, x, y, flag; col < 3; col++) {
x = cur / m, y = cur % m, flag = 1;
for (short i = 0; i < x && flag; i++) {
for (short j = 0; j < y && flag; j++) {
if (a[i][y] == col && a[i][j] == a[x][j]) {
flag = 0;
break;
}
if (a[x][j] == col && a[i][j] == a[i][y]) {
flag = 0;
break;
}
}
}
a[x][y] = col;
if (flag)
dfs(cur + 1);
a[x][y] = -1;
}
}
ll res[9][9] =
{{0,0,0,0,0,0,0,0},
{0,15,339,4761,52929,517761,4767849,43046721},
{0,339,16485,518265,14321907,387406809,460338013,429534507},
{0,4761,518265,43022385,486780060,429534507,792294829,175880701},
{0,52929,14321907,486780060,288599194,130653412,748778899,953271190},
{0,517761,387406809,429534507,130653412,246336683,579440654,412233812},
{0,4767849,460338013,792294829,748778899,579440654,236701429,666021604},
{0,43046721,429534507,175880701,953271190,412233812,666021604,767713261}};
int main() {
int T = rd();
while (T--) {
ans = 0;
n = rd(), m = rd();
if (min(n, m) == 1) {
puts("0");
continue;
}
if (n >= 9 || m >= 9) {
printf("%lld\n", ksm(3, n*m)%md);
} else {
printf("%lld\n", res[n-1][m-1]%md);
}
}
return 0;
}
GYM102992 [2020-2021 ACM-ICPC, Asia Nanjing Regional Contest (XXI Open Cup, Grand Prix of Nanjing)](https://codeforces.com/gym/102992)
原文：https://www.cnblogs.com/YjmStr/p/15236426.html
THE END
二维码