The game link

A

Train of thought

NNN less than 333 is the first layer, otherwise 222 of the first layer is subtracted, and the answer is 1+n+x−1×1+\frac{n+x-1}{x}1+xn+x−1.

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));
}
ll n,x;
void solve(a)
{
	cin>>n>>x;
	if(n<=2)
		cout<<1<<endl;
	else
	{
		n-=2;
		cout<<(n+x- 1)/x+1<<endl; }}int main(a)
{
	int _;
	cin>>_;
	while(_ --) {solve();
	}
}
Copy the code

B

Train of thought

For the elements above the diagonals from the top left to the bottom right, I =ji=ji=j is always the case, so just consider the diagonals from the top right to the bottom left. This requires the existence of a brick, the element in the upper right corner is equal to the element in the lower left corner, and determine whether there is such a brick and whether the size of the laying is even.

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));
}
ll n,m;
void solve(a)
{
	In(2,&n,&m);
	ll flag=0;
	rep(i,1,n)
	{
		ll a,b,c,d;
		In(4,&a,&b,&c,&d);
		if(b==c)
			flag=1;
	}
	if(m%2| |! flag) {puts("NO");
	}
	else
		puts("YES");
}
int main(a)
{
	int _;
	cin>>_;
	while(_ --) {solve();
	}
}
Copy the code

C

Train of thought

Adding and copying the same number of times will obviously get the most value. If x=nx= SQRT nx=n, the total cost is x−1+nxx-1+\frac{n}{x}x−1+xn, and the formula is rewritten as x+nx−1x+\frac{n}{x}-1x+xn−1. According to the basic inequality, this formula is minimum if and only if x=nx=\ SQRT nx=n. N −1+nn\ SQRT n-1+\frac{n}{\ SQRT n}n −1+nn.

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));
}
void solve(a)
{
	ll n;
	In(1,&n);
	ll tmp=sqrt(n);
	ll ans=(tmp- 1)+n/tmp;
	if(n%tmp==0)
		--ans;
	Out(1,ans);
}
int main(a)
{
	int _;
	cin>>_;
	while(_ --) {solve();
	}
}
Copy the code

D

Train of thought

Let the sum of the preceding iii items be sumisum_isumi. If the sum of subsegments [L,r][L,r][L,r] is 000, then sumr= sumL −1sum_r=sum_{L-1}sumr= sumL −1. So as long as the sumsumsum value is repeated, it means that the sum of the subsegments between the two repeated positions is 000. Because we want to insert as few new elements as possible, we want to make the prefix sum repeat as little as possible, so we insert an INFINFINF in front of the RRR element, after which the preceding prefix sum is irrelevant to the subsequent calculation, leaving ara_RAR as the only prefix sum that has ever occurred. The number of occurrences of prefix and can be maintained using mapmapMap.

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,ans;
ll a[N];
map<ll,int> ma;
int main(a)
{
	In(1,&n);
	rep(i,1,n)
		In(1,&a[i]);
	ll sum=0;
	rep(i,1,n)
	{
		sum+=a[i];
		if(sum==0 || ma.find(sum)! =ma.end())
		{
			sum=a[i];
			ma.clear(a); ++ans; } ma.insert(ma.end(),pair<ll,int>(sum,1));
	}
	Out(1,ans);
}
Copy the code

E

Train of thought

To win the least, use your fists to offset the opponent’s punches and baggage, and the rest is what you have to win. Similarly for the other two, at most one of them is positive, so maxmaxmax. To win the most, win as much as you can, using the smallest amount of your fists and the other two scissors to maintain your answer.

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));
}
ll n,ans1=LLm,ans2;
ll a[5],b[5];
int main(a)
{
	In(1,&n);
	a[0]=LLm;
	b[0]=LLm;
	rep(i,1.3)
		In(1,&a[i]);
	rep(i,1.3)
		In(1,&b[i]);
	rep(i,1.3)
	{
		ans1=max(ans1,a[i]-b[i]-b[i- 1= =0?3:i- 1]);
		ans2+=min(a[i],b[i+1= =4?1:i+1]);
	}
	Out_(2.max(0ll,ans1),ans2);
	
}
Copy the code

F

Train of thought

For the sake of presentation, the?? Change to #\##. Can contribute to the answer of the combination of ABC, ab#, BC, # # b#, c #, # #, # #, c # # # ABC, ab \ #, # \ BC, # # \ \ b, a \ # c, a, #, #, # # \ \ c, #, #, #, ABC, ab#, BC, # # b#, c #, # #, # #, c # # #. You can see that the middle element is either BBB or #\##. Take ab#ab #ab# as an example. If you take each BBB as an intermediate element, then the product of all the aaa’s to the left and all the ## ab’s to the right is the number of ABcabcabcs transformed from ab#ab #ab# ab#ab #ab# ab#ab #ab# ab#ab #ab# ab#ab #ab# ab#ab #ab# ab#ab #ab# ab# When a pair of ab#ab #ab# is converted to abcabcabc, other unconverted ## # (assuming the entire string has sumxsumxsumx ## #) will have sumx−1sumx-1sumx−1, each of which can be converted into any of three letters. The total number of schemes is 3sumx−13^{sumx-1}3sumx−1. The same goes for other cases. Linear sweep over the string calculated each BBB and # \ front how many a, # # # a, \ # a, #, behind how much c, c #, # \ c #.

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=2E5+10,M=1E9+7;
ll n,ans,sumx;
ll pre[N][5],lst[N][5];
string s;
void print(a)
{
	rep(i,1,n)
		Out_(4,pre[i][0],pre[i][1],lst[i][0],lst[i][3]);
	puts("");
}
ll ksm(ll a,ll b)
{
	if(b<0)
		return 0ll;
	ll ret=1;
	while(b)
	{
		if(b&1)
			ret=ret*a%M;
		a=a*a%M;
		b>>=1;
	}
	return ret;
}
int main(a)
{
	In(1,&n);
	cin>>s;
	s=' '+s;
	ll cnta=0,cntx=0;
	rep(i,1,n)
	{
		if(s[i]=='a')
			++cnta;
		else if(s[i]=='b')
		{
			pre[i][0]=cntx;
			pre[i][1]=cnta;
		}
		else if(s[i]=='? ')
		{
			pre[i][0]=cntx;
			pre[i][1]=cnta;
			++cntx;
		}
	}
	sumx=cntx;
	ll cntc=0;
	cnta=cntx=0;
	for(inti=n; i>=1; --i) {if(s[i]=='c')
			++cntc;
		else if(s[i]=='b')
		{
			lst[i][0]=cntx;
			lst[i][3]=cntc;
		}
		else if(s[i]=='? ')
		{
			lst[i][0]=cntx;
			lst[i][3]=cntc; ++cntx; }}/ * 0? 1 a 2 b 3 c */
	rep(i,1,n)
	{
		if(s[i]=='b')
		{
			ans+=pre[i][1]*lst[i][3] *ksm(3,sumx);
			ans%=M;
			ans+=pre[i][1]*lst[i][0] *ksm(3,sumx- 1);
			ans%=M;
			ans+=pre[i][0]*lst[i][3] *ksm(3,sumx- 1);
			ans%=M;
			ans+=pre[i][0]*lst[i][0] *ksm(3,sumx2 -);
			ans%=M;
		}
		else if(s[i]=='? ')
		{
			ans+=pre[i][1]*lst[i][3] *ksm(3,sumx- 1);
			ans%=M;
			ans+=pre[i][1]*lst[i][0] *ksm(3,sumx2 -);
			ans%=M;
			ans+=pre[i][0]*lst[i][3] *ksm(3,sumx2 -);
			ans%=M;
			ans+=pre[i][0]*lst[i][0] *ksm(3,sumx- 3); ans%=M; }}Out(1,ans%M);
}
Copy the code