620A - Professor GukiZ's Robot 20171122
\(ans=max(\left | x2-x1 \right |,\left | y2-y1 \right |)\)
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int X[],Y[],x,y;
int main()
{
scanf("%d%d%d%d",&X[],&Y[],&X[],&Y[]);
x=abs(X[]-X[]),y=abs(Y[]-Y[]);
printf("%d\n",max(x,y));
return ;
}
620B - Grandfather Dovlet’s calculator 20171122
预处理每个字符的花费，按照题意模拟即可
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int ans,a,b,f[];
int cal(int k)
{
int _=;
while(k)
_+=f[k%],k/=;
return _;
}
int main()
{
scanf("%d%d",&a,&b);
f[]=,f[]=,f[]=,f[]=,f[]=;
f[]=,f[]=,f[]=,f[]=,f[]=;
for(int i=a;i<=b;i++)
ans+=cal(i);
printf("%d\n",ans);
return ;
}
620C - Pearls in a Row 20171122
开个set记录当前已在区间类的珍珠种类，O(n)扫一遍即可
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<set>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int>l,r;
int n,x,t=;
set<int>s;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
if(t==i)s.clear();
scanf("%d",&x);
if(s.count(x))
l.push_back(t),r.push_back(i),t=i+;
else s.insert(x);
}
if(!l.size())return printf("-1\n"),;
r[r.size()-]=n;
printf("%d\n",l.size());
for(int i=;i<l.size();i++)
printf("%d %d\n",l[i],r[i]);
return ;
}
620D - Professor GukiZ and Two Arrays 20171122
暴力分类讨论\(k=0,1,2\)的所有情况就好了
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#define N 2001
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
struct rua
{
LL i,j,v;
}f[N*N];
LL n,m,d,sa,sb,a[N],b[N],ans[],v[N*N],_,a1,b1,b2;
bool cmp(rua x,rua y){return x.v<y.v;}
void cdx(LL i,LL _)
{
if(!_)return;
if(f[_].i==f[i].i || f[_].j==f[i].j)return;
if(ans[]>abs(d+v[_]))
ans[]=abs(d+v[_]),b1=i,b2=_;
}
int main()
{
ans[]=(1ll<<);
scanf("%I64d",&n);
for(LL i=;i<=n;i++)
scanf("%I64d",&a[i]),sa+=a[i];
scanf("%I64d",&m);
for(LL i=;i<=m;i++)
scanf("%I64d",&b[i]),sb+=b[i];
d=sa-sb;
for(LL i=;i<=n;i++)
for(LL j=;j<=m;j++)
{
f[i*m-m+j].v=*(b[j]-a[i]);
f[i*m-m+j].i=i;
f[i*m-m+j].j=j;
}
ans[]=abs(d);
sort(f+,f+n*m+,cmp);
for(LL i=;i<=n;i++)
for(LL j=;j<=m;j++)
v[i*m-m+j]=f[i*m-m+j].v;
_=lower_bound(v+,v+n*m+,-d)-v;
if(_==n*m+)ans[]=abs(d+v[_-]),a1=_-;else
if(_==)ans[]=abs(d+v[]),a1=_;else
if(abs(d+v[_])<abs(d+v[_-]))ans[]=abs(d+v[_]),a1=_;
else ans[]=abs(d+v[_-]),a1=_-;
for(int i=;i<n*m;i++)
{
d+=v[i];
_=lower_bound(v+,v+n*m+,-d)-v;
if(_==n*m+)cdx(i,_-);
else if(_==)cdx(i,-(i==));else
cdx(i,_+(i==_)),cdx(i,_--(i==_-));
d-=v[i];
}
if(ans[]<=ans[] && ans[]<=ans[])
return printf("%I64d\n0\n",ans[]),;
if(ans[]<=ans[] && ans[]<=ans[])
return printf("%I64d\n1\n%I64d %I64d\n",ans[],f[a1].i,f[a1].j),;
printf("%I64d\n2\n",ans[]);
printf("%I64d %I64d\n",f[b1].i,f[b1].j);
printf("%I64d %I64d\n",f[b2].i,f[b2].j);
return ;
}
620E - New Year Tree 20180919
预处理每个点的DFS序，可以得出每棵子树对应的DFS序的范围。由于\(c_i\)不超过60，故可将修改操作转换为：把子树内所有点的价值改为\(2^{c}\)，将询问操作转换为：询问子树内所有点价值进行或运算的结果在二进制中1的个数，用线段树做就好了
#include<bits/stdc++.h>
using namespace std;
#define N 400001
#define LL long long
vector<int>d[N];
int n,m,t,x,y,c[N],l[N],r[N];
struct rua{int l,r;LL f,w;}tr[N<<];
LL a[N];
void update(int x)
{
int lson=x*,rson=x*+;
tr[x].w=tr[lson].w|tr[rson].w;
}
void down(int x)
{
LL c=tr[x].w;tr[x].f=;
int lson=x*,rson=x*+;
tr[lson].f=tr[lson].w=c;
tr[rson].f=tr[rson].w=c;
}
void Build(int l,int r,int x)
{
tr[x]={l,r,,};
if(l==r){tr[x].w=a[l];return;}
int mid=l+r>>;
Build(l,mid,x*);
Build(mid+,r,x*+);
update(x);
}
void Change(int L,int R,LL c,int x)
{
int l=tr[x].l,r=tr[x].r;
int mid=l+r>>;
if(L<=l && r<=R){tr[x].f=tr[x].w=c;return;}
if(tr[x].f)down(x);
if(L<=mid)Change(L,R,c,x*);
if(R>mid)Change(L,R,c,x*+);
update(x);
}
LL Query(int L,int R,int x)
{
int l=tr[x].l,r=tr[x].r;
int mid=l+r>>;
LL res=;
if(L<=l && r<=R)return tr[x].w;
if(tr[x].f)down(x);
if(L<=mid)res|=Query(L,R,x*);
if(R>mid)res|=Query(L,R,x*+);
update(x);
return res;
}
void dfs(int cur,int pre)
{
l[cur]=++x;
a[x]=1ll<<c[cur];
for(auto nxt:d[cur])if(nxt!=pre)dfs(nxt,cur);
r[cur]=x;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&c[i]);
for(int i=;i<=n;i++)
scanf("%d%d",&x,&y),
d[x].push_back(y),
d[y].push_back(x);
x=,dfs(,);
Build(,n,);
for(int i=;i<=m;i++)
{
scanf("%d",&t);
if(t==)
scanf("%d%d",&x,&y),
Change(l[x],r[x],1ll<<y,);
else
scanf("%d",&x),
printf("%d\n",(int)__builtin_popcountll(Query(l[x],r[x],)));
}
}
620F - Xors on Segments 20171122
这题...预处理从1异或到n的值（即前缀异或和），\(O(n^{2})\)莽一下就过了...CF的评测机是跑得真快
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#define N 50001
#define M 1000001
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,a[N],l[N],r[N],t[N],ans[N],f[M];
int main()
{
for(int i=;i<M;i++)
f[i]=f[i-]^i;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=m;i++)
scanf("%d%d",&l[i],&r[i]);
for(int i=;i<=n;i++)
{
int _=;t[i-]=;
for(int j=i;j<=n;j++)
_=max(_,f[a[i]]^f[a[j]]^min(a[i],a[j])),t[j]=_;
for(int j=;j<=m;j++)
if(l[j]<=i && r[j]>=i)
ans[j]=max(ans[j],t[r[j]]);
}
for(int i=;i<=m;i++)printf("%d\n",ans[i]);return ;
}