T1

原题，降智题。

求 的个数

卡速米打炸了，然后又犯了(int)1e18 送的分都没拿到

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdlib>
#include<ctime>

typedef long long ll;

using namespace std;

namespace mstd{

    inline void qread(int &x)
    {
        x=0; int f=1;
        static char c=getchar();
        while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
        while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
        x*=f;
    }

    inline void qread(long long &x)
    {
        x=0; long long f=1;
        static char c=getchar();
        while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
        while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
        x*=f;
    }
}

ll n,m;

const ll looker=(long long)1e12;

ll ksm(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1ll) ans=ans*x;
        x=x*x;
        if(x>=looker||ans>=looker||(x>=(long long)1e9&&y!=1)) return max(x,ans);
        y>>=1;
    }
    return ans;
}

inline void solve()
{
    mstd::qread(n);
    mstd::qread(m);
    if(m==1)
    {
        printf("%lld\n",n);
        return ;
    }
    if(m==2)
    {
        int t=sqrt(n);
        printf("%d",t);
        return ;
    }
    int i;
    for(i=1;ksm(i,m)<=n;i++) ;
    printf("%d",i-1);
    return ;
}

int main()
{
    //freopen("check.in","r",stdin);
    //freopen("check.out","w",stdout);
    //int i,j;
    solve();
    return 0;
}


T2

考试的时候突然胡出来1+4n,2+4n,3+4n,4+4n 这种划分，稍微证了下答案随 n 不下降，感觉答案都写在样例里面了

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdlib>
#include<ctime>

typedef long long ll;

using namespace std;

namespace mstd{

    inline void qread(int &x)
    {
        x=0; int f=1;
        static char c=getchar();
        while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
        while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
        x*=f;
    }

    inline void qread(long long &x)
    {
        x=0; long long f=1;
        static char c=getchar();
        while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
        while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
        x*=f;
    }
}

const int maxn=10010;

int n,col[maxn];

int main()
{
    //freopen("color.in","r",stdin);
    //freopen("color.out","w",stdout);
    int i,j;
    mstd::qread(n);
    if(n<=6)
    {
        if(n==1) printf("1\n1");
        if(n==2) printf("1\n1 1");
        if(n==3) printf("2\n1 1 2");
        if(n==4) printf("2\n1 1 2 2");
        if(n==5) printf("3\n1 1 2 2 3");
        if(n==6) printf("3\n1 1 2 2 3 3");
        return 0;
    }
    else
    {
        printf("4\n");
        for(i=1;i<=n;i+=4) col[i]=1;
        for(i=2;i<=n;i+=4) col[i]=2;
        for(i=3;i<=n;i+=4) col[i]=3;
        for(i=4;i<=n;i+=4) col[i]=4;
        for(i=1;i<=n;i++) printf("%d ",col[i]);
        return 0;
    }
    return 0;
}


T3

不开 longlong 见祖宗

由于此题是第三题，故考虑三分

发现最小值可以枚举，因此答案可以写成

即为 不上升，由于是一个单调不上升的函数加上了一个一次函数（这个不上升只会是 极大的情况，其他情况都是单峰）

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define int long long
 
typedef long long ll;

using namespace std;

namespace mstd{

    inline void qread(int &x)
    {
        x=0; int f=1;
        static char c=getchar();
        while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
        while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
        x*=f;
    }

    inline void mqread(long long &x)
    {
        x=0; long long f=1;
        static char c=getchar();
        while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
        while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
        x*=f;
    }
}

const int maxn=200100;

ll n,m,a[maxn],K,D,mmn,ans;

int check(int i)
{
    ll ntot=0,nowsz=0,ans=0;
    ntot=D-mmn*i;
    nowsz=i*m;
    for(int j=1;j<=m;j++)
    {
        if(a[j]>ntot) break;
        ll nowtmp=min(ntot/a[j],n-i);
        ntot-=nowtmp*a[j];
        nowsz+=nowtmp;
    }
    ans=nowsz+K*i;
    return ans;
}

int getans()
{
    int l=0,r=min(n,D/mmn);
    int m1,m2,ans=0,tm1,tm2;
    while(l<=r)
    {
        m1=l+(r-l+1)/3;
        m2=l+(r-l+1)*2/3;
        tm1=check(m1);
        tm2=check(m2);
        if(tm2>tm1) l=m1+1,ans=max(ans,tm2);
        else r=m2-1,ans=max(ans,tm1);
    }
    return ans;
}

inline void solve()
{
    int i,j;
    mmn=0;
    ans=0;
    mstd::qread(n);
    mstd::qread(m);
    mstd::qread(K);
    mstd::qread(D);
    for(i=1;i<=m;i++)
    {
        mstd::qread(a[i]);
        mmn+=a[i];
    }
    sort(a+1,a+m+1);
    printf("%lld\n",getans());
}

signed main()
{
    //int i,j;
    //freopen("array.in","r",stdin);
    //freopen("array.out","w",stdout);
    int t;
    mstd::qread(t);
    while(t--)
    {
        solve();
    }
    return 0;
}


T4

考场觉得不可做，考虑到出题人T1都出了原题那么自然没啥比较高的水平，造的树最多也就用一下 ，乱搞性价比很高。

然后后面作死打了一下链的部分分，结果炸了，好好地

考虑正解其实比较简单，对于一次询问拆分成两个来做，

对于深度为 的点 ，如果向下贡献，这个点的深度必然为

向上贡献是 但是由于可能存在一条链比深度还高，因此要加一个 即为

分别用两颗主席树维护即可

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdlib>
#include<ctime>

typedef long long ll;

using namespace std;

namespace mstd{

    inline void qread(int &x)
    {
        x=0; int f=1;
        static char c=getchar();
        while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
        while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
        x*=f;
    }

    inline void qread(long long &x)
    {
        x=0; long long f=1;
        static char c=getchar();
        while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
        while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
        x*=f;
    }
}

const int maxn=300300;

int n,m,head[maxn],size;
int _fat[maxn],son[maxn];
int sz[maxn],id[maxn],top[maxn],dep[maxn];
int cnt,rk[maxn],rt1[maxn],rt2[maxn];

struct edge{
    int next,to;
}e[maxn];

inline void addedge(int next,int to)
{
    e[++size].to=to;
    e[size].next=head[next];
    head[next]=size;
}

struct segment_tree{
    
    #define ls(i) t[(i)].l
    #define rs(i) t[(i)].r
    
    int tot=0;
    
    struct tree{
        int l,r,sz;
    }t[maxn*20];
    
    void change_tree(int &i,int looker,int l,int r,int x)
    {
        if(!i) i=++tot;
        t[i]=t[looker];
        if(x>r||x<l) return ;
        t[i].sz++;
        if(l==r) return ;
        int mid=(l+r)>>1;
        if(x<=mid) change_tree(ls(i)=++tot,ls(looker),l,mid,x);
        else change_tree(rs(i)=++tot,rs(looker),mid+1,r,x);
    }
    
    int ask_sum_tree(int i,int l,int r,int x)
    {
        if(!i) return 0;
        if(l==r) return t[i].sz;
        int mid=(l+r)>>1;
        int ans=0;
        if(x<=mid) ans+=ask_sum_tree(ls(i),l,mid,x);
        else ans+=ask_sum_tree(rs(i),mid+1,r,x);
        return ans;
    }
    
}st1,st2;

void dfs1(int t,int fat)
{
    int i,j;
    _fat[t]=fat;
    dep[t]=dep[fat]+1;
    sz[t]=1;
    st1.change_tree(rt1[t],rt1[fat],1,n,t+dep[t]);
    st2.change_tree(rt2[t],rt2[fat],1,n*2,dep[t]-t+n);
    //printf("%d %d %d\n",t,t+dep[t],dep[t]-t+n);
    for(i=head[t];i;i=e[i].next)
    {
        j=e[i].to;
        if(j==fat) continue;
        dfs1(j,t);
        sz[t]+=sz[j];
        if(sz[j]>sz[son[t]]) son[t]=j;
    }
}

void dfs2(int t,int topt)
{
    id[t]=++cnt;
    top[t]=topt;
    rk[cnt]=t;
    int i,j;
    if(!son[t]) return ;
    dfs2(son[t],topt);
    for(i=head[t];i;i=e[i].next)
    {
        j=e[i].to;
        if(j==son[t]||j==_fat[t]) continue;
        dfs2(j,j);
    }
}

int getlca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=_fat[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    return x;
}

inline void getans(int t1,int t2)
{
    int lca=getlca(t1,t2);
    int fakedis=dep[t1]-dep[lca];
    int llca=_fat[lca];
    int ans=0;
    ans+=st1.ask_sum_tree(rt1[t1],1,n,dep[t1]);
    ans+=st2.ask_sum_tree(rt2[t2],1,n*2,n+dep[lca]-fakedis);
    ans-=st1.ask_sum_tree(rt1[llca],1,n,dep[t1]);
    ans-=st2.ask_sum_tree(rt2[lca],1,n*2,n+dep[lca]-fakedis);
    //if(dep[lca]+lca==dep[t1]&&dep[lca]-lca+n==n+dep[lca]-fakedis) ans--;
    printf("%d\n",ans);
}

int main()
{
    int i,j;
    mstd::qread(n);
    mstd::qread(m);
    int t1,t2;
    for(i=1;i<n;i++)
    {
        mstd::qread(t1);
        mstd::qread(t2);
        addedge(t1,t2);
        addedge(t2,t1);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(i=1;i<=m;i++)
    {
        mstd::qread(t1);
        mstd::qread(t2);
        getans(t1,t2);
    }
    return 0;
}