====== codeforces educational round 87(div2) ======
===== A =====
题意:大 模 拟
题解:题目比较长,理清逻辑关系即可,没什么好说的……
#include
using namespace std;
int main()
{
int t,a,b,c,d;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
if(b>=a)
{
printf("%d\n",b);
continue;
}
else
{
int res=a-b;
if(d>=c)
{
printf("-1\n");
continue;
}
else
{
int t=ceil((double)res/(c-d));
printf("%lld\n",1ll*t*c+1ll*b);
}
}
}
}
===== B =====
题意:给定一个只由1 2 3组成的字符串,问取该字符串的一段连续字串,至少要取多长的字串才能满足子串中既有1也有2还有3。
题解:首先判断是否三个数都出现了,若没有都出现,直接就可以判定不成立。然后,最不动脑经的做法,就是从第一个开始模拟,找出每一段连续的且同为一个字符的串,观察该串开头的左边和末尾的右边的字符是否为同一个,若不是则为一种情况。复杂度O(n)
#include
using namespace std;
const int maxn=2e5+13;
char s[maxn];
int flag[4];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
for(int i=1;i<=3;i++) flag[i]=0;
int ans=0x7fffffff;
int yes=1;
scanf("%s",s+1);
int len=strlen(s+1);
for(int i=1;s[i];i++)
{
flag[s[i]-'0']=1;
}
for(int i=1;i<=3;i++)
{
if(!flag[i]) yes=0;
}
if(!yes) {
printf("0\n");continue;}
int k=1,st;
while(s[k]==s[1]) k++;
st=k-1;
for(int i=k;i<=len;i++)
{
int j=i;
while(s[j]==s[i]) j++;
if(j>len) {
break;}
if(s[j]!=s[st]) ans=min(ans,j-i+2);
st=j-1;
i=st;
}
printf("%d\n",ans);
}
}
===== C1 =====
题意:给一个边长全部都为1的正2*n边形,这里n取偶数,要求一个正方形完全盖住这个正2*n边形,问最小边长是什么。
题解:如果n是偶数我们能够比较容易的看出合法的情况为下图
{{:2020-2021:teams:manespace:img_20200524_202525.jpg?400|}}
则很容易得出答案为 $\frac{1}{\tan\frac{\pi}{2n}}$
#include
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);
}
}
===== 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}}$
#include
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);
}
}
===== D =====
题意:给一系列数,每个数都满足小于等于n,每次可能进行两个操作,一种操作为将k插入序列,第二种操作为将第k个数消去。问k个操作后是否还有数。
题解:注意一下空间限制,这个限制不能用平衡树,不然死的很惨……,可以利用权值线段树,空间复杂度0(2n),可以满足。
#include
#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));
}