Codeforces Round #725 (Div. 3) 题解

Codeforces Round #725 (Div. 3) 题解

Problem A. Stone Game

本题有\(t\)组数据。

给出一个数组\(\{a_n\}\),每次可以花费\(a_i\)的能量拿走位于两边的数\(a_i\),若需要拿走最大和最小的\(a_i\),求所需花费的最少的能量。

对于\(100\%\)的数据满足:\(1\leq t \leq 100,2\leq n \leq 100\)

标记出最小值和最大值的位置\(p_1,p_2\),则需要取出该位置的两个数。

\(q_1,q_2 \in \{ p_1,p_2\},q_1<q_2\)。分类讨论:

  • case1:从左到右依次取。
  • case2:从右到左依次取。
  • case3:从左往右取\(q_1\),从右往左取\(q_2\)

只需求出以上三种方案的最小值即可。

复杂度\(O(tn)\)

# include <bits/stdc++.h>
using namespace std;
int a[105];
int main()
{
	int t; scanf("%d",&t);
	while (t--) {
		int n;
		scanf("%d",&n);
		int Min=n+1,Max=0;
		for (int i=1;i<=n;i++) {
			scanf("%d",&a[i]);
			Min=min(Min,a[i]);
			Max=max(Max,a[i]);
		}
		int p1,p2;
		for (int i=1;i<=n;i++) {
			if (a[i]==Min) p1=i;
			if (a[i]==Max) p2=i;
		}
		if (p1>p2) swap(p1,p2);
		int ans1=p2,ans2=n-p1+1,ans3=n-(p2-p1-1);
		int ans=n+1;
		if (ans>ans1) ans=ans1;
		if (ans>ans2) ans=ans2;
		if (ans>ans3) ans=ans3;
		printf("%d\n",ans);		
	} 
 
	return 0;
}

Problem B. Friends and Candies

本题有\(t\)组数据。

给出一个数组\(\{a_n\}\),每一次可以取出任意\(k\)个元素,将他们的和重新分配到其他元素和其本身上,使分配完成后,\(\{a_n\}\)数组各个元素都相等。如果无论怎么做都不可能做到,则输出\(-1\),否则输出最小的\(k\)

对于\(100\%\)的数据\(1\leq t \leq 10^4,1 \leq n,\sum n \leq 2 \times 10^5,1\leq a_i \leq 10^4\)

\(k=n\)时,若能平均分配,则一定能完成任务,当且仅当\(\sum a_i\)不能整除\(n\)时,输出\(-1\)

否则,令\(k\)等于所有大于\(\frac{\sum a_i}{n}\)数的个数\(d\)时恰好可以满足题设。

\(k<d\)则显然至少有一个数会大于平均值,不成立。

\(k>d\)则显然至少有一个数会小于平均值,则该数不取上,也能通过更小的\(k\)满足题设。

复杂度\(O(tn log_2 n)\)

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N=2e5+10;
int a[N];
signed main()
{
	int t; scanf("%lld",&t);
	while (t--) {
		int n; scanf("%lld",&n);
		int sum=0;
		for (int i=1;i<=n;i++) {
			scanf("%lld",&a[i]);
			sum+=a[i];
		}
		if (sum%n!=0) {
			printf("-1\n");
			continue;
		}
		sort(a+1,a+1+n);
		int ans=0;
		for (int i=n;i>=1;i--) {
			if (a[i]<=sum/n) {
				ans=n-i; break;
			}
		}
		printf("%lld\n",ans);	
	}
	return 0;
}

Problem C. Number of Pairs

本题有\(t\)组数据。

给出一个数组\(\{a_n\}\),求出所有符合\(l\leq a_i +a_j \leq r , 1 \leq i<j\leq n\)的二元组\((i,j)\)的个数。

对于\(100\%\)的数据:\(1 \leq t \leq 10^4,1\leq n,\sum n \leq 2\times10^5,1\leq a_i \leq 10^9,1\leq l\leq r \leq 10^9\).

考虑枚举左边界\(i\),用二分查找右边界\(j\)的范围满足\(l-a_i \leq a_j \leq r - a_i\)

只需对原数组排序进行预处理即可,复杂度\(O(tnlog_2n)\)

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N=2e5+10;
int a[N];
signed main()
{
	int t; scanf("%lld",&t);
	while (t--) {
		int n,L,R; scanf("%lld%lld%lld",&n,&L,&R);
		for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
		sort(a+1,a+1+n);
		int ans=0;
		for (int i=1;i<=n;i++) {
			int l=i+1,r=n,left=-1;
			while (l<=r) {
				int mid=(l+r)/2;
				if (a[mid]>=L-a[i]) r=mid-1,left=mid;
				else l=mid+1;
			}
			int right=-1;l=i+1,r=n;
			while (l<=r) {
				int mid=(l+r)/2;
				if (a[mid]<=R-a[i]) l=mid+1,right=mid;
				else r=mid-1;
			}
			if (left!=-1&&right!=-1) ans+=right-left+1;
		}
		printf("%lld\n",ans);	
	}
	return 0;
 } 

Problem D. Another Problem About Dividing Numbers

本题有\(t\)组数据。

给出\(a,b,k\),每次可以任取一个数\(c\),将\(a\)\(b\)中的一个数变成\(a/c\)或者\(b/c\),需满足\(c\)可被对应的数整除。

\(k\)次操作之内能否让\(a=b\),若能输出\(YES\)否则输出\(NO\).

对于\(100\%\)的数据\(1 \leq a,b,k \leq 10^9 , 1 \leq t \leq 10^4\)

\(k\)应当是连续的一个区间,一般情况下\(k\geq 1\)

考虑\(k\)最大的边界情况,最终\(a=b=1\),并且每一次除以相对应的质因子。

\(f(x)\)为数\(x\)所有质因子指数和。则\(1 \leq k \leq f(a)+f(b)\)

# include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int h(int x)
{
	int cnt=0;
	for (int i=2;i*i<=x;i++)
		if (x%i==0) while (x%i==0) x/=i,cnt++;
	if (x>1) cnt++;
	return cnt;
}
int main() {
	int T; scanf("%d",&T);
	while (T--) {
		int a,b,k; scanf("%d%d%d",&a,&b,&k);
		if((a%b!=0&&b%a!=0&&k==1)||(a==b&&k==1)) {
			puts("NO");
			continue;
		}
		if (k<=h(a)+h(b)) puts("YES"); else puts("NO");
	}
	return 0;
}

Problem E. Funny Substrings

本题有\(t\)组数据。

给出\(n\)条语句,是下列两个指令之一:

  • a := b (表示将字符串\(b\)所表示的文本赋值到变量\(a\)中)
  • a = b + c (表示将字符串变量\(b\)\(c\)前后串联赋值到变量\(a\)中)

询问最后一个操作的字符串变量有多少个子串"haha"。

对于\(100\%\)的数据\(1 \leq t \leq 10^3 , 1 \leq n \leq 50\)

两个字符串只有前\(3\)个字符和后\(3\)个字符对答案有贡献,所以直接忽略掉中间部分。

若字符串长度小于\(3\)直接暴力计算。

将两个字符串变量\(a,b\)合并,新变量中的答案为\(a\)的答案+\(b\)的答案+中间\(6\)个字符的答案。

直接模拟即可。

复杂度\(O(tn)\)

# include <bits/stdc++.h>
# define int long long
# define end iuaod
using namespace std;
const int N=51;
const string HH="haha";
int tot;
map<string,int>mp; 
char aa[N][6],pre[N][3],end[N][3];
bool bo[N];
int ans[N],len[N];
void init() {
	tot=0; mp.clear();
	memset(aa,‘\0‘,sizeof(aa));
	memset(pre,‘\0‘,sizeof(pre));
	memset(end,‘\0‘,sizeof(end));
	memset(bo,false,sizeof(bo));
	memset(ans,0,sizeof(ans));
	memset(len,0,sizeof(len));
}
signed main(){
	int T; scanf("%lld",&T);
	while (T--) {
		init();
		int lastid;
		int n; scanf("%lld",&n);
		while (n--) {
			char s[6]; scanf("%s",s);
			string tmp="";
			int tt=strlen(s);
			for (int i=0;i<tt;i++) tmp=tmp+s[i];
			int id;
			if (mp.count(tmp)==0) {
				id=++tot; mp[tmp]=id; bo[id]=false;
			} else id=mp[tmp];
			scanf("%s",s);
			lastid=id;
			if (s[0]==‘:‘) {
				scanf("%s",s); 
				len[id]=strlen(s);
				bo[id]=(len[id]>=3);
				if (!bo[id]) {
					ans[id]=0;
					for (int i=0;i<len[id];i++) 
						aa[id][i]=s[i];
				} else {			
					for (int i=0;i<3;i++) pre[id][i]=s[i];
					for (int i=len[id]-1,t=2;i>=len[id]-3;i--,t--) {
						end[id][t]=s[i];
					}
					ans[id]=0;
					for (int i=0;i<=len[id]-4;i++) {
						bool flag=true;
						for (int j=0;j<4;j++) 
							if (HH[j]!=s[i+j]) {flag=false; break;}
						if (flag) ans[id]++;
					}
				}
			} else {
				char a[6],b[6]; scanf("%s%s%s",a,s,b);
				tmp=""; int right=strlen(a);
				for (int i=0;i<right;i++) tmp=tmp+a[i];
				int id1=mp[tmp];
				tmp=""; right=strlen(b);
				for (int i=0;i<right;i++) tmp=tmp+b[i];
				int id2=mp[tmp]; 
				if ((!bo[id1])&&(!bo[id2])) {
					char c[6]; int p=0;
					for (int i=0;i<len[id1];i++) 
						c[p++]=aa[id1][i];
					for (int i=0;i<len[id2];i++)
						c[p++]=aa[id2][i];
					ans[id]=0;
					for (int i=0;i<=p-4;i++) {
						bool flag=true;
						for (int j=0;j<4;j++) 
							if (HH[j]!=c[i+j]) {flag=false; break;}
						if (flag) ans[id]++;
					}
					for (int i=0;i<p;i++)
						aa[id][i]=c[i];	
					if (p>=3) {
						bo[id]=true;
						for (int i=0;i<3;i++) pre[id][i]=aa[id][i];
						for (int i=p-1,t=2;i>=p-3;i--,t--) {
							end[id][t]=aa[id][i];
						}
					}
				} else if ((!bo[id1])&&bo[id2]) {
					char c[6]; int p=0;
					for (int i=0;i<len[id1];i++) 
						c[p++]=aa[id1][i];
					for (int i=0;i<3;i++)
						c[p++]=pre[id2][i];				
					bo[id]=true;
					for (int i=0;i<3;i++) pre[id][i]=c[i];
					for (int i=0;i<3;i++) end[id][i]=end[id2][i];
					ans[id]=ans[id1]+ans[id2];
					for (int i=0;i<=p-4;i++) {
						bool flag=true;
						for (int j=0;j<4;j++) 
							if (HH[j]!=c[i+j]) {flag=false; break;}
						if (flag) ans[id]++;
					}
				} else if ((!bo[id2])&&bo[id1]) {
					char c[6]; int p=0;
					for (int i=0;i<3;i++) 
						c[p++]=end[id1][i];
					for (int i=0;i<len[id2];i++)
						c[p++]=aa[id2][i];
					bo[id]=true;
					for (int i=0;i<3;i++) pre[id][i]=pre[id1][i];
					for (int i=0,t=p-3;i<3;i++,t++) 
						end[id][i]=c[t];
					ans[id]=ans[id1]+ans[id2];
					for (int i=0;i<=p-4;i++) {
						bool flag=true;
						for (int j=0;j<4;j++) 
							if (HH[j]!=c[i+j]) {flag=false; break;}
						if (flag) ans[id]++;
					}
				} else {
					char c[6]; int p=0;
					for (int i=0;i<3;i++) 
						c[p++]=end[id1][i];
					for (int i=0;i<3;i++)
						c[p++]=pre[id2][i];	
					bo[id]=true;
					for (int i=0;i<3;i++) pre[id][i]=pre[id1][i];
					for (int i=0;i<3;i++) end[id][i]=end[id2][i];
					ans[id]=ans[id1]+ans[id2];
					for (int i=0;i<=p-4;i++) {
						bool flag=true;
						for (int j=0;j<4;j++) 
							if (HH[j]!=c[i+j]) {flag=false; break;}
						if (flag) ans[id]++;
					}
				}
			}
		}
		printf("%lld\n",ans[lastid]);	
	}
	return 0;
}
 

Problem F. Interesting Function

本题有\(t\)组数据

给出\(l,r\)求出\(i= l \ to \ r\)过程中变化的数位个数之和。

对于\(100\%\)的数据,\(1\leq t \leq 10^4,1\leq l\leq r\leq 10^9\)

\(f(x)\)\(i=0 \ to \ x\)过程中变化的位数个数之和。

观察到普通变化时是变化\(1\)位,而逢\(9\)增加\(1\)位。

  • 所以逢\(9\)新增的\(1\)位有\(x/10\)个。

  • \(99\)新增的\(1\)位有\(x/100\)个。

    ...

    以此类推。

所以本题的答案为\(f(x)=x+x/10+x/100+...\)

\(ans(l,r)=f(r)-f(l)\)

复杂度\(O(tlg n)\)

# include <bits/stdc++.h>
using namespace std;
int f(int n) {
	int ans=0;
	while (n) {
		ans+=n;
		n/=10;
	}
	return ans;
}
int main()
{
	int t; scanf("%d",&t);
	while (t--) {
		int l,r; scanf("%d%d",&l,&r);
		printf("%d\n",f(r)-f(l));
	}
	return 0;
}

Problem G. Gift Set

本题有\(t\)组数据

现在共有\(x\)\(1\)物品,\(y\)\(2\)物品,做一个产品需要\(a\)\(1\)物品和\(b\)\(2\)物品或者\(b\)\(1\)物品和\(a\)\(2\)物品

问最多能做多少个物品。

对于\(100\%\)的数据,\(1\leq t \leq 10^4,1\leq x,y,a,b\leq 10^9\)

直接二分答案\(m\)。设使用方案\(a\)\(1\)物品和\(b\)\(2\)物品\(w\)套,则使用方案\(b\)\(1\)物品和\(a\)\(2\)物品\(m-w\)

其中\(0 \leq w \leq m , m\in N\)

需要满足两个不等式:

  • \(wa+(m-w)b\leq x\)
  • \(wb+(m-w)a\leq y\)

只需要解不等式判断\(w\)的有解性即可。

复杂度\(O(tlog_2max)\)

# include <bits/stdc++.h>
# define int long long
using namespace std;
int max(int a,int b,int c,int d) {
	int t=0;
	if (a>t) t=a;
	if (b>t) t=b;
	if (c>t) t=c;
	if (d>t) t=d;
	return t;
}
int a,b,x,y;
bool check(int m) {
	if (a==b) return (x>=b*m)&&(y>=a*m);
	if (a<b) {
		if (y-a*m<0) return 0;
		int l,r=(y-a*m)/(b-a);
		if (x-b*m>0) l=0;
		else if ((b*m-x)%(b-a)==0) l=(b*m-x)/(b-a);
		else l=(b*m-x)/(b-a)+1;
		r=min(r,m);
		return l<=r;
	}
	if (a>b) {
		if (x-b*m<0) return 0;
		int l,r=(x-b*m)/(a-b);
		if (y-a*m>0) l=0;
		else if ((a*m-y)%(a-b)==0) l=(a*m-y)/(a-b);
		else l=(a*m-y)/(a-b)+1;
		r=min(r,m);
		return (l<=r);
	}
}
signed main()
{
	int T; scanf("%lld",&T);
	while (T--) {
		scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
		int l=0,r=1e9,ans;
		while (l<=r) {
			int m=(l+r)/2;
			if (check(m)) ans=m,l=m+1;
			else r=m-1;
		}
		printf("%lld\n",ans);	
	}
	return 0;
}

Codeforces Round #725 (Div. 3) 题解

上一篇:CMD快捷键


下一篇:Mvc自定义验证