layout: post
title: Codeforces Round #532 (Div. 2)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
A. [A - Roman and Browser(水题)
题意
太水不想写
B.Build a Contest (水题)
题意
给出一个n,m, 接下来吗每一时刻出现m个数,如果在某一时刻N种数字都出现过就输出'1'并同时把1-n种数字各删去一个
题解
很明显和每个数出现的最小值有关,如果出现数的最小值都大于等于1代表这n个数都出现过了,那么如何解决删去呢,如果每时刻都判断每个数都是否大于1就太浪费时间了,我们可以用个变量记录已经出现了多少个数,如果达到n再删去,这样复杂度并不会达到(n*m);
同时也可以换方向,如果我不删去呢?
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int a[maxn],mx[maxn];
int flag[maxn];
set<int>st;
int num[maxn];
double pi=acos(-1.0);
void update(int now,int l,int r,int pos){
if(l==r){
mx[now]++;
return;
}
int mid=(l+r)/2;
if(pos<=mid)update(now<<1,l,mid,pos);
else update(now<<1|1,mid+1,r,pos);
mx[now]=min(mx[now<<1],mx[now<<1|1]);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,m;
cin>>n>>m;
int k=1;
for(int i=1;i<=m;i++)cin>>a[i];
for(int i=1;i<=m;i++){
update(1,1,n,a[i]);
if(mx[1]==k)k++,cout<<1;
else cout<<0;
}
return 0;
}
//
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=69;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int a[maxn];
int aa[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,m;
cin>>n>>m;
int now=1;
for(int i=1;i<=m;i++){
int p;
cin>>p;
a[p]++;
aa[a[p]]++;
if(aa[now]>=n){
cout<<1;now++;
}
else cout<<0;
}
return 0;
}
C.NN and the Optical Illusion (简单几何)
一个圆均匀得被许多大小相等的小圆包围给你小圆个数和小圆半径 让你求出大圆半径.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=69;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int sx,sy;
struct node{
int x,y;
int id;
}my[700];
double pi=acos(-1.0);
int main()
{
/* std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);*/
// cin>>sx>>sy;
// for(int i=1;i<=666;i++)cin>>my[i];
double n,r;
cin>>n>>r;
printf("%.7f
",sin(pi/n)*r/(1.0-sin(pi/n)));
return 0;
}
D.Dasha and Chess (鸽笼定理)
题意
你操控白棋可以八连通走动,电脑操控黑棋会直接跳到任意没棋的格子,
如果你操纵白棋走到和某个黑棋的行或者列你就赢了
棋盘999*999,黑棋个数666个
题解
首先666/4=166.5
先把棋子挪到中间,这时棋子就会分布在四个方位中,假设最分散的情况 比较多的三个方位中的棋子数肯定是大于或者等于666-166=500个的
然后让棋子往最多棋子的那三个方向中的对角线的走去,因为棋子每次移动都向三个方向都移动一格,相当于同时把三个方向都扫了过去,而500.500到顶点只需要499步,所以肯定会有黑棋跑不掉
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=69;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int sx,sy;
struct node{
int x,y;
int id;
}my[700];
int u,v,w;
int vis[1005][1005];
void go(int x,int y){
sx+=x;sy+=y;
if(vis[sx][sy])sx-=x;
cout<<sx<<" "<<sy<<endl;
cin>>u>>v>>w;
if(u==-1)exit(0);
vis[my[u].x][my[u].y]=0;
vis[v][w]=1;
my[u].x=v;my[u].y=w;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>sx>>sy;
for(int i=1;i<=666;i++)cin>>my[i].x>>my[i].y,vis[my[i].x][my[i].y]=1;
int ok=1;
while(sx<500)go(1,0);
while(sx>500)go(-1,0);
while(sy<500)go(0,1);
while(sy>500)go(0,-1);
int a=0,b=0,c=0,d=0;
for(int i=1;i<=499;i++)
for(int j=1;j<=499;j++)a+=vis[i][j];
for(int i=1;i<=499;i++)
for(int j=501;j<=999;j++)b+=vis[i][j];
for(int i=501;i<=999;i++)
for(int j=1;j<=499;j++)c+=vis[i][j];
for(int i=501;i<=999;i++)
for(int j=501;j<=999;j++)d+=vis[i][j];
int aa=a+b+c,bb=a+b+d,cc=a+c+d,dd=c+b+d;
int mx=max(max(aa,bb),max(cc,dd));
if(aa==mx)while(true)go(-1,-1);
if(bb==mx)while(true)go(-1,1);
if(cc==mx)while(true)go(1,-1);
else while(true)go(1,1);
return 0;
}
E.Andrew and Taxi (二分答案+拓扑判环)
题意
给出一个有向图,让你把一些边反转需要花费费用Ci ,问你把这个图变成一个无环图需要的反转边的最大值最小是多少
题意
问最大最小值那必须是二分答案;
首先可以二分答案,然后把大于答案的边 拿去进行拓扑判断是否有环,如果没环,那么这个答案就是合法的
如果有环说明答案还要加,然后小于答案的边我们就把他们当成双向的就行了,因为题目要输出反转哪些边,所以我们可以记录拓扑序处理一下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=69;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int n,m;
struct node{
int u,v;
ll c;
}my[maxn];
vector<int>e[maxn];
int in[maxn];
int cnt[maxn];
vector<int>anw;
bool isok(ll mid){
for(int i=1;i<=n;i++)e[i].clear();
memset(in,0,sizeof(in));
for(int i=1;i<=m;i++){
if(my[i].c>mid)e[my[i].u].push_back(my[i].v),++in[my[i].v];
}
queue<int>p;
int now=0;
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++)if(in[i]==0)p.push(i),cnt[i]=++now;
while(!p.empty()){
int no=p.front();p.pop();
for(int i=0;i<e[no].size();i++){
int nex=e[no][i];
in[nex]--;
if(in[nex]==0){
p.push(nex);
cnt[nex]=++now;
}
}
}
for(int i=1;i<=n;i++)if(in[i])return false;
anw.clear();
for(int i=1;i<=m;i++){
if(my[i].c<=mid&&cnt[my[i].u]>cnt[my[i].v]){
anw.push_back(i);
}
}
return true;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>n>>m;
ll l=0,r=0;
for(int i=1;i<=m;i++){
cin>>my[i].u>>my[i].v>>my[i].c;
r=max(r,my[i].c);
}
ll ans=0;
while(l<=r){
ll mid=(l+r)/2;
if(isok(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
isok(ans);
cout<<ans<<" "<<anw.size()<<"
";
for(int i=0;i<anw.size();i++)cout<<anw[i]<<" ";
return 0;
}
F.Ivan and Burgers (线性基)
题意
题意进行翻译就是求出区间的最大异或值了,因为n(nabc)==abc
题解
考虑贪心,对于每个位的贡献 如果大就留下来,如果同样大那就把比较后面的留下来 ,当然,需要离线处理区间
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=5e5+50;
const ll inf=69;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
const int maxbit=32;
int n;
int c[maxn];
int q;
struct node{
int id;
int l,r;
bool operator <(const node &a)const{
return this->r<a.r;
}
}Q[maxn];
struct base{
int num;
int id;
}my[maxbit];
void ins(int num,int id){
for(int i=31;i>=0;i--){
if(num&(1<<i)){
if(my[i].num==0){
my[i].id=id;
my[i].num=num;
break;
}
else if(my[i].id<id){
swap(my[i].id,id);
swap(my[i].num,num);
}
num^=my[i].num;
}
}
}
int ans[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>c[i];
cin>>q;
for(int i=1;i<=q;i++){
cin>>Q[i].l>>Q[i].r;Q[i].id=i;
}
sort(Q+1,Q+1+q);
int now=1;
for(int i=1;i<=q;i++){
while(now<=Q[i].r)ins(c[now],now),now++;
for(int j=31;j>=0;j--){
if(my[j].id>=Q[i].l&&((ans[Q[i].id]^my[j].num)>ans[Q[i].id]))ans[Q[i].id]^=my[j].num;
}
}
for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
return 0;
}