Codeforces Round #529 (Div. 3)

比赛链接： http://codeforces.com/contest/1095

A. Repeating Cipher

#include <cstdio>
#include <cstring>
#include <cctype> 
#include <iostream>
using namespace std;
int n,cnt;
char s[101];
int main()
{
    scanf("%d",&n);
    scanf("%s",s);
    if(n==1) return 0&printf("%s\n",s);
    for(int i=0;i+cnt<=n;i+=cnt)
    {
        cnt++;
        printf("%c",s[i]);
    }
    return 0;
}

B. Array Stabilization

一遍，后取删去最小值或删去最大值结果的最小值。

#include <cstdio>
#include <cstring>
#include <cctype> 
#include <iostream>
#include <algorithm>
using namespace std;
int n,a[100050];
inline int read()
{
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x; 
}
int main()
{
    n=read();
    if(n==2) return 0&printf("0\n");
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1);
    printf("%d\n",min(a[n-1]-a[1],a[n]-a[2]));
    return 0;
}

C. Powers Of Two

比赛时做出了却没做出这道。。

先计算出二进制位下的个数，若>，显然结果为。

开个优先队列，上一步计算时同时把满足的(1<<i)加入队列。

然后不断分解队列中的值，同时入队个，因为。

若还没分成个已经为，显然结果为。

比赛不会写。。躺在床上突然想出来了。。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector> 
#include <algorithm>
static const int lim=30;
using namespace std;
priority_queue<int,vector<int>,less<int> > q;
vector<int> vec;
int n,k;
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=lim;i>=0;i--) if((1<<i)&n) q.push((1<<i));
    if((int)q.size()>k) return 0&printf("NO\n");
    while(q.size()!=k)
    {
        if(q.top()==1&&q.size()!=k) return 0&printf("NO\n");
        else
        {
            int t=q.top();
            q.pop();
            q.push(t/2);q.push(t/2);
        }
    }
    printf("YES\n");
    while(!q.empty()) vec.push_back(q.top()),q.pop();
    sort(vec.begin(),vec.end());
    for(vector<int>::iterator it=vec.begin();it!=vec.end();it++) printf("%d ",*it);
    return 0;
}

D. Circular Dance

怒搞了一遍。

因为每个点就个孩子，所以依次枚举。

对于每个节点，若第一个孩子出现在了第二个孩子的孩子队列中，则说明在前，在后，入队，记录末尾元素，直到。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstring>
#include <vector>
#include <algorithm>
static const int MAXN=200050;
using namespace std;
int n,x,y;
bool vis[MAXN];
vector<int> vec[MAXN];
vector<int> res;
inline int read()
{
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x; 
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        x=read();y=read();
        vec[i].push_back(x);
        vec[i].push_back(y);
    }
    int i=1;
    while(res.size()!=n)
    {
        vector<int>::iterator s=find(vec[vec[i][0]].begin(),vec[vec[i][0]].end(),vec[i][1]);
        if(s==vec[vec[i][0]].end())
        {
            if(!vis[vec[i][1]]) res.push_back(vec[i][1]),vis[vec[i][1]]=true;
            if(!vis[vec[i][0]]) res.push_back(vec[i][0]),vis[vec[i][0]]=true;
            i=vec[i][1];
        }
        else
        {
            if(!vis[vec[i][0]]) res.push_back(vec[i][0]),vis[vec[i][0]]=true;
            if(!vis[vec[i][1]]) res.push_back(vec[i][1]),vis[vec[i][1]]=true;
            i=vec[i][0];
        }
    }
    for(vector<int>::iterator it=res.begin();it!=res.end();it++) printf("%d ",*it);
    return 0;
}