The game link

A

Train of thought

The operation can only be performed once at most. It only needs to determine whether A and B have only A continuous interval [L,r][L,r][L,r]. There is a [I] – [I] b = constant (I, j ∈] [l, r) [I] a [I] – b = constant (I, j \] [l, r) in a [I] – [I] b = constant (I, j ∈] [l, r).

code

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int (i)=(st); (i)<=(ed); ++(i))
#definebl(u,i) for(int (i)=head[(u)]; (i); (i)=e[(i)].nxt)
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef long long ll;
typedef double db;
using namespace std;
inline void In(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		scanf("%lld".va_arg(lis,ll*));
}
inline void Out(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		printf("%lld\n".va_arg(lis,ll));
}
inline void Out_(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		printf("%lld ".va_arg(lis,ll));
	puts("");
}
const int N=1E5+10;
ll n;
ll a[N],b[N];
void solve(a)
{
	In(1,&n);
	rep(i,1,n)
		In(1,&a[i]);
	rep(i,1,n)
		In(1,&b[i]);
	ll flag=0,end=0;
	rep(i,1,n)
	{
		if(a[i]<b[i])
		{
			if(end)
			{
				puts("NO");
				return;
			}
			else if(! flag) flag=b[i]-a[i];else if(b[i]-a[i]! =flag) {puts("NO");
				return; }}else if(a[i]==b[i] && flag)
			end=1;
		else if(a[i]>b[i])
		{
			puts("NO");
			return; }}puts("YES");
}
int main(a)
{
	int _;
	cin>>_;
	while(_ --) {solve();
	}
}
Copy the code

B

Train of thought

The legal data sum of a day must be 000. Consider maintaining the data sum of the day sumsumsum. Once sumsumsum is cleared, the day ends. If sumsumsum is negative or an element appears more than once in a day, it is considered an invalid day, and mapmapMap is used to maintain whether the element appears, and mapmapMap is cleared at the end of each day. Sumsumsum is 000. If it is 000, end the day with the repeated element as the first element of the new day. Otherwise, it is illegal. This is not true, because if there is a chance to end the day before the recurring element, then the element can legally be added to the new day. Ending the day as early as possible always makes sense, as it allows later elements to be added to the day without colliding with the elements of the previous day.

code

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int (i)=(st); (i)<=(ed); ++(i))
#definebl(u,i) for(int (i)=head[(u)]; (i); (i)=e[(i)].nxt)
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef long long ll;
typedef double db;
using namespace std;
inline void In(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		scanf("%lld".va_arg(lis,ll*));
}
inline void Out(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		printf("%lld\n".va_arg(lis,ll));
}
inline void Out_(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		printf("%lld ".va_arg(lis,ll));
}
const int N=1E5+10;
ll n,cnt,sum,lst=1;
ll ans[N];
map<ll,ll> ma;
int main(a)
{
	In(1,&n);
	ll flag=1;
	rep(i,1,n)
	{
		ll cur;
		In(1,&cur);
		sum+=cur;
		if(sum==0)
		{
			ans[++cnt]=i-lst+1;
			lst=i+1;
			ma.clear(a); }else if(sum<0)
		{
			flag=0;
			break;
		}
		else if(cur>0)
		{
			if(ma.find(cur)==ma.end())
				ma.insert(pair<ll,ll>(cur,1));
			else
			{
				flag=0;
				break; }}else if(cur<0 && ma.find(-cur)==ma.end())
		{
			flag=0;
			break; }}if(! flag || sum)puts("1");
	else
	{
		sum=0;
		rep(i,1,cnt)
			sum+=ans[i];
		if(sum! =n) ans[++cnt]=n-sum;Out(1,cnt);
		rep(i,1,cnt)
			Out_(1,ans[i]);
		puts(""); }}Copy the code

C

Train of thought

It’s a little bit more watery than question B. Since there is no order in which to take sugar, it must be optimal to take sugar from small to large. And then how do you allocate which day to eat? The cost of small in the next few days to eat, the cost of large in the first few days to eat must be optimal, specific proof can be disproved. But every time you do ab initio you’re going to run out of time, so think about how to optimize. Assuming that we currently know the cost of day III, now consider moving to day I +1i+1i+1. The solution is to move all the sweets one place back, making room for the most expensive newcomer to take the first place on the first day. Then, every MMMM candy of a day is delivered to the next day. Accordingly, every candy deferred to the next day will contribute an extra price. K −m, K −2m, K −3m… K-M, K-2m, K-3m \cdotsk−m,k−2m,k−3m… all the elements in the position contribute to the answer. Just maintain the prefix sum of every MMM bit in the original array and the transfer can be completed in O(1)O(1)O(1).

Train of thought

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int (i)=(st); (i)<=(ed); ++(i))
#definebl(u,i) for(int (i)=head[(u)]; (i); (i)=e[(i)].nxt)
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef long long ll;
typedef double db;
using namespace std;
inline void In(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		scanf("%lld".va_arg(lis,ll*));
}
inline void Out(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		printf("%lld\n".va_arg(lis,ll));
}
inline void Out_(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		printf("%lld ".va_arg(lis,ll));
}
const int N=2E5+10;
ll n,m,ans;
ll a[N],sum[N];
int main(a)
{
	In(2,&n,&m);
	rep(i,1,n)
		In(1,&a[i]);
	sort(a+1,a+n+1);
	rep(i,1,n)
	{
		if(i-m>=1)
			sum[i]=sum[i-m]+a[i];
		else
			sum[i]=a[i];
	}
	ll ans=0;
	rep(i,1,n)
	{
		if(i<=m)
		{
			ans+=a[i];
			Out_(1,ans);
		}
		else
		{
			ans+=sum[i];
			Out_(1,ans); }}}Copy the code

D

Train of thought

All unicom block points on a number line must be straight, check first using the weighted and set the record in the original unicom piece of information (the parent node and node number), then on the number line scan it again, if two integers in unicom block is not connected, a unicom block before and behind the number axis and node, they merged the two unicom blocks (such as 7 and 8 block does not belong to the same unicom, However, as 7 and 9 belong to the same unicom block, the unicom block 8 and the unicom block 7 and 9 must be combined. Remember to maintain the number of nodes when merging.

code

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int (i)=(st); (i)<=(ed); ++(i))
#definebl(u,i) for(int (i)=head[(u)]; (i); (i)=e[(i)].nxt)
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef long long ll;
typedef double db;
using namespace std;
inline void In(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		scanf("%lld".va_arg(lis,ll*));
}
inline void Out(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		printf("%lld\n".va_arg(lis,ll));
}
inline void Out_(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		printf("%lld ".va_arg(lis,ll));
}
const int N=2E5+10;
ll n,m,tot,ans;
ll head[N],fa[N],vis[N],sum[N];
struct Edge{
	ll nxt,to;
}e[2*N];
inline void add_edge(ll u,ll v,int flag)
{
	e[++tot].nxt=head[u];
	e[tot].to=v;
	head[u]=tot;
	if(flag)
		add_edge(v,u,0);
}
ll find(ll x)
{
	returnfa[x]==x? x:fa[x]=find(fa[x]);
}
ll dfs(ll u)
{
	ll flag=0;
	bl(u,i)
	{
		ll v=e[i].to;
		if(vis[v])
			continue;
		flag=1;
		vis[v]=1;
		dfs(v);
		fa[v]=u;
	}
	return flag;
}
void print(a)
{
	rep(i,1,n)
		Out_(1,sum[i]);
}
int main(a)
{
	In(2,&n,&m);
	rep(i,1,m)
	{
		ll u,v;
		In(2,&u,&v);
		add_edge(u,v,1);
	}
	rep(i,1,n)
		fa[i]=i;
	rep(i,1,n)
	{
		if(! vis[i]) { vis[i]=1;
			ll tmp=dfs(i);
			if(! tmp) vis[i]=0; }}rep(i,1,n)
		sum[find(i)]++;
	rep(i,1,n)
	{
		--sum[find(i)];
		if(sum[find(i)] && find(i+1)! =find(i))
		{
			++ans;
			sum[find(i)]+=sum[find(i+1)];
			fa[find(i+1)]=i; }}Out(1,ans);
}
Copy the code

E

Train of thought

Let f[x]f[x]f[x] be the cost of continuing to cover MMM after [1,x][1,x] has been covered. Can be overridden to MMM by violent extension, so f[x]f[x]f[x] has an initial value of m−xm-xm− X. In addition, it can also be connected to the following section as a “springboard” to reduce costs. Because NNN is relatively small, it can find all the intervals after x+1x+1x+1, and extend its left endpoint to XXX (obviously, extending XXX to the right is not better than extending the left endpoint to the left, because extending the left endpoint also extends the right endpoint backward). The total price is dis = a [I]. L – x – 1 dis = a [I]. Dis = l – x – 1 a [I]. L – x – 1. R +dis min(m,a[I].r+dis)min(m,a[I].r+dis)min(m,a[I].r+dis)min(m,a[I].r+dis) R]f[x]=f[a[I].r]f[x]=f[a[I].r]f[x]=f[a[I].r], a[I]a[I]a[I]a[I]a[I], namely, the interval covering XXX. Covered here refers to when the cover [1] x [1] x [x] 1, then don’t need any operation can be directly by visiting the [] a [I] r f [] a [I] r f [a [I] r] to get more optimal solution, so x = a [I] rx = a [I] rx = a [I] r does not belong to the cover. Another x = a [I]. L – 1 x = a [I]. L – 1 x = a [I]. L – 1 case can also be accessed directly f [] a [I] r f [] a [I] r f [] a [I]. Am j r, see judgment conditions in your code.

code

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int (i)=(st); (i)<=(ed); ++(i))
#definebl(u,i) for(int (i)=head[(u)]; (i); (i)=e[(i)].nxt)
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef long long ll;
typedef double db;
using namespace std;
inline void In(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		scanf("%lld".va_arg(lis,ll*));
}
inline void Out(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		printf("%lld\n".va_arg(lis,ll));
}
inline void Out_(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		printf("%lld ".va_arg(lis,ll));
	puts("");
}
struct Node{
	ll x,s,l,r;
	bool operator < (const Node &tmp) const
	{
		return l>tmp.l;
	}
}a[85];
ll n,m;
ll f[(ll)1E5+10];
int main(a)
{
	In(2,&n,&m);
	rep(i,1,n)
	{
		In(2,&a[i].x,&a[i].s);
		a[i].l=max(0ll,a[i].x-a[i].s);
		a[i].r=min(m,a[i].x+a[i].s);
	}
	sort(a+1,a+n+1);
	for(intj=m; j>=0; --j) { f[j]=m-j;rep(i,1,n)
		{
			if(a[i].l<=j+1 && a[i].r>=j+1)
			{
				f[j]=f[a[i].r];
				break;
			}
			if(j<a[i].l)
			{
				ll dis=a[i].l-j- 1;
				f[j]=min(f[j],dis+f[min(m,a[i].r+dis)]); }}}Out(1,f[0]);
}
Copy the code

F

Train of thought

This one is awesome. Let’s start with the code

code

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int (i)=(st); (i)<=(ed); ++(i))
#definebl(u,i) for(int (i)=head[(u)]; (i); (i)=e[(i)].nxt)
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef long long ll;
typedef double db;
using namespace std;
inline void In(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		scanf("%lld".va_arg(lis,ll*));
}
inline void Out(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		printf("%lld\n".va_arg(lis,ll));
}
inline void Out_(ll _,...)
{
	va_list lis;
	va_start(lis,_);
	while(_--)
		printf("%lld ".va_arg(lis,ll));
}
const int N=6E5+10;
ll n,m,k,t,tot;
ll fa[N],head[N],vis[N],dis[N],f[N][24],p[N][24],dep[N];
struct Node{
	ll u,d;
	bool operator < (const Node &tmp) const
	{
		returnd>tmp.d; }};struct Edge{
	ll frm,nxt,to,w;
	bool operator < (const Edge &tmp) const
	{
		return w<tmp.w;
	}
}e[N];
priority_queue<Node> q;
inline void add_edge(ll u,ll v,ll w,int flag)
{
	e[++tot].nxt=head[u];
	e[tot].frm=u;
	e[tot].to=v;
	e[tot].w=w;
	head[u]=tot;
	if(flag)
		add_edge(v,u,w,0);
}
void Dij(a)
{
	rep(i,1,n)
	{
		if(i>k)
			dis[i]=LLM>>1;
		else
			q.push((Node){i,0});
	}
	while(! q.empty())
	{
		Node cur=q.top(a); q.pop(a); ll u=cur.u;if(vis[u])
			continue;
		vis[u]=1;
		bl(u,i)
		{
			ll v=e[i].to;
			if(dis[v]>dis[u]+e[i].w)
				q.push((Node){v,dis[v]=dis[u]+e[i].w}); }}}ll find(ll x)
{
	returnfa[x]==x? x:fa[x]=find(fa[x]);
}
void print(a)
{
	rep(i,1,n)
		Out(1,dep[i]);
}
void Kru(a)
{
	rep(i,1,tot)
		e[i].w+=dis[e[i].frm]+dis[e[i].to];
	rep(i,1,n)
	{
		head[i]=0;
		fa[i]=i;
	}
	stable_sort(e+1,e+tot+1);
	ll cnt=0;
	ll tot_=tot;
	tot=0;
	rep(i,1,tot_)
	{
		ll u=e[i].frm,v=e[i].to;
		ll uu=find(u),vv=find(v);
		if(uu==vv)
			continue;
		fa[uu]=vv;
		++cnt;
		add_edge(u,v,e[i].w,1);
		if(cnt==n- 1)
			break; }}void dfs(ll u,ll father)
{
	dep[u]=dep[father]+1;
	rep(i,0.22)
	{
		p[u][i+1]=p[p[u][i]][i];
		f[u][i+1] =max(f[u][i],f[p[u][i]][i]);
	}
	bl(u,i)
	{
		ll v=e[i].to;
		if(v==father)
			continue;
		p[v][0]=u;
		f[v][0]=e[i].w;
		dfs(v,u); }}ll lca(ll x,ll y)
{
	ll ret=LLm;
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=22; i>=0; --i) {if(dep[p[x][i]]>=dep[y])
		{
			ret=max(ret,f[x][i]);
			x=p[x][i];
		}
		if(x==y)
			return ret;
	}
	for(int i=22; i>=0; --i) {if(p[x][i]! =p[y][i]) { ret=max(ret,f[x][i]);
			ret=max(ret,f[y][i]); x=p[x][i]; y=p[y][i]; }}return max(ret,max(f[x][0],f[y][0]));
}
int main(a)
{
	In(4,&n,&m,&k,&t);
	rep(i,1,m)
	{
		ll u,v,w;
		In(3,&u,&v,&w);
		add_edge(u,v,w,1);
	}
	Dij(a);Kru(a);dfs(1.0);
	while(t--)
	{
		ll x,y;
		In(2,&x,&y);
		Out(1.lca(x,y)); }}Copy the code