2020-2021:teams:manespace:codeforces_educational_round_87_div2

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:manespace:codeforces_educational_round_87_div2 [2020/05/24 18:33]
iuiou 创建
+++ 2020-2021:teams:manespace:codeforces_educational_round_87_div2 [2020/05/24 21:21] (当前版本)
iuiou
@@ 行 92: / 行 92: @@
 ===== C1 =====
 题意：给一个边长全部都为1的正2*n边形，这里n取偶数，要求一个正方形完全盖住这个正2*n边形，问最小边长是什么。
+题解：如果n是偶数我们能够比较容易的看出合法的情况为下图
+{{:2020-2021:teams:manespace:img_20200524_202525.jpg?400|}}
+则很容易得出答案为 $\frac{1}{\tan\frac{\pi}{2n}}$
+<hidden>
+<code c++>
+#include <bits/stdc++.h>
+using namespace std;
+const double pi=3.1415926535;
+int main()
+{
+	int t;
+	scanf("%d",&t);
+	while(t--)
+	{
+		int n;
+		scanf("%d",&n);
+		n*=2;
+		double ans=1.0/(tan(pi/((double)n)));
+		printf("%.10lf\n",ans);
+	}
+ }
+</code>
+</hidden>
+===== C2 =====
+题意：将上述题的n改成奇数
+题解：如图
+{{:2020-2021:teams:manespace:owilt40_08lns_7ctj9c_l.png?400 |}}
+利用对称性，发现当n是奇数时我们可以发现当正多边形在旋转时具有一个对称性，我们旋转$\frac{\pi}{2n}$时，图形会变为原来的状态。则我们不难发现当旋转为一半，即为$\frac{\pi}{4n}$，可以达到最大，那么我们有几何关系可以得到答案为$\frac{\cos\frac{\pi}{4n}}{\sin\frac{\pi}{2n}}$
+<hidden>
+<code c++>
+#include <bits/stdc++.h>
+using namespace std;
+const double pi=3.1415926535;
+int main()
+{
+	int t;
+	scanf("%d",&t);
+	while(t--)
+	{
+		int n;
+		scanf("%d",&n);
+		double x=pi/(4.0*n);
+		double ans=1.0/(2*sin(x));
+		printf("%.10lf\n",ans);
+	}
+}
+</code>
+</hidden>
+===== D =====
+题意：给一系列数，每个数都满足小于等于n，每次可能进行两个操作，一种操作为将k插入序列，第二种操作为将第k个数消去。问k个操作后是否还有数。
+题解：注意一下空间限制，这个限制不能用平衡树，不然死的很惨……，可以利用权值线段树，空间复杂度0(2n),可以满足。
+<hidden>
+<code c++>
+#include <bits/stdc++.h>
+#define mid (l+r)/2
+const int maxn=1e6+13;
+using namespace std;
+int p=0;
+int lc[maxn<<1],rc[maxn<<1];
+int val[maxn<<1];
+void modify(int l,int r,int &rt,int lo,int add)
+{
+	if(!rt) rt=++p;
+	if(l==r)
+	{
+		val[rt]+=add;
+		return;
+	}
+	if(lo<=mid) modify(l,mid,lc[rt],lo,add);
+	else modify(mid+1,r,rc[rt],lo,add);
+	val[rt]=val[lc[rt]]+val[rc[rt]];
+}
+int find(int l,int r,int rt,int k)
+{
+	if(l>=r) return l;
+	if(val[lc[rt]]>=k)
+	{
+		return find(l,mid,lc[rt],k);
+	}
+	else
+	{
+		return find(mid+1,r,rc[rt],k-val[lc[rt]]);
+	}
+}
+int main()
+{
+	int rt=0,n,m,cnt=0;
+	int x;
+	scanf("%d%d",&n,&m);
+	for(int i=1;i<=n;i++)
+	{
+		scanf("%d",&x);
+		modify(1,n,rt,x,1);
+		cnt++;
+	}
+	for(int i=1;i<=m;i++)
+	{
+		scanf("%d",&x);
+		if(x>0)
+		{
+			modify(1,n,rt,x,1);
+			cnt++;
+		}
+		else
+		{
+			int k=find(1,n,rt,-x);
+			modify(1,n,rt,k,-1);
+			cnt--;
+		}
+	}
+	if(cnt==0) printf("0");
+	else printf("%d",find(1,n,rt,1));
+ }
+</code>
+</hidden>

2020-2021/teams/manespace/codeforces_educational_round_87_div2.1590316399.txt.gz · 最后更改: 2020/05/24 18:33 由 iuiou