Codeforces Round #624 (Div. 3) 解(补)题报告
A - Add Odd or Subtract Even(签到)
题目大意
给出两个数 a , b a,b a,b,每次可以对 a a a或 b b b加减任意数,求最少多少步可以使 a , b a,b a,b相等
直接模拟即可,我们发现,先求出二者的差值,那么再分别对其正负情况考虑是奇偶性。最多两步就能得到答案。
代码:
#include <iostream>
#include <math.h>
using namespace std;
int a,b,t;
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d%d",&a,&b);
int c=b-a;
if(c>0){
if(c&1) printf("1\n");
else printf("2\n");
}else if(c<0){
c=abs(c);
if(c&1) printf("2\n");
else printf("1\n");
}else printf("0\n");
}
return 0;
}
B - WeirdSort (BFS)
题目大意
给出一个大小为 n n n的 1 − n 1-n 1−n的序列 a a a,再给出一个数组 p p p, p p p数组的每个数代表 p p p的下标,意思是 a a a数组下标 p p p和 p + 1 p+1 p+1可以交换位置。求在指定交换序列下, a a a数组能否变为升序。
如果 a a a序列变为升序,那么每一个元素的后继一定比它大 1 1 1,这里我想的是 B F S BFS BFS,每一次将所有不符合的节点入队,接下来一次性把入队的节点都按照条件交换,然后判断是否升序成功。当队列空了如果还没成功就代表无法得到。
代码:
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int a[105],vis[105];
int t,n,m,x;
queue<int> q;
bool check(){
int flag=1;
for(int i=2;i<=n;i++)
if(a[i]<a[i-1]){
q.push(i);
flag=0;
}
if(flag) return true;
else return false;
}
bool bfs(){
while(!q.empty()) q.pop();
if(check()) return true;
while(!q.empty()){
int MAX=q.size(); //一定要一次性操作完上一次入队的所有节点
while(MAX--){
int u=q.front();q.pop();
if(!vis[u-1]) return false;
swap(a[u-1],a[u]);
}
if(check()) return true;
}
return true;
}
int main()
{
scanf("%d",&t);
while(t--){
memset(vis,0,sizeof vis);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
while(m--){
scanf("%d",&x);
vis[x]=1;
}
if(bfs()) printf("YES\n");
else printf("NO\n");
}
return 0;
}
C - Perform the Combo (差分+树状数组)
题目大意
给出一串字符( a − z a-z a−z),每次下面给出一个序列。从字符串的第一个节点开始按,每次按到序列的第 i i i个元素,就返回第一个字母。当这个序列按完之后就额外从头按到尾,求在按的过程中所有字母出现的次数。
解题思路
对于序列 a [ i ] a[i] a[i],实际上就是对字符串前 a [ i ] a[i] a[i]个都按一次,即区间都加一,而且我们最后要求的是每个节点的次数,显然是树状数组。首先我们引入差分的概念:差分即相邻两个数的差,由 a a a数组我们能得到 a a a的差分数组 d [ i ] = a [ i ] − a [ i − 1 ] d[i]=a[i]-a[i-1] d[i]=a[i]−a[i−1],还可以得到二者之间的关系:
a[i]=d[1]+…+d[i]
那么我们会发现,如果对一个区间 [ x , y ] [x,y] [x,y]内的所有数都执行加法,那么显然只有 d [ x ] d[x] d[x]和 d [ y + 1 ] d[y+1] d[y+1]的值会改变, [ x + 1 , y ] [x+1,y] [x+1,y]区间的值都不变。因此我们用 d d d数组维护树状数组,当我们进行区间加法时,很明显只用更新 d [ x ] d[x] d[x]和 d [ y + 1 ] d[y+1] d[y+1],即 d [ x ] + k d[x]+k d[x]+k, d [ y + 1 ] − k d[y+1]-k d[y+1]−k。
代码:
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
#define lowbit(x) (x&(-x))
const int maxn=2e5+10;
int a[maxn],t[maxn],ans[30];
int T,m,n,x;
string s;
void update(int i,int k){
while(i<=n){
t[i]+=k;
i+=lowbit(i);
}
}
int ask(int i){
int ans=0;
for(;i;i-=lowbit(i)){
ans+=t[i];
}
return ans;
}
int main()
{
scanf("%d",&T);
while(T--){
memset(t,0,sizeof t);
memset(ans,0,sizeof ans);
scanf("%d%d",&n,&m);
cin>>s;
for(int i=0;i<s.size();i++){
a[i+1]=s[i]-'a';
}
while(m--){
scanf("%d",&x);
update(1,1);
update(x+1,-1);
}
update(1,1);
update(n+1,-1);
for(int i=1;i<=n;i++){
ans[a[i]]+=ask(i);
}
for(int i=0;i<26;i++){
printf("%d%c",ans[i],i==25?'\n':' ');
}
}
return 0;
}
D - Three Integers (枚举)
https://blog.csdn.net/qq_44691917/article/details/104539224
E - Construct the Binary Tree (思维)
题目大意
给出节点个数去构造二叉树,求是否能构造出深度和为 d d d的二叉树。刚开始我写的是剪枝+搜索,结果超时了,原来是我没怎么计算时间复杂度, 5000 5000 5000个节点即使剪枝也会超时的,如果有几百个节点可以试一下爆搜。
看别人思路,原来是这样:链状的二叉树总深度一定是最大的,然后完全二叉树总深度是最小的,那么我们就先假设构成一条链,看看能否一步步移动节点构成需要的二叉树。首先每层节点选择一个代表并标记,然后从大到小将未标记的节点作为本层代表的子节点,若当层代表还有其他子节点,继续下移。直到移动到最后一层后自己作为新一层的代表并标记即可。
#include<bits/stdc++.h>
using namespace std;
const int N=5005+5;
int t,n,m,l,r,sum[N],dep[N];
bool solve(){
fill(dep+1,dep+n+1,1);
m=n*(n-1)/2-m;
for(l=2,r=n;l<r;r--){
while(l<r && (m-r+l<0 || dep[l]==dep[l-1]*2)) l++;
if(l>=r) break;
m-=r,dep[r]--;
m+=l,dep[l]++;
}
return m==0;
}
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
if(!solve()) printf("NO\n");
else{
printf("YES\n");
for(int i=1;i<=r;++i)
sum[i]=sum[i-1]+dep[i];
for(int i=2;i<=r;++i){
for(int j=0;j<dep[i];++j)
printf("%d ",sum[i-2]+1+j/2);
}
printf("\n");
}
}
return 0;
}
/* 剪枝搜索超时了
#include <iostream>
using namespace std;
int t,n,m;
int tot;
int a[5005];
bool dfs(int cur,int num,int ans,int maxn){ //cur表示当前第几层,num表示上一层传下来几个数,ans表示当前层数总和,maxn表示当前一共用了几个数字
if(maxn==n && ans==m) return true;
else if(ans>m || maxn>n) return false;
if((2*cur+n-maxn)*(n-maxn)/2+ans<n) return false;
int MAX=2*num;
int p=maxn-num+1;
for(int i=1;i<=MAX;i++){
if(i&1) a[maxn+i]=p;
else a[maxn+i]=p++;
if(dfs(cur+1,i,ans+cur*i,maxn+i)) return true;
}
return false;
}
void solve(){
for(int i=2;i<=n;i++)
printf("%d%c",a[i],i==n?'\n':' ');
}
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
tot=1;
if(m>n*(n-1)/2){
printf("NO\n");
continue;
}
if(dfs(1,1,0,1)){
printf("YES\n");
solve();
}else printf("NO\n");
}
return 0;
}*/
F - Moving Points (树状数组+离散化)
https://blog.csdn.net/qq_44691917/article/details/104539711