A-吐泡泡

链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

 

小鱼儿吐泡泡，嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡：大泡泡"O"，小泡泡"o"。两个相邻的小泡泡会融成一个大泡泡,两个相邻的大泡泡会爆掉。（是的你没看错，小气泡和大气泡不会产生任何变化的，原因我也不知道。） 例如:ooOOoooO经过一段时间以后会变成oO。

输入描述:

数据有多组，处理到文件结束。 每组输入包含一行仅有'O'与'o'组成的字符串。

输出描述:

每组输出仅包含一行，输出一行字符串代表小鱼儿吐出的泡泡经过融合以后所剩余的泡泡。

示例1

输入

ooOOoooO

输出

oO

说明

自左到右进行合并

备注:

对于100%的数据， 字符串的长度不超过100。

 

#include
      
       using namespace std;stack
       
        st;void sol(int j){    if(st.empty()) st.push(j);    else{        int k=st.top();        if(k==0&&j==0){            st.pop();            sol(1);        }else if(k==1&&j==1){            st.pop();        }else st.push(j);    }}int main(){    char s[105];     while(~scanf("%s",s)){        for(int i=0;s[i]!='\0';i++){            if(s[i]=='o'){sol(0);}            else{sol(1);}        }        stack
        
          tt;        while(!st.empty())//导出        {            int k=st.top();st.pop();            if(k==0) tt.push('o');            else tt.push('O');        }        while(!tt.empty()){
    //输出            char k=tt.top();tt.pop();            printf("%c",k);        }        printf("\n");    }    return 0;}
        
       
      

 

B-TaoTao要吃鸡

链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

Taotao的电脑带不动绝地求生，所以taotao只能去玩pc版的荒野行动了，和绝地求生一样，游戏人物本身可以携带一定重量m的物品，装备背包之后可以多携带h（h为0代表没有装备背包）重量的东西。 玩了几天taotao发现了一个BUG，当装备背包之后，如果可携带重量没有满，就可以拿一个任意重的东西。（解释看样例）有一天taotao空降到了一个奇怪的岛上，岛上有n件装备，每个装备都有重量Wi和威力值Vi,但taotao不认识这些装备，所以他来求助你，挑选威力最大的装备，帮助他吃鸡。

输入描述:

本题有多组输入（小于10），当n=0时结束输入。 第一行输入n,m,h。n，m，h为整数，并且0<=n,m,h<=100， 接下来n行，每行输入第i个物品的物品的重量Wi和威力值Vi。0<=Wi,Vi<=100.

输出描述:

输出最大威力值，每组输出一行。

示例1

输入

3 3 32 33 22 30

输出

8

说明

可携带的总重量为6，当拿了前两件装备，此时容量为5/6，还可以再拿第三件物品。

 

#include
      
         using namespace std;     int n,m,h;  int v[105],w[105],dp[20500];     struct thing  {      int w,v;  }a[105];     bool cmp(thing aa,thing bb)  {      return aa.w
       
        =a[i].w;j--)                      dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);              printf("%d\n",dp[m]);          }          else          {              m+=h;              for(int i=1;i<=n;i++)                  for(int j=m-1;j>=0;j--)                      if(j+a[i].w
       
      

//第二种思路：枚举那个有特权的物品 #include
      
       using namespace std;  const int N = 100 + 5;    int n, m, h, w[N], v[N], dp[N << 1];    int main()  {      while (~scanf("%d", &n) && n)      {          scanf("%d%d", &m, &h);          for (int i = 1; i <= n; ++i) scanf("%d%d", &w[i], &v[i]);          if (h == 0)          {              memset(dp, 0, sizeof(dp));              for (int i = 1; i <= n; ++i)                  for (int j = m; j >= w[i]; --j)                      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);              printf("%d\n", dp[m]);          }          else          {              int ans = 0;              for (int k = 1; k <= n; ++k)              {                  memset(dp, 0, sizeof(dp));                  for (int i = 1; i <= n; ++i)                  {                      if (i == k)                          continue;                      for (int j = m + h; j >= w[i]; --j)                          dp[j] = max(dp[j], dp[j - w[i]] + v[i]);                  }                  for (int j = m + h - 1; j >= m + h - w[k]; --j)                      dp[m + h] = max(dp[m + h], dp[j] + v[k]);                  ans = max(ans, dp[m + h]);              }              printf("%d\n", ans);          }      }  }
      

 

C-小仙女过生日啦

链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

小仙女过生日啦，好多名人都来了，像是小金刚，凹凸曼，光头强啊。来了那么多人，小仙女羞涩的躲了起来。这时，空气中传来了一缕蛋糕的香气，小仙女再也顾不得羞涩了，冲了出来两眼冒绿光的看着（n边形）蛋糕，小仙女心想：emmmm。。。 人好多啊，自己一个人吃不好啊。可是我想吃大份啊！！！怎么办怎么办！！！小G看到了这一幕，为了让小仙女不能开开心心的吃大的蛋糕，只能是沿着对角线切切(n-3)次，切成三角形，切成（n-2）块把最大的那一块给小仙女，现在想怎么才能让最大的那块蛋糕最小呢。

输入描述:

多组数据输入输出 第一行一个整数n代表多边形的顶点的个数， 下列n行每行两个整数x ，y分别代表点的横纵坐标

输出描述:

每组输出占一行。 输出最大块的蛋糕的面积 s 到浮点数后一位。

示例1

输入

67 06 29 53 50 31 1

输出

9.0

备注:

对于100%的样例, 4<=n<=100; -100<=x,y<=100

 

#include
      
       #include
       
        #include
        
         double len[110][110];double dp[110][110];double px[110],py[110];int n;double max(double a,double b,double c){    if(a>b) b=a;    return b>c?b:c;}double s(int a,int b,int c){    double s1,s2,s3;    if(len[a][b]) s1=len[a][b];    else len[b][a]=len[a][b]=s1=sqrt((px[a]-px[b])*(px[a]-px[b])+(py[a]-py[b])*(py[a]-py[b]));    if(len[b][c]) s2=len[b][c];    else len[c][b]=len[b][c]=s2=sqrt((px[b]-px[c])*(px[b]-px[c])+(py[b]-py[c])*(py[b]-py[c]));    if(len[a][c]) s3=len[a][c];    else len[c][a]=len[a][c]=s3=sqrt((px[a]-px[c])*(px[a]-px[c])+(py[a]-py[c])*(py[a]-py[c]));    double p=(s1+s2+s3)/2;    return sqrt(p*(p-s1)*(p-s2)*(p-s3));}bool jump(int a,int b,int c)//检查三角形中是否有点（三角形是否合法）:({    double s0=s(a,b,c);    for(int k=0;k
        
       
      

 

D-YB要打炉石

链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

Wozuinb非常喜欢打炉石传说，但是菜的不行，所以他决定打竞技场来练练手。系统按顺序给出n张卡牌，每张卡牌都有自己的使用消耗a[i]，每次只给出一张，wozuinb可以选择或者弃掉这张牌。每选择一张牌都会按选择顺序放在卡槽中，当卡槽中放满30张即可组成一套套牌。Wozuinb希望自己的套牌的消耗满足一个平滑的曲线，即30张卡牌都满足第i张卡牌的消耗不小于第i-1张(i>1)。请你帮助wozuinb看一看，这些卡牌能不能组成想要的套牌，如果能组成输出“yes”，如果不能输出“no”。

输入描述:

第一行输入一个整数n，0
     
      <100。 第二行输入一行数字a[i]，每个数字用空格隔开，代表第i张出现的卡牌的消耗。
     

输出描述:

输出一行，“yes”或“no”

示例1

输入

51 2 3 4 5

输出

no

 

#include
      
       using namespace std;typedef long long LL;const int MAXN=1e5+100;int a[105],dp[105];int n;int main(){    scanf("%d",&n);        memset(dp,0,sizeof(dp));        for(int i=1;i<=n;i++){            scanf("%d",&a[i]);        }        dp[1]=a[1];        int len=1;        for(int i=2;i<=n;++i){            if(a[i]>=dp[len])                dp[++len]=a[i];            else{                int pos=lower_bound(dp,dp+len,a[i])-dp;                dp[pos]=a[i];            }        }        //printf("%d\n",len);        printf("%s\n",(len>=30)?"yes":"no");     return 0;}
      

 

E-小G有一个大树

链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

小G想要把自己家院子里的橘子树搬到家门口（QAQ。。就当小G是大力水手吧）可是小G是个平衡性灰常灰常差的人，他想找到一个这个橘子树的平衡点。怎么描述这棵树呢。。。就把它看成由一个个节点构成的树吧。结点数就代表树重。

输入描述:

多组数据输入输出， 第一行包含一个整数n（3<=n<=1000）代表树的结点的个数 以下n-1行描述（1-n）节点间的连接关系。

输出描述:

输出两个个整数 x，num 分别代表树的平衡点，和删除平衡点后最大子树的结点数（如果结点数相同输出编号小的）。

示例1

输入

31 21 3

输出

1 1

 

#include
      
       using namespace std;typedef long long LL; int N; // 1<= N <= 20000const int maxn = 20000;vector
       
         tree[maxn + 5]; // tree[i]表示节点i的相邻节点int d[maxn + 5]; // d[i]表示以i为根的子树的节点个数#define INF 10000000int minNode;int minBalance;void dfs(int node, int parent) // node and its parent{    d[node] = 1; // the node itself    int maxSubTree = 0; // subtree that has the most number of nodes    for (int i = 0; i < tree[node].size(); i++) {        int son = tree[node][i];        if (son != parent) {            dfs(son, node);            d[node] += d[son];            maxSubTree = max(maxSubTree, d[son]);        }    }    maxSubTree = max(maxSubTree, N - d[node]); // "upside substree with (N - d[node]) nodes"     if (maxSubTree < minBalance){        minBalance = maxSubTree;        minNode = node;    }} int main(){    scanf("%d", &N);    for (int i = 1; i <= N - 1; i++){        tree[i].clear();    }    for (int i = 1; i <= N-1; i++){        int u, v;        scanf("%d%d", &u, &v);        tree[u].push_back(v);        tree[v].push_back(u);    }    minNode = 0;    minBalance = INF;    dfs(1, 0); // fist node as root    printf("%d %d\n", minNode, minBalance);    return 0;}
       
      

 

F-德玛西亚万岁

链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。结果比尔吉沃特领土太小，只有长为n宽为m共计n*m块土地，其中有些土地标记为0表示为高山峻岭或者深海湖泊，英雄们无法在其中站立，只有标记为1的土地才能容纳一个英雄。德玛西亚的英雄们战斗时有一个特点，他们不希望队友站在自己旁边显得很暧昧。请问最多能有多少种安排德玛西亚英雄的方法？

输入描述:

输入包含多组测试数据； 每组数据的第一行包含2个整数n和m (n <= 12, m <= 12 )，之间用空格隔开； 接下来的n行，每行m个数，表示n*m的比尔吉沃特领土。

输出描述:

输出一个整数n代表安排应用的方法。 （答案取膜100000000）

示例1

输入

3 31 1 10 1 11 0 0

输出

24

 

#include 
      
       using namespace std;  int n, m;int a[20][20];int h[20];  long long dp[15][80][4100];long long mod = 100000000LL;int cnt[4100], error[4100];  int limit = 75;  int lowbit(int x) {  return x & (-x);}  void init() {  for(int i = 1; i < (1 << 12); i ++) {    cnt[i] = cnt[i - lowbit(i)] + 1;  }  for(int i = 0; i < (1 << 12); i ++) {    for(int j = 0; j < 12; j ++) {      int A = i & (1 << j);      int B = i & (1 << (j + 1));      if(A && B) error[i] = 1;    }  }}  int main() {  init();  while(~scanf("%d%d", &n, &m)) {    for(int i = 1; i <= n; i ++) {      h[i] = 0;      for(int j = 0; j < m; j ++) {        scanf("%d", &a[i][j]);        h[i] = h[i] * 2 + a[i][j];      }    }          dp[0][0][0] = 1;    for(int i = 1; i <= n; i ++) {      for(int num = 0; num <= limit; num ++) {        for(int now = 0; now < (1 << m); now ++) {          dp[i][num][now] = 0;          if(error[now]) continue;          if((now | h[i]) != h[i]) continue;          if(num - cnt[now] < 0) continue;                      for(int pre = 0; pre < (1 << m); pre ++) {            if(pre & now) continue;            dp[i][num][now] = (dp[i][num][now]                               + dp[i - 1][num - cnt[now]][pre]) % mod;          }        }      }    }    long long ans = 0;    for(int num = 0; num <= limit; num ++) {      for(int now = 0; now < (1 << m); now ++) {        ans = (ans + dp[n][num][now]) % mod;      }    }    printf("%lld\n", ans);        }  return 0;}
      

 

G-送分了QAQ

链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

杭州人称傻乎乎的人为62，而嘟嘟家这里没有这样的习俗。相比62，他那里的人更加讨厌数字38，当然啦，还有4这个数字！所以啊，嘟嘟不点都不想见到包含38或者4的数字。每次给出一个区间[n，m],你能找到所有令人讨厌的数字吗？

输入描述:

多组输入输出； 输入的都是整数对n、m（0
     
      <1000000）， 如果遇到都是0的整数对，则输入结束。
     

输出描述:

对于每次的输入 输出全部令人讨厌的数的个数

示例1

输入

1 1000 0

输出

20

 

#include
      
       using namespace std;int a[1000005];int main(){    int n,m;    a[0]=0;    for(int i=1;i<=1000000;i++){        int t=i;        a[i]=a[i-1];        while(t)        {            if(t%10==4) break;            if(t%100==38) break;            t/=10;        }        if(t) a[i]++;    }    while(~scanf("%d%d",&m,&n)){        if(n==0&&m==0) break;        printf("%d\n",a[n]-a[m-1]);    }}
      

 

H-了断局

链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

既然是了断局了，大家就随便玩玩数字呗。已知一个数列前10项分别是 {0, 1, 1, 2, 4, 7, 13, 24, 44, 81}小G不满足呀：我要更多的数！！！不给就不让你们玩了。小G会问你第n项是什么数字，请回答这个顽皮的孩子吧。

输入描述:

多组数据输入输出； 第一行输入一个整数n（1<=n<=50）

输出描述:

输出数列中的第n个数。

示例1

输入

123

输出

011

 

#include
      
       using namespace std;typedef long long LL;LL a[55];LL f(int n){    if(n==1) return a[n]=0;    else if(n==2) return a[n]=1;    else if(n==3) return a[n]=1;    else{        if(a[n]) return a[n];        else return a[n]=f(n-1)+f(n-2)+f(n-3);    }}int main(){    int n;    while(~scanf("%d",&n))    {        printf("%lld\n",f(n));    }}