Codeforces Round
940 (Div. 2) and CodeCraft-23
A
贪心计算直接/3，然后就
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 <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+100;
int a[N];
void solve()
{
int n;
cin>>n;
map<int,int>mp;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mp[a[i]]++;
}
int ans=0;
for(auto &[x,y]:mp)
{
if(y>=3)
{
ans+=y/3;
}
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
|
B
本题由于可以是非负整数，可以凑出0，然后就可以直接凑出最大的数字，比如32，直接凑一个31出来，其他弄一个m-31,再弄全部都是0的就可以了
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
|
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
int lowbit(int i)
{
return i&(-i);
}
void solve()
{
int n,k;
cin>>n>>k;
if(n==1)
{
cout<<k<<'\n';
}
else
{
int sum=1;
while(sum*2+1<=k)
{
sum=sum*2+1;
}
cout<<sum<<" "<<k-sum<<' ';
for(int i=1;i<=n-2;i++)
{
cout<<0<<' ';
}
cout<<'\n';
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
|
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
|
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
const int N=5e5+100;
const int mod=1e9+7;
ll dp[N];
int n,m;
void solve()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
if(x==y)
{
n-=1;
}
else
{
n-=2;
}
}
cout<<dp[n]<<'\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
dp[0]=1;
dp[1]=1;
dp[2]=3;
for(int i=3;i<=N;i++)
{
dp[i]=dp[i-1]+(i-1)*2*dp[i-2];
dp[i]%=mod;
}
while (t--)
{
solve();
}
}
|
D
由于等式两边只会加一个数字，只需要枚举那个数字的最高位，如果是1，两端到这一位的数字有1的个数之和是奇数的话就满足。
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
|
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N=5e5+100;
const int mod=1e9+7;
int n;
LL a[N];
void solve()
{
cin >> n;
LL dp1[n + 5][32][2];
LL dp2[n + 5][32][2];
for(int i = 1 ; i <= n ; i ++)
{
cin >> a[i];
}
memset(dp1 , 0 , sizeof dp1);
memset(dp2 , 0 , sizeof dp2);
for(int i = 1 ; i <= n ; i ++){
for(int j = 0 ; j < 32 ; j ++)
{
if((a[i] >> j) & 1)
{
dp1[i][j][1] = dp1[i - 1][j][0] + 1;
dp1[i][j][0] = dp1[i - 1][j][1];
}
else
{
dp1[i][j][1] = dp1[i - 1][j][1];
dp1[i][j][0] = dp1[i - 1][j][0] + 1;
}
}
}
for(int i = n ; i >= 1 ; i --){
for(int j = 0 ; j < 32 ; j ++){
if((a[i] >> j) & 1){
dp2[i][j][1] = dp2[i + 1][j][0] + 1;
dp2[i][j][0] = dp2[i + 1][j][1];
}
else{
dp2[i][j][1] = dp2[i + 1][j][1];
dp2[i][j][0] = dp2[i + 1][j][0] + 1;
}
}
}
LL ans = 0;
for(int i = 1 ; i <= n ; i ++){
for(int j = 32 ; j >= 0 ; j --){
if((a[i] >> j) & 1){
ans += dp1[i - 1][j][0] * dp2[i + 1][j][1];
ans += dp1[i - 1][j][1] * dp2[i + 1][j][0];
ans += dp1[i - 1][j][1];
ans += dp2[i + 1][j][1];
break;
}
}
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
}
|
