Codeforces Gym100495 B、D、E、F、K

http://codeforces.com/gym/100495

K题 草地的面积减去相交的面积，计算几何，垃圾题，避免不必要的计算损失精度（能约分的约分）

卡了老子一个星期了 再加前几天的一道题 这一星期真的是难受 什么都没干

AC代码

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <sstream>
 7 #include <algorithm>
 8 #include <string>
 9 #include <queue>
10 #include <map>
11 #include <vector>
12 using namespace std;
13 const int maxn = 1e3+50;
14 const int maxm = 1e4+10;
15 const int inf = 0x3f3f3f3f;
16 const int mod = 998244353;
17 const double epx = 1e-10;
18 typedef long long ll;
19 const ll INF = 1e18;
20 const double pi = acos(-1.0);
21 int main()
22 {
23     int t,kase=1;
24     double x1,y1,r1,x2,y2,r2;
25     cin>>t;
26     while(t--)
27     {
28         scanf("%lf %lf %lf %lf %lf %lf",&x1,&y1,&r1,&x2,&y2,&r2);
29         double len=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
30         double ans;
31         if(len>=r1+r2)
32         {
33             ans=r1*r1*pi;
34         }
35         else if(fabs(r1-r2)>=len)
36         {
37             if(r1>r2)
38                 ans=pi*r1*r1-pi*r2*r2;
39             else
40                 ans=0;
41         }
42         else
43         {
44             double a1=acos((len*len+r1*r1-r2*r2)/(2*len*r1));
45             double a2=acos((len*len+r2*r2-r1*r1)/(2*len*r2));
46             double area1=a1*r1*r1;
47             double area2=a2*r2*r2;
48             double area3=len*r1*sin(a1);
49             ans=pi*r1*r1-(area1+area2-area3);
50         }
51         printf("Case #%d: %.8lf
",kase++,ans);
52     }
53 }
54 close
View Code

给出被卡一万年的K的代码

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <sstream>
 7 #include <algorithm>
 8 #include <string>
 9 #include <queue>
10 #include <map>
11 #include <vector>
12 using namespace std;
13 const int maxn = 1e3+50;
14 const int maxm = 1e4+10;
15 const int inf = 0x3f3f3f3f;
16 const int mod = 998244353;
17 const double epx = 1e-10;
18 typedef long long ll;
19 const ll INF = 1e18;
20 const double pi = acos(-1.0);
21 int main()
22 {
23     int t,kase=1;
24     double x1,y1,r1,x2,y2,r2;
25     cin>>t;
26     while(t--)
27     {
28         scanf("%lf %lf %lf %lf %lf %lf",&x1,&y1,&r1,&x2,&y2,&r2);
29         double len=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
30         double ans;
31         if(len>=r1+r2)
32         {
33             ans=r1*r1*pi;
34         }
35         else if(fabs(r1-r2)>=len)
36         {
37             if(r1>r2)
38                 ans=pi*r1*r1-pi*r2*r2;
39             else
40                 ans=0;
41         }
42         else
43         {
44             double a1=2.0*acos((len*len+r1*r1-r2*r2)/(2*len*r1));
45             double a2=2.0*acos((len*len+r2*r2-r1*r1)/(2*len*r2));
46             double area1=0.5*a1*r1*r1;
47             double area2=0.5*a2*r2*r2;
48             double area3=len*r1*sin(a1);
49             ans=pi*r1*r1-(area1+area2-area3);
50         }
51         printf("Case #%d: %.11lf
",kase++,ans);
52     }
53 }
View Code

B题  把每个字符串开头和结尾中间的字符排序，用map标记一下 然后在判断是否出现过就好了

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <sstream>
 7 #include <algorithm>
 8 #include <string>
 9 #include <queue>
10 #include <map>
11 #include <vector>
12 using namespace std;
13 const int maxn = 1e3+50;
14 const int maxm = 1e4+10;
15 const int inf = 0x3f3f3f3f;
16 const int mod = 998244353;
17 const double epx = 1e-10;
18 typedef long long ll;
19 const ll INF = 1e18;
20 const double pi = acos(-1.0);
21 string s;
22 int ans[maxn];
23 int main()
24 {
25     int n,m,t,kase=1;
26     cin>>t;
27     while(t--)
28     {
29         map<string,int> mp;
30         cin>>n>>m;
31         for(int i=0;i<n;i++)
32         {
33             cin>>s;
34             int len=s.length();
35             if(len>2)
36                 sort(s.begin()+1,s.end()-1);
37             //cout<<len<<" "<<s<<endl;
38             mp[s]++;
39         }
40         for(int i=0;i<m;i++)
41         {
42             cin>>s;
43             int len=s.length();
44             if(len>2)
45                 sort(s.begin()+1,s.end()-1);
46             //cout<<len<<" "<<s<<endl;
47             if(mp[s]>0)
48                 ans[i]=1;
49             else
50                 ans[i]=0;
51         }
52         printf("Case #%d: ",kase++);
53         for(int i=0;i<m;i++)
54             cout<<ans[i];
55         cout<<endl;
56     }
57 }
View Code

E题  可以推出要求子串满足min+a>=max 的最大长度  尺取法 右端点从左端点开始推进  直到右端点不符合条件

　　　再从左端点开始到右端点找最值 并且不断推进左端点 直到满足条件 再向右推进

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <sstream>
 7 #include <algorithm>
 8 #include <string>
 9 #include <queue>
10 #include <map>
11 #include <vector>
12 using namespace std;
13 const int maxn = 1e5+50;
14 const int maxm = 1e4+10;
15 const int inf = 0x3f3f3f3f;
16 const int mod = 998244353;
17 const double epx = 1e-10;
18 typedef long long ll;
19 const ll INF = 1e18;
20 int s[maxn];
21 int main()
22 {
23     int t,a,n,kase=1;
24     scanf("%d",&t);
25     while(t--)
26     {
27         scanf("%d %d",&n,&a);
28         memset(s,0,sizeof(s));
29         for(int i=1;i<=n;i++)
30             scanf("%d",&s[i]);
31         int len=1;
32         int l=1,maxx,minn;
33         maxx=minn=s[l];
34         for(int r=1;r<=n;)
35         {
36             if(minn+a>=maxx)
37             {
38                 len=max(len,r-l+1);
39                 r++;
40                 if(r>n)
41                     break;
42                 maxx=max(maxx,s[r]);
43                 minn=min(minn,s[r]);
44             }
45             else
46             {
47                 if(s[r]==maxx)
48                 {
49                     while(minn+a<maxx)
50                     {
51                         int tempmin=s[r];
52                         for(int i=l+1;i<=r;i++)
53                             tempmin=min(tempmin,s[i]);
54                         minn=tempmin;
55                         l++;
56                     }
57                 }
58                 else if(s[r]==minn)
59                 {
60                     while(minn+a<maxx)
61                     {
62                         int tempmaxx=s[r];
63                         for(int i=l+1;i<=r;i++)
64                             tempmaxx=max(tempmaxx,s[i]);
65                         maxx=tempmaxx;
66                         l++;
67                     }
68                 }
69             }
70             //cout<<"l="<<l<<" r="<<r<<" min="<<minn<<" max="<<maxx<<endl;
71         }
72         printf("Case #%d: %d
",kase++,len);
73     }
74 }
75 close
View Code

D题 水题 边乘边取模

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <sstream>
 7 #include <algorithm>
 8 #include <string>
 9 #include <queue>
10 #include <map>
11 #include <vector>
12 using namespace std;
13 const int maxn = 1e6+10;
14 const int maxm = 1e4+10;
15 const int inf = 0x3f3f3f3f;
16 const int mod = 998244353;
17 const double epx = 1e-10;
18 typedef long long ll;
19 const ll INF = 1e18;
20 ll n,m;
21 char a[maxn];
22 int sum[maxn];
23 int sushu(int x)
24 {
25    for(int i=2;i<n;i++)
26         if(x%i==0)
27             return 0;
28    return 1;
29 }
30 int poww(int x,int y,int z)
31 {
32     int ans=1;
33     for(int i=1;i<=y;i++)
34         ans=(ans*x)%n;
35     return ans;
36 }
37 int main()
38 {
39     int t;
40     cin>>t;
41     int kase=1;
42     while(t--)
43     {
44         cin>>n;
45         if(n==1)
46             printf("Case #%d: %d
",kase,n);
47         else if(sushu(n))
48         {
49             printf("Case #%d: %d
",kase,poww(2,n-1,n)%n);
50         }
51         else
52             printf("Case #%d: %d
",kase,poww(n-1,2,n)%n);
53         kase++;
54     }
55 }
56 close
View Code

F题  一遍dfs回溯，记录最大深度就好了

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <sstream>
 7 #include <algorithm>
 8 #include <string>
 9 #include <queue>
10 #include <map>
11 #include <vector>
12 using namespace std;
13 const int maxn = 1e3+50;
14 const int maxm = 1e4+10;
15 const int inf = 0x3f3f3f3f;
16 const int mod = 998244353;
17 const double epx = 1e-10;
18 typedef long long ll;
19 const ll INF = 1e18;
20 char a[maxn][maxn];
21 int visit[maxn][maxn];
22 int n,m,k;
23 int sum,flag;
24 int dire[4][2]= {{1,0},{-1,0},{0,-1},{0,1}};
25 void dfs(int x,int y)
26 {
27     visit[x][y]=1;
28     for(int i=0; i<4; i++)
29     {
30         int x1=(x+dire[i][0]+n)%n;
31         int y1=(y+dire[i][1]+m)%m;
32         //printf("x=%d y=%d x1=%d y1=%d sum=%d c=%c
",x,y,x1,y1,sum,a[x1][y1]);
33         if(visit[x1][y1]==0&&a[x1][y1]!='#'&&a[x1][y1]!='x')
34         {
35             if(a[x1][y1]=='o')
36             {
37                 dfs(x1,y1);
38                 visit[x1][y1]=0;
39             }
40             else if(a[x1][y1]=='.')
41             {
42                 sum++;
43                 if(sum>=k)
44                     flag=1;
45                 dfs(x1,y1);
46                 visit[x1][y1]=0;
47                 sum--;
48             }
49         }
50     }
51 }
52 int main()
53 {
54     int t,kase=1;
55     cin>>t;
56     while(t--)
57     {
58         cin>>n>>m>>k;
59         for(int i=0; i<n; i++)
60             cin>>a[i];
61         int x,y;
62         for(int i=0; i<n; i++)
63             for(int j=0; j<m; j++)
64                 if(a[i][j]=='x')
65                     x=i,y=j;
66 //        cout<<x<<" "<<y<<endl;
67 //        for(int i=0;i<4;i++)
68 //            cout<<dire[i][0]<<" "<<dire[i][1]<<endl;
69         memset(visit,0,sizeof(visit));
70         flag=0;sum=1;dfs(x,y);
71 //        for(int i=0;i<n;i++)
72 //        {
73 //            for(int j=0;j<m;j++)
74 //            {
75 //                cout<<visit[i][j]<<" ";
76 //            }
77 //            cout<<endl;
78 //        }
79         if(flag==1)
80             printf("Case #%d: Fits perfectly!
",kase++);
81         else
82             printf("Case #%d: Oh no, snake's too fat!
",kase++);
83     }
84 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/stranger-/p/8597880.html