最近急速補練藍橋杯中，疏于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;
}