Educational Codeforces Round 25 A

【题目以及连接】

A. Binary Protocol

time limit per test:1 second
memory limit per test:256 megabytes
input: standard input
output: standard output

Polycarp has just invented a new binary protocol for data transmission. He is encoding positive integer decimal number to binary string using following algorithm:

  • Each digit is represented with number of ‘1’ characters equal to the value of that digit (for 0 it is zero ones).
  • Digits are written one by one in order corresponding to number and separated by single ‘0’ character.

Though Polycarp learnt how to encode the numbers, he has no idea how to decode them back. Help him calculate the decoded number.

Input

The first line contains one integer number n (1 ≤ n ≤ 89) — length of the string s.

The second line contains string s — sequence of ‘0’ and ‘1’ characters, number in its encoded format. It is guaranteed that the number corresponding to the string is positive and doesn’t exceed 109. The string always starts with ‘1’.

Output

Print the decoded number.

Examples
Input
3
111
Output
3
Input
9
110011101
Output

2031

Link: Codeforce Educational Codeforces Round 25 A

【题意】
给出一串二进制字符串,翻译成原来的数字.规则为数字间以单独的0为分隔符.多余的0当做一个0输出,最后有几个0输出几个0.
(后面那个意思蒙出来的,英语渣,有点没搞懂最后一个条件是为什么).
【题解】
逐位记录即可.
【Source Code】
github:Educational Codeforces Round 25 A.cpp
–忽然发现–原来链接中有空格使用%20处理的.但是空格多了,复制的时候不会复制上%20..要手敲

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        char digit,pre='0';
        int cnt=0;
        for(int i=0;i<n;++i){ 
            cin>>digit;
            if(digit=='1') cnt++;
            if(digit=='0') {printf("%d",cnt);cnt=0;}
        }
        if(digit=='1') printf("%d",cnt);
        if(digit=='0') printf("0");
        printf("\n");
    }
    return 0;
}

玲珑杯 Round#18 A

【Topic Link】

1143 – 计算几何你瞎暴力

【题解】

用vis统计每个点上有多少教室.可以发现,最大的距离是30.

然后枚举所有的点求出两点之间的距离以及所有的组合总数.

1.如果两点是同一个点.先判断该点是否存在房子.如果存在,就用等差数列求和公式: N-1+N-2+…+1=(1+N-1)*(N-1)/2  计算出组合种数记录在d[0].

2.如果两点不同一点,判断两点教室数都不为0,然后计算组合种数: S*S2 计算组合种数记录在d[dist(S,S2)].

3.由于计算的时候每个点都在点一和点二计算过一次.所以最终统计的时候之前统计得值需要除以二.

【Source Code】

github: Round#18 A.cpp


#include<bits/stdc++.h>
#define cle(x) memset(x,0,sizeof(x))
#define INF 0x3f3f3f3f
using namespace std;

const int maxn=50000+10;
int T,n,q,d[1420];
char str[200];
long long vis[20][20][20];
bool vi[1420];

int main(){
    scanf("%d",&T);
    while(T--){
        cle(d),cle(vis),cle(vi);
        scanf("%d%d",&n,&q);
        for(int i=0;i<n;++i){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            vis[x][y][z]++;
        }
        for(int i=0;i<=10;i++)
        {
            for(int j=0;j<=10;j++)
            {
                for(int k=0;k<=10;k++)
                {
                    for(int x=0;x<=10;x++)
                    {
                        for(int y=0;y<=10;y++)
                        {
                            for(int z=0;z<=10;z++) { 
                                int dis=abs(i-x)+abs(j-y)+abs(k-z); 
                                if(i==x&&j==y&&k==z) { 
                                    if(vis[i][j][k]-1>=0){
                                        d[dis]+=(vis[i][j][k])*(vis[i][j][k]-1)/2;
                                        vi[dis]=true;
                                    }
                                }
                                else if(vis[i][j][k]*vis[x][y][z]>0)
                                {
                                    d[dis]+=vis[i][j][k]*vis[x][y][z];
                                    vi[dis]=true;
                                }
                            }
                        }
                    }
                }
            }
        }
        for(int i=1;i<=30;++i)d[i]=d[i-1]+d[i]/2;
        for(int i=0;i<q;++i){
            int R;
            scanf("%d",&R);
            R=min(30,R);
            printf("%lld\n",d[R]);
        }
    }
    return 0;
}

UVa 11464

【生词】

gird 网格,格子

so taht 以便

The parity 奇偶校验

even 有偶数意

transformation 转化

achieve 取得,获得,实现,成功

requirement 要求

indicates 表明

character 性格,品质

separated 分开,隔开

instead 代替,反而,相反

【题解】

蓝书 P16

【Code】

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=20;
int A[maxn][maxn],B[maxn][maxn],n,T,ca=1;

int check(int s){
    memset(B,0,sizeof(B));
    //先初始化第一行
    for(int i=0;i<n;++i){
        if(s & (1<<i)) B[0][i]=1;//这句意思是判断每一位上是否是1
        //即(1<<n)只有第n位是1,其他位都是0 为真即为1
        else if(A[0][i]==1) return INF;//1不能变成0
    }
    for(int i=1;i<n;++i){
        for(int j=0;j<n;++j){
            int sum=0;//元素B[i-1][0]的上,左,右元素之和
            if(i>1)sum+=B[i-2][j];
            if(j>0)sum+=B[i-1][j-1];
            if(j<n-1)sum+=B[i-1][j+1];
            B[i][j]=sum%2;//sum是偶数,=0,奇数,=1
            if(A[i][j]==1 && B[i][j]==0) return INF;
            //不存在1->0的操作.
        }
    }
    int cnt=0;
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            if(A[i][j]!=B[i][j])
            cnt++;
        }
    }
    return cnt;
}

int main(){
    scanf(“%d”,&T);
    while(T–){
        printf(“Case %d: “,ca++);
        scanf(“%d”,&n);
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                scanf(“%d”,&A[i][j]);
        int ans=INF;
        for(int i=0;i<(1<<n);++i)
            ans=min(ans,check(i));
        if(ans==INF) ans=-1;
        printf(“%d\n”,ans);
    }
    return 0;
}