CF1872(div3)题解
CF1872
D. Plus Minus Permutation(思维)
题意：
给定三个整数n,x,y,定义一个permutation的价值是:
$(p_{1 \cdot x}+p_{2 \cdot x}+…+p_{i \cdot x})-(p_{1 \cdot y}+…+p_{j \cdot y}) $ ,其中 $i \cdot x<=n$, $j \cdot y<=n$
求permutation最大价值
思路：
分别求i，j的值，再求出lcm(x,y)对应的k值，表示二者共同走过的格子，这不会产生价值，所以i-=k，j-=k，后i个数的和减去前j个数的和即为答案
注意：
用等差数列求和公式，否则会爆TLE
复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve(){
ll n,x,y;
cin>>n>>x>>y;
ll cnt1=n/x,cnt2=n/y;
ll c=x*y/__gcd(x,y);
ll cnt3=n/c;
cnt1-=cnt3,cnt2-=cnt3;
ll sum=0;
ll bg=n,eg=n-cnt1+1;
sum+=cnt1*(eg+bg)/2;
bg=1,eg=cnt2;
sum-=cnt2*(bg+eg)/2;
cout<<sum<<"\n";
}
E. Data Structures Fan(前缀异或和)
题意：
给定一个数组a和一个string01串,有q次访问,每次访问：
“1 l r”,将[l,r]的0反转，0变1，1变0 “2 g”,g=0:求所有s[i]=’0’的对应的a[i]的异或和;反之亦然
思路：
容易联想到前缀异或和，先将0和1分别的异或和求出来，每次询问l,r时，两个答案异或上区间异或和，原来为0的数会在ans0中被抵消掉，为1的加进来，从而可以维护当前值，每次操作O(1)
复杂度：O(n+q)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void solve(){
int n;
cin>>n;
vector<ll> a(n+1),sum(n+1);
ll ans0=0,ans1=0;
for(int i=1;i<=n;i++)cin>>a[i];
string s;
cin>>s;
s=" "+s;
for(int i=1;i<=n;i++){
if(s[i]=='0'){
ans0^=a[i];
}
else ans1^=a[i];
sum[i]=sum[i-1]^a[i];
}
int q;
cin>>q;
while(q--){
int op;
cin>>op;
if(op==1){
int l,r;
cin>>l>>r;
ans0^=(sum[r]^sum[l-1]);
ans1^=(sum[r]^sum[l-1]);
}
else{
int x;
cin>>x;
if(x==0)cout<<ans0<<" ";
else cout<<ans1<<" ";
}
}
cout<<"\n";
}
F. Selling a Menagerie(dfs+集合+dfs内置写法)
题意：
c[i]表示i的价值，当i在a[i]前面出现时，i的贡献价值为2*c[i]，否则为c[i],求一个顺序使总价值最大，所有a[i],i<=n
思路：
i向a[i]连边,先做个拓扑序,剩下还有数说明有环，在环内找出最小的c[i],当前i在该环排最后即可(题目中集合可分为三种：1.单个环，2.单条边，3.一个环和若干条指向它的边（环指向边不可能存在）)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void solve(){
int n;
cin>>n;
vector<int> a(n+1),c(n+1),deg(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
deg[a[i]]++;
}
for(int i=1;i<=n;i++)cin>>c[i];
vector<int> ans;
vector<bool> vis(n+1);
auto dfs=[&](auto self,int u)->void{
if(--deg[a[u]]==0&&!vis[a[u]]){
vis[a[u]]=1;
ans.pb(a[u]);
self(self,a[u]);
}
};
for(int i=1;i<=n;i++){
if(vis[i])continue;
if(deg[i]==0){
vis[i]=1;
ans.pb(i);
dfs(dfs,i);
}
}
for(int i=1;i<=n;i++){
if(vis[i])continue;
vector<int> b,C;
for(int j=i;!vis[j];j=a[j]){
b.pb(j);
C.pb(c[j]);
vis[j]=1;
}
int p=min_element(all(C))-C.begin();
for(int j=0;j<b.size();j++){
ans.pb(b[(j+1+p)%b.size()]);
}
}
for(auto it:ans)cout<<it<<" ";
cout<<"\n";
}
G. Replace With Product(剪枝+前缀和)
题意：
对数组a做一次操作：
选择l,r,[l,r]的数相乘变成一个数，然后求和使和最大，求此时l,r
思路：
1相乘任何数不变，只有相加才能增加贡献，所以前缀1和后缀1可以先排除掉，此时范围从[1,n]缩小到[l,r]
如果直接对范围内的数用前缀求解，相乘时会爆long long，枚举l,r复杂度为 $N^2$ 承受不住
容易得知，当相乘大于某个值，即使是最小的数2，相乘的贡献都要大于相加，可以把这个值设为1e9(大约INT_MAX)，当大于1e9时直接输出l,r
小于1e9时，直接算复杂度也不一定过得去，因此先把[l,r]中大于1的值对应的坐标取出来，再用类似前缀和的知识计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void solve(){
int n;
cin>>n;
vector<int> a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
int l=1,r=n;
while(l<r&&a[l]==1)l++;
while(l<r&&a[r]==1)r--;
vector<ll> sum(n+1),mul(n+1,1);
for(int i=l;i<=r;i++){
mul[i]=mul[i-1]*a[i];
sum[i]=sum[i-1]+a[i];
if(mul[i]>1e9){
cout<<l<<" "<<r<<'\n';
return;
}
}
ll ans=-INF,lpos=l,rpos=r;
vector<int> b;
for(int i=1;i<=n;i++){
if(a[i]>1)b.pb(i);
}
for(int i=0;i<b.size();i++){
for(int j=i;j<b.size();j++){
ll tmp=sum[b[i]-1]+sum[r]-sum[b[j]]+mul[b[j]]/mul[b[i]-1];
if(tmp>ans){
ans=tmp;
lpos=b[i];
rpos=b[j];
}
}
}
cout<<lpos<<" "<<rpos<<"\n";
}