B. Vladik and Complicated Book
E. Vladik and Entertaining Flags
A. Vladik and Courtesy
暴力
代码如下：
#include <iostream>
using namespace std;
typedef long long ll;
ll a,b;
int main(void){
cin>>a>>b;
ll t=1;
while(1){
if(t&1)a-=t;
else b-=t;
t++;
if(a<0||b<0)break;
}
if(a<0)cout<<"Vladik";
else cout<<"Valera";
}B. Vladik and Complicated Book
题目大意：判断区间内第$k$大是否为$x$.
离线+树状数组
看到数据范围$10^4$ ，想成学校的老年机，半天想出个$O（mlgm+mlgn）$的。
考虑到每个数都不相同，可以先离线询问，然后将小于$x$ 的数插入树状数组后查询区间$[L,R]$ 内有多少比$x$ 小的数。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,m,a[10005],c[10005],f[10005];
bool ans[10005];
struct node{
int l,r,x,id;
friend bool operator<(node qq,node pp){
return a[qq.x]<a[pp.x];
}
}q[10005];
int lowbit(int x){
return x&-x;
}
void add(int x){
for(int i=x;i<=n;i+=lowbit(i))
c[i]++;
}
int sum(int x){
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
ans+=c[i];
return ans;
}
int main(void){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
f[a[i]]=i;
}
for(int i=0;i<m;++i){
scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x);
q[i].id=i;
}
sort(q,q+m);
int l=1;
for(int i=0;i<m;++i){
int id=q[i].id;
while(l<a[q[i].x]){
add(f[l]);
l++;
}
int t=sum(q[i].r)-sum(q[i].l-1);
if(q[i].l+t==q[i].x)ans[id]=1;
else ans[id]=0;
}
for(int i=0;i<m;++i){
if(ans[i])printf("Yesn");
else printf("Non");
}
}主席树模板
主席树可以查询区间第$k$ 大，判断区间第$k$ 大是否为$x$ 自然不在话下，复杂度$O(mlgn)$ ，常数略比上面方法大，代码不贴。
暴力
也可以直接暴力，复杂度$O(nm)$ 。
代码如下form xdujlx：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e4+7;
int p[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>p[i];
int l,r,x;
while(m--){
cin>>l>>r>>x;
int rk=0;
for(int i=l;i<=r;i++)
if(p[i]<p[x]) rk++;
if(l+rk==x) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}C. Vladik and Memorable Trip
题目大意：将一个数组划分成若干个不交叉的块，要求块外不含块内元素，每个块的价值为块内不同元素的异或值，总价值为所有块的价值和，问最大价值。
DP
想着先区间合并再dp，然后算法错误…
看到数据范围其实$O(n^2)$可过，直接dp就好了…
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int n,a[5005],dp[5005],r[5005];
bool vis[5005],f[5005];
int main(void){
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%d",&a[i]);
r[a[i]]=i;
}
int ans=0;
for(int i=0;i<n;++i){
int t=a[i];
if(!vis[t]){
vis[t]=1;
memset(f,0,sizeof(f));
f[t]=1;
bool flag=1;
int temp=t;
int R=r[t];
for(int j=i+1;j<R;++j){
if(vis[a[j]]&&a[j]!=t){
flag=0;break;
}
if(!f[a[j]]){
temp^=a[j];
R=max(R,r[a[j]]);
f[a[j]]=1;
}
}
if(flag)dp[R]=max(dp[R],temp+ans);
}
ans=max(ans,dp[i]);
}
printf("%dn",ans);
}D. Vladik and Favorite Game
题目大意：交互题，要求输出从起点到终点的行动方向，其中左右和上下的方向可能会被改变一次。
模拟
先dfs出不改变方向的情况下的原行动方向，然后一步一步模拟即可。
代码如下：
#include <cstdio>
using namespace std;
int n,m,d=-1,x,y,px,py,nx,ny;
char mp[105][105];
char ans[10005];
bool vis[105][105];
void dfs(int px,int py,int k){
if(mp[px][py]=='F'){
d=k;
return;
}
int heng=0,shu=0;
if(px-1>=0&&mp[px-1][py]!='*')shu++;
if(px+1<n&&mp[px+1][py]!='*')shu++;
if(py-1>=0&&mp[px][py-1]!='*')heng++;
if(py+1<m&&mp[px][py+1]!='*')heng++;
if(shu>heng){
if(px-1>=0&&!vis[px-1][py]&&mp[px-1][py]!='*'){
vis[px-1][py]=1;
ans[k]='U';
dfs(px-1,py,k+1);
if(d!=-1)return;
}
if(px+1<n&&!vis[px+1][py]&&mp[px+1][py]!='*'){
vis[px+1][py]=1;
ans[k]='D';
dfs(px+1,py,k+1);
if(d!=-1)return;
}
if(py-1>=0&&!vis[px][py-1]&&mp[px][py-1]!='*'){
vis[px][py-1]=1;
ans[k]='L';
dfs(px,py-1,k+1);
if(d!=-1)return;
}
if(py+1<m&&!vis[px][py+1]&&mp[px][py+1]!='*'){
vis[px][py+1]=1;
ans[k]='R';
dfs(px,py+1,k+1);
if(d!=-1)return;
}
}else{
if(py-1>=0&&!vis[px][py-1]&&mp[px][py-1]!='*'){
vis[px][py-1]=1;
ans[k]='L';
dfs(px,py-1,k+1);
if(d!=-1)return;
}
if(py+1<m&&!vis[px][py+1]&&mp[px][py+1]!='*'){
vis[px][py+1]=1;
ans[k]='R';
dfs(px,py+1,k+1);
if(d!=-1)return;
}
if(px-1>=0&&!vis[px-1][py]&&mp[px-1][py]!='*'){
vis[px-1][py]=1;
ans[k]='U';
dfs(px-1,py,k+1);
if(d!=-1)return;
}
if(px+1<n&&!vis[px+1][py]&&mp[px+1][py]!='*'){
vis[px+1][py]=1;
ans[k]='D';
dfs(px+1,py,k+1);
if(d!=-1)return;
}
}
}
char another(char c){
if(c=='R')return 'L';
if(c=='L')return 'R';
if(c=='U')return 'D';
if(c=='D')return 'U';
}
int main(void){
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)scanf("%s",mp[i]);
dfs(0,0,0);
px=nx=0,py=ny=0;
bool heng=1,shu=1;
for(int i=0;i<d;){
bool LR=ans[i]=='L'||ans[i]=='R';
bool UD=ans[i]=='U'||ans[i]=='D';
if(LR){
if(heng)printf("%cn",ans[i]);
else printf("%cn",another(ans[i]));
if(ans[i]=='R')ny=py+1;
else ny=py-1;
}else{
if(shu)printf("%cn",ans[i]);
else printf("%cn",another(ans[i]));
if(ans[i]=='D')nx=px+1;
else nx=px-1;
}
fflush(stdout);
scanf("%d%d",&x,&y);x--,y--;
if((x==-2&&y==-2)||mp[x][y]=='F')return 0;
if(x==px&&y==py){
if(ans[i]=='L'&&y+1>=m)heng=0;
if(ans[i]=='R'&&y-1<0)heng=0;
if(ans[i]=='D'&&x-1<0)shu=0;
if(ans[i]=='U'&&x+1>=n)shu=0;
}else if(x!=nx||y!=ny){
if(ans[i]=='R'&&y!=ny){
heng=0;
printf("Ln");
fflush(stdout);
scanf("%d%d",&x,&y);x--,y--;
}
if(ans[i]=='L'&&y!=ny){
heng=0;
printf("Rn");
fflush(stdout);
scanf("%d%d",&x,&y);x--,y--;
}
if(ans[i]=='U'&&y!=ny){
shu=0;
printf("Dn");
fflush(stdout);
scanf("%d%d",&x,&y);x--,y--;
}
if(ans[i]=='D'&&y!=ny){
shu=0;
printf("Un");
fflush(stdout);
scanf("%d%d",&x,&y);x--,y--;
}
}else i++;
nx=px=x,ny=py=y;
}
}E. Vladik and Entertaining Flags
题目大意：有一个$n×m$的矩阵，$q$次询问，每次询问l列到r列围成的图中有多少连通块。
线段树+并查集
注意到$n leqslant 10$，故可以用线段树维护。
每段维护从$L$列到$R$列的图中有多少连通块，以及$L$列及$R$列的段内数字编号（保证段内的联通的数字编号是相同的）。
段与段合并时，只需判断相邻的数字是否相同，若相同且不为同一连通块，则合并。
查询前，需要将段两端的数字编号的$pre$指向自己（build操作中有可能将$pre$指向了其他段中的数字编号；同时因为段内联通的数字编号相同，故该操作不会改变段内数字的连通性），之后同合并操作。
复杂度$O(nmlgm+qnlgm)$.
代码如下：
#include <cstdio>
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
using namespace std;
int n,m,q,mp[12][100005],pre[1000005],tot;
bool flag;
struct node{
int num;
int L[12],R[12];
}a[100005<<2],ans;
void init(int x){
for(int i=0;i<=x;++i)pre[i]=i;
}
int Find(int x){
return pre[x]==x?x:pre[x]=Find(pre[x]);
}
void Union(int a,int b){
int x=Find(a),y=Find(b);
if(x!=y)pre[x]=y;
}
void push_up(int x,int mid){
int l=x<<1,r=x<<1|1;
a[x].num=a[l].num+a[r].num;
for(int i=0;i<n;++i){
if(mp[i][mid]==mp[i][mid+1]){
if(Find(a[l].R[i])!=Find(a[r].L[i])){
a[x].num--;
Union(a[l].R[i],a[r].L[i]);
}
}
}
for(int i=0;i<n;++i){
a[x].L[i]=Find(a[l].L[i]);
a[x].R[i]=Find(a[r].R[i]);
}
}
void build(int x,int l,int r){
if(l==r){
a[x].num=1;
a[x].L[0]=a[x].R[0]=++tot;
for(int i=1;i<n;++i){
if(mp[i][r]==mp[i-1][r]){
a[x].L[i]=a[x].R[i]=tot;
}else{
tot++,a[x].num++;
a[x].L[i]=a[x].R[i]=tot;
}
}
return;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
push_up(x,mid);
}
void query(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
if(flag){
flag=0;
ans=a[x];
return;
}else{
ans.num+=a[x].num;
for(int i=0;i<n;++i){
pre[ans.R[i]]=ans.R[i];
pre[a[x].L[i]]=a[x].L[i];
pre[a[x].R[i]]=a[x].R[i];
}
for(int i=0;i<n;++i){
if(mp[i][l-1]==mp[i][l]){
if(Find(ans.R[i])!=Find(a[x].L[i])){
ans.num--;
Union(ans.R[i],a[x].L[i]);
}
}
}
for(int i=0;i<n;++i)
ans.R[i]=Find(a[x].R[i]);
return;
}
}
int mid=(l+r)>>1;
if(ql<=mid)query(lson,ql,qr);
if(mid<qr)query(rson,ql,qr);
}
int main(void){
scanf("%d%d%d",&n,&m,&q);
init(n*m);
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
scanf("%d",&mp[i][j]);
build(1,0,m-1);
while(q--){
int x,y;
scanf("%d%d",&x,&y);x--;y--;
flag=1;
query(1,0,m-1,x,y);
printf("%dn",ans.num);
}
}
近期评论