A

思路

$n$ 小于 $3$ 就是第一层，否则就先减去第一层的 $2$ 个，答案是 $1+\frac{n+x-1}{x}$ 。

代码

#include<bits/stdc++.h>
#define rep(i,st,ed) for(int (i)=(st);(i)<=(ed);++(i))
#define bl(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()
{
	cin>>n>>x;
	if(n<=2)
		cout<<1<<endl;
	else
	{
		n-=2;
		cout<<(n+x-1)/x+1<<endl;
	}
}
int main()
{
	int _;
	cin>>_;
	while(_--)
	{
		solve();
	}
}

B

思路

对左上角到右下角的对角线上面的元素，始终满足 $i=j$ ，所以只考虑从右上角到左下角的对角线即可。这就要求存在一块砖，右上角的元素等于左下角的元素，判断是否有这样的砖以及铺设的规模是否为偶数即可。

代码

#include<bits/stdc++.h>
#define rep(i,st,ed) for(int (i)=(st);(i)<=(ed);++(i))
#define bl(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()
{
	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()
{
	int _;
	cin>>_;
	while(_--)
	{
		solve();
	}
}

C

思路

进行同样次数的增加和复制操作，先增加后复制显然会取得最大的价值。设增加后得到的值为 $x$ ，总的代价为 $x-1+\frac{n}{x}$ ，重写该式为 $x+\frac{n}{x}-1$ ，根据基本不等式，当且仅当 $x=\sqrt n$ 时该式的值最小。因此答案就是 $\sqrt n-1+\frac{n}{\sqrt n}$ ，另外特判 $n$ 为 $x$ 倍数时答案需要 $-1$ 。

代码

#include<bits/stdc++.h>
#define rep(i,st,ed) for(int (i)=(st);(i)<=(ed);++(i))
#define bl(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()
{
	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()
{
	int _;
	cin>>_;
	while(_--)
	{
		solve();
	}
}

D

思路

设前 $i$ 项和为 $sum_i$ 。如果 $[l,r]$ 子段和为 $0$ ，那必然有 $sum_r=sum_{l-1}$ 。所以只要 $sum$ 值重复出现，就说明在重复出现的两个位置之间的子段和为 $0$ 。因为要尽可能少地插入新元素，所以就要让前缀和出现重复的可能性尽可能小，所以在第 $r$ 个元素前面插入一个 $INF$ ，插入后前面的前缀和与后面的计算就没有关系了，只留下了 $a_r$ 作为唯一出现过的前缀和。前缀和的出现次数用 $map$ 维护即可。

代码

#include<bits/stdc++.h>
#define rep(i,st,ed) for(int (i)=(st);(i)<=(ed);++(i))
#define bl(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()
{
	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();
			++ans;
		}
		ma.insert(ma.end(),pair<ll,int>(sum,1));
	}
	Out(1,ans);
}

E

思路

参考博客要赢的最少，就用拳头去抵消对方的拳头和包袱，剩下的就是自己不得不赢的。其他两种同理，三者之中最多有一个是正值，因此取 $max$ 。
要赢的最多，那就尽可能地赢，在自己的拳头和对方的剪刀中取最小值维护进答案，其他两种同理。

代码

#include<bits/stdc++.h>
#define rep(i,st,ed) for(int (i)=(st);(i)<=(ed);++(i))
#define bl(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()
{
	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);
	
}

F

思路

为表述方便，将 $?$ 更改为 $\#$ 。可以对答案产生贡献的组合有 $abc,ab\#,\#bc,\#b\#,a\#c,a\#\#,\#\#c,\#\#\#$ 。可以发现中间的元素要么是 $b$ 要么是 $\#$ 。
拿 $ab\#$ 举例，可以把每个 $b$ 作为中间元素，那么它左边所有 $a$ 和它右边所有 $\#$ 的乘积就是以这个 $b$ 为中心，由 $ab\#$ 转变得到的 $abc$ 的个数。当某一对 $ab\#$ 转变为 $abc$ 之后，其他未转变的 $\#$ （假设整个字符串有 $sumx$ 个 $\#$ ）就有 $sumx-1$ 个，每一个可以变成任意三种字母，总的方案数为 $3^{sumx-1}$ 。其他情况同理。
线性扫一遍字符串计算每个 $b$ 和 $\#$ 前面有多少 $a,\#$ ，后面有多少 $c,\#$ 。

代码

#include<bits/stdc++.h>
#define rep(i,st,ed) for(int (i)=(st);(i)<=(ed);++(i))
#define bl(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()
{
	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()
{
	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(int i=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,sumx-2);
			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,sumx-2);
			ans%=M;
			ans+=pre[i][0]*lst[i][3]*ksm(3,sumx-2);
			ans%=M;
			ans+=pre[i][0]*lst[i][0]*ksm(3,sumx-3);
			ans%=M;
		}
	}
	Out(1,ans%M);
}

Codeforces Round #674 (Div. 3) 题解

A

思路

代码

B

思路

代码

C

思路

代码

D

思路

代码

E

思路

代码

F

思路

代码