Codeforces Round #532 (Div. 2)
题目总链接：https://codeforces.com/contest/1100
A. Roman and Browser
题意：
给出由-1和1组成的n个数，现在任意选定一个起点，从起点开始向左向右k个k个地拿走。最后问abs(cnt(-1)-cnt(1))最大是多少。
题解：
由于n和k最多只有100，所以枚举起点直接暴力就好了。
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+;
int n,k;
int a[N];
int main(){
cin>>n>>k;
int ans=;
for(int i=;i<=n;i++) cin>>a[i];
int sum1=,sum2=;
for(int i=;i<=n;i++){if(a[i]==) sum1++;else sum2++;}
for(int b=;b<=k;b++){
int now1=sum1,now2=sum2;
for(int i=b;i<=n;i+=k){
if(a[i]==) now1--;
else now2--;
}
ans=max(ans,abs(now1-now2));
}
cout<<ans;
return ;
}
B. Build a Contest
题意：
给出m个数，每个数不超过n，然后问从1到哪些位置，能包含1-n所有的数各一个。注意的是，每个数只能被用一次，当它被一个位置用了之后，其余的位置就不能用它了。
最后输出的时候，如果目前位置满足条件，则输出1；否则输出-1。
题解：
比赛的时候我些了个玄学复杂度的代码，最后被卡了...
但可以o(m)来做，具体看代码吧...
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+;
int n,m;
int cnt[N],a[N];
int main(){
int num = ;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d",&a[i]);
cnt[a[i]]++;
if(cnt[a[i]]==) num++;
if(num==n){
printf("");
for(int j=;j<=n;j++){
cnt[j]--;
if(!cnt[j]) num--;
}
}else printf("");
}
return ;
}
C. NN and the Optical Illusion
题意：
给出内圆半径以及外接圆的个数，外接圆都与旁边的外接圆相切，求外接圆的半径。
题解：
高中知识正弦定理推一下就出来了。
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double n,r;
int main(){
cin>>n>>r;
double pi;
double now = (double)/n;
now/=;
double Sin = sin(now*3.1415926/);
double tmp = -Sin;
double ans = r*Sin/tmp;
printf("%.8f",ans);
return ;
}
D. Dasha and Chess
题意：
这是一个交互题。题目给出了一个999*999的格子，现在有1个白棋以及666个黑棋。白棋每次只能走向周围的八个空格子，黑棋每次可以任意走。
现在你来执白子先走，如果你要赢，只要你走到一个位置满足白棋和黑棋同一列或者同一行就行了。
现在你每次输出白棋走的位置，然后会给回应：哪个黑子走到哪个位置。
如果最后白棋赢了，应该立即结束程序。
题解：
这题本来白子只能走2000步的，但是其实白棋是一定可以赢的下面就说说为什么。
我们先假设白棋走到了棋盘的中间，即(500,500)处。那么现在整个棋盘都被分为了四个部分，黑棋想要赢，最好就是平均分布。
因为我们假设白棋往左上角走，其实它是可以辐射三个部分的，白棋只需要走499步即可到(1,1)点，即只需要499步可以将三个部分辐射完。
如果哪个部分比较多，那黑棋可能就不能在499步之内将三个部分的黑棋都移到右下角去。
但是这题中666/4 = 166...2，也就是说，至少有一个部分，它的黑棋数是多余平均数的，这也就说明，我们可以选择白棋往四周走。
恰好166*3+2 > 499，那么我们只需要选择黑棋最少的那个反方向走就行了。
我一开始就是这里被坑了...我是直接看哪个方向黑棋最多就往哪走的...
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = ;
struct node{
int x,y;
}b[N];
int ax,ay,End;
int d[];
int vis[N][N];
void query(int x,int y){
printf("%d %d\n",x,y);
fflush(stdout);
int k,nowx,nowy;
scanf("%d%d%d",&k,&nowx,&nowy);
if(k==-){
End=;
exit();
}
vis[b[k].x][b[k].y]=;
b[k].x=nowx;b[k].y=nowy;
vis[nowx][nowy]=;
}
void go_mid(){
while(){
if(ax== && ay==) break ;
if(ax<) ax++;
else if(ax>)ax--;
else if(ay<)ay++;
else if(ay>)ay--;
query(ax,ay);
if(End) return ;
}
}
int main(){
scanf("%d%d",&ax,&ay);
for(int i=;i<=;i++){
scanf("%d%d",&b[i].x,&b[i].y);
vis[b[i].x][b[i].y]=;
}
go_mid();
if(End) return ;
for(int i=;i<=;i++){
int x=b[i].x,y=b[i].y;
if(x<){
if(y<) d[]++;
else d[]++;
}else{
if(y>) d[]++;
else d[]++;
}
}
int max_d,mx=;
for(int i=;i<;i++){
if(d[i]<mx){
mx=d[i];
max_d=i;
}
}
int dx,dy;
if(max_d==) dx=,dy=-;
else if(max_d==) dx=,dy=;
else if(max_d==) dx=-,dy=;
else if(max_d==) dx=-,dy=-;
while(){
int curx=ax+dx;
int cury=ay+dy;
if(vis[curx][cury]){
ax+=dx;
query(ax,ay);
return ;
}
ax=curx;ay=cury;
query(ax,ay);
if(End) return ;
}
return ;
}
E. Andrew and Taxi
题意：
现在给出一个有向无环图，每条边都有相应的边权。
现在你要翻转一些边，使得这个图中不存在环，要求翻转的边的边权最大值最小。
题解：
看到最大值最小，其实应该比较容易想到二分的。
我们就二分答案x，如果边权小于等于x，我们就将先无视这些边；否则我们边加边到新图中。
然后在新图上跑拓扑排序，如若有环，那此时就不合法；如若没有环，就合法。最后根据拓扑序判断就好了。
简略证明一下这样做的正确性：
我们假设无向边连接u,v两个点，而我们跑出来是不存在环的。假设现在无环，那么自然合法；
如果存在环了，如果u的拓扑序小于v的拓扑序，那么必然是另外一条路径产生环，设其为u->v->...->w->u，我们来分析w->u这条边。
首先可以知道w->u这条边不可能在新图中，所以之前也是一条无向边，如果我们连w->u，说明w的拓扑序要小于u，又因为v到w，所以v的拓扑序小于w，又根据我们的假设，u的拓扑序小于v，这就存在矛盾了。
以上，就是简略的证明，主要还是结合拓扑序的性质。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+;
int n,m,tot;
int head[N],in[N],bfn[N],tmp[N];
struct Edge{
int u,v,w,id;
bool operator < (const Edge&A)const{
return w<A.w;
}
}edge[N];
struct EDGE{
int u,v,next;
}e[N];
void adde(int u,int v){
e[++tot].v=v;e[tot].u=u;e[tot].next=head[u];head[u]=tot;
}
bool check(int x){
memset(head,-,sizeof(head));tot=;
memset(in,,sizeof(in));memset(bfn,,sizeof(tmp));
for(int i=;i<=m;i++){
if(edge[i].w>x){
adde(edge[i].u,edge[i].v);
in[edge[i].v]++;
}
}
queue <int> q;
int cnt = ;
for(int i=;i<=n;i++) if(!in[i]) q.push(i),bfn[i]=++cnt;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i!=-;i=e[i].next){
int v=e[i].v;
in[v]--;
if(!in[v]) q.push(v),bfn[v]=++cnt;
}
}
if(cnt<n) return false;
return true;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
edge[i]={u,v,w,i};
}
sort(edge+,edge++m);
int l = , r = 1e9+,mid;
int ans=;
while(l<r){
mid=(l+r)>>;
if(check(mid)){
r=mid;
ans=mid;
}else l=mid+;
}
check(ans);
tot=;
printf("%d",ans);
for(int i=;i<=m;i++){
int u=edge[i].u,v=edge[i].v,w=edge[i].w;
if(bfn[u]>bfn[v] && w<=ans){
tmp[i]=;
tot++;
}
}
printf(" %d\n",tot);
for(int i=;i<=m;i++){
if(tmp[i]) printf("%d ",edge[i].id);
}
return ;
}