A simple Blog for wyx I've been down the bottle hoping.
POI2014
发表于: | 分类: Oi | 评论:0 | 阅读:123

#POI2014

之前的2015写的自己真是神清气爽,最后剩的题是一点都不想写了……
然后投靠了POI2014…………

###3521: [Poi2014]Salad Bar
$Description$
有一个长度为n的字符串,每一位只会是p或j。你需要取出一个子串S(从左到右或从右到左一个一个取出),使得不管是从左往右还是从右往左取,都保证每时每刻已取出的p的个数不小于j的个数。你需要最大化|S|。
$Soliution$
把一个p看成一个+1,一个j看成一个-1,然后求前缀和,容易发现$[l,r]$满足题中的条件当且仅当 $a[l-1]$是a$[l,r]$的最小值,而$a[r]$是$a[l,r]$的最大值。

这个东西可以用单调栈玩,能求出第一个比他大的位置low,后边第一个比他小的位置far

然后枚举一下右端点,线段树查low到i中far比i大而且最靠前的点,就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int inf = 0x7fffff;
const int N = 1000000;
const int M = N << 2; 
using namespace std;

int tr[M],far[N],low[N];
int sum[N];

char str[N];

inline void updata(int k)
{
    tr[k] = max(tr[k<<1],tr[k<<1|1]);
}

void build(int k,int l,int r)
{
    if(l==r){tr[k] = far[l];return ;}
    int mid = (l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    updata(k);
}

int find(int k,int l,int r,int val)
{
    if(tr[k] < val)return inf;
    if(l==r) return l;
    int mid = (l+r)>>1;
    if(tr[k<<1] >= val)
        return find(k<<1,l,mid,val);
    else return find(k<<1|1,mid+1,r,val);
}

int ask(int k,int l,int r,int x,int y,int val)
{
    if(l == x && r == y)return find(k,l,r,val);
    int mid = (l+r)>>1;
    if(r <= mid)return ask(k<<1,l,mid,x,y,val);
    else if(l>mid)return ask(k<<1|1,mid+1,r,x,y,val);
    else 
    {
        int t = ask(k<<1,l,mid,x,mid,val);
        if(t != inf) return t;
        return ask(k<<1|1,mid+1,r,mid+1,y,val);
    }
}

int stack[N];

int main()
{
    int n,ans = 0;
    scanf("%d%s",&n,str+1);
    for(int i=1;i<=n;++i)
        sum[i] = sum[i-1] + (str[i] == 'p' ? 1 : -1); 
    stack[0] = -1;

//  for(int i=1;i<=n;++i)
//      cout << sum[i] << " ";

    register int top = 0;
    stack[0] = -1;
    stack[++top] = 0;

    for(int i=1;i<=n;++i)
    {
        while(top  && sum[stack[top]] <= sum[i]) top --;
        low[i] = stack[top] + 1;
        stack[++top] = i;
    }
    top = 0;
    stack[++top] = n + 1;
    sum[n+1] = -inf;

    for(int i=n;~i;--i)
    {
        while(top && sum[stack[top]] >= sum[i]) top --;
        far[i] = stack[top] -1;
        stack[++top] = i;
    }

//  for(int i=1;i<=n;++i)
//        cout << far[i] << " " << low[i] << " "<< endl;
    build(1,0,n);  

    for(int i=1;i<=n;++i)
    {
        if(low[i]!=i && i-low[i] > ans)
            ans = max(ans,i-ask(1,0,n,low[i],i-1,i));
    }
    
    cout << ans << endl;

}

###3522: [Poi2014]Hotel
$Description$
给定一棵树,找到三个点,使得三个点到中心点的距离相同,中心点相同算相同方案,求一共多少种方案
树的节点数 $<=5000$

$Solution$
大概这题的数据范围比较小……我就暴力过的……
我要是知道正解以后再重写一下
先说一下暴力怎么写吧
枚举中间点,记录总数,两个点的合法组合数(即不在同一棵子树中的任意搭配)
然后每次$BFS$或者$DFS$跑一下开桶统计一下就行了

时间复杂度$O(N^2)$
要是觉得虚你可以写一下非递归,能快一些

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define N 5000+5
#define M 10000+5
typedef long long LL;
int head[N];

struct graph
{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x);
    head[y] = cnt;
}

int tmp[N],f[N],g[N];

void DFS(int x,int fa,int depth)
{
    tmp[depth]++;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa)
            DFS(edge[i].to,x,depth+1);
}

inline 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<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{
    int n = read();
    for(int i=1;i<n;++i)
    {
        int x = read(),y =read();
        add(x,y);
    }
    LL ans = 0;
    for(int i=1;i<n;++i)
    {
        memset(f,0,sizeof f);
        memset(g,0,sizeof g);
        for(int j=head[i];j;j=edge[j].next)
        {
            memset(tmp,0,sizeof tmp);
            DFS(edge[j].to,i,1);
            for(int k=1;k<=n;++k)
            {
                ans += (LL)(g[k])*tmp[k];
                g[k] +=(LL)f[k] * tmp[k];
                f[k] += tmp[k];
            }
        }
    }
    cout<<ans<<endl;
}

###3523: [Poi2014]Bricks

$Description$
有n种颜色的砖块,第i种颜色的砖块有a[i]个,你需要把他们放成一排,使得相邻两个砖块的颜色不相同,限定第一个砖块的颜色是start,最后一个砖块的颜色是end,请构造出一种合法的方案或判断无解。
$Solution$
显然可以贪心,每次选出数量最多的一个
如果数量相同,就选择末尾的col
然后不合法就不合法了
拿一个堆优化一下就行了

#include <iostream>
#include <cstdio>
#include <queue>
#include <stdlib.h>
#define N 1000010
using namespace std;
struct data
{
    int w,c;
};
int st,en;
bool operator <(const data &x,const data &y)
{
    if(x.w!=y.w) return x.w<y.w;
    if(x.c==en) return false;
    return true;
}

priority_queue<data>q;

void quit()
{
    puts("0");
    exit(0);
}

int ans[N];
int main()
{
    int n;
    scanf("%d%d%d",&n,&st,&en);
    int i,j,x,y,m=0;
    data t,tmp;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&t.w);
        m+=t.w;
        t.c=i;
        if(i==st) t.w--;
        if(i==en) t.w--;
        if(t.w<0) quit();
        q.push(t);
    }
    ans[1]=st;ans[m]=en;
    bool f;
    for(i=2;i<m;i++)
    {
        t=q.top();f=false;
        q.pop();
        if(t.c==st)
        {
            tmp=t;
            if(!q.empty()) 
                t=q.top();
            else quit();
            q.pop();
            f=true;
        }
        st=ans[i]=t.c;
        if(t.w>1)
        q.push((data){t.w-1,t.c});
        if(f) q.push(tmp);
    }
    if(ans[m-1]==ans[m]) {puts("0");return 0;}
    for(i=1;i<=m;i++)
    printf("%d ",ans[i]);
    
}

###3524: [Poi2014]Couriers

$Description$

给一个长度为n的序列a。1≤a[i]≤n。
m组询问,每次询问一个区间[l,r],是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在,输出这个数,否则输出0。

$Solution$
我们把n个数建立可持久化线段树后对于每个询问区间,我们向他区间元素个数大于(R-L+1)/2的子区间继续查询,知道最后区间大小为1或者区间元素个数小于(R-L+1)/2

然后维护一下区间的最大值就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10000000 +10;

inline 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<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int root[500000+10];
int sz,n,m;
int ls[N],rs[N];
int tr[N];

void add(int l,int r,int x,int &y, int dat)
{
    y = ++sz;
    tr[y] = tr[x] + 1;
    if(l==r)return;
    ls[y] = ls[x];
    rs[y] = rs[x];
    int mid = (l + r)>>1;
    if(dat <= mid)add(l,mid,ls[x],ls[y],dat);
    else add(mid+1,r,rs[x],rs[y],dat);
}

int ask(int l,int r)
{
    int L = 1;
    int R = n;
    int len = (r - l + 1) >> 1;
    int x = root[l - 1],y = root[r];
    while(L != R)
    {
        if(tr[y] - tr[x] <= len) return 0;
        int mid = (L+R)>>1;
        if(tr[ls[y]] - tr[ls[x]] > len)
        {
            R = mid;
            x = ls[x];
            y = ls[y];
        }
        else if(tr[rs[y]] - tr[rs[x]] > len)
        {
            L = mid + 1;
            x = rs[x];
            y = rs[y];
        }
        else return 0;
    }
    return L;   
}


int main()  
{  

    n = read(), m =read();
    for(int i=1;i<=n;++i)
    {
        int x = read();
        add(1,n,root[i-1],root[i],x);
    }
    for(int i=1;i<=m;++i)
    {
        int x = read(), y = read();
        printf("%d\n",ask(x,y));
    }

}  

###3526: [Poi2014]Card
$Description$
有n张卡片在桌上一字排开,每张卡片上有两个数,第i张卡片上,正面的数为a[i],反面的数为b[i]。现在,有m个熊孩子来破坏你的卡片了!
第i个熊孩子会交换c[i]和d[i]两个位置上的卡片。
每个熊孩子捣乱后,你都需要判断,通过任意翻转卡片(把正面变为反面或把反面变成正面,但不能改变卡片的位置),能否让卡片正面上的数从左到右单调不降。
$Solution$
线段树
显然对于一段来说结尾的数字越小越好,开头的数字会决定结尾多大
维护一下区间的第一张牌以较小或较大的数开始,这个区间最后一张牌用尽量小的的数来结尾的话,会选较小的还是较大的还是无解。
换位置就是两次单点修改了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 200000+5;
const int M = N << 2;
const int inf = 0x7ffffff;
using namespace std;
 
int a[N],b[N];
int tr1[M],tr2[M];
 
inline 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<<1) + (x<<3) + ch - '0';ch = getchar();}
    return x*f;
}
 
inline void updata(int k,int l,int r)
{
    int mid = (l+r) >> 1;
    if(a[mid+1] >= tr1[k<<1]) tr1[k] = tr1[k<<1|1];
    else if(b[mid+1] >= tr1[k<<1]) tr1[k] = tr2[k<<1|1];
    else tr1[k] = inf;
    if(a[mid+1] >= tr2[k<<1]) tr2[k] = tr1[k<<1|1];
    else if(b[mid+1] >= tr2[k<<1]) tr2[k] = tr2[k<<1|1];
    else tr2[k] = inf;
}
 
void build(int k,int l,int r)
{
    if(l==r)
    {
        tr1[k] = a[l];
        tr2[k] = b[l];
        return ;
    }
    int mid = (l+r) >> 1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    updata(k,l,r);
}
 
void change(int k,int l,int r,int pos)
{
    if(l==r)
    {
        tr1[k] = a[l];
        tr2[k] = b[l];
        return ;
    }
    int mid = (l+r) >> 1;
    if(pos <= mid) change(k<<1,l,mid,pos);
    else change(k<<1|1,mid+1,r,pos);
    updata(k,l,r);
}
 
int main()
{
    int n = read();
    for(int i=1;i<=n;++i)
    {
        a[i] = read(), b[i] = read();
        if(a[i] > b[i]) swap(a[i],b[i]);
    }
    build(1,1,n);
    int T = read();
    while(T--)
    {
        int x = read(),y = read();
        swap(a[x],a[y]);
        swap(b[x],b[y]);
        change(1,1,n,x);
        change(1,1,n,y);
        if(tr1[1] == inf)  puts("NIE");
        else puts("TAK");
    }
}

###3827: [Poi2014]Around the world
$Description$
通过几年的努力,Byteasar最终拿到了飞行员驾驶证。为了庆祝这一事实,他打算买一架飞机并且绕Byteotia星球赤道飞行一圈。但不幸的是赤道非常长所以需要中途加几次油。现在已知赤道上面所有飞机场,所有飞机从飞机场起飞降落也可以加油。因为买飞机是个十分重大的决定,Byteasar决定寻求你的帮助。他将会让你模拟不同的飞行路线。自然这些飞机一次能走的航程是不同的。对于每次模拟,他想要知道最少需要降落多少次(包括最后一次)。需要注意的是起点可以任意选取。
$Solution$
对于每个询问,设油量为d。
先预处理出每个点走一次最多走到哪,这个双指针扫一遍 $O(n)$。
然后得到一颗树,算一下每个点的深度。
枚举起点,在树上一直向上爬,直到距离超过n,爬的过程同时用并查集合并。
直接并查集可能会GG,你可以维护一个$next$各种乱搞

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000001;
const int inf = 2147483647;
#define min(a,b) ((a)<(b) ? (a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
int l[N],next[N<<1],depth[N<<1],n,s,d;
 
char getc()
{
    static const int LEN = 1<<15;
    static char buf[LEN],*S=buf,*T=buf;
    if(S == T)
    {
        T = (S=buf)+fread(buf,1,LEN,stdin);
        if(S == T)return EOF;
    }
    return *S++;
}
 
int read()
{
    static char ch;
    static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0'; isdigit(ch=getc());)
        D=(D<<3)+(D<<1)+(ch-'0');
    return D;
}
 
int calc(int x)
{
    register int fa = x, now = x;
    while(fa - x < n)
        fa = next[fa];
    int k ;
    while(now - x < n)
    {
        k = next[now];
        next[now] = fa;
        now = k;
    }
    return depth[x] - depth[now];
}
 
int MIN = 0;
 
int main()
{
    n = read(), s = read();
    for(int i=1;i<=n;++i)
        l[i] = read(),MIN = max(MIN,l[i]);
    while(s--)
    {
        d = read();
        if(d < MIN)
        {
            puts("NIE");
            continue;
        }
        int sum = 0;
        register int j = 1, i = 1;
        int tmp = n << 1;
        for(i = 1; i <= tmp; ++i)
        {
            while( j < tmp && sum + l[(j>n) ? j-n : j] <= d)
                sum = sum + l[j>n ? (j-n) : j],j ++;
            next[i] = j;
            sum -= l[i>n ? (i-n) : i];
        }
        j = inf,depth[tmp] = 0;
        for(i = tmp;i >= 1; --i)
            depth[i] = depth[next[i]] + 1;
        for(i = 1;i <= n; ++i)
            j = min(j,calc(i));
        printf("%d\n",j);
    }
}

###3829: [Poi2014]FarmCraft
mhy住在一棵有n个点的树的1号结点上,每个结点上都有一个妹子。
mhy从自己家出发,去给每一个妹子都送一台电脑,每个妹子拿到电脑后就会开始安装zhx牌杀毒软件,第i个妹子安装时间为Ci。
树上的每条边mhy能且仅能走两次,每次耗费1单位时间。mhy送完所有电脑后会回自己家里然后开始装zhx牌杀毒软件。
卸货和装电脑是不需要时间的。求所有妹子和mhy都装好zhx牌杀毒软件的最短时间。

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP