Manthan, Codefest 18 (rated, Div. 1 + Div. 2)

1w年没更新了QAQ A. 傻逼题二进制分解一下即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,j,k;
    cin>>n;
    for(i=0;;i++){
        if(n<=(1<<i))break;
        n-=(1<<i);
    }
    cout<<i+1<<endl;

    return 0;
}

B. 排个序贪心搞搞就行,自己zz了还wa了3发…

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int num[200005],n,s,i,j,k;
    ll ans=0;
    cin>>n>>s;
    for(i=1;i<=n;i++)scanf("%d",&num[i]);
    sort(num+1,num+1+n);
    int mid=(n+1)>>1;
    if(num[mid]==s){
        cout<<0<<endl;return 0;
    }
    else if(num[mid]>s){
        for(i=mid;i;i--){
            if(num[i]<=s)break;
            ans+=num[i]-s;
        }
    }
    else{
        for(i=mid;i<=n;i++){

            if(num[i]>=s)break;
            ans+=s-num[i];
            //cout<<ans<<endl;
        }
    }
    //cout<<mid<<endl;
    cout<<ans<<endl;

    return 0;
}

C. 除非相邻位置刚好要交换,否则都没有交换意义,随便搞搞即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,j,k;string str1,str2;
    int ans=0;
    cin>>n;
    cin>>str1>>str2;
    for(i=0;i<str1.size();i++){
        if(str1[i]!=str2[i]){
            if(i<str1.size()-1&&str1[i+1]!=str2[i+1]&&str1[i]!=str1[i+1]){
                ans++;i++;
            }
            else{
                ans++;
            }
        }
    }
    cout<<ans<<endl;

    return 0;
}

D. 其实就是一个二叉树的层次遍历,但是还有一点要注意的就是父亲层的遍历顺序决定了下一层的遍历顺序,所以这也要考虑。解决方案是每个点建一个map记录边,然后检测序列的时候弄两个指针,一个指示当前节点,另一个指示当前节点的儿子。如果是非法序列,最后第二个指针肯定没法走完所有的节点。同时还要注意特判根节点是否为1

#include<bits/stdc++.h>
using namespace std;
map<int,int>mp1[200005];
int main()
{
    int n,i,j,k,x,y;
    cin>>n;
    for(i=1;i<n;i++){
        scanf("%d%d",&x,&y);mp1[x][y]=1;mp1[y][x]=1;
    }
    int num[200005];
    for(i=1;i<=n;i++)scanf("%d",&num[i]);
    for(i=1,j=2;i<=n;i++)
        while(mp1[num[i]][num[j]])
            j++;
    if(j==n+1&&num[1]==1){//注意这里是j==n+1!!
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
//cout<<j<<endl;

    return 0;
}

E. 难点在于怎么去检测一个人是否有至少k个朋友,并且这些朋友也都有至少k个可以去旅游的朋友…标算很精妙…

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+50;
set<int>s,G[maxn];
int k,a[maxn],b[maxn],ans[maxn],n,m;
void check(int x)
{
    if(G[x].size()<k&&s.erase(x)){//如果这个人的朋友小于k,他肯定要滚蛋,同时在s里面也要删去此人
        for(auto a:G[x]){
            G[a].erase(x);check(a);//他的朋友也要check一发
        }
    }
}
int main()
{
    int i,j;
    cin>>n>>m>>k;
    for(i=1;i<=m;i++){
        scanf("%d%d",&a[i],&b[i]);
        G[a[i]].insert(b[i]);G[b[i]].insert(a[i]);//建立朋友关系
    }
    for(i=1;i<=n;i++)s.insert(i);
    for(i=1;i<=n;i++)check(i);//检查每一个人的朋友关系
    for(i=m;i;i--){
        ans[i]=s.size();//此时集合中的所有人都满足要求
        G[a[i]].erase(b[i]);G[b[i]].erase(a[i]);//删去这天才成为朋友的人
        check(a[i]);check(b[i]);
    }
    for(i=1;i<=m;i++)
        printf("%d\n",ans[i]);

    return 0;
}