2024 暑期牛客多校训练营 10
目录
2024 暑期牛客多校训练营 10
A Surrender to My Will
签到题
B std::pair
模拟，建立二叉树即可
D Is it rated?
题目大意
有 $n$ 场$\textbf{按顺序}$的比赛，第 $i$ 场比赛有表现分 $p_i$。参加第 $i$ 场比赛后你的分数 $r$ 将变为 $r\times(1-k)+k\times p_i$。你可以选择最多 $m$ 场比赛不参加。给定初始分数 $r_0$ 和参数 $k$。问经过至少 $n-m$ 场比赛后，分数最高是多少。
题解做法
根据数据范围 $k\geq0.1$, 经过至多 200 场后之前的分数影响将在精度误差之内, 故只需要考虑最后 $\min(m+200,n)$ 场比赛即可.
场上某大佬做法（可忽略 k 范围）
1const int N = 1e6 + 5;
2ll a[N];
3db k, p[N];
4#define vt vct<db>
5vt dfs (int l, int r)
6{
7 if (l == r) rty {0, k * a[l]};
8 int m = l + r >> 1;
9 vt L = dfs (l, m);
10 vt R = dfs (m + 1, r);
11 int i = 0, j = 0;
12 vt ans = {0};
13 while (i + 1 < L.sz && j + 1 < R.sz)
14 {
15 if (L[i] * p[j + 1] + R[j + 1] > L[i + 1] * p[j] + R[j])
16 j++, ans.pb (L[i] * p[j] + R[j]);
17 else
18 i++, ans.pb (L[i] * p[j] + R[j]);
19 }
20 while (i + 1 < L.sz ) i++, ans.pb (L[i] * p[j] + R[j]);
21 while (j + 1 < R.sz ) j++, ans.pb (L[i] * p[j] + R[j]);
22 rty ans;
23}
24void solve()
25{
26 cin >> n >> m >> k >> x;
27 p[0] = 1;
28 fo (i, 1, n) p[i] = p[i - 1] * (1 - k), cin >> a[i];
29 vt rp = dfs (1, n);
30 db ans = 0;
31 fo (i, n - m, n)
32 {
33 ans = max (ans, x * p[i] + rp[i]);
34// print (x * p[i] + rp[i])
35 }
36 sp (12);
37 ANS;
38 rty;
39}用类似归并排序的方式来求区间内选择 $1\sim len$ 场的最大得分. O($n\log n$)
分析: 在相同场次下, 不同的选取方式大小关系与初始分数无关. 基于原始 dp $f_{i,j}$ 表示前 $i$ 场, 选了 $j$ 场参加的最大得分. 寻找性质快速合并.
下面来证明正确性：
F Collinear Exception
按顺序模拟，可以加入时暴力标记新增直线覆盖的点，经分析复杂度正确 O(能过)
1#include<bits/stdc++.h>
2using namespace std;
3
4#define pii pair<int,int>
5#define fi first
6#define se second
7#define ls (rt<<1)
8#define rs (rt<<1|1)
9#define Ls (tr[rt].lc)
10#define Rs (tr[rt].rc)
11
12const int N=1e3+10;
13int n,vis[N][N];
14vector<pii>ans;
15char s[N*N];
16void add(int x1,int y1,int x2,int y2)
17{
18 int dltx=(x1-x2),dlty=(y1-y2),gd=__gcd(abs(dltx),abs(dlty));
19 dltx/=gd;
20 dlty/=gd;
21 int nx=x1,ny=y1;
22 while(nx>=1&&nx<=n&&ny>=1&&ny<=n)
23 {
24 vis[nx][ny]=1;
25 nx+=dltx;
26 ny+=dlty;
27 }
28 nx=x1,ny=y1;
29 while(nx>=1&&nx<=n&&ny>=1&&ny<=n)
30 {
31 vis[nx][ny]=1;
32 nx-=dltx;
33 ny-=dlty;
34 }
35 return;
36}
37int main()
38{
39 read(n);
40 for(int i=1,x,y;i<=n*n;i++)
41 {
42 read(x),read(y);
43 if(!vis[x][y])
44 {
45 s[i]='1';
46 vis[x][y]=1;
47 for(auto p:ans)
48 add(p.fi,p.se,x,y);
49 ans.push_back(make_pair(x,y));
50 }
51 else s[i]='0';
52 }
53 puts(s+1);
54 flushout();
55 return 0;
56}H All-in at the Pre-flop
诈骗题 答案为 $\dfrac{a}{a+b}$
J Doremy’s Starch Trees
换根 dp，维护子树内部点是否满足要求，换根时当前根的新子树 dfs 序是新根 dfs 序的补集。用 dfs 重新编号对每个点的边排序然后二分可以 O($\log n$) 判断是否存在合法边。
1#include<bits/stdc++.h>
2using namespace std;
3const int N=1e6+10;
4int T,n,dfn[N],Time,last[N],f[N],eto[N];
5vector<int>e[N],e2[N];
6
7void dfs(int now,int fa)
8{
9 dfn[now]=++Time;
10 for(int to:e[now])
11 if(to!=fa)dfs(to,now);
12 last[now]=Time;
13 return;
14}
15bool find(int x,int l,int r)
16{
17 if(l>r)return 0;
18 if(e2[x].back()<l)return 0;
19 if(e2[x][0]>r)return 0;
20 int pos=0;
21 int L=0,rr=e2[x].size()-1,mid;
22 while(L<=rr)
23 {
24 mid=(L+rr)>>1;
25 if(e2[x][mid]>=l)pos=mid,rr=mid-1;
26 else L=mid+1;
27 }
28 return e2[x][pos]<=r;
29}
30void dfs2(int now,int fa)
31{
32 f[now]=1;
33 for(int to:e[now])
34 if(to!=fa)
35 {
36 dfs2(to,now);
37 f[now]&=f[to];
38 eto[to]=find(now,dfn[to],last[to]);
39 f[now]&=eto[to];
40 }
41 return;
42}
43int ans=-1;
44void dfs3(int now,int fa)
45{
46// printf("%d %d %d\n",now,fa,f[now]);
47 if(f[now])
48 {
49 ans=now;
50 return;
51 }
52 vector<int>g;
53 g.clear();
54 g.resize(e[now].size());
55 int l=e[now].size();
56 for(int i=0;i<l;i++)
57 if(e[now][i]!=fa)g[i]=f[e[now][i]]&eto[e[now][i]];
58 else g[i]=1;
59 for(int i=l-2;i>=0;i--)
60 g[i]&=g[i+1];
61 int fg=1;
62 for(int i=0;i<l;i++)
63 {
64 int to=e[now][i];
65 if(to!=fa)
66 {
67 if(fg&&(i<l-1?g[i+1]:1)&&(find(to,1,dfn[to]-1)||find(to,last[to]+1,n)))
68 dfs3(to,now);
69 fg&=eto[to]&f[to];
70 }
71 }
72}
73int main()
74{
75 cin>>T;
76 while(T--)
77 {
78 cin>>n;
79 for(int i=1;i<=n;i++)e2[i].clear(),e[i].clear();
80 for(int i=2,p;i<=n;i++)
81 {
82 cin>>p;
83 e2[p].push_back(i);
84 e2[i].push_back(p);
85 }
86 for(int i=2,p;i<=n;i++)
87 {
88 cin>>p;
89 e[p].push_back(i);
90 e[i].push_back(p);
91 }
92 Time=0;
93 dfs(1,0);
94 for(int i=1;i<=n;i++)
95 {
96 for(int j=0;j<e2[i].size();j++)e2[i][j]=dfn[e2[i][j]];
97 sort(e2[i].begin(),e2[i].end());
98 }
99 dfs2(1,0);
100 ans=-1;
101 dfs3(1,0);
102 cout<<ans<<'\n';
103 }
104 flushout();
105 return 0;
106}
107/*
1081
1094
1101 2 3
1111 1 1
112*/K Doremy’s IQ 2
显然是先往小走再往大走（或者反过来），枚举最小走到哪，最大的端点单调不增可以用双指针维护。O(n)
1#include<bits/stdc++.h>
2using namespace std;
3const int N=1e5+10;
4int T,n,a[N],ans;
5int work()
6{
7 int l=1,r=n,res=0;
8 for(int l=n;l;l--)
9 if(l>(-a[l])&&a[l]<=0)
10 {
11 while(a[r]>0&&n-r<a[r]-a[l])r--;
12 res=max(res,r-l+1);
13 }
14 return res;
15}
16int main()
17{
18 read(T);
19 while(T--)
20 {
21 read(n);
22 for(int i=1;i<=n;i++)read(a[i]);
23 ans=work();
24 for(int i=1;i<=n;i++)a[i]=-a[i];
25 reverse(a+1,a+n+1);
26 ans=max(ans,work());
27 write(ans-1);
28 }
29 flushout();
30 return 0;
31}L Tada!
考虑枚举密码，将状态 $A$ 变为 $B$ 所需的步数等于 $A-B$ (每一位在模 $10$ 意义下分别做减法) 通过区间加减 $1$，变为 $00000$ 的步数。 不难发现操作可逆，所以 $A-B$ 变为 $00000$ 的最少步数等于 $00000$ 变为 $A-B$ 的步数，所以从 $00000$ 出发 $\text{bfs}$ 求出每个 $A-B$ 的最少步数即可，记作 $f_{A-B}$ 当 $n>1,t_i>1$ 时，只要 $f_{A-B}\le t_i$ 一定可以成功，与奇偶性无关。 当 $n=1$ 或 $t_i=1$ 时，则需考虑奇偶性。 O($m10^n$)
1#include<bits/stdc++.h>
2using namespace std;
3const int N=1e5+10;
4int T,n,m,cnt[N],d[6],D[6],num[6],f[N];
5void init()
6{
7 memset(f,-1,sizeof(f));
8 f[0]=0;
9 queue<int>q;
10 q.push(0);
11 while(!q.empty())
12 {
13 int now=q.front();
14 q.pop();
15 for(int j=5,nw=now;j;j--)
16 num[j]=nw%10,nw/=10;
17 for(int i=1;i<=5;i++)
18 for(int j=i,v;j<=5;j++)
19 {
20 for(int k=i;k<=j;k++)
21 num[k]++,num[k]%=10;
22 v=0;
23 for(int k=1;k<=5;k++)
24 v=v*10+num[k];
25 if(f[v]==-1)
26 {
27 f[v]=f[now]+1;
28 q.push(v);
29 }
30 for(int k=i;k<=j;k++)
31 num[k]+=18,num[k]%=10;
32 v=0;
33 for(int k=1;k<=5;k++)
34 v=v*10+num[k];
35 if(f[v]==-1)
36 {
37 f[v]=f[now]+1;
38 q.push(v);
39 }
40
41 for(int k=i;k<=j;k++)
42 num[k]++,num[k]%=10;
43 }
44 }
45 return;
46}
47int main()
48{
49 init();
50 read(T);
51 while(T--)
52 {
53 read(n),read(m);
54 int mx=1;
55 for(int i=1;i<=n;i++)mx*=10;
56 for(int i=0;i<mx;i++)cnt[i]=0;
57 for(int i=1,s,t;i<=m;i++)
58 {
59 read(s),read(t);
60 int ns=s;
61 for(int j=n;j;j--)
62 num[j]=ns%10,ns/=10;
63 for(int j=1;j<=n;j++)d[j]=num[j];
64 for(int as=0,now,v;as<mx;as++)
65 {
66 now=as;
67 for(int j=n;j;j--)
68 num[j]=now%10,now/=10;
69 for(int j=1;j<=n;j++)
70 D[j]=num[j]-d[j],D[j]=(D[j]%10+10)%10;
71 v=0;
72 for(int j=1;j<=n;j++)v=v*10+D[j];
73 if(f[v]==0&&t==1)continue;
74 if(n==1&&(abs(t-f[v])&1))continue;
75 if(f[v]<=t)cnt[as]++;
76 }
77 }
78 int ans=0,pos=0;
79 for(int i=0;i<mx;i++)
80 if(cnt[i]==m)ans++,pos=i;
81 if(ans>1)puts("MANY");
82 else if(ans==1)
83 {
84 for(int j=1;j<=n;j++)num[j]=pos%10,pos/=10;
85 for(int j=n;j;j--)
86 putchar(num[j]+'0');
87 putchar('\n');
88 }
89 else puts("IMPOSSIBLE");
90 }
91 flushout();
92 return 0;
93}
94/*
951
963 3
97003 1
98003 3
99025 1
100*/