Codeforces Round #529 (Div. 3)

Posted by

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

sort一遍,后取删去最小值或删去最大值结果的最小值。
#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

比赛时做出了D却没做出这道。。 先计算出二进制位下1的个数cnt,若cnt>k,显然结果为NO。 开个优先队列,上一步计算时同时把满足(1<<i)&n的(1<<i)加入队列。 然后不断分解队列中的top值,同时入队2(top/2),因为2^i=2^{i-1}+2^{i-1}。 若还没分成ktop已经为1,显然结果为NO。 比赛不会写。。躺在床上突然想出来了。。
#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

STL怒搞了一遍。 因为每个点就2个孩子,所以依次枚举。 对于每个节点x,若第一个孩子x1出现在了第二个孩子x2的孩子队列中,则说明x2在前,x1在后,入队,记录末尾元素,直到size()==n
#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;
}
]]>

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注