题

第八周

老和尚与小和尚

problem description

从前有个老和尚对小和尚讲故事，他说他早上看到一个年轻男子赶着n头牛，在农田里耕种，突然下起了大雨，年轻男子怕牛着凉了，就打算把它们安排到几个各自分开的草棚下面避雨，他一共有q次操作，每次操作都将牛Xi与牛Yi所在的草棚合并在一起，对于n头牛，编号分别为1,2,3,...,n。

多组输入。对于每组测试数据，第一行包含两个整数n,m，表示n头牛，m次操作，接下来m行，每行包括三个整数Zi,Xi,Yi,当Zi=1时，将牛Xi与牛Yi所在的草棚合并在一起，当Zi=2时，请输出牛Xi和牛Yi是否在一个草棚，是的输出"Yes",否则输出"No"（不包含双引号）。（1<=n<=10000,1<=m<=200000）

对于Zi=2时，输出"Yes"或"No"（不包含双引号）。行末换行。

sample input

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

sample output

No
Yes
No
Yes

标程

#include <bits/stdc++.h>

using namespace std;

bool check(string a,string b){
    if(a.size()!=b.size())
    return a.size()>b.size();
    int p=0;
    while(p<(a.size())&&a[p]==b[p])
    p++;
    if(p==a.size()||a[p]>b[p])//a>=b为true 
    return true;
    else
    return false;
}
int ans[20010],len;
string a,b;
void work(){
    int jw=0,i,j;
    for(i=a.size()-1,j=b.size()-1;i>=0&&j>=0;i--,j--){
        if(a[i]-b[j]+jw<0)
        ans[len++]=10+jw+(a[i]-b[j]),jw=-1;
        else
        ans[len++]=a[i]-b[j]+jw,jw=0;
    }
    for(;i>=0;i--)
    if(a[i]-'0'+jw<0)
    ans[len++]=10+jw+a[i]-'0',jw=-1;
    else
    ans[len++]=jw+a[i]-'0',jw=0;
}
int main(){
    while(cin>>a>>b){
        int flag=0;
        if(!check(a,b))
        swap(a,b),flag=1;
        memset(ans,0,sizeof(ans));
        len=0;
        work();
        if(flag)
        cout<<"-";
        int flag2=0;
        for(int i=len-1;i>=0;i--){
            if(ans[i]!=0)
            flag2=1;
            if(flag2)
            cout<<ans[i];
        }
        if(!flag2)
        cout<<0;
        cout<<"\n";
    }
}

高飞学长的多边形

problem description

高飞学长最喜欢的几何图形是规则的多面体。请注意，有五种规格的多面体：
四面体。四面体有4个三角形面。
立方体。多维数据集具有6个正方形的面。
八面体。八面体有8个三角形面。
十二面体。十二面体有12个五边形的面。
二十面体。二十面体有20个三角形面。
高飞学长有n个多面体。一天，他想知道他的多面体总共有多少个面。帮助高飞学长，找到答案！

多组输入，输入的第一行包含一个整数n（1≤n≤200000）表示青竹学长拥有的多面体的数量。
接下来n行中的每一行都包含字符串Si表示青竹学长多面体中第i个多面体的名称。该字符串可以如下所示：
如果青竹学长手中的第i个多面体是四面体，则为“Tetrahedron”（不带引号）。
如果青竹学长手中的第i个多面体为立方体，则为“Cube”（不带引号）。
如果青竹学长手中的第i个多面体是八面体，则为“Octahedron”（不带引号）。
如果青竹学长手中的第i个多面体是十二面体，则为“Dodecahedron”（不带引号）。
如果青竹学长手中的第i个多面体是二十面体，则为“Icosahedron”（不带引号）。

行末换行，输出一个数字表示青竹学长拥有的所有多面体的总面数。

sample input

4
Icosahedron
Dodecahedron
Tetrahedron
Cube
3
Dodecahedron
Octahedron
Octahedron

sample output

42
28

标程

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
    int ans=0;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        if(s=="Tetrahedron")
            ans+=4;
        if(s=="Cube")
            ans+=6;
        if(s=="Octahedron")
            ans+=8;
        if(s=="Dodecahedron")
            ans+=12;
        if(s=="Icosahedron")
            ans+=20;
         }
         cout<<ans<<endl;
    }
    return 0;
}

公式求和

problem description

已知：Sn= 2+2/2+2/3+2/4+…+2/n。
现给出一个整数k，要求计算出一个最小的n，使得 Sn>k，保证总能满足该条件。（Sn结果应为浮点型）

多组输入，每行一个正整数k(1<=k<=30)

一个正整数n，行末换行。

sample input

sample output

标程

#include <bits/stdc++.h>

using namespace std;

int main(){
    int k,n;
    while(cin>>k){
        double ans=0;
        n=0;
        for(;ans<=k;++n,ans+=2.0/n);
        cout<<n<<endl;
    }
    return 0;
}

Bernard的遗传密码

problem description

Bernard正在设计一种新型细菌的遗传密码，以有效地生产疫苗。具体来说，Bernard专注于编码一种蛋白质的DN***段。 DN***段由仅包含字符“ A”，“ T”，“ G”和“ C”的字符串表示。
Bernard已确定，如果DN***段中某一段的最大连续相同核苷酸的序列长度为偶数，则该蛋白质将无功能。例如，由DNA字符串“ GTTAAAG”描述的蛋白质。它包含四个最大的连续相同核苷酸序列：“ G”，“ TT”，“ AAA”和“ G”。该蛋白质是无功能的，因为序列“ TT”具有偶数长度。
Bernard正在尝试从他目前拥有的蛋白质中获得功能性蛋白质。 Bernard可以在DN***段中插入其他核苷酸。每个其他核苷酸都是{'A'，'T'，'G'，'C'}中的一个字符。 Bernard希望确定使DNA编码功能蛋白所需的最小插入次数。

多组输入，其中包含长度为n（1≤n≤100）的字符串s。 s的每个字符都来自集合{'A'，'T'，'G'，'C'}。

输出一个整数表示使DNA能够编码功能蛋白所需的最小插入次数。行末换行

sample input

GTTAAAG
AACCAACCAAAAC

sample output

1
5

标程

#include <bits/stdc++.h>

using namespace std;

int main () {
  string s;  
  while(cin>>s){
      int n, sum, res;
      n=sum=res=0;
      for(int i = 0; i < s.size(); i++){
        sum++;
        if(s[i] != s[i+1]){
            if(sum % 2 == 0){
                res++;
            }
            sum = 0;
        }
    }
    cout<<res<<endl;
  }
  return 0;
}

⑨的网格

problem description

sample input

1 1
2 3

sample output

0
14

标程

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
typedef long long ll;

int main() {
    ll i,j,m,n,t,sum;
    while(cin>>m>>n) {
        sum=0;
        for(i=2; i<=n; i+=2)
            for(j=2; j<=m; j+=2)
                sum+=(n-i+1)*(m-j+1);
        sum *= 2;
        for(ll y = 2; y <= m; y += 2) {
            sum += (n + 1) * (m - y + 1);
        }
        for(ll y = 2; y <= n; y += 2) {
            sum += (m + 1) * (n - y + 1);
        }
        cout<<sum<<endl;
    }
    return 0;
}