nan2inf .cn
算法 旧 .com 迁移

2024 暑期牛客多校训练营 10

从 .com 迁入的长算法题解，覆盖多级标题、C++ 代码块、公式和题解过程。

约 3 分钟阅读
algocontestnowcodercodemigration

A Surrender to My Will #

签到题

B std::pair #

模拟，建立二叉树即可

D Is it rated? #

题目大意 #

有 nn 场按顺序\textbf{按顺序}的比赛，第 ii 场比赛有表现分 pip_i。参加第 ii 场比赛后你的分数 rr 将变为 r×(1−k)+k×pir\times(1-k)+k\times p_i。你可以选择最多 mm 场比赛不参加。给定初始分数 r0r_0 和参数 kk。问经过至少 n−mn-m 场比赛后，分数最高是多少。

题解做法 #

根据数据范围 k≥0.1k\geq0.1, 经过至多 200 场后之前的分数影响将在精度误差之内, 故只需要考虑最后 min⁡(m+200,n)\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∼len1\sim len 场的最大得分. O(nlog⁡nn\log n)

分析: 在相同场次下, 不同的选取方式大小关系与初始分数无关. 基于原始 dp fi,jf_{i,j} 表示前 ii 场, 选了 jj 场参加的最大得分. 寻找性质快速合并.

下面来证明正确性：

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 #

诈骗题 答案为 aa+b\dfrac{a}{a+b}

J Doremy’s Starch Trees #

换根 dp，维护子树内部点是否满足要求，换根时当前根的新子树 dfs 序是新根 dfs 序的补集。用 dfs 重新编号对每个点的边排序然后二分可以 O(log⁡n\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! #

考虑枚举密码，将状态 AA 变为 BB 所需的步数等于 A−BA-B (每一位在模 1010 意义下分别做减法) 通过区间加减 11，变为 0000000000 的步数。 不难发现操作可逆，所以 A−BA-B 变为 0000000000 的最少步数等于 0000000000 变为 A−BA-B 的步数，所以从 0000000000 出发 bfs\text{bfs} 求出每个 A−BA-B 的最少步数即可，记作 f_A−Bf\_{A-B} 当 n>1,ti>1n>1,t_i>1 时，只要 fA−B≤tif_{A-B}\le t_i 一定可以成功，与奇偶性无关。 当 n=1n=1 或 ti=1t_i=1 时，则需考虑奇偶性。 O(m10nm10^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
*/

讨论

评论

正在加载评论...