链接：https://codeforces.com/contest/1100
A - Roman and Browser - [暴力枚举]
题意：浏览器有 $n$ 个网页，编号 $1 \sim n$，选择一个整数 $b$，则关掉所有编号为 $b + i \cdot k$ 的网页，其中 $k$ 为给定的整数，$i$ 为任意整数。然后，留下的网页有两种类型，计算两种类型的网页数目差，要求你给出这个差最大可以是多少。
题解：$n$ 的范围很小，可以直接纯暴力做即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int n,k;
int type[maxn],del[maxn];
int main()
{
ios::sync_with_stdio();
cin.tie(), cout.tie(); cin>>n>>k;
for(int i=;i<=n;i++) cin>>type[i];
int ans=;
for(int b=;b<=k;b++)
{
memset(del,,sizeof(int)*(n+));
for(int i=b;i<=n;i+=k) del[i]=;
int c1=, c2=;
for(int i=;i<=n;i++) if(!del[i]) c1+=(type[i]==), c2+=(type[i]==-);
ans=max(ans,abs(c1-c2));
}
cout<<ans<<endl;
}
B - Build a Contest - [计数+简单维护][线段树]
题意：有一个“问题池”，每次都想一个新问题，估计其难度为 $x (1 \le x \le n)$，把这个问题扔进问题池，如果问题池内的问题正好能搞出一套难度系数为 $1 \sim n$ 的 $n$ 道题，就把他们全部取出来。对每次想出来的新问题，确定其扔进池中后，能否产生一套题。
题解1：不难知道，用一个数组 $c[1:n]$ 存储每个难度的题目数，再用一个变量 $cnt$ 记录有多少个难度上是有题目的。如果产生了一套题目，必然是某一个难度的题的数目从 $0$ 变成了 $1$。这样做是 $O(m)$ 的时间复杂度。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
int n,m;
int cnt,c[maxn];
int main()
{
ios::sync_with_stdio();
cin.tie(), cout.tie(); cin>>n>>m;
cnt=;
for(int i=,p;i<=m;i++)
{
cin>>p;
c[p]++;
if(c[p]==)
{
cnt++;
if(cnt==n)
{
cout<<;
for(int k=;k<=n;k++) if((--c[k])==) cnt--;
}
else cout<<;
}
else cout<<;
}
}
题解2：无脑上线段树，单点修改、区间查询，如果产生了一套题目，就暴力的对每个难度点上都减去 $1$，时间复杂度是 $O(mlogn)$（因为最多产生 $O(m/n)$ 套题目）。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
int n,m;
int cnt; #define ls (rt<<1)
#define rs (rt<<1|1)
struct Node{
int l,r;
int val,ok;
}o[maxn<<];
void pushup(int rt)
{
o[rt].val=o[ls].val+o[rs].val;
o[rt].ok=o[ls].ok&o[rs].ok;
}
void build(int rt,int l,int r)
{
o[rt].l=l, o[rt].r=r;
if(l==r)
{
o[rt].val=o[rt].ok=;
return;
}
int mid=(l+r)>>;
build(ls,l,mid), build(rs,mid+,r);
pushup(rt);
}
void update(int rt,int pos,int val)
{
if(o[rt].l==o[rt].r)
{
o[rt].val+=val;
o[rt].ok=o[rt].val>;
return;
}
int mid=(o[rt].l+o[rt].r)>>;
pos<=mid?update(ls,pos,val):update(rs,pos,val);
pushup(rt);
} int main()
{
ios::sync_with_stdio();
cin.tie(), cout.tie(); cin>>n>>m;
build(,,n); cnt=;
for(int i=,p;i<=m;i++)
{
cin>>p;
update(,p,);
if(o[].ok)
{
cout<<;
for(int k=;k<=n;k++) update(,k,-);
}
else cout<<;
}
}
C - NN and the Optical Illusion - [很水的计算几何题]
题意：给出一个圆，半径为 $r$，其周围有 $n$ 个完全相同的圆将其包围，这 $n$ 个圆分别和中心圆互相紧贴，且这 $n$ 个圆构成一个环，环上任意两个相邻的圆也都是紧贴的。要求你求出这 $n$ 个圆的半径 $R$。
题解：$\sin(\frac{\pi}{n}) \cdot (R+r) = R$。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-);
int n;
double r,R;
int main()
{
cin>>n>>r;
R=sin(pi/n)*r;
R/=(-sin(pi/n));
printf("%.8f\n",R);
}
D - Dasha and Chess - []
题意：