Codeforces 874 div3
A
题意
计算每两个相邻字符的不同种类
B
题意
重排一个数组b，使得\(|a_i-b_i|\leq k\)
思路
根据相对大小去一一对应,这样每个位置的绝对值最小，数据保证有解
代码
void solve()
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i].first,a[i].second=i;
for(int i=1;i<=n;i++) cin>>b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
{
ans[a[i].second]=b[i];
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
cout<<endl;
}
C
题意
用数组a构造一个b数组，\(b_i=a_i\)或者\(b_i=a_i-a_j\)，j为1到n的任意一个数,要求\(b_i>0\)，且b数组要么全是奇数，要么全是偶数
思路
记录最小的奇数和最小的偶数，看是否能构造出全是奇数的情况或全是偶数的情况。
代码
bool check(int x)
{
int c1=-1,c0=-1;
for(int i=1;i<=n;i++)
{
if(a[i]%2==0)
{
if(c0==-1) c0=a[i];
else c0=min(a[i],c0);
}
if(a[i]%2==1)
{
if(c1==-1) c1=a[i];
else c1=min(a[i],c1);
}
}
if(x==0)//如果是全是偶数的情况，那么奇数一个都不能有
{
return c1==-1;
}
//全是奇数的情况，要么没有偶数,要么最小的偶数>最小的奇数
else return (c0==-1)||(c0>c1);
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
if(check(0)||check(1)) cout<<"YES\n";
else cout<<"NO\n";
}
D
题意
给出一个排列，选定两个数\(l,r,1\leq l,r\leq n\) ,\([l,r]\)内的数翻转，\([1,l]\)的数移到\(r\)后面，\([r+1,n]\)的数移到\(l\)前面
输出操作后字典序最大的序列
思路
如果n不在开头，那么右端点肯定设在它前面，左端点就往前找，如果当前\(a_l>a_1\)就继续往前。
在开头的话就找n-1好了
还有一种特殊情况，n在末尾的时候，如果\(a_1\)是前面的数中最大的，那么左右端点都设在末尾。
代码
void print(int l,int r)
{
for(int i=r+1;i<=n;i++) cout<<a[i]<<" ";
for(int i=r;i>=l;i--) cout<<a[i]<<" ";
for(int i=1;i<l;i++) cout<<a[i]<<" ";
cout<<endl;
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],pos[a[i]]=i;
if(n==1) {cout<<1<<endl;return;}
int l=-1,r=-1,m=n;
if(pos[m]==1) m--;//n在开头，就找n-1
if(pos[m]==n) //在结尾
{
r=pos[m]-1;
if(a[1]>a[r]) l=r=pos[m];
else
{
int k=r-1;
while(k>=1&&a[k]>a[1]) k--;
l=max(1ll,k+1);
}
}
else
{
r=pos[m]-1;
int k=r-1;
while(k>=1&&a[k]>a[1]) k--;
l=max(1ll,k+1);
}
//cout<<l<<" "<<r<<endl;
print(l,r);
}
E(补)
题意
思路
赛时想得太复杂了，而且理解错了题意，首先每个点的入度最多为2，每个连通块内最多只有一个环，而且环只有两种情况，一种是相邻两个点成环（不把它看作环），一种是一整个连通块都成环，不会在某一部分成环的。所求最少的情况是环的数量+一条链，最多的情况就是连通块数量。
代码
int fd(int x) {return f[x]==x?x:f[x]=fd(f[x]);}
void Merge(int x,int y)
{
int a=fd(x),b=fd(y);
if(a==b) return;
f[b]=a;
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) tag[i]=0,f[i]=i;
for(int i=1;i<=n;i++) cin>>a[i],Merge(i,a[i]);
bool chain=false;
for(int i=1;i<=n;i++)
{
if(a[a[i]]==i)//如果是这种情况那个连通块就没环了
{
tag[fd(i)]=1;
chain=true;
}
}
mx=0,mn=0;
for(int i=1;i<=n;i++)
{
if(f[i]==i)
{
if(!tag[i]) mn++;
mx++;
}
}
cout<<mn+chain<<" "<<mx<<endl;
}
F(补)
题意
给定n个数，构造一个长度为m的数组，要求：任意两个数差值要小于m，且每个数不同。求这类数组的个数。
思路
最大值和最小值差值是m-1，那么就是连续的。那来个记录不同的数和它们的次数，前缀和搞一下就行了。
代码
const int N=2e5+10,M=1010,inf=0x3f3f3f3f,mod=1e9+7;
int n,m,d,k;
int a[N],b[N];
int fac[N];
int q_pow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b/=2;
}
return res;
}
void solve()
{
cin>>n>>m;
map<int,int> mp;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
mp[x]++;
}
vector<pii> p;
for(auto x:mp) p.push_back(x);
sort(p.begin(),p.end());
fac[0]=1;
for(int i=1;i<=p.size();i++)
{
fac[i]=fac[i-1]*p[i-1].second%mod;
}
int ans=0;
for(int i=0;i+m-1<p.size();i++)
{
if(p[i].first+m-1==p[i+m-1].first)
{
ans=(ans+fac[i+m]*q_pow(fac[i],mod-2)%mod)%mod;
}
}
cout<<ans<<endl;
}
G(补)
题意
将一棵树剪成每份三个点，输出要剪去的边
思路
如果当前子树的大小为3，直接把当前根节点的上面那条边给剪掉。把剪掉之后的点标记下，看最后是否所有点都标记过
代码
const int N=2e5+10,M=1010,inf=0x3f3f3f3f,mod=1e9+7;
int n,m,d,k;
int h[N],e[N*2],id[N*2],ne[N*2],idx,vis[N];
int sz[N];
vector<int> ans;
void add(int a,int b,int c)
{
e[idx]=b;
id[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs1(int u,int fa)
{
vis[u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dfs1(j,u);
}
}
void dfs(int u,int fa,int num)
{
sz[u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dfs(j,u,id[i]);
sz[u]+=sz[j];
}
if(sz[u]==3)
{
if(num!=-1) ans.push_back(num);
dfs1(u,fa);
sz[u]=0;
}
}
void solve()
{
memset(h,-1,sizeof(h));
idx=0;
cin>>n;
for(int i=1;i<=n;i++) vis[i]=0,sz[i]=0;
ans.clear();
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
add(a,b,i);
add(b,a,i);
}
if(n%3) {cout<<-1<<endl;return;}
dfs(1,-1,-1);
// for(int i=1;i<=n;i++) cout<<vis[i]<<" ";
// cout<<endl;
for(int i=1;i<=n;i++) if(!vis[i]){cout<<-1<<endl;return;}
cout<<ans.size()<<endl;
for(auto x:ans) cout<<x<<" ";
cout<<endl;
}