2019牛客暑期多校训练营第四场
2019-07-29 / Luo Jinrong   

进度

A B C D E F G H I J K
√ ∅ ∅ √ √

A. meeting

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define per(i, a, b) for(int i=a; i<b; i++)
const int MAXN(2e5+7);
const int INF(0x3f3f3f3f);
 
int N, K;
 
int tto[MAXN], nxt[MAXN];
int head[MAXN];
int cntt=1;
int val[MAXN], vv[MAXN];
 
int outt;
int dfs1(int u,int fa) {   //当前节点、父节点、层次深度
    int mxx1=0, mxx2=0, tmp;
    vv[u]=val[u];
    for(int i=head[u];i;i=nxt[i])
    {
        int v=tto[i];
        if(v==fa)
            continue;
        tmp = dfs1(v,u)+1;    //层次深度+1
        if(vv[v]) {
            if (mxx1 < tmp) {
                mxx2 = mxx1;
                mxx1 = tmp;
            } else if (mxx2 < tmp) {
                mxx2 = tmp;
            }
        }
        vv[u]+=vv[v];
    }
    if(mxx1) {
        if(mxx2 || val[u]) {
            outt = max(outt, mxx1+mxx2);
        }
    }
    return mxx1;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N >> K;
    int u, v;
    per(i, 1, N) {
        cin >> u >> v;
        tto[cntt] = v;
        nxt[cntt] = head[u];
        head[u] = cntt++;
        tto[cntt] = u;
        nxt[cntt] = head[v];
        head[v] = cntt++;
    }
    per(i, 0, K) {
        cin >> u;
        val[u]=1;
    }
    dfs1(1, 0);
    cout << (outt+1)/2 << endl;
 
    return 0;
}

C. sequence

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 <bits/stdc++.h>
using namespace std;
#define per(i, a, b) for(int i=a; i<b; i++)
typedef long long ll;
const ll MAXN(3e6+7);
 
int n;
ll a[MAXN], b[MAXN], outt, pre, ma;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    per(i, 1, n+1) { cin >> a[i]; }
    cin >> b[1];
    outt = a[1]*b[1];
    ma=a[1];
    pre=b[1]<0?0:b[1];
    per(i, 2, n+1) {
        cin >> b[i];
        outt = max(outt, a[i]*b[i]);
        ma = min(ma, a[i]);
        pre+=b[i];
        outt = max(outt, ma*pre);
        if(pre<0) {
            pre=0;
            ma=a[i+1];
        }
    }
    ma=a[1];
    pre=b[1]>0?0:b[1];
    per(i, 2, n+1) {
        ma = min(ma, a[i]);
        pre+=b[i];
        outt = max(outt, ma*pre);
        if(pre>0) {
            pre=0;
            ma=a[i+1];
        }
    }
    cout << outt << endl;
 
    return 0;
}

D. triples I

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
#include<bits/stdc++.h>
#define FIN freopen("./D.in","r",stdin)
#define debug(x) cout<<#x"=["<<x<<"]"<<endl
using namespace std;
typedef long long ll;
const ll maxn(1e2+5);
const double pi=acos(-1);
ll n,mod[3][maxn],num[3],ans[2],T;
int main(){
#ifndef ONLINE_JUDGE
    FIN;
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
        memset(ans,0,sizeof(ans));
        num[1]=num[2]=0;
        cin>>n;
        if(n%3==0){
            cout<<1<<" "<<n<<endl;
            continue;
        }
        for(ll i=0;i<=60;i++){
            if((n&(1ll<<i))){
                mod[(1ll<<i)%3][num[(1ll<<i)%3]++]=1ll<<i;
            }
        }
        if(num[1]>=1&&num[2]>=1){
            ans[0]+=mod[1][0]+mod[2][0];
            for(ll i=1;i<num[1];i++){
                ans[1]+=mod[1][i];
            }
            for(ll i=1;i<num[2];i++){
                ans[1]+=mod[2][i];
            }
            if(ans[1]%3==1){
                ans[1]+=mod[2][0];
            }else if(ans[1]%3==2){
                ans[1]+=mod[1][0];
            }
        }else if(num[1]>=3){
            ans[0]+=mod[1][0]+mod[1][1]+mod[1][2];
            for(ll i=3;i<num[1];i++){
                ans[1]+=mod[1][i];
            }
            if(ans[1]%3==1){
                ans[1]+=mod[1][0]+mod[1][1];
            }else if(ans[1]%3==2){
                ans[1]+=mod[1][0];
            }
        }else if(num[2]>=3){
            ans[0]+=mod[2][0]+mod[2][1]+mod[2][2];
            for(ll i=3;i<num[2];i++){
                ans[1]+=mod[2][i];
            }
            if(ans[1]%3==1){
                ans[1]+=mod[2][0];
            }else if(ans[1]%3==2){
                ans[1]+=mod[2][0]+mod[2][1];
            }
        }
        cout<<"2 "<<ans[0]<<" "<<ans[1]<<endl;
    }
}

J. free

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
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define pi 3.1415926
#define mp(x, y) make_pair(x, y)
#define vi vector<int>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pair;
const int MAX = 1e3 + 10;
 
struct edge {
    int nxt, to, w;
}e[MAX * 2];
 
int head[MAX], tot;
 
void add(int u, int v, int w) {
    e[++tot].nxt = head[u];
    e[tot].to = v;
    e[tot].w = w;
    head[u] = tot;
}
 
int N, M, S, T, K;
int f[MAX][MAX], vis[MAX];
int grap[MAX][MAX];
 
void Dijkstra0(int u) {
    for(int i=1; i<=N; i++) {
        vis[i]=0;
    }
    vis[u] = 1;
    f[u][0] = 0;
    int k=0;
    for(int i=1; i<N; i++) {
        for(int it=head[u]; it; it=e[it].nxt) {
            if(vis[e[it].to]) continue;
            f[e[it].to][k] = min(f[e[it].to][k], f[u][k]+e[it].w);
        }
        int mm = INF, mp=u;
        for(int i=1; i<=N; i++) {
            if(!vis[i] && mm>f[i][k]) {
                mm=f[i][k];
                mp = i;
            }
        }
        u = mp;
        vis[u] = 1;
    }
}
 
inline void Dijkstra(int k) {
    for(int i=1; i<=N; i++) {
        for(int it=head[i]; it; it=e[it].nxt) {
            f[e[it].to][k] = min(f[e[it].to][k], f[i][k-1]);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    tot = 0;
    cin >> N >> M >> S >> T >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            grap[i][j] = INF;
        }
    }
    for(int i=0; i<=K; i++) {
        for(int j=1; j<=N; j++) {
            f[j][i]=INF;
        }
    }
    for (int i = 1; i <= M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        grap[v][u] = grap[u][v] = min(grap[u][v], w);
    }
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            if (grap[i][j] < INF) {
                add(i, j, grap[i][j]);
                add(j, i, grap[i][j]);
            }
        }
    }
    Dijkstra0(S);
    for(int i=1; i<=K; i++) {
        Dijkstra(i);
    }
    cout << f[T][K] << endl;
    return 0;
}

K. number

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
#include<bits/stdc++.h>
#define FIN freopen("./K.in","r",stdin)
#define debug(x) cout<<#x"=["<<x<<"]"<<endl
using namespace std;
typedef long long ll;
const ll maxn(1e5+5);
const double pi=acos(-1);
ll len,dp[3][maxn],sum[maxn],ans;
string s;
int main(){
#ifndef ONLINE_JUDGE
    FIN;
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>s;
    len=s.length();
    sum[0]=s[0]-'0';
    dp[(s[0]-'0')%3][0]=1;
    for(ll i=1;i<len;i++){
        if((s[i]-'0')%3==0){
            dp[0][i]=dp[0][i-1]+1;
            dp[1][i]=dp[1][i-1];
            dp[2][i]=dp[2][i-1];
        }else if((s[i]-'0')%3==1){
            dp[0][i]=dp[2][i-1];
            dp[1][i]=dp[0][i-1]+1;
            dp[2][i]=dp[1][i-1];
        }else{
            dp[0][i]=dp[1][i-1];
            dp[1][i]=dp[2][i-1];
            dp[2][i]=dp[0][i-1]+1;
        }
    }
    ll flag=0,pre0=1,pre0num=0;
    for(ll i=0;i<len;i++){
        if(pre0==1&&s[i]=='0'){
            pre0num++;
        }
        if(pre0==1&&s[i]!='0'){
            ans+=(pre0num+1)*pre0num/2;
            pre0=0;
        }
        if(pre0==0&&s[i]=='0'){
            flag++;
        }
        if(pre0==0&&s[i]!='0'&&flag){
            if(flag>=2){
                if(dp[0][i-1]-flag>0){
                    ans+=(dp[0][i-1]-flag)*(flag-1);
                }
                ans+=(1+flag)*flag/2;
            }else{
                ans++;
            }
            flag=0;
        }
    }
    if(pre0){
        ans+=(pre0num+1)*pre0num/2;
    }
    if(flag>=2){
        if(dp[0][len-1]-flag>0){
            ans+=(dp[0][len-1]-flag)*(flag-1);
        }
        ans+=(1+flag)*flag/2;
    }
    cout<<ans<<endl;
}

return 0;

本文链接：
https://luojinrong.github.io/2019/07/29/2019牛客暑期多校训练营第四场/