题
第八周
老和尚与小和尚
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
1
sample output
1
标程
#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;
}
