@
CF1872B The Corridor or There and Back Again
Description
有若干个房间排成一行，其中有 \(n\) 个房间有陷阱，对于这 \(n\) 个房间，它们有两个属性：\(d_i\) 和 \(s_i\)，分别代表标号和陷阱形成的时间，即若你第 \(t\) 秒第一次到达 \(i\) 号房间，\(t+s_i\) 秒时陷阱就会在此房间形成，此后你无法通过此房间。每秒你可以走到与当前房间标号相邻的房间。
你需要从1号房间走到 \(k\) 号房间，并且再从 \(k\) 号房间走回1号房间。求 \(k\) 最大是多少。
Solution
对于一个有陷阱的 \(i\) 号房间，我们最远可以走到 \(limit_i=d_i+\lfloor(s_i)\div2\rfloor\) 号房间（减一是因为 \(d_i+s_i\) 时是不能走的，要提前一秒）。
如果 \(d_{i+1}>limit_i\)，那就无法走到第 \(d_{i+1}\) 号房间，最多只能走到 \(limit_i\) 号房间。
遍历 \(n\) 个有陷阱的房间，将 \(d_i\) 与 \(limit_1,limit_2\dots limit_{i-1}\) 比较一下就行了，对于没有陷阱的房间，它要么包含在 \(limit_j\) 中，要么就走不到，所以不用考虑。
Code
#include<bits/stdc++.h>
using namespace std;
int t;
struct node{
int d,s;
}a[110];
int limit[110];
bool cmp(node x,node y){
if(x.d==y.d) return x.s<y.s;
return x.d<y.d;
}
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].d>>a[i].s;
}
sort(a+1,a+1+n,cmp); //需要先排序
limit[1]=a[1].d+(a[1].s-1)/2;
int now=limit[1];
for(int i=2;i<=n;i++){
bool f=0;
for(int j=1;j<i;j++){
if(a[i].d>limit[j]) {
f=1;break;
}
}
if(f) break;
limit[i]=a[i].d+(a[i].s-1)/2;
now=min(now,limit[i]); //可能之前的limit比当前还大，需要取最小值保证正确性
}
cout<<now<<endl;
}
int main(){
cin>>t;
while(t--){
solve();
}
return 0;
}
CF1872C Non-coprime Split
Description
给定两个数 \(l,r\)，你需要找到一对正整数 \(a,b\)，使得 \(l\leq a+b\leq r\) 且 \(\gcd(a,b)\neq1\)。
Solution
若 \(r\leq3\)，无论怎么取都无法满足条件，输出 -1即可。
否则我们在 \(l\sim r\) 中找到一个合数 \(x\)，对其质因数分解。若 \(y\) 是它的一个质因子，输出 \((x\div y-1)\times y\) 和 \(y\) 即可。
Code
#include<bits/stdc++.h>
using namespace std;
int t;
void count(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0){
cout<<i<<" "<<x-i<<endl;
return ;
}
}
cout<<-1<<endl;
}
void solve(){
int l,r;
cin>>l>>r;
if(l==r){
count(l);
}else if(r<=3) cout<<-1<<endl;
else{
for(int i=r;i>=l;i--){
if(i%2==0) { //偶数是合数中最多的一类数，可以降低复杂度
count(i);//从r往l遍历，是因为r肯定大于3，而l可能小于3，大于3的偶数一定为合数
return;
}
}
}
}
int main(){
cin>>t;
while(t--){
solve();
}
return 0;
}
CF1872D Plus Minus Permutation
Description
每次询问给定3个数 \(n,x,y\)，\(p_1,p_2\dots p_n\) 为一个 \(n\) 的排列，求 \(\sum\limits_{i=1,x\mid i}^n p_i-\sum\limits_{j=1,y\mid j}^n p_j\) 的最大值。
Solution
我们发现，有一部分 \(p_i\) ，\(i\) 即能被 \(x\) 整除，又能被 \(y\) 整除，所以需要加一遍 \(p_i\)，又减一遍，相当于没有贡献。
设 \(a_1,a_2\dots a_{\lfloor\frac{n}{x}\rfloor-\lfloor\frac{n}{\operatorname{lcm}(x,y)}\rfloor}\) 为 \(n\) 以内，只被 \(x\) 整除，不被 \(y\) 整除的数，\(b_1,b_2\dots b_{\lfloor\frac{n}{y}\rfloor-\lfloor\frac{n}{\operatorname{lcm}(x,y)}\rfloor}\) 为 \(n\) 以内，只被 \(y\) 整除，不被 \(x\) 整除的数。
为了使总贡献最大，需要最大化 \(p_{a_1}+p_{a_2}+\dots+p_{a_{\lfloor\frac{n}{x}\rfloor-\lfloor\frac{n}{\operatorname{lcm}(x,y)}\rfloor}}\)，那么我们让这些数取 \(n\sim n-(\lfloor\frac{n}{x}\rfloor-\lfloor\frac{n}{\operatorname{lcm}(x,y)}\rfloor)+1\)，同时还需要最小化 \(p_{b_1}+p_{b_2}+\dots+p_{b_{\lfloor\frac{n}{y}\rfloor-\lfloor\frac{n}{\operatorname{lcm}(x,y)}\rfloor}}\)，那我们让这些数取 \(1\sim \lfloor\frac{n}{y}\rfloor-\lfloor\frac{n}{\operatorname{lcm}(x,y)}\rfloor\) 就好了。
最后算出数值即可。
Code
#include<bits/stdc++.h>
using namespace std;
int t;
long long get(long long x){
return (x+1)*x/2;
}
int gcd(int x,int y){
if(x==0) return y;
if(x>y) swap(x,y);
return gcd(y%x,x);
}
void solve(){
long long n,x,y;
cin>>n>>x>>y;
long long cnt1=n/x,cnt2=n/y,cnt3=n/(x*y/gcd(x,y)); //lcm(x,y)=x*y/gcd(x,y)，不会的需自行了解一下
cnt1-=cnt3,cnt2-=cnt3;
long long sum1=get(n)-get(n-cnt1),sum2=get(cnt2);
cout<<sum1-sum2<<endl;
}
int main(){
cin>>t;
while(t--){
solve();
}
return 0;
}