首页 > 代码库 > 1.19测试题

1.19测试题

1.19测试题

1P1007绕钉子的长绳子(https://vijos.org/p/1007)

背景

平面上有N个圆柱形的大钉子,半径都为R,所有钉子组成一个凸多边形。

现在你要用一条绳子把这些钉子围起来,绳子直径忽略不计。

描述

求出绳子的长度

格式

输入格式

第1行两个数:整数N(1<=N<=100)和实数R。

接下来N行按逆时针顺序给出N个钉子中心的坐标
坐标的绝对值不超过100。

输出格式

一个数,绳子的长度,精确到小数点后2位。

样例1

样例输入1

4 1
0.0 0.0
2.0 0.0
2.0 2.0
0.0 2.0

样例输出1

14.28

限制

各个测试点1s

提示

如果你用比较复杂的方法AC了,请想一想有没有更加简便的方法。

answer=多边形的周长+2*π*r

#include<iostream>#include<cmath>#include<cstdio>#include<algorithm>using namespace std;const double pi=3.14159;int n;long long x1,x2,y3,y2,sx,sy;double a,b,ans,r;void solve(){    ans+=sqrt(abs(x1-x2)*abs(x1-x2)+abs(y3-y2)*abs(y3-y2));}int main(){    cin>>n>>r;    cin>>a>>b;    x1=a*10000;y3=b*10000;    sx=x1;sy=y3;    for(int i=1;i<n;i++)    {        cin>>a>>b;        x2=a*10000;y2=b*10000;        solve();        x1=x2;y3=y2;    }    x2=sx;y2=sy;    solve();    ans/=10000.0;    ans+=(double)2*pi*r;    printf("%.2lf",ans);}

 首次提交得分:30

错误有2:1、实数R存成整数

           2、精度,将原数据*100,以int存

2、洛谷P1276 校门外的树(增强版)

题目描述

校门外马路上本来从编号0到L,每一编号的位置都有1棵树。有砍树者每次从编号A到B处连续砍掉每1棵树,就连树苗也不放过(记 0 A B ,含A和B);幸运的是还有植树者每次从编号C到D 中凡是空穴(树被砍且还没种上树苗或树苗又被砍掉)的地方都补种上树苗(记 1 C D,含C和D);问最终校门外留下的树苗多少棵?植树者种上又被砍掉的树苗有多少棵?

输入输出格式

输入格式:

第一行L和N,表示校园外原来有L+1棵树,并有N次砍树或种树的操作。

以下N行,砍树或植树的标记和范围,每行3个整数。

L(1 <= L <= 10000)和 N(1 <= N <= 100)

输出格式:

共两行。第1行校门外留下的树苗数目,第2行种上又被拔掉的树苗数目。

输入输出样例

输入样例#1

10 3

0 2 6

1 1 8

0 5 7

输出样例#1

3

2

#include<cstring>#include<cstdio>using namespace std;#define N 10010int n,m,a,b,p,ans1,ans2;int tot[N];int have[N];int main(){    scanf("%d%d",&n,&m);    n++;    memset(tot,0,sizeof(tot));    memset(have,1,sizeof(have));    for(int i=1;i<=m;i++)    {        scanf("%d%d%d",&p,&a,&b);        a++;b++;        if(p==0)        {            for(int j=a;j<=b;j++)            if(have[j])            {                 if(have[j]==2)  tot[j]++;                 have[j]=0;            }        }        else        {            for(int j=a;j<=b;j++)                if(!have[j]) have[j]=2;        }     }    for(int i=0;i<=n;i++)    {        if(have[i]==2) ans1++;        ans2+=tot[i];    }    printf("%d\n%d",ans1,ans2);}

 


3、食物链(http://acm.nyist.net/JudgeOnline/problem.php?pid=207)

时间限制:1000 ms  |  内存限制:65535 KB

难度:5

描述

动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。 
现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。 
有人用两种说法对这N个动物所构成的食物链关系进行描述: 
第一种说法是"1 X Y",表示X和Y是同类。 
第二种说法是"2 X Y",表示X吃Y。 
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。 
1) 当前的话与前面的某些真的话冲突,就是假话; 
2) 当前的话中X或Y比N大,就是假话; 
3) 当前的话表示X吃X,就是假话。 
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。 

输入

第一行是两个整数N和K,以一个空格分隔。 
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。 
若D=1,则表示X和Y是同类。 
若D=2,则表示X吃Y。

输出

只有一个整数,表示假话的数目。

样例输入

100 7

1 101 1

2 1 2

2 2 3

2 3 3

1 1 3

2 3 1

1 5 5

样例输出

3

#include<cstdio>using namespace std;#define N 50001int n,k,ans,r1,r2,fa[N*3];int p[N];int x,y,c;int find(int i){    if(fa[i]!=i) fa[i]=find(fa[i]);    return fa[i];}int find2(int i){    if(p[i]!=i) p[i]=find2(p[i]);    return p[i];}void unionn(int k,int l){    fa[k]=l;}void unionn2(int k,int l){    p[k]=l;}int main(){    scanf("%d%d",&n,&k);    for(int i=1;i<=3*n;i++) fa[i]=i;        for(int i=1;i<=n;i++) p[i]=i;    for(int i=1;i<=k;i++)    {        scanf("%d%d%d",&c,&x,&y);        if(x>n||y>n) ans++;        else if(c==2&&x==y) ans++;        else        {            int r1=find2(x),r2=find2(y);            int x1=find(x),x2=find(x+n),x3=find(x+2*n);            int y1=find(y),y2=find(y+n),y3=find(y+2*n);            if(r1==r2)            {                if(c==1)                 {                    if(x1!=y1||x2!=y2||x3!=y3) ans++;                }                else                {                    if(x1!=y2||x2!=y3||x3!=y1) ans++;                }            }            else             {                unionn2(r1,r2);                if(c==1)                 {                    unionn(x1,y1);                    unionn(x2,y2);                    unionn(x3,y3);                }                else                {                    unionn(x1,y2);                    unionn(x2,y3);                    unionn(x3,y1);                }            }        }    }    printf("%d",ans);}

 

 

 

1.19测试题