第十五届北京师范大学程序设计竞赛现场决赛题解&源码(A.思维，C,模拟,水,坑，E,几何,思维，K,字符串处理)...-白红宇

1 #include 
     
       2 using namespace std; 3 int main() 4 { 5     int T,n,a,b; 6     while(cin>>T) 7     { 8         while(T--) 9         {10             cin>>n;11             int ans=1e+6;12             for(int i=1;i<=n-1;i++)13             {14                 cin>>a>>b;15                 ans=min(ans,a+b);16             }17             cout<
      
       <

C. Captcha Cracker

题目大意：给一个字符串，识别出0,2,4,6,9以及英文单词并

按照出现顺序输出。

通过人数/提交人数：60/62

题目解法：直接模拟。

连续两题是因为被卡时卡挂的，精明的出题人，只能说我自己没注意一个细节，然后刚好被出题人卡到这个点，TL.....

1 #include 
     
       2 using namespace std; 3 char s[100010]; 4 int main() 5 { 6     int n; 7     scanf("%d",&n); 8         while(n--) 9         {10             scanf("%s",s);11             int len=strlen(s);12             for(int i=0;i

1 #include 
     
       2 using namespace std; 3 const double pi=acos(-1.0); 4 int main() 5 { 6     int n; 7     int a[4]; 8     scanf("%d",&n); 9     while(n--)10     {11         for(int i=0;i<3;i++)12             scanf("%d",&a[i]);13             sort(a,a+3);14         printf("%.12lf\n",pi*(pow(a[1],2)+pow((a[2]-a[1]),2)));15     }16     return 0;17 }

F. Find Quailty

题目大意：给一个凸多边形，求出从不在多边形内一点?出

发走不超过?距离且不进入多边形内部所能到的区域面积。

通过人数/提交人数：0/3

题目解法：圆面积减去圆和凸多边形交的面积是显然不对的。

如果?不在边界上，过?作两条凸包的切线，那么区域被分为

两部分，其中一部分如下图所示，只需要计算圆和简单多边

形的交，这是个经典的几何模板题。

另一部分面积首先是个大扇形，然后沿着凸多边形的边界从

两侧爬到另一边会得到很多小扇形。

?值足够大的时候会有一些扇形发生相交，需要减去相交部

分的面积

由于从任意一侧爬过去的途中得到的若干小扇形是两两交为

空的，那么两侧小扇形各自并集的交集就是从两侧小扇形任

取两个的交集的并集，于是减去从两侧分别枚举一个小扇形

求交的结果，再减去两侧小扇形与大扇形求交的结果即可。

复杂度是O(n^2).

1 #include
     
       2 using namespace std; 3 #define N 100010 4 unordered_map
      
        mp; 5 int n; 6 bool vis[N]; 7 int main() 8 { 9     int T;10     scanf("%d",&T);11     while(T--)12     {13         memset(vis,0,sizeof(vis));14         scanf("%d",&n);15         char opt[5];string name;16         int x,last=0;17         mp.clear();18         int ans=0,cnt=0;19         while(n--)20         {21             scanf("%s",opt);22             cin>>name;23             if(opt[0]=='i') mp[name]=++cnt;24             else25             {26                 x=mp[name];27                 vis[x]=true;28                 if(x==last+1) ans++;29                 while(vis[last+1]) ++last;30             }31         }32         printf("%d\n",ans);33     }34     return 0;35 }