Codeforces Round #581(Div. 2)
CF 1204 A. BowWow and the Timetable
题解:发现,$4$的幂次的二进制就是一个$1$后面跟偶数个$0$。
所以暴力判一下就好。
Code:
#include <bits/stdc++.h> #define N 110 using namespace std; char s[N]; int main() {
scanf("%s", s + 1);
int n = strlen(s + 1);
int now = n / 2;
int flag = 0;
for (int i = 2; i <= n; i ++ ) {
if (s[i] == '1') {
flag = 1;
}
}
now += flag;
cout << now << endl ;
return 0;
}
CF 1204 B. Mislove Has Lost an Array
题解:发现题目的要求就是出现的数是前$k$个$2$的幂次,每个都得出现至少一次。
最小值的话,就是满足了$k$等于$l$的情况下,剩下的都等于$1$即为最小值。
最大值的话,就是满足了$k$等于$r$的情况下,剩下的都等于$2^r$即为最大值。
Code:
#include <bits/stdc++.h> using namespace std; int bin[21]; int main() {
int n, l, r;
cin >> n >> l >> r;
bin[0] = 1;
for (int i = 1; i <= r; i ++ ) {
bin[i] = bin[i - 1] << 1;
}
int mn, mx;
mn = bin[l] + n - l - 1;
mx = (n - r + 2) * bin[r - 1] - 1;
cout << mn << ' ' << mx << endl ;
return 0;
}
CF 1204 C. Anna, Svyatoslav and Maps
题解:我就是个得看样例才能读懂题意的傻屌中国人......
就是要看一下,能不能拿出来一些点使得,这些点之间的最短路和原图的最短路长度一样。
直接暴力一个一个判就行。
最短路的话求个$floyd$就好。
Code:
#include <bits/stdc++.h> #define N 110 using namespace std; char s[N][N]; int dis[N][N]; int p[1000010 ]; int ans[1000010 ]; int main() {
int n;
cin >> n ;
for (int i = 1; i <= n; i ++ ) {
scanf("%s", s[i] + 1);
}
memset(dis, 0x3f, sizeof dis);
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
if (s[i][j] == '1') {
dis[i][j] = 1;
}
}
dis[i][i] = 0;
}
for (int k = 1; k <= n; k ++ ) {
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
} int m;
cin >> m;
for (int i = 1; i <= m; i ++ ) {
scanf("%d", &p[i]);
}
ans[ ++ ans[0]] = p[1];
int pre = p[1];
for (int i = 2; i <= m; i ++ ) {
if (pre == p[i - 1]) {
continue;
}
if (dis[pre][p[i - 1]] + 1 != dis[pre][p[i]]) {
pre = p[i - 1];
ans[ ++ ans[0]] = pre;
}
}
ans[ ++ ans[0]] = p[m];
cout << ans[0] << endl ;
for (int i = 1; i <= ans[0]; i ++ ) {
printf("%d ", ans[i]);
}
puts("");
return 0;
}
CF 1204 D2. Kirk and a Binary String (hard version)
题解:妈呀神仙题......
就是我们发现什么样的串串是不能动的:
“10”显然。
如果$s$不能动,那么$1s0$不能动。
那么我们把所有的,不能动的串都删掉即可,剩下的就都变成1就好了。
Code:
#include <bits/stdc++.h> #define N 100010 using namespace std; char s[N]; int main() {
scanf("%s", s + 1);
int n = strlen(s + 1);
int tmp = 0;
for (int i = n; i; i -- ) {
if (s[i] == '0') {
tmp ++ ;
}
else if (tmp) {
tmp -- ;
}
else {
s[i] = '0';
}
}
for (int i = 1; i <= n; i ++ ) {
putchar(s[i]);
}
return 0;
}
CF 1204 E. Natasha, Sasha and the Prefix Sums
好题呀
先设$g[x][y]$表示,$x$个数有$y$个是$-1$,构成的所有序列中,$f$值等于$0$的序列个数。
显然当$x>y$时,$g[x][y]=0$。否则就是$C(x + y, y) - C(x + y, y + 1)$。
再设$f[x][y]$表示答案。
转移用$g[x][y]$和组合数就好。
Code:
#include <bits/stdc++.h> #define N 4010 using namespace std; const int mod = 998244853 ; typedef long long ll; int qpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1) {
ans = (ll)ans * x % mod;
}
y >>= 1;
x = (ll)x * x % mod;
}
return ans;
} int f[N][N], g[N][N]; int fac[N], inv[N]; inline int C(int x, int y) {
if (x < y) {
return 0;
}
return (ll)fac[x] * inv[y] % mod * inv[x - y] % mod;
} int main() {
int n, m;
cin >> n >> m ;
fac[0] = 1;
for (int i = 1; i <= n + m; i ++ ) {
fac[i] = (ll)fac[i - 1] * i % mod;
}
inv[n + m] = qpow(fac[n + m], mod - 2);
for (int i = n + m - 1; ~i; i -- ) {
inv[i] = (ll)inv[i + 1] * (i + 1) % mod;
} g[0][0] = 1;
for (int i = 0; i <= n; i ++ ) {
for (int j = i; j <= m; j ++ ) {
if (i) {
g[i][j] = g[i - 1][j];
}
if (j) {
g[i][j] = (g[i][j] + g[i][j - 1]) % mod;
}
}
} for (int i = 1; i <= n; i ++ ) {
for (int j = 0; j <= m; j ++ ) {
f[i][j] = (f[i - 1][j] + C(i + j - 1, j)) % mod;
if (j) {
f[i][j] = (((f[i][j] + f[i][j - 1]) % mod + g[i][j - 1] - C(i + j - 1, j - 1)) % mod + mod) % mod;
}
}
}
cout << f[n][m] << endl ;
return 0;
}