注意负数和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;
}
排序后求一下组合数就好了。。
#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;
}
肯定存在某个数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;
}
暴力枚举每个区间 复杂度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);
}
很有趣的一道数据结构题
我们考虑 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);
}
}
}
首先 这道题是离线询问的 也就是我们预知了所有询问。
那么，一个数字如果要成为答案，那么它必然是某个询问的边界值。
所以我们只要维护所有询问的边界值即可，总共有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;
}