2017-10-17 NOIP模拟赛

Reverse

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char c[100010];
int len,cnt,sum[100010];
struct node{
    int n1,n0;
}a[100010];
int main(){
    freopen("reverse.in","r",stdin);freopen("reverse.out","w",stdout);
    //freopen("Cola.txt","r",stdin);
    scanf("%s",c+1);
    len=strlen(c+1);
    int x1=0,x0=0;
    for(int i=1;i<=len;i++){
        if(c[i]=='0')x0++;
        if(c[i]=='1')x1++;
        if((c[i]=='1'&&c[i+1]=='0')||i==len){
            a[++cnt].n0=x0;
            a[cnt].n1=x1;
            x0=0;x1=0;
        }
    }
    for(int i=cnt;i>=1;i--)sum[i]=sum[i+1]+a[i].n0;
    int ans=0;
    for(int i=1;i<=cnt;i++){
        if(a[i].n1<sum[i+1])ans+=a[i].n1;
        else{
            ans+=sum[i+1];
            break;
        }
    }
    printf("%d",ans);
    return 0;
}

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100100
using namespace std;
int len,ans=0x7f7f7f7f;
char s[MAXN];
int sum[MAXN];
int main(){
    freopen("reverse.in","r",stdin);
    freopen("reverse.out","w",stdout);
    scanf("%s",s);
    len=strlen(s);
    sum[0]=s[0]-'0';
    for(int i=1;i<len;i++)
        sum[i]=sum[i-1]+s[i]-'0';
    for(int i=0;i<len;i++)
        ans=min(ans,sum[i]+(len-1-i-sum[len-1]+sum[i]));
    cout<<ans;
}  

 

 

Number

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#ifdef WIN32
#define PLL "%I64d"
#else
#define PLL "%lld"
#endif
using namespace std;
int n,cnt[10];
long long ans;
short b[100000001];
int count(int x){
    memset(cnt,0,sizeof(cnt));
    while(x){
        cnt[x%10]++;
        x/=10;
    }
    int res=0;
    for(int i=9;i>=0;i--){
        if(cnt[i])res=res*10+i;
    }
    return res;
}
int main(){
    //freopen("Cola.txt","r",stdin);
    freopen("number.in","r",stdin);freopen("number.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int now=count(i);
        ans+=b[now];
        b[now]++;
    }
    printf(PLL,ans);
    return 0;
}

/*
枚举，用vis一个二进制数组表示当前数每一位的状态，出现或者不出现。 
然后把二进制转为十进制，cnt[十进制]+1。 
最后因为要求多少对，所以答案累加C(i,2)。 
*/
#include<iostream>
#include<cstdio>
#include<cstring>

#define size 1024

using namespace std;
int n,cnt[size],vis[10];
int Use[10]={1,2,4,8,16,32,64,128,256,512};
long long ans;

int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    cin>>n;
    int start,End;
    for(int i=1;i<=n;i++)
    {
        start=i;End=0;memset(vis,0,sizeof vis);
        while(start) vis[start%10]=1,start/=10;
        for(int j=0;j<=9;j++) if(vis[j]) End+=Use[j];
        cnt[End]++;
    }
    for(int i=0;i<size;i++) ans+=1ll*cnt[i]*(cnt[i]-1)/2;
    cout<<ans<<endl;
    fclose(stdin);fclose(stdout);
    return 0;
}

 

Wave

#include<iostream>
#include<cstdio>
#define maxn 2000010
using namespace std;
int f[maxn][2],n,k,a[maxn],ans;
int qread(){
    int i=0,j=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')j=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){i=i*10+ch-'0';ch=getchar();}
    return i*j;
}
int main(){
    freopen("wave.in","r",stdin);freopen("wave.out","w",stdout);
    //freopen("Cola.txt","r",stdin);
    n=qread();k=qread();
    for(int i=1;i<=n;i++){
        a[i]=qread();
        f[i][1]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[j]-a[i]>=k){//i是奇数项 
                f[i][1]=max(f[i][1],f[j][0]+1);
                ans=max(ans,f[i][1]);
            }
            if(a[i]-a[j]>=k){//i是偶数项 
                f[i][0]=max(f[i][0],f[j][1]+1);
                ans=max(ans,f[i][0]);
            }
        }
    }
    printf("%d",ans);
}

/*
很神奇。
贪心，在满足k的限制下，偶数项尽量大，奇数项尽量小。
*/
#include<iostream>
#include<cstdio>
#include<cstring>

#define N 2000007

using namespace std;
int a[N];
int n,k,m,ans,cur;

inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int main()
{
    n=read();k=read();
    for(int i=0;i<n;i++) a[i]=read();
    ans=1,m=0,cur=a[0];
    for(int i=1;i<n;i++)
    {
        if(m)
          if(cur-a[i]>=k)
            m=0,ans++,cur=a[i];
          else cur=max(cur,a[i]);
          
        else
          if(a[i]-cur>=k)
            m=1,ans++,cur=a[i];
          else cur=min(cur,a[i]);
    }
    printf("%d\n",ans);
    return 0;
}