今天唯一的成果就是把上次几个人一起开房打的那场cf补一下。
A. Combination Lock
此等水题看一眼样例加上那个配图我就明白题意了，可是手抽没有注释掉freopen，WA了一发。
#include <bits/stdc++.h>
using namespace std; const int maxn = + ; char s1[maxn], s2[maxn]; int main()
{
int n; cin >> n;
scanf("%s", s1);
scanf("%s", s2);
int ans = ;
for(int i = ; i < n; i++)
{
int a = s1[i] - '';
int b = s2[i] - '';
if(a < b) swap(a, b);
ans += min(a - b, - a + b);
}
cout << ans << "\n"; return ;
}
代码君
B. School Marks
这道题本身不难，因为所给的n是奇数。但有可能会想错细节或漏掉情况。
n个数排好序，中间那个数一定是中位数，而且左右两边各n / 2个数。
所以我们看已知的k个数中比y小的数有多少个，如果大于n/2个，那么中位数一定小于y，无解。
如果k个数中不小于y的大于n / 2个，那么根据贪心，中位数已经在这些数里面了，所以剩下的n-k个数补成1就好了。
其次可以把中位数y插到这里面去，而且能算出中位数左边要补多少个1，右边要补多少个y。
注意在上面所有的情况中还要判断总数是否不超过x。
#include <bits/stdc++.h>
using namespace std; const int maxn = + ;
int a[maxn]; int main()
{
//freopen("in.txt", "r", stdin); int n, k, p, x, y;
cin >> n >> k >> p >> x >> y;
for(int i = ; i < k; i++) scanf("%d", &a[i]);
sort(a, a + k);
int t = lower_bound(a, a + k, y) - a;
if(t > n / ) { puts("-1"); return ; } int s = ;
for(int i = ; i < k; i++) s += a[i];
if(k - t > n / )
{
int p = n - k;
if(s + p > x) { puts("-1"); return ; }
printf("");
for(int i = ; i < p; i++) printf("");
puts(""); return ;
} int l = n / - t;
int r = n / - k + t;
if(s + l + (r + ) * y > x) { puts("-1"); return ; }
bool print = false;
for(int i = ; i < l; i++) { if(print) printf(" "); print = true; printf(""); }
for(int i = ; i <= r; i++) { if(print) printf(" "); print = true; printf("%d", y); } return ;
}
代码君
C. Ice Cave (BFS)
总体来说这场CF难度偏易，虽然比赛的时候逗比地爆一了。但是下来的时候，手写一遍，没有编译错误交上去还过了，比赛要是这状态，啧啧
这道题一开始没有理解题意，其实就是地图上的'.'走过一遍就变成'X'，而且'X'就不能再走了，终点除外。
问从能否起点走到终点，而且把终点变成'X'
把题意理解了，直接BFS就好啦，而且vis标记都不用，直接修改地图就好了。
#include <bits/stdc++.h>
using namespace std; const int maxn = + ; char s[maxn][maxn];
int n, m; struct Node
{
int x, y;
Node(int x = , int y = ):x(x), y(y) {}
}st, ed; int dx[] = { , , -, };
int dy[] = { , , , - }; inline bool in(int x, int y) { return x > && x <= n && y > && y <= m; } bool BFS()
{
queue<Node> Q;
Q.push(st);
while(!Q.empty())
{
Node now = Q.front(); Q.pop();
for(int i = ; i < ; i++)
{
int x = now.x + dx[i];
int y = now.y + dy[i];
if(!in(x, y)) continue;
if(s[x][y] == 'X') { if(x == ed.x && y == ed.y) return true; continue; }
s[x][y] = 'X';
Q.push(Node(x, y));
}
}
return false;
} int main()
{
//freopen("in.txt", "r", stdin); cin >> n >> m;
for(int i = ; i <= n; i++) scanf("%s", s[i] + );
scanf("%d%d%d%d", &st.x, &st.y, &ed.x, &ed.y);
printf("%s\n", BFS() ? "YES" : "NO"); return ;
}
代码君
D. Bad Luck Island (概率 DP)
题解写得很清楚，递推或者DFS都行。
#include <cstdio>
#include <iostream>
using namespace std; const int maxn = + ;
double d[maxn][maxn][maxn]; int main()
{
int a, b, c;
cin >> a >> b >> c;
d[a][b][c] = 1.0;
for(int i = a; i >= ; i--)
for(int j = b; j >= ; j--)
for(int k = c; k >= ; k--)
{
if(!i && !j) continue;
if(!i && !k) continue;
if(!j && !k) continue;
double cur = d[i][j][k];
double tot = i*j + i*k + j*k;
if(i) d[i-][j][k] += cur * (double)(i*k) / tot;
if(j) d[i][j-][k] += cur * (double)(i*j) / tot;
if(k) d[i][j][k-] += cur * (double)(j*k) / tot;
} double aa = , bb = , cc = ;
for(int i = ; i <= a; i++) aa += d[i][][];
for(int i = ; i <= b; i++) bb += d[][i][];
for(int i = ; i <= c; i++) cc += d[][][i]; printf("%.12f %.12f %.12f\n", aa, bb, cc); return ;
}
代码君
E. Infinite Inversions (树状数组 离散化)
可以把所求分成两个部分来计：
把这2n个数进行一次离散化，比如排序去重以后变成m个数。
那么经过m次操作，这m个数相较于初始状态是一个这m个数的排列。所以可以用树状数组计算一个这m个数之间的逆序数，注意这里不涉及位置没有变化的那些数。
这样我们便完成了第一部分的计数。
剩下的一部分是这m个数与其他位置未发生变化的逆序数。
预处理一下m个数中第i个数与第1个数之间有多少个数未发生位置改动sum[i]。
比如这m个数经过n次两两交换以后，第i个数的大小为rank[i]，那么未发生位置改动的数与第i个数构成的逆序对有abs(sum[i] - sum[rank[i]])
举个栗子：
比如2 7互换，序列由
1 2 3 4 5 6 7 8 变成 1 7 3 4 5 6 2 8
2和7之间有4个数没有变(即3 4 5 6)，对于2 7而言，7到2前面去了这是一个逆序对，也就是我们计数的第一部分。
对于2来说，2在7的位置，而且3 4 5 6都与2构成一个逆序对，因此贡献了4个逆序对；
对于7同样，7在2的位置，3 4 5 6在7的后面也贡献了4个逆序对。
所以最终答案为9
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std; typedef long long LL;
const int maxn = + ; int a[maxn], b[maxn], x[maxn], r[maxn];
LL sum[maxn], s[maxn];
int n, m; inline int lowbit(int x) { return x&(-x); } void add(int x, LL d)
{ while(x <= m) { s[x] += d; x += lowbit(x); } } LL query(int x)
{
LL ans = ;
while(x) { ans += s[x]; x -= lowbit(x); }
return ans;
} int main()
{
//freopen("in.txt", "r", stdin); cin >> n;
for(int i = ; i <= n; i++)
{
scanf("%d%d", &a[i], &b[i]);
x[i*-] = a[i]; x[i*] = b[i];
}
sort(x + , x + + n*);
m = unique(x + , x + + n*) - x - ;
for(int i = ; i <= m; i++)
{
sum[i] = sum[i - ] + x[i] - x[i - ] - ;
r[i] = i;
}
for(int i = ; i <= n; i++)
{
int ta = lower_bound(x + , x + + m, a[i]) - x;
int tb = lower_bound(x + , x + + m, b[i]) - x;
swap(r[ta], r[tb]);
} LL inv = ;
for(int i = m; i > ; i--)
{
inv += query(r[i]);
add(r[i], );
inv += abs(sum[i] - sum[r[i]]);
} cout << inv << endl; return ;
}
代码君