codeforces gym 102114 水题题解
shadowice1984
2019-03-16 22:06:27
~~毒瘤鎕的多校题，淦爆了~~
无论怎么说这也是一套acm题，因此还是有水题的，再加上我最近鸽子本质暴露无心写详细的题解，所以写几句一句话题解水一水博客好了
话说这场的每一道题都是一首歌的名字还挺好听的
## A Always Online
仔细读读题发现是仙人掌上最大流，自然是要求仙人掌上最小鸽了
那么路径上的鸽边必须被鸽掉，而环边则同时需要鸽两条，容易发现环上的最小值一定会被鸽割掉，那么我们可以对每一个环鸽掉这个环的最小边，然后让环上剩余边的权值加上被鸽的边的权值，此时仙人掌就成了一颗树
而最小鸽就等于两个点间路径的最小值了
接下来的问题就很trivial了，排序之后从大到小枚举边权，跑个启发式合并统计每一条边对答案的贡献即可，剩下的部分是基础数据结构知识不在赘述了
```C
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;const int N=1e5+10;typedef unsigned long long ll;int n;int m;
struct data
{
int u;int v;ll val;
friend bool operator <(data a,data b){return a.val>b.val;}
}ed[N];int tp;ll ans;
namespace Grph
{
int v[N<<2];int x[N<<2];int ct=1;int al[N];ll val[N<<2];
bool mrk[N<<2];int q[N];int hd;int fa[N];bool book[N];int dep[N];
inline void add(int u,int V,ll va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;}
inline void subsolve()
{
int mi=0;ll miv=(1LL<<55);
for(int i=1;i<=hd;i++)if(val[q[i]]<miv)miv=val[q[i]],mi=i;
for(int i=1;i<=hd;i++)val[q[i]]+=miv,val[q[i]^1]+=miv;
mrk[q[mi]]=true;mrk[q[mi]^1]=true;
}
inline void dfs(int u)
{
book[u]=true;for(int i=al[u];i;i=x[i])if(i!=fa[u])
{
if(book[v[i]])
{
if(v[i]>u)continue;int p=u;int t=v[i];hd=0;
while(p!=t){if(dep[p]<dep[t])swap(p,t);q[++hd]=fa[p],p=v[fa[p]];}
q[++hd]=i;subsolve();continue;
}fa[v[i]]=i^1;dep[v[i]]=dep[u]+1;dfs(v[i]);
}
}inline void solve()
{
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<=m;i++)scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);dfs(1);
for(int i=2;i<=ct;i+=2)if(!mrk[i])ed[++tp]=(data){v[i],v[i+1],val[i]};
}
inline void clr()
{
for(int i=1;i<=n;i++)al[i]=0;for(int i=1;i<=n;i++)book[i]=false;
for(int i=1;i<=ct;i++)mrk[i]=false;ct=1;
}
}
struct bcj
{
int fa[N];vector <int> ve[N];int cnt[N][20][2];
inline void ih()
{
for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=n;i++)ve[i].clear(),ve[i].push_back(i);
for(int i=1;i<=n;i++)
{
for(int j=0;j<=17;j++)cnt[i][j][0]=cnt[i][j][1]=0;
for(int j=0;j<=17;j++)cnt[i][j][(i>>j)&1]++;
}
}inline int f(int x){return fa[x]=(fa[x]==x)?x:f(fa[x]);}
inline void u(int x,int y,ll we)
{
x=f(x);y=f(y);if(cnt[x][17][0]<cnt[y][17][0])swap(x,y);fa[y]=x;
ans+=(ll)cnt[x][17][0]*(we-(we&131071))*cnt[y][17][0];we&=131071;
for(vector <int>:: iterator it=ve[y].begin();it!=ve[y].end();++it)
{
ve[x].push_back(*it);int qv=we^(*it);
for(int i=0;i<=16;i++)ans+=(1LL<<i)*cnt[x][i][((qv>>i)&1)^1];
}for(int i=0;i<=17;i++)cnt[x][i][0]+=cnt[y][i][0],cnt[x][i][1]+=cnt[y][i][1];
}
}s;
inline void clear(){Grph::clr();tp=0;ans=0;}
inline void solve()
{
Grph::solve();sort(ed+1,ed+tp+1);s.ih();
for(int i=1;i<=tp;i++)s.u(ed[i].u,ed[i].v,ed[i].val);cout << ans << endl;
}int main(){int T;scanf("%d",&T);for(int z=1;z<=T;z++)solve(),clear();return 0;}
close
```
## B Beautiful Now
做人要有信仰，写代码不要管时间复杂度
枚举全排列然后check一下最少交换次数你就win了~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=12;typedef long long ll;
int pl[N];int mrk[N];int n;int k;int bt[N];int ans[N];int hd;
inline void solve()
{
scanf("%d%d",&n,&k);int mi=n;int mx=n;
hd=0;while(n)bt[++hd]=n%10,n/=10;reverse(bt+1,bt+hd+1);
for(int i=1;i<=hd;i++)pl[i]=i;
do
{
int cnt=0;
for(int i=1;i<=hd;i++)
if(!mrk[i]){cnt++;int p=i;do{mrk[p]=true,p=pl[p];}while(p!=i);}
for(int i=1;i<=hd;i++)mrk[i]=0;
if(hd-cnt>k)continue;
//printf("cnt=%d\n",cnt);
for(int i=1;i<=hd;i++)ans[pl[i]]=bt[i];
if(ans[1]==0)continue;int va=0;
for(int i=1;i<=hd;i++)va=va*10+ans[i];mi=min(mi,va);mx=max(mx,va);
}while(next_permutation(pl+1,pl+hd+1));printf("%d %d\n",mi,mx);
}
int main(){int T;scanf("%d",&T);for(int z=1;z<=T;z++)solve();return 0;}
```
# E Everything has changed
其实现在我也很喜欢这首歌的吉他，调子很干净
~~(哎，现在你霉转炸逼曲风了说多了都是泪)~~
哦，寄蒜几盒？扔了扔了
啊，圆不重叠？
那你发现这就是道思博题了,很显然我们要做的就是判断两个圆是否有交和交的弧度是多少然后该加加该减减
值得一提的是求弧度可以余弦定理之后acos求，这样写出来的代码会非常好写
```C
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;const int N=1e5+10;typedef long long ll;
typedef long double ld;const ld eps=1e-9;
const ld pi=acos(-1.0);int rd;int n;ld ans;
inline void ud(int x,int y,int r)
{
ll dis=(ll)x*x+(ll)y*y;ll dis1=(ll)(rd-r)*(rd-r);
if(dis==dis1){ans+=2*pi*r;return;}
ll dis2=(ll)(rd+r)*(rd+r);
if(dis<dis1)return;if(dis>dis2)return;
ans-=2*acos(((ld)rd*rd+dis-(ld)r*r)/(2*rd*sqrt(dis)))*rd;
ans+=2*acos(((ld)r*r+dis-(ld)rd*rd)/(2*r*sqrt(dis)))*r;
}
inline void solve()
{
scanf("%d",&n);scanf("%d",&rd);ans=2*pi*rd;
for(int i=1,x,y,r;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&r),ud(x,y,r);
}printf("%.10lf\n",(double)ans);
}
int main(){int T;scanf("%d",&T);for(int z=1;z<=T;z++)solve();return 0;}
```
# G Glad You Came
~~所以为啥the wanted 要解散呢?~~
标算使用st表将每一个修改拆成两个长度为2的整次幂的修改，然后递归的拆分每一个修改就做完了，复杂度是$O(m+nlogn)$的
但是我们喜欢暴力，对于区间取max操作，将所有操作按照关键字排序就变成了将没有被修改过的位置赋值的操作，如果仅仅要求输出最后的序列，我们有一个均摊$O(nlogn+m)$的算法可以完成这个过程，使用并查集维护每一段被链接起来的集合和集合的最小值即可
如果直接排序复杂度$O(mlogm)$太大难以接受怎么办呢？
当然是使用松式基排啦~使用256进制基数排序即可高效的完成排序
不过尽管如此我们还是tle……怎么办呢
发现数据是瞎random的，因此我们当所有元素都被赋好值之后就可以break了
然后你就过了~
复杂度$O(wys)/O(mlogm+nlogn)$
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;const int M=5*1e6+10;typedef unsigned int uit;
typedef unsigned long long ull;
namespace Mker
{
uit x;uit y;uit z;
inline uit ih(){scanf("%u%u%u",&x,&y,&z);}
inline uit rand()
{
x=x^(x<<11);x=x^(x>>4);x=x^(x<<5);x=x^(x>>14);
uit w=x^y^z;x=y;y=z;z=w;return z;
}
}int sum1[279];int sum2[279];int sum3[279];int sum4[279];
int l[M];int r[M];uit val[M];ull res1[M];ull res2[M];int n;int m;
inline void srt()
{
for(int i=0;i<256;i++)sum1[i]=0;for(int i=0;i<256;i++)sum2[i]=0;
for(int i=0;i<256;i++)sum3[i]=0;for(int i=0;i<256;i++)sum4[i]=0;sum1[0]=sum2[0]=sum3[0]=sum4[0]=1;
for(int i=1;i<=m;i++)
{uit vp=val[i];++sum1[vp&255];++sum2[(vp>>8)&255];++sum3[(vp>>16)&255];++sum4[(vp>>24)&255];}
for(int i=1;i<256;i++)sum1[i]+=sum1[i-1];for(int i=1;i<256;i++)sum2[i]+=sum2[i-1];
for(int i=1;i<256;i++)sum3[i]+=sum3[i-1];for(int i=1;i<256;i++)sum4[i]+=sum4[i-1];
for(int i=1;i<=m;i++)res1[i]=val[i]|((ull)i<<32);
for(int i=m;i>=1;i--)res2[--sum1[res1[i]&255]]=res1[i];
for(int i=m;i>=1;i--)res1[--sum2[(res2[i]>>8)&255]]=res2[i];
for(int i=m;i>=1;i--)res2[--sum3[(res1[i]>>16)&255]]=res1[i];
for(int i=m;i>=1;i--)res1[--sum4[(res2[i]>>24)&255]]=res2[i];
}
struct bcj
{
int fa[N];
inline void ih(){for(int i=1;i<=n;i++)fa[i]=i;}
inline int f(int x){return fa[x]=(x==fa[x])?x:f(fa[x]);}
inline void u(int x,int y){fa[f(x)]=f(y);}
}s;uit a[N];int mrk[N];int cnt;
inline void app(int l,int r,uit va)
{
for(int p=l;p<=r;p=s.f(p)+1)
if(!mrk[p])
{
a[p]=va,mrk[p]=1;cnt++;
if(mrk[p-1])s.u(p-1,p);if(mrk[p+1])s.u(p,p+1);
}
}
inline void clear(){for(int i=1;i<=n;i++)a[i]=0;for(int i=1;i<=n;i++)mrk[i]=0;cnt=0;}
inline void solve()
{
scanf("%d%d",&n,&m);Mker::ih();
for(int i=1;i<=m;i++)
{
l[i]=Mker::rand()%n+1;r[i]=Mker::rand()%n+1;val[i]=Mker::rand()&1073741823;
if(l[i]>r[i])swap(l[i],r[i]);
}srt();s.ih();
for(int i=m;i>=1&&cnt!=n;i--){int id=res1[i]>>32;app(l[id],r[id],val[id]);}
ull ans=0;for(int i=1;i<=n;i++)ans^=(ull)i*a[i];printf("%I64d\n",(long long)ans);
}
int main(){int T;scanf("%d",&T);for(int z=1;z<=T;z++)solve(),clear();return 0;}
```
# H Hills And Valleys
还是那句话，做人要有信仰，写代码不要管时间复杂度，写出来你就win了
胡了半天两个log不会，最后发现标算就是三个log的大暴力
容易发现翻转前的序列会长的十分扭曲，这种序列是自动机识别不了的
但是我们可以枚举翻转的那一段区间当中值域的最大值和最小值，然后我们就可以编一个自动机出来识别我们想要的子序列了
所以枚举一下翻转的值域区间的上下界然后造自动机跑dp就可以了
复杂度$O(10^3n)$
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;const int M=14;
struct data
{
int l;int r;int val;
friend bool operator <(data a,data b){return a.val<b.val;}
}dp[N][M],ans;char mde[N];int n;int a[N];int mp[M][10];int f[10];
inline void build(int l,int r)
{
for(int i=0;i<12;i++)for(int j=0;j<10;j++)mp[i][j]=-1;
for(int i=0;i<=l;i++)for(int j=i;j<=l;j++)mp[i][j]=j;
for(int i=0;i<=l;i++)mp[i][r]=10;
for(int i=l+1;i<r;i++)for(int j=i;j>l;j--)mp[i][j]=j;
for(int i=l+1;i<r;i++)mp[i][l]=11;
for(int i=r;i<10;i++)for(int j=i;j<10;j++)mp[i][j]=j;
for(int i=l+1;i<r;i++)mp[10][i]=i;for(int i=r;i<10;i++)mp[11][i]=i;
mp[10][r]=10;mp[11][l]=11;mp[10][l]=11;
}
inline void subsolve(int l,int r)
{
build(l,r);
for(int i=0;i<n;i++)
for(int j=0;j<12;j++)
{
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
int tw=mp[j][a[i+1]];if(tw==-1)continue;
if(tw!=j&&tw==10)dp[i][j].l=i+1;
if(tw!=j&&j==11)dp[i][j].r=i;dp[i][j].val++;
dp[i+1][tw]=max(dp[i+1][tw],dp[i][j]);
}for(int j=0;j<12;j++)if(dp[n][j].r==0)dp[n][j].r=n;
for(int j=0;j<12;j++)ans=(ans<dp[n][j])?dp[n][j]:ans;
for(int i=0;i<=n;i++)for(int j=0;j<12;j++)dp[i][j]=(data){0,0};
}
inline void solve()
{
scanf("%d",&n);scanf("%s",mde+1);for(int i=1;i<=n;i++)a[i]=mde[i]-'0';
for(int i=0;i<10;i++)f[i]=0;
for(int i=1;i<=n;i++)
{
int mx=0;for(int j=0;j<=a[i];j++)mx=max(mx,f[j]);
f[a[i]]=max(f[a[i]],mx+1);
}ans=(data){1,1,0};for(int i=0;i<10;i++)ans.val=max(ans.val,f[i]);
for(int i=0;i<10;i++)
for(int j=i+1;j<10;j++)subsolve(i,j);printf("%d %d %d\n",ans.val,ans.l,ans.r);
}
int main(){int T;scanf("%d",&T);for(int z=1;z<=T;z++)solve();return 0;}
```