Educational Codeforces Round 23 A-F 补题

注意负数和0的特殊处理。。水题。。然而又被Hack了吗的智障

#include<bits/stdc++.h>

using namespace std;

int main()

{

 int sa,sb,da,db,x,y;

 scanf("%d%d%d%d%d%d",&sa,&sb,&da,&db,&x,&y);

 sa=da-sa;sb=db-sb;

 if(sa<0)sa*=-1;

 if(sb<0)sb*=-1;

 if(x<0)x*=-1;

 if(y<0)y*=-1;

 if((sa!=0&&x==0)||(sb!=0&&y==0)){printf("NO\n");return 0;}

 if((sa==0)&&(sb==0)){printf("YES\n");return 0;}

 if(((sa%x)!=0)||((sb%y)!=0)){printf("NO\n");return 0;}

 if((((max(sa/x,sb/y))-(min(sa/x,sb/y)))%2)!=0){printf("NO\n");return 0;}

 printf("YES\n");

 return 0;

}

B Makes And The Product

排序后求一下组合数就好了。。

#include<bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int N=2e5;

LL num[N];

map<LL,LL>ma;

LL C(LL n,LL m)

{

 LL ans=1;

 for(int i=0;i<m;i++)

 	ans*=n-i;

 for(int i=m;i>=2;i--)

 	ans/=i;

 return ans;

}

int main()

{

 int n;

 scanf("%d",&n);

 for(int i=0;i<n;i++)scanf("%I64d",num+i);

 sort(num,num+n);

 LL ans=1;

 for(int i=0;i<3;i++)

 	ma[num[i]]++;

 LL l=ma[num[2]];

 for(int i=3;i<n&&num[i]==num[2];i++)

 	{

 	 l++;

	}

 ans=ans*C(l,ma[num[2]]);

 printf("%I64d\n",ans);

 return 0;

}

C Really Big Numbers

肯定存在某个数k 大于k的数都是big number... 二分找最小的k就好了

#include<bits/stdc++.h>

using namespace std;

typedef long long int LL;

LL sum(LL x)

{

 LL dex=1;

 LL ans=0;

 while(x>0)

 	{

 	 ans+=((x%10)*(dex-1));

 	 x/=10;dex*=10;

	}

 return ans;

}

int main()

{

 LL n,s;

 scanf("%I64d%I64d",&n,&s);

 LL l=1,r=n;

 LL i;

 bool flag=false;

 LL ri;

 while(l<=r&&r<=n)

 	{

 	  i=(l+r)>>1;

 	 if(sum(i)>=s){flag=true;ri=i;r=i-1;}

 	 	else {l=i+1;}

	}

if(flag) {printf("%I64d\n",(n-ri+1));return 0;}

 	else printf("0\n");

 return 0;

}

D Imbalanced Array

暴力枚举每个区间复杂度O（n^2）起步显然是不可以的。

那么只能考虑每个位置对答案做的贡献。即它是多少个区间的最值？

用栈维护，从前往后一个一个堆栈，并且保证栈中的所有元素构成不上升序列即可。

复杂度O（n）技巧性还是很强的。。

#include <bits/stdc++.h>

using namespace std;

long long n,pos[1000005],neg[1000005];

long long solve(long long a[]){

    stack<pair<int,long long>> s;

    a[n]=1e8;

    s.push({-1,1e9});

    long long sum=0;

    for(int i=0;i<=n;s.push({i,a[i]}),++i)

        while(a[i]>=s.top().second){

            auto p=s.top();

            s.pop();

            auto p2=s.top();

            sum+=p.second*(i-p.first)*(p.first-p2.first);

        }

    return sum;

}

int main(){

    ios_base::sync_with_stdio(0);

    cin>>n;

    for(int i=0;i<n;neg[i]=(-1)*pos[i],++i)

        cin>>pos[i];

    cout<<solve(pos)+solve(neg);

}

E Choosing The Commander

很有趣的一道数据结构题

我们考虑 xor运算是按位进行的

　　　　比较大小也可以按位进行

那么如果我们同样按位储存所有的士兵性格可以么？

是的，用一颗Trie来储存所有的士兵就可以在logn的时间内完成一个访问了！

#include<bits/stdc++.h>

#define N 3000005

using namespace std;

int size[N],ch[N][2],n,cnt,a,b,type;

inline void ins(int x,int add){

	int now=1;

	for(int i=26;i>=0;i--){

		bool v=((x>>i)&1);

		if(!ch[now][v])ch[now][v]=++cnt;

		now=ch[now][v];

		size[now]+=add;

	}

}

inline void query(int x,int y){

	int ans=0,now=1,val=0;

	for(int i=26;i>=0&&now;i--){

		bool xbit=((x>>i)&1),ybit=((y>>i)&1);

		val+=val;

		if(ybit){

			ans+=size[ch[now][xbit]];now=ch[now][!xbit];

			val+=!xbit;

		}

		else{now=ch[now][xbit];val+=xbit;}

	}

	printf("%d\n",ans);

}

inline int read(){

	int f=1,x=0;char ch;

	do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');

	do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');

	return f*x;

}

int main(){

	cnt=1;n=read();

	while(n--){

		int opt=read(),x=read();

		if(opt==1)ins(x,1);

		if(opt==2)ins(x,-1);

		if(opt==3){

			int y=read();

			query(x,y);

		}

	}

}

F MEX Queries

首先这道题是离线询问的也就是我们预知了所有询问。

那么，一个数字如果要成为答案，那么它必然是某个询问的边界值。

所以我们只要维护所有询问的边界值即可，总共有2*10^5个。

用线段树维护，每个命令要么删除某些数，要么增加某些数。

进行完一个命令后，取线段树上存在的且最靠左的值即可。（每个线段树节点保存当前区间存在的整数个数）

#include<bits/stdc++.h>

#define N 400005

#define LL long long

#define TAT "%I64d"

#define L(__) (__ << 1)

#define R(__) (L(__)|1)

using namespace std;

LL sz[4*N],L[N],R[N],w[N]; int q,op[N],tag[4*N],lw;

void TS(int t,int d,int o)

{

	if(o==1) tag[t]^=1,sz[t]=d-sz[t];

	if(o==2) tag[t]=o,sz[t]=d;

	if(o==3) tag[t]=o,sz[t]=0;

}

void push(int t,int d)

{

	if(!tag[t]) return ;

	TS(L(t),(d+1)/2,tag[t]);

	TS(R(t),d/2,tag[t]);

	tag[t]=0;

}

void M(int t,int l,int r,int l1,int r1,int op)

{

	int mid=(l+r)>>1;

	if(l>r1 || r<l1) return ;

	if(l>=l1&&r<=r1) return TS(t,r-l+1,op);

	push(t,r-l+1);

	M(L(t),l,mid,l1,r1,op);

	M(R(t),mid+1,r,l1,r1,op);

	sz[t]=sz[L(t)]+sz[R(t)];

}

int Q(int t,int l,int r)

{

	int mid=(l+r)>>1,x;

	if(l==r) return l;

	push(t,r-l+1);

	if(sz[L(t)]==(r-l)/2+1)

		x=Q(R(t),mid+1,r);

	else x=Q(L(t),l,mid);

	sz[t]=sz[L(t)]+sz[R(t)];

	return x;

}

int main()

{

	int i;

	scanf("%d",&q),w[lw=1]=1;

	for(i=1;i<=q;i++){

		scanf("%d"TAT""TAT,&op[i],&L[i],&R[i]);

		w[++lw]=L[i],w[++lw]=L[i]+1;

		w[++lw]=R[i],w[++lw]=R[i]+1;

	  }

	sort(w+1,w+lw+1);

	lw=unique(w+1,w+lw+1)-w-1;

	for(i=1;i<=q;i++){

		L[i]=lower_bound(w+1,w+lw+1,L[i])-w;

		R[i]=lower_bound(w+1,w+lw+1,R[i])-w;

		M(1,1,lw,L[i],R[i],op[i]%3+1);

		printf(TAT"\n",w[Q(1,1,lw)]);

	  }

	return 0;

}

巴特西

Educational Codeforces Round 23 A-F 补题

最新文章

热门文章