1.19 测试题
1、P1007 绕钉子的长绳子(https://vijos.org/p/1007)
平面上有 N 个圆柱形的大钉子,半径都为 R, 所有钉子组成一个凸多边形。
现在你要用一条绳子把这些钉子围起来,绳子直径忽略不计。
求出绳子的长度
第 1 行两个数:整数 N(1<=N<=100) 和实数 R。
接下来 N 行按逆时针顺序给出 N 个钉子中心的坐标
坐标的绝对值不超过 100。
一个数,绳子的长度,精确到小数点后 2 位。
- 4 1
- 0.0 0.0
- 2.0 0.0
- 2.0 2.0
- 0.0 2.0
- 14.28
各个测试点 1s
如果你用比较复杂的方法 AC 了,请想一想有没有更加简便的方法。
answer = 多边形的周长 + 2*π*r
- #include#include#include#include 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) {
- 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
- #include
- using namespace std;
- #define N 10010
- int 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);
- }
时间限制: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
- using namespace std;
- #define N 50001
- int 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);
- }
来源: http://www.bubuko.com/infodetail-1971973.html