Educational Codeforces Round 36 (Rated for Div. 2)
题目的质量很不错（不看题解做不出来，笑
Codeforces 920C
题意
给定一个\(1\)到\(n\)组成的数组，只可以交换某些相邻的位置，问是否可以将数组调整为升序的
解题思路
首先如果每个数都能通过交换到它应该到的位置，那么就可以调整为升序的。
但实际上交换是对称的，如果应该在的位置在当前位置前方的数都交换完成，那么整体就是排好序的，因为不可能所有不在相应位置的数都在相应位置的后方。
所以我们从\(1\)到\(n\)扫一遍，在扫描的过程中维护当前位置能向前交换的位置的最小值，这样就可以判断了
AC代码
#include <bits/stdc++.h>
using namespace std;
int n,pos[300020],num[300020];
string str;
bool judge()
{
int maxpre=1;
for (int i=1;i<=n;i++)
{
if(i>=2)
if(str[i-2]=='0') maxpre=i;
if(pos[i]>=i) continue;
if(maxpre>pos[i]) return false;
}
return true;
}
int main(int argc, char const *argv[])
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
pos[num[i]]=i;
}
cin>>str;
if(judge())
puts("YES");
else
puts("NO");
return 0;
}Codeforces 920E
题意
给定一个无向图，求补图的连通分量数和每个连通分量的大小
点数\(n \le 200000\) ，边数\(m \le 200000\)
（原题？：bzoj1098）
解题思路
虽然直接对补图用\(BFS\)求连通分量数复杂度是\(O(n)\)的，但光建图复杂度就要\(O(n^2)\)了，所以直接建补图肯定是不行的
这里用到一个神奇的方法，在对原图\(BFS\)最开始维护一个所有未分配在连通分量中的点的集合，当前点不能到达的点就是补图能到达的点，将补图能到达的点加入队列继续\(BFS\)，对于已经判断在某个连通分量的点，需要在集合中删去。
这个集合可以直接使用std::set<int>，也可以使用链表，在这里我使用链表
这样只需要建原图就可以对补图进行\(BFS\)了，复杂度\(O(n+m)\)
AC代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=200010;
vector <int> G[maxn];
int scc[maxn],scccnt;
int pre[maxn],nxt[maxn],vis[maxn],deled[maxn];
int n,m;
void del(int u)
{
nxt[pre[u]]=nxt[u];
pre[nxt[u]]=pre[u];
}
void bfs(int s)
{
queue<int> Q;
Q.push(s);
del(s);
while(!Q.empty())
{
int u=Q.front();Q.pop();
if(vis[u]) continue;
vis[u]=true;
scc[scccnt]++;
for (int v:G[u])
deled[v]=true;
for (int i=nxt[0];i<=n;i=nxt[i])
if(!deled[i])
{
del(i);Q.push(i);
}
for (int v:G[u])
deled[v]=false;
}
scccnt++;
}
int main(int argc, char const *argv[])
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n+1;i++) pre[i]=i-1;
for (int i=0;i<=n;i++) nxt[i]=i+1;
for (int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
for (int i=nxt[0];i<=n;i=nxt[i])
if(!vis[i])
bfs(i);
sort(scc,scc+scccnt);
printf("%d\n",scccnt);
for (int i=0;i<scccnt;i++)
printf("%d ",scc[i]);
puts("");
return 0;
}Codeforces 920F
题意
定义\(D(x)= Card\{k:k| x,k \in N^+\}\)
给定数组\(a\)，做如下操作：
replace l r：将\(a_l\)到\(a_r\)替换为\(D(a_i)\)
sum l r：输出\(a_l\)到\(a_r\)的和
点数\(n \le 300000\)，操作数\(m \le 300000\) ，\(a_i \le 1000000\)
解题思路
\(D(x)\)可以直接用筛法求出，复杂度\(O(MAXN \log MAXN)\)
首先显然要用线段树进行维护，但是直接套线段树对区间的每个点都单点更新显然是过不了的
注意到对\(D(x)\)迭代收敛很快，根据官方题解，在数据范围内迭代不超过\(6\)次就可以收敛到\(2\)或\(1\)
我们可以用\(2\)棵线段树，一棵维护和，一棵维护最大值，当区间更新时对整个区间进行递归地更新，如果当前子树的最大值$ \le 2$， 那么可以直接返回，这样对于每个点最多不更新超过\(6\)次
复杂度\(O(m \log n+MAN \log MAXN)\)
我看其他的题解说是套路题……难受
AC代码
#include <bits/stdc++.h>
using namespace std;
const int maxnum=1e6+6;
const int maxn=3e5+7;
int D[maxnum],a[maxn];
int n,m;
long long sumv[(maxn<<2)+5];
int maxv[(maxn<<2)+5];
void build(int now,int l,int r)
{
if(l==r)
{
maxv[now]=sumv[now]=a[l];
return;
}
int mid=l+((r-l)>>1);
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
sumv[now]=sumv[now<<1]+sumv[now<<1|1];
maxv[now]=max(maxv[now<<1],maxv[now<<1|1]);
}
void update(int now,int l,int r,int ul,int ur)
{
if(maxv[now]<=2) return; //关键
if(l==r)
{
maxv[now]=sumv[now]=D[sumv[now]];
return;
}
int mid=l+((r-l)>>1);
if(ul<=mid) update(now<<1,l,mid,ul,ur);
if(ur>mid) update(now<<1|1,mid+1,r,ul,ur);
sumv[now]=sumv[now<<1]+sumv[now<<1|1];
maxv[now]=max(maxv[now<<1],maxv[now<<1|1]);
}
long long query_sum(int now,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr) return sumv[now];
int mid=l+((r-l)>>1);
long long ans=0;
if(ql<=mid) ans+=query_sum(now<<1,l,mid,ql,qr);
if(qr>mid) ans+=query_sum(now<<1|1,mid+1,r,ql,qr);
return ans;
}
void pre_solve()
{
for (int i=1;i<=1e6;i++)
{
for (int j=i;j<=1e6;j+=i)
D[j]++;
}
}
int main(int argc, char const *argv[])
{
pre_solve();
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
while(m--)
{
int t,l,r;scanf("%d%d%d",&t,&l,&r);
if(t==1)
update(1,1,n,l,r);
else
printf("%I64d\n",query_sum(1,1,n,l,r));
}
return 0;
}Codeforces 920G
题意
定义\(L(x,p)\)为数列\(\{ y > x, gcd(y,p)=1\}\)
输入\(x,p,k\)，求数列\(L(x,p)\)的第\(k\)项
输入数目\(t \le 30000\)，\(x,p,k \le 1000000\)
解题思路
我们记\(A(x,p)= Card\ L(x,p)\)，可以考虑求\(L\)的补集，用枚举\(p,y\)的\(gcd\)含有的素因子利用容斥原理求解，由于 \(2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17=510510\)，所以数据范围内的数素因子个数不超过\(7\)个，子集不超过\(2^7\)个
那么答案求的就是\(A(ans,p)=A(x,p)+k\)，转化后我们可以利用二分法求解答案\(ans\)
复杂度\(O(t \log MAXANS)\)
经试验，答案的上界不超过\(1e10\)
AC代码
#include <bits/stdc++.h>
using namespace std;
vector <long long> factor;
long long solve(long long x)
{
int num=factor.size();
long long ans=0;
for (int i=0;i<(1<<num);i++)
{
long long flag=1,gcdf=1;
for (int j=0;j<num;j++)
{
if((i>>j)&1)
{
gcdf*=factor[j];
flag*=-1;
}
}
ans+=flag*(x/gcdf);
}
return ans;
}
long long p,x,k;
int main(int argc, char const *argv[])
{
int t;
scanf("%d",&t);
while(t--)
{
factor.clear();
scanf("%I64d%I64d%I64d",&x,&p,&k);
for (int i=2;i*i<=p;i++)
{
if(p%i) continue;
else
factor.push_back(i);
while(p%i==0) p/=i;
}
if(p>1) factor.push_back(p);
k+=solve(x);
long long l=1,r=1e10,mid,ans;
while(l<=r)
{
mid=(l+r)>>1;
if(solve(mid)>=k)
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%I64d\n",ans);
}
return 0;
}