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 范围）
const int N = 1e6 + 5;
ll a[N];
db k, p[N];
#define vt vct<db>
vt dfs (int l, int r)
{
if (l == r) rty {0, k * a[l]};
int m = l + r >> 1;
vt L = dfs (l, m);
vt R = dfs (m + 1, r);
int i = 0, j = 0;
vt ans = {0};
while (i + 1 < L.sz && j + 1 < R.sz)
{
if (L[i] * p[j + 1] + R[j + 1] > L[i + 1] * p[j] + R[j])
j++, ans.pb (L[i] * p[j] + R[j]);
else
i++, ans.pb (L[i] * p[j] + R[j]);
}
while (i + 1 < L.sz ) i++, ans.pb (L[i] * p[j] + R[j]);
while (j + 1 < R.sz ) j++, ans.pb (L[i] * p[j] + R[j]);
rty ans;
}
void solve()
{
cin >> n >> m >> k >> x;
p[0] = 1;
fo (i, 1, n) p[i] = p[i - 1] * (1 - k), cin >> a[i];
vt rp = dfs (1, n);
db ans = 0;
fo (i, n - m, n)
{
ans = max (ans, x * p[i] + rp[i]);
// print (x * p[i] + rp[i])
}
sp (12);
ANS;
rty;
}
用类似归并排序的方式来求区间内选择 $1\sim len$ 场的最大得分. O($n\log n$)
分析: 在相同场次下, 不同的选取方式大小关系与初始分数无关. 基于原始 dp $f_{i,j}$ 表示前 $i$ 场, 选了 $j$ 场参加的最大得分. 寻找性质快速合并.
下面来证明正确性：
F Collinear Exception
按顺序模拟，可以加入时暴力标记新增直线覆盖的点，经分析复杂度正确 O(能过)
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define ls (rt<<1)
#define rs (rt<<1|1)
#define Ls (tr[rt].lc)
#define Rs (tr[rt].rc)
const int N=1e3+10;
int n,vis[N][N];
vector<pii>ans;
char s[N*N];
void add(int x1,int y1,int x2,int y2)
{
int dltx=(x1-x2),dlty=(y1-y2),gd=__gcd(abs(dltx),abs(dlty));
dltx/=gd;
dlty/=gd;
int nx=x1,ny=y1;
while(nx>=1&&nx<=n&&ny>=1&&ny<=n)
{
vis[nx][ny]=1;
nx+=dltx;
ny+=dlty;
}
nx=x1,ny=y1;
while(nx>=1&&nx<=n&&ny>=1&&ny<=n)
{
vis[nx][ny]=1;
nx-=dltx;
ny-=dlty;
}
return;
}
int main()
{
read(n);
for(int i=1,x,y;i<=n*n;i++)
{
read(x),read(y);
if(!vis[x][y])
{
s[i]='1';
vis[x][y]=1;
for(auto p:ans)
add(p.fi,p.se,x,y);
ans.push_back(make_pair(x,y));
}
else s[i]='0';
}
puts(s+1);
flushout();
return 0;
}
H All-in at the Pre-flop
诈骗题 答案为 $\dfrac{a}{a+b}$
J Doremy's Starch Trees
换根 dp，维护子树内部点是否满足要求，换根时当前根的新子树 dfs 序是新根 dfs 序的补集。用 dfs 重新编号对每个点的边排序然后二分可以 O($\log n$) 判断是否存在合法边。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int T,n,dfn[N],Time,last[N],f[N],eto[N];
vector<int>e[N],e2[N];
void dfs(int now,int fa)
{
dfn[now]=++Time;
for(int to:e[now])
if(to!=fa)dfs(to,now);
last[now]=Time;
return;
}
bool find(int x,int l,int r)
{
if(l>r)return 0;
if(e2[x].back()<l)return 0;
if(e2[x][0]>r)return 0;
int pos=0;
int L=0,rr=e2[x].size()-1,mid;
while(L<=rr)
{
mid=(L+rr)>>1;
if(e2[x][mid]>=l)pos=mid,rr=mid-1;
else L=mid+1;
}
return e2[x][pos]<=r;
}
void dfs2(int now,int fa)
{
f[now]=1;
for(int to:e[now])
if(to!=fa)
{
dfs2(to,now);
f[now]&=f[to];
eto[to]=find(now,dfn[to],last[to]);
f[now]&=eto[to];
}
return;
}
int ans=-1;
void dfs3(int now,int fa)
{
// printf("%d %d %d\n",now,fa,f[now]);
if(f[now])
{
ans=now;
return;
}
vector<int>g;
g.clear();
g.resize(e[now].size());
int l=e[now].size();
for(int i=0;i<l;i++)
if(e[now][i]!=fa)g[i]=f[e[now][i]]&eto[e[now][i]];
else g[i]=1;
for(int i=l-2;i>=0;i--)
g[i]&=g[i+1];
int fg=1;
for(int i=0;i<l;i++)
{
int to=e[now][i];
if(to!=fa)
{
if(fg&&(i<l-1?g[i+1]:1)&&(find(to,1,dfn[to]-1)||find(to,last[to]+1,n)))
dfs3(to,now);
fg&=eto[to]&f[to];
}
}
}
int main()
{
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)e2[i].clear(),e[i].clear();
for(int i=2,p;i<=n;i++)
{
cin>>p;
e2[p].push_back(i);
e2[i].push_back(p);
}
for(int i=2,p;i<=n;i++)
{
cin>>p;
e[p].push_back(i);
e[i].push_back(p);
}
Time=0;
dfs(1,0);
for(int i=1;i<=n;i++)
{
for(int j=0;j<e2[i].size();j++)e2[i][j]=dfn[e2[i][j]];
sort(e2[i].begin(),e2[i].end());
}
dfs2(1,0);
ans=-1;
dfs3(1,0);
cout<<ans<<'\n';
}
flushout();
return 0;
}
/*
1
4
1 2 3
1 1 1
*/
K Doremy's IQ 2
显然是先往小走再往大走（或者反过来），枚举最小走到哪，最大的端点单调不增可以用双指针维护。O(n)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,n,a[N],ans;
int work()
{
int l=1,r=n,res=0;
for(int l=n;l;l--)
if(l>(-a[l])&&a[l]<=0)
{
while(a[r]>0&&n-r<a[r]-a[l])r--;
res=max(res,r-l+1);
}
return res;
}
int main()
{
read(T);
while(T--)
{
read(n);
for(int i=1;i<=n;i++)read(a[i]);
ans=work();
for(int i=1;i<=n;i++)a[i]=-a[i];
reverse(a+1,a+n+1);
ans=max(ans,work());
write(ans-1);
}
flushout();
return 0;
}
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$)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,n,m,cnt[N],d[6],D[6],num[6],f[N];
void init()
{
memset(f,-1,sizeof(f));
f[0]=0;
queue<int>q;
q.push(0);
while(!q.empty())
{
int now=q.front();
q.pop();
for(int j=5,nw=now;j;j--)
num[j]=nw%10,nw/=10;
for(int i=1;i<=5;i++)
for(int j=i,v;j<=5;j++)
{
for(int k=i;k<=j;k++)
num[k]++,num[k]%=10;
v=0;
for(int k=1;k<=5;k++)
v=v*10+num[k];
if(f[v]==-1)
{
f[v]=f[now]+1;
q.push(v);
}
for(int k=i;k<=j;k++)
num[k]+=18,num[k]%=10;
v=0;
for(int k=1;k<=5;k++)
v=v*10+num[k];
if(f[v]==-1)
{
f[v]=f[now]+1;
q.push(v);
}
for(int k=i;k<=j;k++)
num[k]++,num[k]%=10;
}
}
return;
}
int main()
{
init();
read(T);
while(T--)
{
read(n),read(m);
int mx=1;
for(int i=1;i<=n;i++)mx*=10;
for(int i=0;i<mx;i++)cnt[i]=0;
for(int i=1,s,t;i<=m;i++)
{
read(s),read(t);
int ns=s;
for(int j=n;j;j--)
num[j]=ns%10,ns/=10;
for(int j=1;j<=n;j++)d[j]=num[j];
for(int as=0,now,v;as<mx;as++)
{
now=as;
for(int j=n;j;j--)
num[j]=now%10,now/=10;
for(int j=1;j<=n;j++)
D[j]=num[j]-d[j],D[j]=(D[j]%10+10)%10;
v=0;
for(int j=1;j<=n;j++)v=v*10+D[j];
if(f[v]==0&&t==1)continue;
if(n==1&&(abs(t-f[v])&1))continue;
if(f[v]<=t)cnt[as]++;
}
}
int ans=0,pos=0;
for(int i=0;i<mx;i++)
if(cnt[i]==m)ans++,pos=i;
if(ans>1)puts("MANY");
else if(ans==1)
{
for(int j=1;j<=n;j++)num[j]=pos%10,pos/=10;
for(int j=n;j;j--)
putchar(num[j]+'0');
putchar('\n');
}
else puts("IMPOSSIBLE");
}
flushout();
return 0;
}
/*
1
3 3
003 1
003 3
025 1
*/