A、C、I、J出题人题解

来自讲题PPT（这一部分作者也是我）。

J:

std：

//written by Amekawa_kanade
#include<bits/stdc++.h>
using namespace std;
void syncoff()//fuck you sync
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
}
#define endl '\n'
const int N=1e6+11;
using ll=long long;
int t,n,k,m,q;
vector<int> G[N],R[N];
vector<int> T[N];
int fa[N][21],dep[N];
int asklca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=20;i>=0;--i) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
	if(u==v) return u;
	for(int i=20;i>=0;--i) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
void addleaf(int u,int lf)
{
	fa[u][0]=lf;dep[u]=dep[lf]+1;T[lf].push_back(u),T[u].push_back(lf);
	for(int i=1;i<=20;++i) fa[u][i]=fa[fa[u][i-1]][i-1];
}
int gdi[N],ord[N],ct;ll sum[N];
void dfs(int u,int f)
{
	sum[u]=(G[u].size()==0)?1:0;
	for(auto v:T[u])
	{
		if(v==f) continue;
		//cout<<u<<' '<<v<<endl;
		dfs(v,u);
		sum[u]+=sum[v];
	}
}
void solve()
{
	cin>>n>>m;int nid=n;
	for(int i=1;i<=m;++i)
	{
		int iu,iv;
		cin>>iu>>iv;++nid;
		G[iu].push_back(nid);++gdi[nid];
		R[nid].push_back(iu);
		G[nid].push_back(iv);++gdi[iv];
		R[iv].push_back(nid);
	}
	stack<int> qq;
	qq.push(1);
	while(qq.size())
	{
		int u=qq.top();qq.pop();
		ord[++ct]=u;
		for(auto v:G[u]) 
		{
			--gdi[v];
			if(gdi[v]==0) qq.push(v);
		}
	}
	for(int i=1;i<=nid;++i) for(int j=0;j<=20;++j) fa[i][j]=1;
	for(int i=1;i<=ct;++i)
	{
		int u=ord[i];
		if(R[u].size())
		{
			int w=R[u][0];
			for(int j=1,usz=R[u].size();j<usz;++j) w=asklca(w,R[u][j]);
			addleaf(u,w);
		}
	}
	dfs(1,0);
	int ans=0;
	for(int i=1;i<=n;++i) if(G[i].size()==1&&sum[G[i][0]]==0) ++ans;
	cout<<ans<<endl;
}
int main()
{
	syncoff();
 	t=1;
    while(t--) solve();
    return 0;
}

A：

std：

//written by Amekawa_kanade
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+11;
using ll=long long;
using i128=__int128;
int t,n,k,m,q;
ll ans[N];pair<int,int> scps[N];
ll d[N],didx[N],ds[N],rcnt[N],req[N];
int ida[N],_ida[N],_idb[N];
struct opts
{
	int l,r,ti,id,tl,tr;ll v;
};
opts cs[N*5];
void solve(int l,int r,int cl,int cr,int siz,int xl,int xr)
{
	if(cl>cr) return;
	if(l==r)
	{
		for(int i=cl;i<=cr;++i) ans[ida[i]]=l;
		return;
	}
	for(int i=0;i<=siz;++i) d[i]=didx[i]=ds[i]=0;
	for(int i=cl;i<=cr;++i) d[scps[ida[i]].first]=1;
	for(int i=xl;i<=xr;++i) d[cs[i].l]=1,d[cs[i].r]=1,d[cs[i].r+1]=1;
	for(int i=1;i<=siz;++i) d[i]+=d[i-1];
	for(int i=cl;i<=cr;++i) scps[ida[i]].first=d[scps[ida[i]].first],didx[scps[ida[i]].first]=scps[ida[i]].second;
	for(int i=xl;i<=xr;++i)
	{
		cs[i].l=d[cs[i].l],cs[i].r=d[cs[i].r];didx[cs[i].l]=cs[i].tl,didx[cs[i].r]=cs[i].tr,didx[cs[i].r+1]=cs[i].tr+1;
	}
	siz=d[siz];
	int mid=(l+r)/2,ptl=0,ptr=0;
	for(int i=0;i<=siz;++i) d[i]=0;
	for(int i=xl;i<=xr;++i) if(cs[i].ti<=mid) d[cs[i].l]+=cs[i].v,d[cs[i].r+1]-=cs[i].v;
	for(int i=1;i<=siz;++i) d[i]+=d[i-1];
	for(int i=1;i<=siz;++i) ds[i]=ds[i-1]+d[i]+d[i-1]*(didx[i]-didx[i-1]-1);
	for(int i=cl;i<=cr;++i)
	{
		rcnt[i]=0;
		rcnt[i]=rcnt[i]+ds[scps[ida[i]].first];
		if(rcnt[i]>=req[ida[i]]) _ida[++ptl]=ida[i];
		else _idb[++ptr]=ida[i],req[ida[i]]-=rcnt[i];
	}
	int cm=cl-1;
	for(int i=1;i<=ptl;++i) ida[++cm]=_ida[i];
	int cd=cm;
	for(int i=1;i<=ptr;++i) ida[++cd]=_idb[i];
	int xm=xl-1;
	while(xm<xr&&cs[xm+1].ti<=mid) ++xm;
	solve(l,mid,cl,cm,siz,xl,xm);solve(mid+1,r,cm+1,cr,siz,xm+1,xr);
}
pair<int,int> asks[N];
struct BIT
{
	vector<ll> c;int _n;
	BIT(int _n):_n(_n)
	{
		c=vector<ll>(_n+3,0);
	}
	void add(int x,ll v)
	{
		while(x<=_n) c[x]+=v,x+=(x&(-x));
	}
	ll sum(int x)
	{
		ll ret=0;
		while(x>0) ret+=c[x],x-=(x&(-x));
		return ret;
	}
	ll ask(int l,int r)
	{
		if(r<l) return 0;
		return sum(r)-sum(l-1);
	}
};
int dq[N],ctr;
#define gc getchar_unlocked
inline ll qread()
{
    ll x=0,f=1;char c=gc();
    while(c<'0' || c>'9') f=(c=='-'?-1:1),c=gc();
    while(c>='0' && c<='9') x=x*10+c-'0',c=gc();
    return x*f;
}
inline void qwrite(ll x,char ed='\n')
{
    if(!x) {putchar('0'),putchar(ed);return;}
    char w[44];ll cnt=0;
    if(x<0) putchar('-'),x=-x;
    while(x) w[++cnt]=(x%10)+'0',x/=10;++cnt;
    while(--cnt) putchar(w[cnt]);putchar(ed);
}
void solve()
{
	n=qread();m=qread();BIT cx(n+1);
	for(int i=1;i<=n;++i) scps[i]=(make_pair(i,i));
	for(int i=1;i<=n;++i) req[i]=qread(),ida[i]=i;
	int cnt=0;
	for(int i=1;i<=m;++i)
	{
		int opt;
		int il,ir;
		opt=qread();il=qread();ir=qread();
		if(opt==1)
		{
			int mid=(il+ir)/2;ll sp1=mid-il+1;
			cs[++cnt]={il,il,i,cnt,il,il,sp1};
			if(mid>il) cs[++cnt]={il+1,mid,i,cnt,il+1,mid,-1};
			cs[++cnt]={mid+1,mid+1,i,cnt,mid+1,mid+1,-1};
			cs[++cnt]={mid+1,ir,i,cnt,mid+1,ir,1};
			cs[++cnt]={ir+1,ir+1,i,cnt,ir+1,ir+1,mid-ir};
		}
		else
		{
			asks[i]=make_pair(il,ir);
		}
	}
	solve(1,m+1,1,n+1,n+1,1,cnt);
	for(int i=1;i<=n;++i) dq[i]=i;ctr=1;
	sort(dq+1,dq+n+1,[](int x,int y){return ans[x]<ans[y];});
	for(int i=1;i<=m;++i)
	{
		while(ctr<=n&&ans[dq[ctr]]<=i)
		{
			cx.add(dq[ctr],1);++ctr;
		}
		if(asks[i].first==0) continue;
		int x=asks[i].first,y=asks[i].second;
		qwrite(cx.ask(x,y));
	}
}
int main()
{
 	solve();
    return 0;
}

I：

std：

//written by Amekawa_kanade
#include<bits/stdc++.h>
using namespace std;
void syncoff()//fuck you sync
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
}
#define endl '\n'
const int N=5e5+11;
using ll=long long;
int t,n,k,m,q;
int dd[N*2],d1[N],d2[N];
void manacher(string s)
{
	vector<char> ss;int _n;
	ss.push_back('^'),ss.push_back('$');
	for(auto x:s) ss.push_back(x),ss.push_back('$');
	_n=ss.size();//dd[1]=1;
	for(int i=1,l=1,r=0;i<=_n;++i)
	{
		int p=(i>r)?(1):(min(r-i+1,dd[l+r-i]));
		while(i+p-1<=_n&&i-p+1>=1&&ss[i-p+1]==ss[i+p-1]) ++p;
		--p;dd[i]=p;if(i+p-1>r) r=i+p-1,l=i-p+1;
	}
	for(int i=2;i<=_n-1;++i) if(i&1) d2[(i-1)/2]=(dd[i]-1)/2;
	else d1[i/2]=dd[i]/2;
}
bool pp[N],ps[N];
int qp[N],qs[N],qpsz,qssz;
void clr()
{
	for(int i=1;i<=n;++i) d1[i]=d2[i]=0,pp[i]=ps[i]=0;
	for(int i=1;i<=2*n+3;++i) dd[i]=0;
	qpsz=0,qssz=0;
}
ll getans(string ss)
{
	manacher(ss);
	pp[1]=ps[n]=1;
	for(int i=2;i<=n;++i)
	{
		int px=(i/2)+(i&1);
		if(i&1)
		{
			if(d1[px]>=px) pp[i]=1;
			else pp[i]=0;
		}
		else
		{
			if(d2[px]>=px) pp[i]=1;
			else pp[i]=0;
		}
	}
	for(int i=n-1;i>=1;--i)
	{
		int halfl=(n-i+1)/2+((n-i+1)&1);
		int px=i+halfl-1;
		if((n-i+1)&1)
		{
			if(d1[px]>=halfl) ps[i]=1;
			else ps[i]=0;
		}
		else
		{
			if(d2[px]>=halfl) ps[i]=1;
			else ps[i]=0;
		}
	}
	qp[++qpsz]=0;
	for(int i=1;i<=n;++i)
	{
		if(pp[i]) qp[++qpsz]=i;
		if(ps[i]) qs[++qssz]=i;
	}
	qs[++qssz]=n+1;
	ll ans=1e18;
	int qpt=1,qst=1;
	while(qpt<=qpsz)
	{
		while(qst<qssz&&qp[qpt]>=qs[qst]) ++qst;
		if(qp[qpt]==0)
		{
			ans=min(ans,1ll+(qs[qst]-1ll));
		}
		else if(qs[qst]==n+1)
		{
			int pos=qp[qpt]+1;
			if(pos>n)
			{
				ans=min(ans,1ll);
			}
			else break;
		}
		else
		{
			int lp=qp[qpt]+1,rp=qs[qst]-1;
			if(lp>rp)
			{
				if(ps[1]) ans=min(1ll,ans);
				else ans=min(0ll,ans);
			}
			else
			{
				int nlen=n+(rp-lp+1);
				if(nlen&1)
				{
					ans=min(ans,rp-lp+1ll);
				}
				else
				{
					ans=min(ans,rp-lp+1ll);
				}
			}
		}
		++qpt;
	}
	clr();return ans;
}
void solve()
{
	string s;
	cin>>s;n=s.length();
	if(n==1)
	{
		cout<<1<<endl;
		return clr();
	}
	string rs=s;reverse(rs.begin(),rs.end());
	ll ans=min(getans(s),getans(rs));
	cout<<ans<<endl;
}
int main()
{
 	t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}

C：

std：

//written by Amekawa_kanade
#include<bits/stdc++.h>
using namespace std;
void syncoff()//fuck you sync
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
}
#define endl '\n'
const int N=7e5+11;
using ll=long long;
int t,n,k,m,q;
vector<int> G[N];
ll f[N],g[N];
ll a[N],b[N],c[N];
int ndl[N],ndr[N];
bool vis[N];
void dfs(int u,int ff)
{
	vis[u]=1;
	g[u]+=(b[u]-c[u]);
	bool ok=0;ll dlt=1e18;
	ll fprod=0,fprod0=0;
	for(auto v:G[u])
	{
		if(v==ff) continue;
		dfs(v,u);
		g[u]+=g[v];
		ll prod=max(f[v],g[v]);
		dlt=min(dlt,max(f[v],g[v])-min(f[v],g[v]));
		if(f[v]>=g[v]) ok|=1;
		fprod+=prod;
	}
	fprod0=fprod;fprod0+=b[u];
	if(!ok) fprod0-=dlt;
	f[u]=max(fprod0,fprod);
}
stack<int> stk0;
int mambaout[N];
void clr()
{
	while(stk0.size()) stk0.pop();
	for(int i=1;i<=n;++i) G[i].clear(),f[i]=g[i]=vis[i]=0;
	for(int i=1;i<=n;++i) a[i]=b[i]=c[i]=ndl[i]=ndr[i]=0;
}
void solve()
{
	cin>>n;ll ans=0,prep=0;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i) cin>>b[i];
	for(int i=1;i<=n;++i) cin>>c[i],prep+=c[i];
	stack<int> stk;
	for(int i=n;i>=1;--i)
	{
		ndl[i]=i;
		while(stk.size()&&a[stk.top()]<=a[i]) stk.pop();
		if(!stk.size()) ndr[i]=n;
		else ndr[i]=stk.top()-1;
		stk.push(i);
	}
	for(int i=1;i<=n;++i)
	{
		if(stk0.size())
		{
			int u=stk0.top();
			G[u].push_back(i);
			G[i].push_back(u);
		}
		stk0.push(i);++mambaout[ndr[i]];
		while(mambaout[i]) stk0.pop(),--mambaout[i];
	}
	for(int i=1;i<=n;++i)
	{
		if(vis[i]) continue;
		dfs(i,0);ans+=max(f[i],g[i]);
	}
	cout<<ans+prep<<endl;
	return clr();
}
int main()
{
    syncoff();
 	solve();
    return 0;
}

全部评论

相关推荐

05-01 15:23
门头沟学院
现在26届后端几种同学的处境分析
[一]已拿大厂/中厂/小厂暑期Offer-大部分时间陷于日常工作，抽空整理项目，丰满简历-八股和算法无法经常巩固，秋招前可能因太长时间没复习，而有些准备不足-建议方案：合理分配时间，抽空学习&nbsp;[二]实力充足但无暑期Offer-实力充足指的是该学的东西都学完了，简历八股算法项目都还可以，但是运气问题/投的晚，没有Offer-建议方案：持续找暑期实习/日常实习&nbsp;[三]实力不足且无暑期Offer-学习进度落后，简历或八股或算法或项目都没准备好，面试无法通过-建议方案：沉淀八股、算法、项目，直接备战秋招-个人理解：从大局看没有实习的同学占大多数，只要八股、项目准备充分，秋招进中大厂是有机会的，如果算法...
ResourceUtilization：还有的是拿了大厂offer但是做的dirty work 的
点赞 评论 收藏
分享
04-29 20:18
字节跳动_后端开发(实习员工)
暑期后端高频问题汇总
菜鸡暑期一共面了40+场的大厂的面试，在这里汇总我遇见的问题及高频问题，希望帮助到五月份的同学们拿到暑期offer。先叠个甲，可能因为学历问题，腾讯以及阿里给我的面试并不多，40场中接近一半是字节，所以可能会有一些内容不涉及，仅作参考。计算机网络TCP三次握手四次挥手，为什么是三次四次问题time_wait状态的作用，以及为什么持续时间是2MSL？现代网络发展中，这个还是固定的2MSL吗？TCP超时重传机制，sack算法，hpack算法TCP拥塞控制（慢启动，拥塞发生，拥塞避免，快速恢复）HTTP2和HTTP3的特点操作系统进程间通信方式Linux为何采用页式内存管理io多路复用，...
开心的菜鸡在评审：感谢各位一下子给我从中级干到校招领航者了
牛客创作赏金赛
点赞 评论 收藏
分享
04-18 15:58
已编辑
门头沟学院 设计
你面试不通过的原因
看到一个hr发的，面试不通过的原因有够离谱的🥴
kaoyu：这一看就不是计算机的，怎么还有个排斥洗碗？
点赞 评论 收藏
分享
03-15 08:33
安徽农业大学 算法工程师
这个时间点投是不是不迟了，只有一个ICPC银
咩咩子_：项目和图形引擎岗没啥关系，最好还是项目和岗位有相关度好点，不然真有面也不一定会问很多
点赞 评论 收藏
分享
04-29 12:36
华南师范大学 Java
淘天 面经
淘天-一面手撕：多线程打印&nbsp;ABC请介绍一个你觉得复杂度较高或印象深刻的项目？在五六万&nbsp;QPS&nbsp;下，这个项目带来了什么问题？是因为资源本身有限吗？货拉拉的机器配置是怎么样的？理论上简单扩容能解决问题吗？数据是缓存到本地还是&nbsp;Redis？活动数据会有资金损失（资损）相关的问题吗？缓存是怎么刷新的？如果流量都打到&nbsp;Redis&nbsp;上，有什么优化方法？你说的“get&nbsp;加本地聚合代替&nbsp;mget”具体是什么意思？本地聚合是指什么？【先用&nbsp;size&nbsp;做判定是否在本地缓存中已经缓存了，没有的部分再去单独&nbsp;get】本地聚合加&nbsp;mget&nbsp;不好吗？【分散在各个&nbsp;slot&nbsp;上面，导致阻塞获取】如何保证本地和&nbsp;Redis...
牛客693977006号：牛逼，都看不懂
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 你上一次加班是什么时候？ #
49400次浏览 345人参与
# 学历or实习经历，哪个更重要 #
94948次浏览 683人参与
# 深信服求职进展汇总 #
177898次浏览 1663人参与
# 租房找室友 #
14476次浏览 101人参与
# 大疆求职进展汇总 #
478223次浏览 3191人参与
# 如何排解工作中的焦虑 #
149814次浏览 1750人参与
# 秋招签约后的心态变化 #
74050次浏览 790人参与
# 秋招最大的收获是什么？ #
24410次浏览 275人参与
# 实习要如何选择和准备？ #
55748次浏览 917人参与
# 秋招想进国企该如何准备 #
50376次浏览 350人参与
# 牛友打假中心 #
82489次浏览 2633人参与
# 摸鱼被leader发现了怎么办 #
49736次浏览 323人参与
# 找工作，行业重要还是岗位重要？ #
27497次浏览 460人参与
# 生化医药面经大本营 #
99894次浏览 466人参与
# 你觉得通信/硬件有必要实习吗？ #
99530次浏览 895人参与
# 多益网络求职进展汇总 #
21773次浏览 126人参与
# 如果可以，你希望哪个公司来捞你 #
70507次浏览 304人参与
# 潍柴工作体验 #
24672次浏览 18人参与
# 产品每日一题 #
39014次浏览 551人参与
# 实习工作，你找得还顺利吗？ #
401054次浏览 5541人参与
牛客网
牛客企业服务