CF每日5题（1300-1500）

最近急速补练蓝桥杯中，疏于cf练习。
感觉自己过题还是太慢了。
今日水题，我水水水水。

1- 1979C lcm 水 1400

• 第$i$局赢了，1个硬币顶$k[i]$个贡献，所以每局分硬币$x_i=\frac{1}{k[i]}$个，最后能赢一个硬币。整个游戏下来，如果能赢回来必须$\sum \frac{1}{k[i]}<1$
• 将$\frac{1}{k[i]}$变成整数就是答案，变成整数要$\times lcm(k)$，因为如果直接累乘$k$的话会是$50^{20}$超范围。

#define int long long
int lcm(int x,int y){return x*y/(__gcd(x,y));
}
void solve(){int n;cin>>n;vector<int>k(n+1);int mul=1;forr(i,1,n){cin>>k[i];mul=lcm(mul,k[i]);}int sum=0;forr(i,1,n){sum+=(mul/k[i]);}if(sum>=mul)return cout<<-1<<endl,void();else {forr(i,1,n){cout<<mul/k[i]<<' ';}cout<<endl;}}

2- 2077A 找规律 构造？1500

思路来源
凑数 构造

• $b$有$2n$个数，$a$比$b$多一个
• 对$n=2$，$a$数组$-a_1+a_2-a_3+a_4-a_5=0$
• $a$数组两两不同，多构造的那个数不能和其他相同

从第一条可以有：
$a_1=a_2-a_3+a_4-a_5$
$a_2=a_3+a_4+a_5-a_1$
排序角度想 如果$a_1<a_3<a_4<a_5$，那么$a_2=a_5+a_3+a_4-a_1>a_5$，$a_2>a_5$，$a_2$肯定和$a_5$不同。
做法就是把$b$排序后，后$n-1$个数和前$n-1$个数做差，再加中间俩剩下的数，得到一个$a_{2k}$位置的数。
其他的数，被减数做奇数位，减数做偶数位，

void solve(){int n;cin>>n;vector<int>b(2*n),a(2*n+2);forr(i,0,2*n-1){cin>>b[i];}sort(b.begin(),b.end());int idx=1,sum=0;//idx走的是奇数位置forr(i,0,n-2){sum+=(b[2*n-1-i]-b[i]);a[idx]=b[2*n-1-i];a[idx+1]=b[i];idx+=2;}sum+=(b[n-1]+b[n]);a[idx]=b[n-1];a[idx+1]=sum;a[idx+2]=b[n];forr(i,1,2*n+1)cout<<a[i]<<' ';cout<<endl;
}

3- 2075C 思维 二分

思路来源

• 枚举需要涂的数目，排序后二分查找能满足该数目的颜色种数$x,y$
• 组合两拨颜色，种数$x\times y$
• $x、y$两拨颜色中有包含关系，需要减去相同颜色组合的情况，数目是$min(x,y)$

void solve(){int n,m;cin>>n>>m;vector<int>a(m);forr(i,1,m)cin>>a[i-1];sort(a.begin(),a.end());int ans=0;forr(i,1,n-1){int x=lower_bound(a.begin(),a.end(),i)-a.begin();int y=lower_bound(a.begin(),a.end(),n-i)-a.begin();x=m-x,y=m-y;ans+=(x*y-min(x,y));}cout<<ans<<endl;
}

4- 2075B 贪心 思维 1300

思路来源
目的让结果最大

• 取前k个数时取最大的前k个数
• 最后一个数的问题：
  • 如果$k>1$，已经涂蓝色的可以向中间和两边拓展，跳过剩下的数中最大的最后涂蓝色。最后的答案相当于所有$k+1$大的数的和

  我们设这个没取到的为 i，显然它夹在第一轮取得的数的中间。设它夹在位置 x 和 y 间，显然我们可以通过染色挨个挨个从 x 向右染到位置 i−1，不染 i，接着从 y 向左染到位置 i+1，然后考虑这个连续子序列外的红色，显然可以都染成蓝色，最后在把位置 i 染成蓝色并计入它的贡献。

  • 如果$k=1$，不能从两边推进蓝色，不好控制最后一个数选最大的。退而求其次，
    • 一个蓝色往两边拓展，最后一定选数组两端的数，选个较大的。
    • 选的蓝色在边上，最后一个数一定在另一头。
    • 两种情况取最大。

void solve(){int n,k;cin>>n>>k;vector<int>a(n);forr(i,1,n)cin>>a[i-1];int sum=0;if(k==1){int maxn=0;forr(i,1,n-2)maxn=max(maxn,a[i]);sum+=max(maxn+max(a[0],a[n-1]),a[0]+a[n-1]);//两个策略：中间+两边任一  两边}else{sort(a.begin(),a.end());forr(i,1,k+1)sum+=a[n-i];}cout<<sum<<endl;
}

5- 2091E 数论 1300

题目要求$(a,b)$满足$\frac{lcm(a,b)}{gcd(a,b)}=prime$

• 根据算术基本定理
  • $lcm(a,b)=\Pi p_i^{max(a_i,b_i)}$
  • $gcd(a,b)=\Pi p_i^{min(a_i,b_i)}$
• 两个比值想要为质数，只能有一个i，$max(a_i,b_i)-min(a_i,b_i)\ne 0$
• $a<b$那么$\frac{lcm(a,b)}{gcd(a,b)}=\frac{b}{a}=prime$
• 找出质数，枚举a即可

const int N=1e7+10;
// map<int,int>vis; 用map会MLE
bitset<N>vis;
vector<int>p;
void find_p(){vis[0]=vis[1]=1;forr(i,2,N){if(vis[i]==0)p.push_back(i);for(auto j:p){if(j*i>N)break;vis[j*i]=1;if(i%j==0)break;}}
}
void solve(){int n;cin>>n;int ans=0,idx=0;while (idx<p.size()&&p[idx]<n)idx++;idx=min(idx,(int)(p.size()-1));//这里的i遍历a a×最小的p（就是2） 保持<=nforr(i,1,n/2){//随着i增大 i*p<n 的p个数在减小 所以idx不断减小while (p[idx]*i>n)idx--;ans+=(idx+1);}cout<<ans<<endl;
}
signed main()
{ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);int _ ;_ = 1;find_p();cin>>_;while (_--){solve();}return 0;
}