这场感觉很对电波，前三题切的很快，d卡了很久，e是完全不懂数学的
蓝名留念
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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
int read()
{
int a=0;int f=0;char p=getchar();
while(!isdigit(p)){f|=p=='-';p=getchar();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
return f?-a:a;
}
const int N=1e6+5;
int n;
int a[N];
void huangyu(){
n=read();
int ans=0;
for(int i=1;i<=n;++i) a[i]=read();
sort(a+1,a+n+1);
int p=(n+1)/2;
for(int i=p;i<=n;++i)
if(a[i]==a[p]) ans++;
cout<<ans<<endl;
}
int main(){
int tt;
cin>>tt;
while(tt--){
huangyu();
}
return 0;
}
|
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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
int read()
{
int a=0;int f=0;char p=getchar();
while(!isdigit(p)){f|=p=='-';p=getchar();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
return f?-a:a;
}
const int N=1e6+5;
const int P=1e9+7;
int n,m;
int ans;
int a[N];
ll sum[N];
void huangyu(){
n=read(); m=read();
ll mx=0; ll mn=0; ans=0;
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
for(int i=1;i<=n;++i)
{
ans=(ans+(a[i]+P)%P)%P;
mx=max(mx,sum[i]-mn);
mn=min(mn,sum[i]);
}
mx=mx%P;
for(int i=1;i<=m;++i)
{
ans=(ans+mx)%P;
mx=(mx+mx)%P;
}
cout<<ans<<endl;
}
int main(){
int tt;
cin>>tt;
while(tt--){
huangyu();
}
return 0;
}
|
C
二分check一下
树形dp求子树大小，到大小直接分一块，然后dp置为0
为什么这样贪心的想法是正确的呢？
因为作为一棵树，删掉子树的节点不会影响当前节点的连通性，也就是说删子树可以保证节点的有效连通数不会减少，所以在已知连通的情况下删子树最优
二分check一下就好
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<bits/stdc++.h>
using namespace std;
using ll=long long;
int read()
{
int a=0;int f=0;char p=getchar();
while(!isdigit(p)){f|=p=='-';p=getchar();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
return f?-a:a;
}
const int N=1e6+5;
const int P=1e9+7;
int n,m;
int ans;
int a[N];
int root;
vector<int >G[N];
int dp[N],sum,now;
void dfs(int u,int fa)
{
dp[u]=1;
for(auto v:G[u])
{
if(v==fa) continue;
dfs(v,u); dp[u]+=dp[v];
}
if(dp[u]>=now)
{
sum++;
dp[u]=0;
}
}
void huangyu(){
n=read(); m=read();
for(int i=1;i<=n;++i) G[i].clear();
for(int i=1;i<n;++i)
{
int x=read();
int y=read();
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1;i<=n;++i)
if(G[i].size()==1) root=i;
int l=1; int r=n;
while(l<r)
{
int mid=(l+r+1)>>1;
now=mid; sum=0;
dfs(root,0);
if(sum>=m+1) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
int main(){
int tt;
cin>>tt;
while(tt--){
huangyu();
}
return 0;
}
|
D
我的做法是考虑枚举x的每一位，先将x++，考虑对每个数拆位考虑
从高位到低位枚举，如果x这一位是1且不是最高位，那么cotinue
否则x是0的位置，所有这一位置是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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
int read()
{
int a=0;int f=0;char p=getchar();
while(!isdigit(p)){f|=p=='-';p=getchar();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
return f?-a:a;
}
const int N=1e6+5;
const int P=1e9+7;
int n,m;
int ans;
int a[N];
vector<int >V[31];
int d[N];
int top;
void huangyu(){
n=read(); m=read()+1; ans=0;
for(int i=0;i<31;++i) V[i].clear();
for(int i=1;i<=n;++i)
{
int x=read();
for(int k=0;k<31;++k)
if((x>>k)&1) V[k].push_back(i);
}
for(int p=0;p<31;++p)
{
if(((~m)>>p)&1) continue;
bool flag=true;
for(int i=1;i<=n;++i) d[i]=0;
for(int j=p;j<31;++j)
{
if(j!=p&&((m>>j)&1)) continue;
if(V[j].size()&1)
{
flag=false;
break;
}
for(int i=0;i<V[j].size();i+=2)
{
d[V[j][i]]++;
d[V[j][i+1]]--;
}
}
if(!flag) continue;
for(int i=1;i<=n;++i) d[i]+=d[i-1];
int res=n;
for(int i=1;i<=n;++i)
if(d[i]) res--;
ans=max(ans,res);
}
if(!ans) ans=-1;
cout<<ans<<endl;
}
int main(){
int tt;
cin>>tt;
while(tt--){
huangyu();
}
return 0;
}
|
E
组合数思维
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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N = 2e6 + 5;
const ll mod = 1e9 + 7;
ll n, m;
int a[N], b[N];
bool flag[N];
ll inv[N], finv[N];
ll f[N];
int read()
{
int a=0;int f=0;char p=getchar();
while(!isdigit(p)){f|=p=='-';p=getchar();}
while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
return f?-a:a;
}
void get_inv(int n) {
inv[0]=inv[1]=1;
for (int i=2;i<=n;i++) inv[i] = (mod-mod/i)*inv[mod%i]%mod;
for (int i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
finv[1] = f[1] = finv[0] = f[0] = 1;
for (int i = 2; i <= n; i++) finv[i] = finv[i - 1] * inv[i] % mod;
for (int i = 2; i <= n; i++) f[i] = f[i - 1] * i % mod;
}
ll A(ll n, ll m) {
if (n == 0 || m == 0) return 1;
return f[n] %mod * finv[n - m] % mod;
}
ll C(ll n, ll m) {
if (n == 0 || m == 0) return 1;
ll ans = A(n, m);
ans = ans %mod * finv[m] % mod;
return ans;
}
void huangyu(){
n=read();
int x=read(),y=read();
for (int i = 1; i <= x; i++) {
cin >> a[i];
}
for (int i = 1; i <= y; i++) {
cin >> b[i];
}
if (a[x] != b[1] || a[1] != 1 || b[y] != n) {
cout << 0 << '\n';
return ;
}
ll need = a[x] - 1;
ll ans = 1, lst = a[x];
for (int i = x - 1; i >= 1; i--) {
need--;
ll num = lst - a[i] - 1;
ans = ans * A(need, num) % mod;
need -= num;
lst = a[i];
}
need = n - a[x];
lst = a[x];
for (int i = 2; i <= y; i++) {
need--;
ll num = b[i] - lst - 1;;
ans = ans * A(need, num) % mod;
need -= num;
lst = b[i];
}
ans = ans * C(n - 1, a[x] - 1) % mod;
cout << ans << endl;
}
int main(){
int tt;
cin>>tt;
get_inv(3e5+10);
while(tt--){
huangyu();
}
return 0;
}
|
