ZROI 2022NOIP10联测 Round 5 解题报告
100 + 0 + 10 + 30, rk 70。
我不想玩啦!还是找个班上吧。
A
Subtask 1,2,3
直接按照题目里面给的做法,那么每一次都尝试把可以合并的元素合并,迭代若干次后如果没有修改,则说明无解。如果任意时刻只剩下一个元素,那么显然是合法的,直接用 long long
实现,可以得到 80 pts 的高分!
const int N = 1e5 + 10;
ll n;
vector <ll> a,b;
ll gcd(ll x,ll y) {return !y ? x : gcd(y,x % y);}
ll lcm(ll x,ll y) {return x / gcd(x,y) * y;}
signed main() {
read(n);
for (int i = 0,x;i < n;++i) read(x),a.emplace_back(x);
bool flag = 0,cor = 0;
while (1) {
ll nowlcm = a[0];
int le = a.size();
b.clear();
if (le == 1) {
cor = 1;
break;
}
bool tmp = 0;
for (int i = 1;i < le;++i) {
if (gcd(a[i],a[i-1]) != 1) {
nowlcm = lcm(nowlcm,a[i]);
tmp = 1;
} else {
b.emplace_back(nowlcm);
nowlcm = a[i];
}
}
b.emplace_back(nowlcm);
if (!tmp) break;
a = b;
}
if (cor) puts("Yes");
else puts("No");
return 0;
}
Subtask 4
我们考虑,上边的做法会在
我们发现,我们其实并不需要直接求出 bitset
来表示 (x & y).any()
,求 x |= y
即可。
然后发现上边过程时间的正确性,其实是基于我们一共只需要扫描两次:第一次合并所有段,第二次考察是否有
所以我们可以直接用栈维护以上过程,时间复杂度
bool isprime(int x) {
for (int i = 2;i * i <= x;++i) {
if (x % i == 0) return 0;
}
return 1;
}
signed main() {
//FO(ex_cai4)
//freopen("ex_cai4.in","r",stdin);
read(n);
for (int i = 1,x;i <= n;++i) read(A[i]),maxx = max(maxx,A[i]);
for (int i = 2;i <= maxx;++i) {
int now = i;
for (int j = 2;j * j <= i;++j) {
if (!isprime(j)) continue;
int cnt = 0;
while (now % j == 0) {
now /= j;
++cnt;
}
if (cnt) fac[i].set(j);
}
if (now != 1) fac[i].set(now);
}
for (int i = 1;i <= n;++i) {
st[++top] = fac[A[i]];
while (top > 1 && (st[top-1] & st[top]).any()) --top,st[top] |= st[top+1];
}
if (top == 1) puts("Yes");
else puts("No");
return 0;
}
B
场上弱智了完全没有想到分开来讨论……好好把一个弱智DP题做成逆天图论数数题。
首先最强的观察在于,我们考虑这个约束实际上具有一个非常强的暗示,我们可以把 U/D
和 L/R
分开来讨论,也就是说,我们对于每一行每一列分别考虑。
接下来叙述对于行的 DP 过程,对于列的 DP 过程也是同理。
我们首先发现这个问题有点类似一个括号匹配的过程,即 R
视为左括号,L
视为右括号,那么我们可以套路地定义出状态
接下来我们开始分类讨论:
-
如果当前为
L
,那么括号数 -1,如果选择就是:f_{i,j-1} \leftarrow f_{i-1,j} \times j\\ g_{i,j-1} \leftarrow g_{i-1,j}\times j + f_{i-1,j}\times j\times a_i 意义:对于方案数,考虑当前位置的可以和前
j 个左括号选择一个匹配;对于权值和,同样考虑有j 个括号可供转移,并且加上当前的权值和(即f_{i-1,j} \times j\times a_i ) - 如果当前为
R
,那么括号数 +1,如果选择就是:f_{i,j-1} \leftarrow f_{i-1,j}\\ g_{i,j-1}\leftarrow g_{i-1,j} + f_{i-1,j}\times a_i 类比上方,此处意义显然。
注意这两处都是只考虑了选择的,如果不选择,那么有
这个是显然的,转移的时候注意一下,总时间复杂度
const int N = 510;
char s[N][N];
int n,a[N][N],m,cnt[N * N],ans,f[N][N],g[N][N];
signed main() {
scanf("%lld\n",&n);
for (int i = 1;i <= n;++i) scanf("%s",s[i] + 1);
for (int i = 1;i <= n;++i)
for (int j = 1;j <= n;++j)
scanf("%lld",&a[i][j]);
ll tmp = 1,ans = 0;
for (int x = 1;x <= n;++x) {
memset(f,0,sizeof f);
memset(g,0,sizeof g);
f[0][0] = 1;
for (int i = 1;i <= n;++i) {
for (int j = 0;j <= i;++j) {
f[i][j] = f[i-1][j];
g[i][j] = g[i-1][j];
if (s[x][i] == 'U' || s[x][i] == 'D') continue;
if (s[x][i] == 'L') {
f[i][j] = (f[i][j] + f[i-1][j+1] * (j + 1)) % mod;
g[i][j] = (g[i][j] + g[i-1][j+1] * (j+1) % mod + f[i-1][j+1] * (j+1) % mod * a[x][i] % mod) % mod;
} else if (s[x][i] == 'R' && j > 0) {
f[i][j] = (f[i][j] + f[i-1][j-1]) % mod;
g[i][j] = (g[i][j] + g[i-1][j-1] + f[i-1][j-1] * a[x][i] % mod) % mod;
}
}
}
ans = (ans * f[n][0] % mod + tmp * g[n][0] % mod) % mod;
tmp = (tmp * f[n][0]) % mod;
}
for (int x = 1;x <= n;++x) {
memset(f,0,sizeof f);
memset(g,0,sizeof g);
f[0][0] = 1;
for (int i = 1;i <= n;++i) {
for (int j = 0;j <= i;++j) {
f[i][j] = f[i-1][j];
g[i][j] = g[i-1][j];
if (s[i][x] == 'L' || s[i][x] == 'R') continue;
if (s[i][x] == 'U') {
f[i][j] = (f[i][j] + f[i-1][j+1] * (j + 1)) % mod;
g[i][j] = (g[i][j] + g[i-1][j+1] * (j+1) % mod + f[i-1][j+1] * (j+1) % mod * a[i][x] % mod) % mod;
} else if (s[i][x] == 'D' && j > 0) {
f[i][j] = (f[i][j] + f[i-1][j-1]) % mod;
g[i][j] = (g[i][j] + g[i-1][j-1] + f[i-1][j-1] * a[i][x] % mod) % mod;
} else {
continue;
}
}
}
ans = (ans * f[n][0] % mod + tmp * g[n][0] % mod) % mod;
tmp = (tmp * f[n][0]) % mod;
}
printf("%lld\n",ans);
return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。