水题笔记_ CF458 A ~ D [模拟, 数论, 贪心, 线段树, DP, 翻车]

太晚了…并没有参加比赛…这几天做了一下…
从雪下做到雪融(菜爆了)…

懵逼的 题目

传送至 CrossFire

扯淡的 题解

A

Emmmmmm…水…

B

并没有看过几集Conan…
考虑只有一些相等的数:

  • 偶数先手输
  • 奇数先手赢

(因为只会去掉严格小于选择的数的数, 所以和这个数相等的数并不会去掉, 所以一次只能取走一个)

然后考虑最大的数:

  • 如果最大数有奇数个, 一定先手赢
  • 如果最大的数有偶数个, 一定先手输

(第一次就把不是最大的数全部去掉了, 只剩下奇数或偶数个相等的数, 而一次仍然只能去掉一个数)

所以考虑Conan的最优策略: 如果最大数是偶数个, Conan一定不会去取最大数(因为先手就输了), 所以Conan就会去看倒数第二大的数, 而Agasa也不会去取最大数(不傻), 如果倒数第二大的数的个数是偶数, 那么取完倒数第二大的数还是Conan先手, GG, 如果是奇数, 取完倒数第二大的数后先后手翻转, Conan就赢了…所以就有了算法:

  1. 排序, 让相等的数在一起
  2. 从大到小扫描, 如果找到一些相等的数个数是奇数, 返回Canon赢, 如果一直到了最后还是相等的数都是偶数, 返回Agasa赢

水…30min- 1A

C

思路很显然, 因为logn的范围比较小, 我们就可以求出 [1 ~ log(n)]中所有数变成1的次数, 找所有次数为k - 1的数(cans[]), 这些数就是一个Ans的二进制位中1的个数(不要忘了变成cans[]还需要一步), 然后用数位DP的思想(舒老师原话%%%)枚举给定n的每一位, 如果这一位是1, 设答案的这一位为0(保证了比n要小), 然后加上剩余1的个数在剩下的位数中组合的方案数, 然后把剩余1的个数–(表示这一位也放上1, 保证置零前的二进制位和n的一样), 最后加上和n相等的方案数

有很多细节要注意…好多Dalao都被Hack点艹翻了…比如考虑相等的情况, 和k == 0的情况和n == 0的情况…
还有…

1
2
10000000000000000000000000000
1

这种恶心的Hack点…答案要减一…因为1在最后一位的时候其实是不合法的…

D

反而相对来说简单一点…显然如果一个区间要满足[可以改动一个数就以x为GCD]必须让[最多一个数不能整除GCD]我们发现[区间是否可以整除一个数]是可以区间合并的(取两个子区间的GCD的GCD即可), 所以我们就可以用线段树了…

查找的话就是如果这个区间的GCD能整除x, 就返回, 否则看哪个子区间不能整除x, 查询这个子区间, 直到找到不能整取的单个数, ok++, 如果ok > 1就输出"NO"

总之…

AB倒都是秒了…CD一个从七点调到十二点, 从机房调到了家里, 一个也是调了两节课发现某些实现有问题
题目并不难, 但是代码能力还是菜的一批, 主要大概是一直闷头调试的问题, 之后一时调到焦头烂额就应该出去洗把脸, 理一理思路(C就是回家的路上想到哪里出了问题的), 还有…不能再一不小心看见标签了…Emmmmm
又: 是不是该准备期末考试了…

沙茶的 代码

A

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN (1000 + 5)
using namespace std;
int n, a[MAXN];
bool cmp(int, int);
void solve();
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
solve();
return 0;
}
bool cmp(int x, int y)
{
return x > y;
}
void solve()
{
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
int x = (int)sqrt(a[i]);
if (x * x != a[i])
{
printf("%d\n", a[i]);
return ;
}
}
}

B

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int n;
int a[MAXN];
bool Conanwin;
void solve();
bool cmp(int, int);
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
solve();
if (Conanwin)
puts("Conan");
else
puts("Agasa");
return 0;
}
void solve()
{
sort(a + 1, a + n + 1, cmp);
int last = a[1], cnt = 0;
for (int i = 1; i <= n;)
{
while (a[i] == last)
{
++i;
++cnt;
}
last = a[i];
if (cnt & 1)
{
Conanwin = true;
return ;
}
}
Conanwin = false;
return ;
}
bool cmp(int x, int y)
{
return x > y;
}

C

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#define MAXB (1010 + 5)
#define MAXK (1010 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define REFUN (1000000000 + 7)
#define LL long long
using namespace std;
int n, k, suma;
bool a[MAXB];
LL c[MAXB][MAXK], f[MAXB], ans; // f[i]: i需要多少步归一
void initf();
void initc();
void solve();
inline int bit1(int);
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
string srs;
cin >> srs >> k;
if (!k)
{
puts("1");
return 0;
}
if (srs == "1")
{
puts("0");
return 0;
}
n = srs.length();
for (int i = 0; i < n; i++)
{
a[n - i] = (srs[i] == '1');
if (a[n - i])
++suma;
}
initc();
initf();
solve();
/*if (ans == 157)
{
cout << 158;
return 0;
}*/
cout << ans % REFUN;
return 0;
}
inline int bit1(int x)
{
int re = 0;
while (x)
{
re = ((x & 1) ? (re + 1) : (re));
x >>= 1;
}
return re;
}
void initc()
{
memset(c, 0, sizeof(c));
c[0][0] = 1;
c[0][1] = c[1][1] = 1;
for (int i = 2; i < MAXB; i++)
{
for (int j = 0; j <= i; j++)
{
if (!j)
c[j][i] = c[j][i - 1];
else
c[j][i] = (c[j - 1][i - 1] + c[j][i - 1]) % REFUN;
// cout << j << " " << i << " " << c[14][0] << endl;
}
}
}
/*
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
*/
void initf()
{
memset(f, 0x7f, sizeof(f));
f[1] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (bit1(j) == i)
f[j] = min(f[j], (f[i] + 1) % REFUN);
}
}
}
void solve()
{
vector<int> cans;
for (int i = 1; i <= n; i++)
{
if (f[i] == k - 1)
{
/*if (i == suma)
++ans;*/
cans.push_back(i);
}
}
int cnn = cans.size();
/*
for (int i = 0; i < cnn; i++)
{
ans += c[cans[i]][n - 1];
ans %= REFUN;
}
*/
int cnt1 = 0; //代表之前有几个1是相同的(即已经放过几个1了)
for (int i = n; i >= 1; i--)
{
while (!a[i] && i > 1)
{
--i;
}
if (!a[i])
break;
for (int j = 0; j < cnn; j++)
{
if (cans[j] < cnt1)
continue;
ans += c[cans[j] - cnt1][i - 1];
if (cans[j] == 1 && i == n)
--ans;
ans %= REFUN;
}
++cnt1;
}
for (int i = 0; i < cnn; i++)
{
if (cans[i] == suma)
{
++ans;
}
}
}

/*
111111011
2

确定了在n位中有x位是1
看看怎么做到比这个小
首先C(x, n - 1)肯定可以
然后从高位逐位相等看看比这个小的有多少
*/

D

XP学长: 我这道题想到思路以后就去打炉石了%%%

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (500000 + 5)
#define INF (0x7ffffff)
#define LL long long
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
using namespace std;
struct node
{
int le, ri, zh;
}b[MAXN << 3];

int n, a[MAXN];
int ok;
void js(int, int, int);
void xg(int, int, int);
void cx(int, int, int, int);
int gcd(int, int);
inline void pushup(int);
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
js(1, 1, n);
int q, srx, sry, srz, sre;
scanf("%d", &q);
for (int i = 1; i <= q; i++)
{
scanf("%d%d%d", &sre, &srx, &sry);
if (sre & 1)
{
scanf("%d", &srz);
ok = 0;
cx(1, srx, sry, srz);
if (ok <= 1)
puts("YES");
else
puts("NO");
}
else
xg(1, srx, sry);
}
return 0;
}
int gcd(int a, int b)
{ return ((b == 0) ? (a) : (gcd(b, a % b))); }
inline void pushup(int dq)
{ b[dq].zh = gcd(b[LS(dq)].zh, b[RS(dq)].zh); }
void js(int dq, int le, int ri)
{
b[dq].le = le, b[dq].ri = ri;
if (le == ri)
{
b[dq].zh = a[le];
return ;
}
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
pushup(dq);
}
void xg(int dq, int wz, int zh)
{
if (b[dq].le == b[dq].ri && b[dq].le == wz)
{
b[dq].zh = zh;
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz <= mi)
xg(LS(dq), wz, zh);
else
xg(RS(dq), wz, zh);
pushup(dq);
}
void cx(int dq, int le, int ri, int zh)
{
if (!(b[dq].zh % zh))
return ;
if (b[dq].le == b[dq].ri && le == ri)
{
if (b[dq].zh % zh)
++ok;
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (ri <= mi)
cx(LS(dq), le, ri, zh);
else if (le > mi)
cx(RS(dq), le, ri, zh);
else
{
if (b[LS(dq)].zh % zh)
cx(LS(dq), le, mi, zh);
if (ok > 1)
return ;
if (b[RS(dq)].zh % zh)
cx(RS(dq), mi + 1, ri, zh);
}
}

By 期末药丸的 Cansult

话说我怎么攻变受了啊