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;
}