Codeforces Round 936 (Div. 2)

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
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N=1e6+100;
int a[N];
void solve()
{
    int n;
    cin>>n;
rep(i,1,n)
{
    cin>>a[i];
}
sort(a+1,a+1+n);
int ans=1;
int x=(n+1)/2;
rep(i,x,n-1)
{
if(a[i]==a[i+1])
{
    ans++;
}
else
{
    break;
}
}
cout<<ans<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//取消同步流
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    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
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
#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;
#define int long long
const int N=1e6+100;
int a[N];
const int mod=1e9+7;
int qpow(int a, int n)
{
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
           {
ans *= a;
ans%=mod;
}  //ans乘上当前的a
        a *= a;
        a%=mod;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}
void solve()
{
    int n;
    cin>>n;
int m;
cin>>m;
int sum=0;
int ans=0;
int x=0;
rep(i,1,n)
{
    cin>>a[i];
    if(x<0)
    {
x=0;
    }
    x+=a[i];
    sum=max(sum,x);
    ans+=a[i];
}
if(sum==0)
{
    if(ans==0)
    {
        cout<<ans%mod<<'\n';
    }
    else
    {
cout<<(ans%mod+mod)%mod<<'\n';
    }
}
else
{
    m=qpow(2,m)-1;
    m%=mod;
    if((ans%mod+m*(sum%mod))%mod<0)
    {
        cout<<(ans%mod+m*(sum%mod))%mod+mod<<'\n';
    }
    else
    {
        cout<<(ans%mod+(m)*(sum%mod))%mod<<'\n';
    }
}
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//取消同步流
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

C

树形dp+二分

写的时候知道二分，但树形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
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;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
#define ll long long
#define int long long
const int N=1e6+100;
int a[N];
int sum;
int now;
vector<int>G[N];
void dfs(int u,int fa)
{
    a[u]=1;
    for(auto v:G[u])
    {
if(v==fa)
{
    continue;
}
dfs(v,u);
a[u]+=a[v];
        //先到底下再加
    }
if(a[u]>=now)
{
    sum++;
    a[u]=0;
    //大于计数归零
}
    }
void solve()
{
    int n;
    cin>>n;
    int k;
    cin>>k;
    rep(i,1,n)
    {
        G[i].clear();
    }
    rep(i,1,n-1)
{
    int x,y;
    cin>>x>>y;
    G[x].push_back(y);
    G[y].push_back(x);
}
int l=1;
int r=n;
int root;
rep(i,1,n)
{
    if(G[i].size()==1)
    {
        root=i;
    }
}
    //找根
while(l<r)
{
    int mid=(l+r+1)>>1;
    now=mid;
    sum=0;
    dfs(root,0);
    if(sum>=k+1)
    {
        l=mid;
    }
    else
    {
        r=mid-1;
    }
}
    //二分值
cout<<l<<'\n';

}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//取消同步流
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}