CF 刷题之路
人一我百，人十我万。 ——kuangbin
搜集模板
//惯用函数
// 类型别名
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
// 取消cin,cout同步(需要在main()里使用)
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Round #456 (Div. 2)
A（水）
无算法可言，直接将总共需要的黄色水晶与总拥有的黄色水晶数量比较，若小，则无需额外的水晶，若大，则费用是其差，蓝色同理。
黄蓝水晶相加即为总费用。
B（位运算）
此题考查二进制表示，显而易见，如果n由k位二进制表示，比如 9 = 1 0 0 1（2），则不难发现，0 1 1 0（2）这个数与它的异或和为1111，而且不可能存在其他数异或和更大(因为一共就这几位)，所以，最后输出的结果一定是 2^(k+1) - 1 即k个1(二进制)
所以这题 k 大于1 的情况就是取两个数，样例存在迷惑性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
long long n, k;
int main() {
cin >> n >> k;
if (k == 1) {//最多取一个数就输出最大的
cout << n << endl;
} else {//否则就按照“互补”的策略
long long ans = 1;
while (n) {
n >>= 1;
ans <<= 1;
}
cout << (long long) (ans - 1) << endl;
}
return 0;
}
D(模拟)
这个题本质上还是数学题+模拟题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iomanip>
#include <iostream>
#include <cstddef>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <fstream>
#include <tuple>
#include <queue>
#include <map>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
//<======================head======================>
int n, m, r, k;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
map<pair<int, int>, bool> vis;//仔细一想这样能节省内存，因为并不是所有点都会访问到，实际上访问的点不过1e5
struct node {
int x;
int y;
long long val;
node(int x, int y, long long int val) : x(x), y(y), val(val) {}
bool operator<(const node a) const {
return val < a.val;
}
};
long long cal(int x, int y) {
return (min(n, x + r - 1) - max(x, r) + 1) * (min(m, y + r - 1) - max(y, r) + 1);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
priority_queue<node> q;
cin >> n >> m >> r >> k;
//先将画面最中央的点放进去
q.push(node((n + 1) / 2, (m + 1) / 2, cal((n + 1) / 2, (m + 1) / 2)));
vis[make_pair((n + 1) / 2, (m + 1) / 2)] = true;
long long sum = 0;
//本质上是bfs，按照 可能出现在的方块的数量 加入优先队列(堆)，贪心计算
while (!q.empty()) {
node cur = q.top();
q.pop();
sum += cur.val;
k--;
if (k == 0) {
break;
}
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m)
continue;
//当时写到这里迷茫了一下，因为对于1e5的数据，二维数组开不下，但是通过map映射这种方式，使得仅需储存k个点，又能满足(1e5)级别的询问，非常巧妙，看cf的算法，应该set也可以做到
if (vis[make_pair(nx, ny)])
continue;
vis[make_pair(nx, ny)] = true;
q.push(node(nx, ny, cal(nx, ny)));
}
}
//最后的期望就是按照贪心策略放置完鱼之后 其最多占渔网数量之和/总渔网数
cout << setiosflags(ios::fixed) << setprecision(12) << (long long) (sum) * 1.0 / (n - r + 1) / (m - r + 1) << endl;
return 0;
}
Hello 2018
A(取模)
题意非常直白，求 m mod (2^n) ，此处需要注意的是，n和m的范围都是1e8，所以2^n理论上超出计算机储存能力，所以在 log(m)/log(2) < n 的时候（只能取对数才能比较），直接输出m即可。除此之外的情况下，2^n一定不大于 1e8，所以可以放心的用位运算来输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iomanip>
#include <iostream>
#include <cstddef>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <fstream>
#include <tuple>
#include <queue>
#include <map>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
//<======================head======================>
ll m, n;
int main() {
cin >> n >> m;
double tmp = log(m) * 1.0 / log(2);
if (int(ceil(tmp)) < n) {//此处细节，tmp是个浮点数，此处向上取整和n比较大小，否则易出误差
cout << m << endl;
} else {
ll a = 1;
a <<= (n);
cout << m % a << endl;
}
return 0;
}
B(树)
题意简单，验证树上每个非叶子节点是否拥有三个叶子孩子。对于每个节点都建立vector储存其孩子的下标，最后遍历所有节点，检验其是否拥有三个叶子孩子即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iomanip>
#include <iostream>
#include <cstddef>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <fstream>
#include <tuple>
#include <queue>
#include <map>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
//<======================head======================>
int n;
vector<int> tree[1005];
int main() {
cin >> n;
for (int i = 2; i <= n; i++) {
int tmp;
cin >> tmp;
tree[tmp].push_back(i);
}
bool flag = 0;
for (int i = 1; i <= n; i++) {
int cnt = 0;
int len = tree[i].size();
if (!len)
continue;
for (int j = 0; j < len; j++) {
if (!(tree[tree[i][j]].size()))
cnt++;
}
if(cnt<3){
flag=1;
break;
}
}
if(flag){
cout<<"No"<<endl;
} else{
cout<<"Yes"<<endl;
}
return 0;
}
C(位运算)
1
这题看起来像一个背包问题（其实数组开不下），其实是用二进制来解（否则他们的容量怎么会用2^n的形式呢）,所以思路就是将 l 分解成二进制，逐位计算，最后的和就是总费用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iomanip>
#include <iostream>
#include <cstddef>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <fstream>
#include <tuple>
#include <queue>
#include <map>
#include <utility>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
//<======================head======================>
int n;
ll c[35];
int l;
long long sum = 0;
int dp[35];
ll p[35];
int main() {
p[0] = 1;
cin >> n >> l;
for (int i = 1; i <= n; i++) {
cin >> c[i];
//预先处理一下费用，因为若是c[i] > 2 * c[i - 1]，那么用c[i]就不如用两次c[i-1]划算了
if (i > 1 && c[i] > 2 * c[i - 1]) {
c[i] = 2 * c[i - 1];
}
}
for (int i = 1; i <= n; i++) {
sum = min(sum,c[i]); //这一步很重要，因为若是容积大的还便宜，自然用其取代之前的组合
int base = l % 2;
sum += base * c[i];
l >>= 1;
}
//以上的过程只处理到第n位，所以剩下的位数就需要乘若干个c[n]再加入总费用
l *= 2;//l被多除了一次，在这里乘回来
sum += l * c[n];
cout << (ll) sum << endl;
return 0;
}
Round #504 (Div. 1 + Div. 2)
实力丢人,FST两题
A(字符串匹配)
A 题简直都要把我逼疯啦，听取WA声一片，其实就是很简单的搜索比较就好啦，非要用STL的函数，唉，还手滑写成子串了，下次不熟悉的还是不要乱用啦。
放大神代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<lint, int>;
const int MAXN = 100005;
const int mod = 1e9 + 7;
int n, m;
string s1, s2;
int main(){
cin >> n >> m;
cin >> s1 >> s2;
int idx = -1;
for(int i=0; i<n; i++){
if(s1[i] == '*') idx = i;
}
if(idx == -1){
//如果没有通配符就直接比较就好
puts(s1 == s2 ? "YES" : "NO");
return 0;
}
int rem = m - (n - 1);
if(rem < 0){
//如果上面-下面长度>1，则无论如何也不能匹配
puts("NO");
return 0;
}
//截取字符串,（其实就是把通配符替换成下面字符串对应位置的字母，然后直接比较
s1 = s1.substr(0, idx) + s2.substr(idx, rem) + s1.substr(idx + 1, n - idx - 1);
puts(s1 == s2 ? "YES" : "NO");
return 0;
}
B(水)
这个弱智题居然还FST了 o(TヘTo)
首先考虑到，如果不可能凑成k的情况，其实仔细一想就是最大的两个加起来也不到K, 即 k>2*n-1，这种情况是不可能凑成的，当然k==1也不能凑出来，特判一下是否是这两种情况。如果不是，就分K奇偶讨论
- 如果K为奇数, k/2+k/2+1 == k ,然后比较谁距离端点近
- 如果K为偶数，k/2 -1 + k/2+1 ==k,同理比较谁近即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iomanip>
#include <iostream>
#include <cstddef>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <fstream>
#include <queue>
#include <map>
#include <algorithm>
#include <cctype>
#include <string>
#include <cstdlib>
//#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
//const long double PI = acos(-1);
const ll mod = 998244353;
ll powmod(ll a, ll b) {
ll res = 1;
a %= mod;
for (; b; b >>= 1) {
if (b & 1)res = res * a % mod;
a = a * a % mod;
}
return res;
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline void myInit(void) { ios::sync_with_stdio(0); }
//<======================head======================>
ll n, k;
int main() {
cin >> n >> k;
//默认为奇数
long long l = k / 2;
long long r = k / 2 + 1;
if (k % 2 == 0) {
//偶数情况
l = k / 2 - 1;
r = k / 2 + 1;
}
if (r > n) {
//第一次这里写错了，其实这里等价于 k>2*n+1，
cout << 0 << endl;
} else {
//左右分别距离端点的距离
cout << min(l, n - r + 1) << endl;
}
return 0;
}
Round #363(Div 2)
C(dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 心血来潮做一个dp压压惊，div2后三题就是Div1前三题
#include <iostream>
#include <cstring>
#include <iomanip>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
//<======================head======================>
using namespace std;
// dp[i][j]表示第i天做j(0为不训练，1为contest,2为gym)的话，其工作时间的长度
long long dp[150][5];
int main() {
int n;
cin >> n;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
int tmp;
// 此处有些误入歧途,其实不需要管各种情况，直接使用默认的0就好
// 对状态转移还是理解不深刻，转化不能随意转，只能通过现有条件进行转移，比如第i天只能参加gym或不参加，那它就不可能从dp[i-1][2]转化而来，并且也不会发生dp[i][1]由谁转化而来这个问题，因为这个前提不成立(第i天不能参加contest)
cin >> tmp;
// 能够参加Gym,其状态只能由“未参加”“参加contest”转化
if (tmp == 2 || tmp == 3) {
dp[i][2] = max(dp[i - 1][1], dp[i - 1][0]) + 1;
}
// 能够参加contest，其状态只能由"未参加""参加gym"转化
if (tmp == 1 || tmp == 3) {
dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + 1;
}
// 未参加可以从"未参加""参加gym""参加contest"转化
// 此处小细节，max()填三个数的话，CLion不会警告，但是编译会出错
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]));
}
long long ans = 0;
for (int i = 0; i <= 2; i++) {
ans = max(ans, dp[n][i]);
}
cout << n - (long long) ans << endl;
return 0;
}
