【日常摸鱼】IOI2014

技术文章 10个月前 完美者
1,069 0

标签:protoc   back   线段   有一个   pow   insert   从后往前   return   print   

【日常摸鱼】IOI2014

前言

摸鱼~~

Rail

链接

http://uoj.ac/problem/24

题解

问题是好想的,因为 \(3(n-1)\) 次询问确实搞不出什么花样。
第一轮肯定是询问所有点到 \(0\) 的距离,记为 \(dis(i)\) 。最近的点一定是离 \(0\) 最近的右边的类型2的车站,记为y。
然后询问所有点到y的距离,记为\(Dis(i)\) 。然后根据\(dis(y)+Dis(i)\)是否等于\(dis(i)\),可以判断点是在y的左边还是右边。
如果i在y的左边并且\(Dis(i)<dis(y)\),说明i在0和y中间,类型是1。
然后两边的做法是一样的,现在考虑在y右边的。
按照\(dis(x)\)排序,用一个栈维护当前最靠右的类型2的点,设栈顶的点为z。
假设现在有一个新点r,我们先假设这个新点的类型是1,那么我们可以求出到达r应使用的类型2的车站到z的距离。
直接列式子:\((dis(z)-dis(r)+L(z,r))/2\)
于是可以算出这个点的位置,直接判断这个位置上的点是不是类型2,因为如果存在这个点,一定在询问r之前就出现过了。
再假设r是类型2,这条式子依然可以代表z左边离z最近的类型1的距离。
也就意味着这个位置一定是有点的,如果不是类型2,那一定是类型1,不管这个点是否在r之前出现。
于是标记一下每个位置的类型,就可以通过这个式子直接判断r的类型及位置了。

\(Code\)

#include "rail.h"
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5050;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
void print(LL x){
    if(x>9) print(x/10);
    putchar(x%10+‘0‘);
}

int dis[N],D[N];
vector<int> A,B,C;
bool cmp(int x,int y){
	return dis[x]<dis[y];
}
bool cmp2(int x,int y){
	return D[x]<D[y];
}
int tp=0;
int p[5050];
int vis[1000050];
void findLocation(int n, int first, int location[], int stype[]){
	location[0]=first;stype[0]=1;vis[location[0]]=stype[0];
	if(n==1) return;
	for(int i=1;i<n;++i) {
		dis[i]=getDistance(0,i);
		A.push_back(i);
	}
	sort(A.begin(),A.end(),cmp);
	int x,y,z,r;
	x=0;y=A[0];
	location[y]=first+dis[y];
	stype[y]=2;
	vis[location[y]]=stype[y];
	D[y]=0;D[x]=dis[y];
	for(int i=1;i<A.size();++i) D[A[i]]=getDistance(y,A[i]);
	for(int i=1;i<n;++i){
		if(i==y) continue;
		if(dis[i]==dis[y]+D[i]){
			if(D[i]<dis[y]){
				location[i]=location[y]-D[i];
				stype[i]=1;
				vis[location[i]]=stype[i];
			}
			else B.push_back(i);
		}
		else{
			C.push_back(i);
		}
	}
	sort(B.begin(),B.end(),cmp2);
	sort(C.begin(),C.end(),cmp);
	tp=1;p[tp]=y;
	for(int i=0;i<C.size();++i){
		r=C[i];z=p[tp];
		int L=getDistance(z,r);
		int val=(L+dis[z]-dis[r])/2;
		if(vis[location[z]-val]==2){
			stype[r]=1;
			location[r]=location[z]-L;
			vis[location[r]]=stype[r];
		}
		else{
			stype[r]=2;
			location[r]=location[x]+dis[r];
			vis[location[r]]=stype[r];
			p[++tp]=r;
		}
	}
	tp=1;p[tp]=x;
	for(int i=0;i<B.size();++i){
		r=B[i];z=p[tp];
		int L=getDistance(z,r);
		int val=(L+D[z]-D[r])/2;
		if(vis[location[z]+val]==1){
			stype[r]=2;
			location[r]=location[z]+L;
			vis[location[r]]=stype[r];
		}
		else{
			stype[r]=1;
			location[r]=location[y]-D[r];
			vis[location[r]]=stype[r];
			p[++tp]=r;
		}
	}
}

Wall

链接

http://uoj.ac/problem/25

题意

给一个长度为\(n\)(\(n \leq 2000000\))的序列。序列初始都是\(0\)\(k(k \leq 500000)\)次操作,每次选一段区间对\(x\)取min或max。求最后的序列。

题解

对同一个区间进行的操作是可以叠加的。于是就变成线段树的裸题了QAQ
记min和max两个懒标记就行。

\(Code\)

//#include "wall.h"
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e6+10;
const int M=5e5+10;
const int INF=1e9;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
void print(LL x){
    if(x>9) print(x/10);
    putchar(x%10+‘0‘);
}

struct seg{
    int l,r;
    int mx,mn;
}d[N<<2];

#define ls id<<1
#define rs id<<1|1

void build(int l,int r,int id){
    d[id].l=l;d[id].r=r;d[id].mx=0;d[id].mn=INF;
    if(l==r)return;
    int mid=l+r>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
}

void U(int id,int x,int t){
    if(t==1){
        d[id].mn=max(d[id].mn,x);
        d[id].mx=max(d[id].mx,x);
    }
    else if(t==2){
        d[id].mn=min(d[id].mn,x);
        d[id].mx=min(d[id].mx,x);
    }
}

void pushdown(int id){
    if(d[id].l==d[id].r) return;
    U(ls,d[id].mx,1);U(rs,d[id].mx,1);d[id].mx=0;
    U(ls,d[id].mn,2);U(rs,d[id].mn,2);d[id].mn=INF;
}

void C(int L,int R,int id,int x,int t){
    pushdown(id);
    if(d[id].l==L&&d[id].r==R){U(id,x,t);return;}
    if(R<=d[ls].r) C(L,R,ls,x,t);
    else if(L>d[ls].r) C(L,R,rs,x,t);
    else{
        C(L,d[ls].r,ls,x,t);
        C(d[rs].l,R,rs,x,t);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    build(1,n,1);
    for(int i=0;i<k;++i)
        C(left[i]+1,right[i]+1,1,height[i],op[i]);
    int tot=0;
    for(int i=1;;++i){
        if(d[i].l!=d[i].r) pushdown(i);
        else if(d[i].l!=0){
            finalHeight[d[i].l-1]=min(max(0,d[i].mx),d[i].mn);
            ++tot;if(tot==n) break;
        }
    }
    return;
}
//int op[M],L[M],R[M],height[M],finalHeight[N];
//int main(){
//    int n,k;
//    scanf("%d%d",&n,&k);
//    for(int i=0;i<k;++i)
//        scanf("%d%d%d%d",&op[i],&L[i],&R[i],&height[i]);
//    buildWall(n,k,op,L,R,height,finalHeight);
//    for(int i=0;i<n;++i) printf("%d\n",finalHeight[i]);
//    return 0;
//}

Game

链接

http://uoj.ac/problem/26

题解

并不难啊QAQ要让对方无法判断是否一定成树嘛
我们在构造一颗树的时候,一个很常见的方法是对于每个i>=2,找到一个j<i,让其成为i的父亲。
然后我们先假设比i小的都可能是i的父亲,然后在删边的时候,如果这是i的最后一个父亲,就返回1,否则返回0.

\(Code\)

#include "game.h"
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e3+10;
const int M=5e5+10;
const int INF=1e9;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
void print(LL x){
    if(x>9) print(x/10);
    putchar(x%10+‘0‘);
}

int val[N];

void initialize(int n){
	for(int i=0;i<n;++i)
		val[i]=i;
}
int hasEdge(int u, int v){
	if(u>v) swap(u,v);
	--val[v];
	if(val[v]) return 0;
	else return 1;
}

//int main(){
//	int n;scanf("%d",&n);initialize(n);
//	int u,v;
//	for(int i=1;i<=n*(n-1)/2;++i){
//		scanf("%d%d",&u,&v);
//		printf("%d\n",hasEdge(u,v));
//	}
//    return 0;
//}

Gondola

链接

http://uoj.ac/problem/27

题解

第一问:如果有重复数字肯定不行。否则记下序列的最小值,然后验证一下不超过n的数的相对位置就行。
第二问:对于数值超过n的值,如果出现在序列中,则直接放在哪个位置,否则随便找一个值比它大的位置放,反正之后会被覆盖。
第三问:从小往大考虑数值,如果没出现在序列中,则剩余的比它大的位置都可以放,乘上这个系数即可。有很长一段数系数相同,需要快速幂。然后特判一下给定序列全都大于n的情况。

\(Code\)

#include "gondola.h"
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=3e5+10;
const LL P=1e9+9;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
void print(LL x){
    if(x>9) print(x/10);
    putchar(x%10+‘0‘);
}
int vis[N];
int valid(int n, int inputSeq[]){
	for(int i=1;i<=250000;++i) vis[i]=0;
	int mn=0;
	for(int i=0;i<n;++i){
		if(vis[inputSeq[i]]) return 0;
		vis[inputSeq[i]]=1;
		if(inputSeq[i]<inputSeq[mn]) mn=i;
	} 
	for(int i=0;i<n;++i){
		int j=(i+mn)%n;
		if(inputSeq[j]>n) continue;
		else if(inputSeq[j]==inputSeq[mn]+i) continue;
		else return 0;
	}
	return 1;
} 
int yuan[N];
int sta[N];
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	int now=0,x=0,tp=0,mn=0;
	for(int i=1;i<=250000;++i) vis[i]=0;
	for(int i=0;i<n;++i){
		vis[gondolaSeq[i]]=i+1;
		if(gondolaSeq[i]>n) ++x;
		if(gondolaSeq[i]<gondolaSeq[mn]) mn=i;
	}
	if(gondolaSeq[mn]>n){
		for(int i=0;i<n;++i) yuan[i]=i+1;
	}
	else{
		int y=gondolaSeq[mn];
		for(int i=mn;i<n;++i){
			yuan[i]=y;
			++y;if(y>n) y=1;
		}
		for(int i=0;i<mn;++i){
			yuan[i]=y;
			++y;if(y>n) y=1;
		}
	}
	tp=0;
	for(int i=n+1;i<=250000;++i){
		if(x==0) break;
		if(!vis[i]) sta[++tp]=i;
		else{
			for(int j=1;j<=tp;++j) {
				replacementSeq[now++]=yuan[vis[i]-1];
				yuan[vis[i]-1]=sta[j];
			}
			tp=0;
			replacementSeq[now++]=yuan[vis[i]-1];
			yuan[vis[i]-1]=i;
		}
	}
	return now;
}
LL qpow(LL x,LL y){
	LL re=1;
	while(y){
		if(y&1) re=re*x%P;
		x=x*x%P;y>>=1; 
	}
	return re;
}
map<int,int> mp;
int countReplacement(int n, int inputSeq[]){
	for(int i=1;i<=250000;++i) mp[i]=0;
	int mn=0,tp=0;
	for(int i=0;i<n;++i){
		if(mp[inputSeq[i]]) return 0;
		mp[inputSeq[i]]=1;
		if(inputSeq[i]<inputSeq[mn]) mn=i;
		if(inputSeq[i]>n) sta[++tp]=inputSeq[i];
	} 
	sort(sta+1,sta+1+tp);
	for(int i=0;i<n;++i){
		int j=(i+mn)%n;
		if(inputSeq[j]>n) continue;
		else if(inputSeq[j]==inputSeq[mn]+i) continue;
		else return 0;
	}
	int res=1,las=n;
	for(int i=1;i<=tp;++i){
		res=(LL)res*qpow((LL)(tp-i+1),(LL)(sta[i]-1-las))%P;
		las=sta[i];
	}
	if(inputSeq[mn]>n) res=(LL)res*(LL)n%P;
	return res;
}

Friend

链接

http://uoj.ac/problem/28

题解

直接暴力是不好做的。但是容易发现每个点只有一个hostQAQ
然后i和host的关系也挺明显的,直接就是树形DP了。
直接从后往前DP(因为已经保证host<i了),然后分三类边DP就行。
f[0/1][i]表示不选/选i的情况下,i的子树的最大值。
第一类边: 最普通的树形DP
第二类边:如果选了儿子,相当于也选了父亲,儿子父亲不冲突
第三类边:如果选了儿子,相当于也选了父亲,儿子父亲冲突

\(Code\)

#include "friend.h"
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=3e5+10;
const LL P=1e9+9;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
void print(LL x){
    if(x>9) print(x/10);
    putchar(x%10+‘0‘);
}
int f[2][N];
int findSample(int n, int confidence[], int host[], int protocol[]){
	for(int i=0;i<n;++i) {
		f[0][i]=0;
		f[1][i]=confidence[i];
	}
	for(int i=n-1;i>0;--i){
		if(protocol[i]==0){
			f[0][host[i]]=max(f[0][host[i]],max(f[0][i],f[1][i])+f[0][host[i]]);
			f[1][host[i]]=max(f[1][host[i]],f[0][i]+f[1][host[i]]);
		}
		if(protocol[i]==1){
			f[1][host[i]]=max(max(f[1][host[i]],f[1][i]+f[0][host[i]]),max(f[0][i],f[1][i])+f[1][host[i]]);
			f[0][host[i]]=max(f[0][host[i]],f[0][i]+f[0][host[i]]);
		}
		if(protocol[i]==2){
			f[1][host[i]]=max(f[1][host[i]],max(f[0][i]+f[1][host[i]],f[1][i]+f[0][host[i]]));
			f[0][host[i]]=max(f[0][host[i]],f[0][i]+f[0][host[i]]);
		}
	}
	return max(f[0][0],f[1][0]);
}

Holiday

链接

http://uoj.ac/problem/29

题解

显然只有四种情况,左,右,先左后右,先右后左。
然后\(O(n^2)\)的DP就有了。然而不能过。
然后会发现这个DP是有决策单调性的。
\(g[i]\)表示想左走到i再向右走的最优的终止位置,那么有\(i \neq j\)时,\(g[i] \leq g[j]\)
然后对于决策单调性,一般来说有用数据结构优化或者分治两种路线。
这里的单调并不能保证连续,用数据结构很难直接搞,所以考虑用分治。
分治时需要多次询问区间前K大,这个用主席树即可。

\(Code\)

//#include<holiday.h>
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1e5+10;
const int INF=1e9;
int ls[N*32],rs[N*32],num[N*32];
LL sum[N*32];
int root[N];
int cnt,Lm,Rm;
void insert(int x,int &y,int l,int r,int w){
    y=++cnt;
    ls[y]=ls[x];rs[y]=rs[x];num[y]=num[x]+1;sum[y]=sum[x]+(LL)w;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(w<=mid) insert(ls[x],ls[y],l,mid,w);
    else insert(rs[x],rs[y],mid+1,r,w);
}
LL ask(int L,int R,int K){
    ++R;K=min(K,R-L);K=max(K,0);
    LL res=0;
    int l=Lm,r=Rm,mid,x=root[L],y=root[R];
    while(1){
        if(l==r) {
            K=min(K,num[y]-num[x]);
            res+=(LL)l*(LL)K;
            break;
        }
        mid=(l+r)>>1;
        if(num[rs[y]]-num[rs[x]]<K){
            res+=sum[rs[y]]-sum[rs[x]];
            K-=num[rs[y]]-num[rs[x]];
            r=mid;x=ls[x];y=ls[y];
        }
        else{
            l=mid+1;x=rs[x];y=rs[y];
        }
    }
    return res;
}
int D,star;
LL sol1(int l,int r,int L,int R){
    if(l>r) return 0;
    int mid=(l+r)>>1,x=R;
    LL res=0,y;
    for(int i=L;i<=R;++i){
        y=ask(min(mid,i),max(mid,i),D-abs(star-mid)-abs(mid-i));
        if(y>=res) {
            res=y;x=i;
        }
    }
    res=max(res,sol1(l,mid-1,L,x));
    res=max(res,sol1(mid+1,r,x,R));
    return res;
}
LL sol2(int l,int r,int L,int R){
    if(l>r) return 0;
    int mid=(l+r)>>1,x=L;
    LL res=0,y;
    for(int i=L;i<=R;++i){
        y=ask(min(mid,i),max(mid,i),D-abs(star-mid)-abs(mid-i));
        if(y>res) {
            res=y;x=i;
        }
    }
    res=max(res,sol2(l,mid-1,L,x));
    res=max(res,sol2(mid+1,r,x,R));
    return res;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]){
    cnt=0;ls[0]=0;rs[0]=0;num[0]=0;sum[0]=0;root[0]=0;Lm=0;Rm=INF;
    for(int i=0;i<n;++i){
        insert(root[i],root[i+1],Lm,Rm,attraction[i]);
    }
    LL res=0;
    for(int i=start;i<n;++i){
        //cout<<start<<" "<<i<<" "<<d-(i-start)<<" "<<ask(start,i,d-(i-start))<<endl;
        res=max(res,ask(start,i,d-(i-start)));
    }
    for(int i=start;i>=0;--i){
        res=max(res,ask(i,start,d-(start-i)));
    }
    D=d;star=start;
    res=max(res,sol2(0,start-1,start,n-1));
    res=max(res,sol1(start+1,n-1,0,start));
    return res;
}
//int n,start,d,attraction[N];
//int main(){
//    scanf("%d%d%d",&n,&start,&d);
//    for(int i=0;i<n;++i)
//        scanf("%d",&attraction[i]);
//    printf("%lld\n",findMaxAttraction(n,start,d,attraction));
//    return 0;
//}

【日常摸鱼】IOI2014

标签:protoc   back   线段   有一个   pow   insert   从后往前   return   print   

原文地址:https://www.cnblogs.com/Yuigahama/p/13656834.html

版权声明:完美者 发表于 2020-12-16 12:31:52。
转载请注明:【日常摸鱼】IOI2014 | 完美导航

暂无评论

暂无评论...