位运算1(bit)

Time Limit:1000ms   Memory Limit:128MB

 

题目描述

LYK拥有一个十进制的数N。它赋予了N一个新的意义：将N每一位都拆开来后再加起来就是N所拥有的价值。例如数字123拥有6的价值，数字999拥有27的价值。

假设数字N的价值是K，LYK想找到一个价值是K-1的数字，当然这个答案实在太多了，LYK想使得这个价值为K-1的数字尽可能大。

 

输入格式(bit.in)

一个数N。

 

输出格式(bit.out)

一个数表示答案。你需要输出一个非负整数，且这个数不包含前导0。

 

输入样例1

199

 

输出样例1

198

 

输入样例2

1000

 

输出样例2

0

 

对于20%的数据n<=10

对于40%的数据n<=100

对于60%的数据n<=1000

对于100%的数据1<=n<=100000。

 

 

 通过观察，我们可以发现一个性质，当n的最后一位为大于等于1的数的时候我们可以直接将这个数减1以后就是答案、

但是如果最后一位为0的时候我们肯定不能这样再减了，为什么？你减去以后出来的数为9，不论怎么加都比当前数的价值大。这样的话我们我更高位上找，遇到一个不为0得数以后在减1，如果这个不为零的数在最高位上，且为1，这样我们就直接输出0

zz一样的没有考虑，n<10的这种情况，白丢掉了10分、、（呜呜）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,s,sum;int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return x*f;}int main(){    freopen("bit.in","r",stdin);    freopen("bit.out","w",stdout);    n=read();    while(n)    {        sum=n%10,n/=10;        if(sum>0)         {            sum--;            if(n) printf("%d%d",n,sum);            else {
    if(sum) {printf("%d",sum);break;} s=1;}            for(int i=1;i<=s;i++) printf("0");            break;        }        else s++;    }    return 0;}
          
         
        
       
      

 

 

火柴棒 (stick)

Time Limit:1000ms   Memory Limit:128MB

 

题目描述

众所周知的是，火柴棒可以拼成各种各样的数字。具体可以看下图：

通过2根火柴棒可以拼出数字“1”，通过5根火柴棒可以拼出数字“2”，以此类推。

现在LYK拥有k根火柴棒，它想将这k根火柴棒恰好用完，并且想知道能拼出的最小和最大的数分别是多少。

 

输入格式(stick.in)

一个数k。

 

输出格式(stick.out)

两个数，表示最小的数和最大的数。注意这两个数字不能有前导0。

 

输入样例

15

 

输出样例

108 7111111

 

数据范围

对于30%的数据k<=10。

对于60%的数据k<=20。

对于100%的数据1<k<=100。

 

 

对于最大的那个数我们可以发现一个小规律，我们知道位数最多的数一定最大对吧，那么我们就让我们凑出来的这个数位数最多，那么我们就尽量选那个耗用火柴数最少的那个，我们先用2个的，然后如果他是一个奇数的话，那么最后一定会剩下一个1，那么我们就判断如果他是奇数的话，我们就用一个耗3个火柴的，其余的又还是用2，如果是偶数，那么没有商量，直接用2.

然后我们再来考虑那个最小的数，同理我们需要把把我们拼出的数位数尽可能小，那么我们就要选用耗火柴数最多的数字，我们又可以发现0

耗用6个火柴，8耗用7个火柴，这两种可能在选用的时候拼出的数字位数一样多，在这个时候我们就只能选0，不选8了（这不废话吗、、），然后我们还可以发现我们如果讲能凑成8或6的都用来凑的话，可能不是最优的，例如15，我们完全可以拼出2个0但是这样的话我们剩下的就是3，这样的话我们拼出的数就是700了，这样显然不是最小的。这样我们就用其他的两个数来代替他们，我们在上面如果选用1个0的话，那么剩下的数为9，我们用随意两个数在组成这个9，看看最小可以是几。然后用一个数组记录一下，我们要输出最小值，那么在前面的数一定要最小，但是同时也不能等于0.再就是我们在用6个火柴的时候可以不选择0，可以选择6，我们知道68一定比80小

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int a[7]={
    0,2,3,4,5,6,7};int b[8]={
    0,0,1,7,4,2,0,8};int n,s,n1,n2,cnt,sum,ans[50];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return x*f;}int work1(int n){    int m=0x7fffffff;    if(n<=7) printf("%d",b[n]);    else     {        if(n/7==n/6)        {            s=n/6-1,n=n%6+6;            for(int i=n-7;i<=7;i++)            {                n1=b[i],n2=b[n-i];                  if(n1>n2&&n2!=0||!n1) swap(n1,n2);                  if(n1*10+n2>m) continue;                m=n1*10+n2;                ans[1]=n1,ans[2]=n2;                if(n2==0)                {                    n2=6;                    if(n1>n2&&n2!=0||!n1) swap(n1,n2);                      if(n1*10+n2>m) continue;                    m=n1*10+n2;                    ans[1]=n1,ans[2]=n2;                }            }            for(int i=3;i<=s+3;i++) ans[i]=b[6];            sort(ans+1,ans+s+3);            if(!ans[1])             for(int i=2;i<=s+2;i++)               if(ans[i]) {m=ans[1],ans[1]=ans[i],ans[i]=m; break;}            for(int i=1;i<=s+2;i++)             printf("%d",ans[i]);        }        else         {            s=n/7-1,n=n%7+7;            for(int i=n-7;i<=7;i++)            {                n1=b[i],n2=b[n-i];                   if(n1>n2&&n2!=0||!n1) swap(n1,n2);                  if(n1*10+n2>m) continue;                m=n1*10+n2;                ans[1]=n1,ans[2]=n2;                if(n2==0)                {                    n2=6;                    if(n1>n2&&n2!=0||!n1) swap(n1,n2);                      if(n1*10+n2>m) continue;                    m=n1*10+n2;                    ans[1]=n1,ans[2]=n2;                }            }            for(int i=3;i<=s+3;i++) ans[i]=b[7];            sort(ans+1,ans+s+3);            if(!ans[1])             for(int i=2;i<=s+2;i++)               if(ans[i]) {m=ans[1],ans[1]=ans[i],ans[i]=m; break;}            for(int i=1;i<=s+2;i++)             printf("%d",ans[i]);        }    }    printf(" ");}int work2(int n){    if(n%2)      printf("7"),n-=2;    for(int i=1;i<=n/2;i++)      printf("1");}int main(){    freopen("stick.in","r",stdin);    freopen("stick.out","w",stdout);    n=read();    work1(n),work2(n);    return 0;}
          
         
        
       
      

 

 

听音乐(music)

Time Limit:1000ms   Memory Limit:128MB

 

题目描述

LYK喜欢听音乐，总共有n首音乐，有m个时刻，每个时刻LYK会听其中一首音乐，第i个时刻会听第ai首音乐。它给自己定了一个规定，就是从听音乐开始，听的每连续n首音乐都是互不相同的。例如当n=3时，从听歌开始，123321就是一个合法的顺序（此时LYK听了两轮歌，分别是123和321，每一轮的歌都是互不相同的），而121323就是一个不合法的顺序（LYK也听了两轮歌，第一轮中121存在听了两次相同的歌）。我们现在只截取其中一个片段，也就是说并不知道LYK之前已经听了什么歌。因此121323也仍然可以是一个合法的顺序，因为LYK之前可能听过3，然后再听121323，此时LYK听了三轮歌，分别是312,132和3。

现在LYK将告诉你这m个时刻它听的是哪首歌。你需要求出LYK在听这m首歌之前可能听过的歌的不同方案总数（我们认为方案不同当且仅当之前听过的歌的数量不同）。LYK向你保证它之前听过的歌的数量是在0~n-1之间的。因此你输出的答案也应当是0~n中的某个整数（答案是0表示LYK记错了，没有一个合法的方案）。

 

输入格式(music.in)

第一行两个数n,m。 

第二行m个数表示ai。

 

输出格式(music.out)

一个数表示答案。 

 

输入样例1

4 10

3 4 4 1 3 2 1 2 3 4

 

输出样例1

1

 

样例解释1：LYK之前一定只听过2首歌（12或者21），这样可以分成3部分分别是34,4132,1234，每一部分都没有出现相同的歌。对于其它情况均不满足条件。

 

输入样例2

6 6

6 5 4 3 2 1

 

输出样例2

6

 

样例解释2：LYK之前听过0~5首歌的任意几首都是有可能满足条件的。

 

 

数据范围

对于50%的数据n,m<=1000。

对于100%的数据1<=n,m<=100000,1<=ai<=n。

其中均匀分布着n<m以及n>=m的情况。

 

提示：

LYK知道这个题目很长，但为了便于理解已经加了很多注释了……建议没看懂的同学们再重新看一遍……

 

 

暴力做法：如果要以前听过歌，那么听过歌的情况一定是第一轮听的歌的个数在n以内。这样我们先确定第一轮的长度，看看当前这一轮是否合乎条件，如果满足条件的话，我们在判断在这种划分的前提下其他的划分出的轮数是否满足条件，如果均满足条件，那么这种情况就是合法的，我们在这个地方统计一个前缀和，用于判断一段区间是否满足条件，如果满足条件那么ans++。

我们这个地方还需要分类讨论，因为n可能比m大，这样的话我们在划分轮数的时候就只能划分为两轮，一轮为最前面的那一轮，另一轮为从i到m这一轮，我们判断这两轮是否都满足条件

#include
      
       #include
       
        #include
        
         #include
         
          #define N 1010using namespace std;bool flag;int n,m,x,s,ans,a[N][N],maxn[N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return x*f; }int main(){    freopen("music.in","r",stdin);    freopen("music.out","w",stdout);        n=read(),m=read();    for(int i=1;i<=m;i++)     {        x=read();        for(int k=1;k<=n;k++)         if(k==x) a[k][i]=a[k][i-1]+1;         else a[k][i]=a[k][i-1];        maxn[i]=max(maxn[i],a[x][i]);    }    if(n
          
           1) {flag=true;break;}            if(flag) break;             for(int j=min(i+n,m);j<=m;j+=n)            {                if(i+n>m) s=i;                else s=j-n;                for(int k=1;k<=n;k++)                   if(a[k][j]-a[k][s]>1) {flag=true;break;}                  if(flag) break;             }             if(!flag) ans++;        }    }    else    {        for(int i=1;i<=m;i++)        {            flag=false;            if(maxn[i]>1) {flag=true;break;}            if(flag) break;             for(int k=1;k<=n;k++)              if(a[k][m]-a[k][i]>1) {flag=true;break;}            if(!flag) ans++;        }    }    printf("%d",ans);    return 0;}
          
         
        
       
      

 我们统计一个前缀和，用来记录从每个点出发向右最远能扩展到的位置，然后我们枚举第一轮的右端点，然后判断在当前这种划分下是否合格，怎么判断是否合格呢，我们可以判断一段区间左端点是否可以扩展到右端点以外，如果可以则说明这种情况是合法的，ans++。

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 100010using namespace std;bool flag,vis[N];int n,m,a[N],sum[N],ans;int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return x*f;}int work(){
     //预处理，x佬说在预处理一个点往右能扩展到的区间要倒这枚举     int r=m;sum[m]=m,vis[a[m]]=true;//最后一个点能扩展到的最远的位置就是他自己     for(int i=m-1;i;i--)    {        if(!vis[a[i]]) sum[i]=r,vis[a[i]]=true;//如果这个点在之前（这里的之前是指原序列的当前点的后面，因为我们是倒着枚举的）没有出现过，说明到现在这段区间是合法的         else//这个点如果在之前出现过，那么要使包含这个点的这个区间合法，我们就要找到那个之前出现过他的位置，从这个点到那个位置这段区间才是合法的（合法的定义为一段不包含同一种音乐的区间）         {            while(i
           
            m，在第一种情况下我们一定可以分出>=2轮，在第二种情况下即为小于两轮 { for(int i=0;i<=n;i++)//这个地方我们枚举的是第一轮的右端点，左端点固定为1. { if(sum[1]
            
             m&&j<=m) s=m; else s=j+n-1;//n为每一轮的长度，若左节点为i，那么右节点为i+n-1 if(sum[j]
             
              =i&&sum[i+1]==m) ans++;}//分别判断这两轮是否都满足条件 else if(sum[1]==m) ans++;//只有一轮的时候，我们就只需要判断这一轮是否满足条件就好了 } } printf("%d",ans); return 0;}
             
            
           
          
         
        
       
      

 

 

 

　　　　　　　　　　　　　

 

　　　　　　　　　　　　　　　　　　　　　　距 NOIp2017 还剩 30 天

 　　                             你可以做的事情还有很多，即使到最后一秒也不要放弃，因为不到结束的那一刻谁也不知道结果会怎样。