2019牛客暑期多校训练营（第七场）（A、B、C、D、E、F题待补、H题待补、J）

最新推荐文章于 2025-04-01 09:47:31 发布

小衣同学

最新推荐文章于 2025-04-01 09:47:31 发布

阅读量495

点赞数

分类专栏： # 牛客多校文章标签：牛客多校思维题线段树数位dp

本文链接：https://blog.csdn.net/Code92007/article/details/98950714

版权

牛客多校专栏收录该内容

12 篇文章

订阅专栏

心得

基础题罚时破天，难题又不会，wtcl

自己通过

A String(最小表示法+贪心/dp)

T(T<=300)组样例，每次给一个01串s，|s|<=200，

要求输出其一个划分，使得分的次数最少，且每一部分的子串都是其循环表示中字典序最小的那个(最小表示法)

~~把判一个串是否是最小表示，魔改成了判[l,r]是否是最小表示~~

贪心，枚举左端点l，从右往左枚举r，每次KMP判[l,r]是否是最小表示，是的话取下这一段，l从r+1开始继续，直至取完

dp，枚举左端点l，枚举右端点r，如果[l,r]可以，dp[r]=dp[l-1]+1，pre[r]=l-1，

实际是bfs的过程，最后找前驱的过程中记录两端点，输出即可

复杂度，似乎是 $O(T*n^3)$ 的，但跑不满，就卡过了

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int T,cnt,len;
char s[N];
struct node
{
	int l,r;
}e[N];
int getmin(char s[],int l,int r)
{
    int i=0,j=1,k=0,t,n=r-l+1;
    while(i<n&&j<n&&k<n)
    {
        t=s[l+(i+k)%n]-s[l+(j+k)%n];
        if(!t)k++;
        else
        {
            if(t>0)i+=k+1;
            else j+=k+1;
            if(i==j)j++;
            k=0;
        }
    }
    return i<j?i:j;
}
bool ok(int l,int r)
{
	return getmin(s,l,r)==0;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		cnt=0;
		scanf("%s",s);
		len=strlen(s);
		int now=0;
		while(now<len)
		{
			int r=len-1;
			while(r>now&&!ok(now,r))r--;
			e[cnt++]=node{now,r};
			now=r+1;
		}
		for(int i=0;i<cnt;++i)
		{
			if(i)putchar(' ');
			for(int j=e[i].l;j<=e[i].r;++j)
			putchar(s[j]);
		}
		puts("");
	}
    return 0;
}

C Governing sand(枚举)

多组样例(不超过30)，每次给出n(n<=1e5)种树，

以下第i行三个数，hi(1<=hi<=1e9)代表树高，ci(1<=ci<=200)代表砍倒一棵这种树的代价，pi(1<=1e9)代表这种树的数量

求最小砍倒的代价和，使得剩余的树中，最高的树的棵数，严格超过剩余的树的棵数的一半，可能存在不同种类的树同高

看题解和很多人写法用了线段树，但我枚举就暴力过去了QAQ

离散化高度h，然后枚举最终保留的树的最高高度h，

把大于h的树都砍掉，后缀和维护一下这个代价

统计高度为h的树数量有多少，后缀和作差维护一下这个数量

砍高度不足h的树时，增序枚举代价1到200，贪心地从小到大砍能砍的

只能砍高度<h的树，那就在增序枚举完当前高度now的时候，

再把树(now,c,p)释放到c对应的数量里，作下一轮h能砍的

也可倒序枚举高度，然后删树，似乎更方便一些

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
const int N=1e5+10;
const int M=205;
typedef long long ll;
typedef pair<ll,ll> P;
int n,cnt;
ll ans,C[M],H[N],tot,suf[N],suf2[N],num[N],tmp,now,can;
vector<P>h[N]; 
struct tree
{
	int h,c,p;
}e[N];
int main()
{
	while(~scanf("%d",&n))
	{
		cnt=0;
		ans=1e18+1;
		memset(C,0,sizeof C);
		memset(suf,0,sizeof suf);
		memset(suf2,0,sizeof suf2); 
		memset(num,0,sizeof num);
		for(int i=1;i<=n;++i)
		{
			scanf("%d%d%d",&e[i].h,&e[i].c,&e[i].p);
			H[++cnt]=e[i].h;
		}
		sort(H+1,H+cnt+1);
		cnt=unique(H+1,H+cnt+1)-(H+1);
		for(int i=1;i<=cnt;++i)
		h[i].clear();
		for(int i=1;i<=n;++i)
		{
			e[i].h=lower_bound(H+1,H+cnt+1,e[i].h)-H;
			h[e[i].h].pb(P(e[i].c,e[i].p));			
			suf[e[i].h]+=1ll*e[i].c*e[i].p;
			num[e[i].h]+=e[i].p;
		}
		for(int i=cnt;i>=1;--i)
		{
			suf[i]+=suf[i+1];//砍倒>=i的所有树的代价
			suf2[i]=suf2[i+1]+num[i];//>=i的所有树的数量 
		}
		for(int i=1;i<=cnt;++i)
		{
			tot=num[i];//高度为i的树个数
			tmp=suf[i+1];//>=i+1都砍掉
			now=suf2[1]-suf2[i];//<i的树的数量 
			//printf("h:%d tot:%lld now:%lld tmp:%lld\n",i,tot,now,tmp);
			for(int j=1;j<=200&&now>=tot;++j)
			{
				can=min(C[j],now-tot+1);
				tmp+=1ll*can*j;//砍小树的代价
				//if(can)printf("j:%d can:%lld\n",j,can); 
				now-=can;
			}
			//printf("tmp:%lld\n",tmp);
			ans=min(ans,tmp);
			int len=h[i].size();
			for(int j=0;j<len;++j)
			{
				ll cos=h[i][j].fi,nu=h[i][j].se;
				C[cos]+=nu;
			}
		} 
		printf("%lld\n",ans);
	}
    return 0;
}
/*
3
10 5 3
9 3 1
8 3 5
*/

J A+B problem(签到题)

人尽皆知sb题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
ll a,b;
ll rev(ll x)
{
	ll ans=0;
	for(;x;x/=10)
	ans=ans*10+(x%10);
	return ans;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld%lld",&a,&b);
		printf("%lld\n",rev(rev(a)+rev(b)));
	}
	return 0;
}

队友通过

D Number(思维题/签到题)

给你一个数n和一个素数p(1<=n<=1e6,2<=p<=1e6)，

要求输出n位的p的倍数，如果没有输出"T_T"

如果p不足n位，显然没有，否则先输出一个p，低位补0

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,p;
int cal(ll p)
{
	int dig=0; 
	for(;p;p/=10)
	dig++;
	return dig;
}
int main()
{
	scanf("%lld%lld",&n,&p);
	int d=cal(p);
	if(d>n)puts("T_T");
	else 
	{
		printf("%lld",p);
		for(int i=1;i<=n-d;++i)
		putchar('0');
		puts("");
	}
	return 0;
}

B Irreducible Polynomial(结论题/实系数多项式因式分解定理)

给你一个最高次为n(0<=n<=20)的实系数多项式，依次输入an,...,a0

问你是否能将其因式分解，能输出No，不能输出Yes

~~poj2126 原题警告~~

实系数多项式因式分解定理:

每个次数不小于1的实系数多项式在实数域上都可以唯一地分解成一次因式与二次不可约因式的乘积。

所以，对于n>=3，一定能提一个一次的或一个二次的因式出来；

n<2显然不可提项，n=2时判 $\Delta >=0$ 即可，有实根就可因式分解

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int t,n,a[N];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=n;i>=0;--i)
        scanf("%d",&a[i]);
        if(n>=3)puts("No");
        else if(n<=1)puts("Yes");
        else
        {
            if(1ll*a[1]*a[1]-4ll*a[0]*a[2]>=0)puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

赛后补题

E Find the median(线段树/左闭右开的离散化技巧)

N(N<=4e5)，初始序列为空，每次向序列里插入[l,r]这个区间完整的数，1<=l<=r<=1e9

然后序列自动排序，问序列的中位数，奇数个时取中，偶数个时取中靠左

左闭右开的离散化技巧，每个线段树节点实际维护[l,r)，

这样对应了原插入序列插入的就是[ql,qr)，[ql,qr)还可以被分裂成[ql,mid)和[mid,qr)，从而做到不重不漏

因此，向下搜的时候，是if(ql<mid)再去搜[l,mid)，同理if(qr>mid)搜[mid,r)，线段树小技巧吧

叶子结点时，l+1==r，代表[l,r)，实际维护了原序列中[al,ar)，是原子区间，即每次与其有交的区间操作都会完整覆盖其一次

那么，统计次数的时候，先统计每个数被覆盖了几次，记做block，

再去统计比k的小的(k-1)个数，占了多少个block位置，

如占了x个位置(0,...,x-1)，则k即为第x个位置，最终加上偏移量a[l]即可，

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
typedef long long ll;
int n,x[N],y[N],A,B,C,M;
int a[N<<1],m,L[N],R[N];
ll num;
void gen(int x[])//generate生成序列 
{
	scanf("%d%d%d%d%d%d",&x[1],&x[2],&A,&B,&C,&M);
	for(int i=3;i<=n;++i)
	x[i]=(1ll*A*x[i-1]+1ll*B*x[i-2]+C)%M;
}
struct node
{
	ll sum,cov;
}e[N<<3];
void pushup(int p)
{
	e[p].sum=e[p<<1].sum+e[p<<1|1].sum;
}
void build(int p,int l,int r)//左闭右开 对应原数组 
{
	if(l+1==r)
	{
		e[p].sum=e[p].cov=0;
		return;
	}
	int mid=(l+r)/2;
	build(p<<1,l,mid);
	build(p<<1|1,mid,r);
	pushup(p);
}
void pushdown(int p,int l,int r)
{
	if(e[p].cov)
	{
		int mid=(l+r)/2;
		e[p<<1].sum+=e[p].cov*(a[mid]-a[l]);
		e[p<<1|1].sum+=e[p].cov*(a[r]-a[mid]);
		e[p<<1].cov+=e[p].cov;
		e[p<<1|1].cov+=e[p].cov;
		e[p].cov=0;
	}
}
//[ql,qr)分为[ql,qr1)[qr1,qr)等... 故线段树每个节点都是左闭右开 
void update(int p,int l,int r,int ql,int qr,ll v)//[l,r)对应[ql,qr) 
{
	if(ql<=l&&r<=qr)
	{
		e[p].cov+=v;
		e[p].sum+=v*(a[r]-a[l]);
		return;
	}
	pushdown(p,l,r);
	int mid=(l+r)/2;
	if(ql<mid)update(p<<1,l,mid,ql,qr,v);//[ql,mid)
	if(qr>mid)update(p<<1|1,mid,r,ql,qr,v);//[mid,qr)
	pushup(p);
} 
int kth(int p,int l,int r,ll k)
{
	if(l+1==r)
	{
		//l+0 l+1 l+2 l+3,l+3前面有3块,故v=l+3;
		//k前面有(k-1)/block块 故v=a[l]+(k-1)/block
		ll block=e[p].sum/(a[r]-a[l]);//每块的大小
		int v=a[l]+(k-1)/block;
		return v; 
	}
	pushdown(p,l,r);
	int mid=(l+r)/2;
	if(k<=e[p<<1].sum)return kth(p<<1,l,mid,k);
	else return kth(p<<1|1,mid,r,k-e[p<<1].sum);
}
int main()
{
	scanf("%d",&n);
	gen(x);gen(y);
	for(int i=1;i<=n;++i)
	{
		L[i]=min(x[i],y[i])+1;
		R[i]=max(x[i],y[i])+2;//左闭右开 
		a[++m]=L[i];
		a[++m]=R[i]; 
	}
	sort(a+1,a+m+1);
	m=unique(a+1,a+m+1)-(a+1);
	for(int i=1;i<=n;++i)
	{
		L[i]=lower_bound(a+1,a+m+1,L[i])-a;
		R[i]=lower_bound(a+1,a+m+1,R[i])-a;
	}
	build(1,1,m);
	for(int i=1;i<=n;++i)
	{
		int l=L[i],r=R[i];
		update(1,1,m,l,r,1);
		num+=a[r]-a[l];
		printf("%d\n",kth(1,1,m,(num+1)/2));
	}
	return 0;
}

H Pair(数位dp)

给你三个数A,B,C(1<=A,B,C<=1e9)，

统计满足1<=x<=A,1<=y<=B且以下两种情况至少满足其一的<x,y>数对的数量

①(x&y)>C

②(x^y)<C