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

一只老年OI选手艰难的写着2011的POI
如果发现有的题没有题解,你可以先上这里看看
如果这里也没有,说明这题我不(根)太(本)清(不)楚(会),请自行百度
###2212: [Poi2011]Tree Rotations
$Description$
现在有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点,满足这些权值为1..n的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换,使得最终所有叶子节点的权值按照遍历序写出来,逆序对个数最少
$Solution$
对于一个非叶子节点,是否交换它的儿子对它之后的统计没有影响
所以我们需要做的就是统计每个点左右儿子是否交换,并暴力求出每个节点贡献的逆序对数
我们该怎么办呢?
线段树合并就行了
对于每个节点,建出权值线段树
每次查询右子树的权值线段树和左子树的权值线段树,左子树中比右子树小的有多少?右子树比左子树小的有多少?(分别对应不交换的逆序对和交换的逆序对)
将左子树和右子树的权值线段树合并
递归进行这个操作就行了
运行复杂度 $O(跑得过)$,理论上的最坏复杂度是$ O(nlog(n))$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 200000+5
#define M 8000000+5
using namespace std;
typedef long long LL;
int ls[M],rs[M],l[M],r[M];
int size[M],v[M],root[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;
}

int n,sz;
int mempool;

void build_a_tree(int x)
{
    v[x] = read();
    if(!v[x])
    {
        l[x] = ++sz;
        build_a_tree(l[x]);
        r[x] = ++sz;
        build_a_tree(r[x]);
    }
}

void updata(int k)
{
    size[k] = size[ls[k]] + size[rs[k]];
}

inline void insert(int &k,int l,int r,int val)
{
    if(!k) k = ++mempool;
    if(l==r){size[k] = 1;return;}
    int mid = (l+r)>>1;
    if(val <= mid)
        insert(ls[k],l,mid,val);
    else insert(rs[k],mid+1,r,val);
    updata(k);  
}

LL cnt1 , cnt2;

int merge(int x,int y)
{
    if(!x) return y;
    if(!y) return x;
    cnt1 += (LL)size[rs[x]] * size[ls[y]];
    cnt2 += (LL)size[ls[x]] * size[rs[y]];
    ls[x] = merge(ls[x],ls[y]);
    rs[x] = merge(rs[x],rs[y]);
    updata(x);
    return x;
}

LL ans = 0;

void solve(int x)
{
    if(!x)return;
    solve(l[x]);solve(r[x]);
    if(!v[x])
    {
        cnt1 = cnt2 = 0;
        root[x] = merge(root[l[x]],root[r[x]]);
        ans += min(cnt1,cnt2);
    }
}

int main()
{   
    int n = read();
    ++sz;
    build_a_tree(1);
    for(int i=1;i<=sz;++i)
        if(v[i])
            insert(root[i],1,n,v[i]);
    solve(1);
    cout<<ans;
}

###2213: [Poi2011]Difference
$Description$
已知一个长度为n的由小写字母组成的字符串,求其中连续的一段,满足该段中出现最多的字母出现的个数减去该段中出现最少的字母出现的个数最大。求这个个数。
$Solution$
套路题,这样的题做过的至少三道了
首先我们容易想到维护前缀和,然后这个东西就变成了最大化$(sum_{col1}[i]-sum_{col1}[j])-(sum_{col2}[i]-sum_{col2}[j])$
然后把带$i$的放在一起,发现就是求一个有关$sum_{col1}[i]-sum_{col2}[i]$
然后发现不需要前缀和了,只需要记录一下两两的差就行了
然后维护一个最小值,每次更新答案
然后WA了
??????【黑人问号脸
回头看题,出现的次数,出题人真阴险,没出现的不算。
然后就又套路了记次数+次小值……

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1e6+5;
using namespace std;

int cnt[27][27];
int tot[N];
int MIN[27][27];
int MIN_L[27][27];
int sec[27][27];
char str[N];
int ans = 0;

void calc(int x,int y){
    if(cnt[x][y] != tot[y])
        ans = max(ans,MIN[x][y] - MIN_L[x][y]);
    else ans = max(ans,MIN[x][y]-sec[x][y]);
    if(MIN[x][y] < MIN_L[x][y])
    {
        if(cnt[x][y] == tot[y]) MIN_L[x][y] = MIN[x][y];
        else{
            sec[x][y] = MIN_L[x][y];
            MIN_L[x][y] = MIN[x][y];
            cnt[x][y] = tot[y];
        }
    }
    else if(MIN[x][y] < sec[x][y]) 
        if(cnt[x][y]!=tot[y])
            sec[x][y] = MIN_L[x][y];    
}

int main()
{
    int n; cin >> n;
    scanf("%s",str+1);
    memset(sec,0x3f,sizeof sec);
    for(int i=1,j=1;i<=n;++i)
    {
        int tmp = str[i] - 'a' + 1;
        tot[tmp] ++;
        for(j=1;j<=26;++j)
            if(tmp!=j)
            {
                MIN[tmp][j] ++;
                calc(tmp,j);
                MIN[j][tmp] --;
                calc(j,tmp);
            }
    }
    cout << ans << endl;
}

###2216: [Poi2011]Lightning Conductor
$Description$
已知一个长度为n的序列$a_1,a_2,...,a_n$。
对于每个1<=i<=n,找到最小的非负整数p满足 对于任意的j, $a_j \le a_i + p - \sqrt{|i-j|}$
$Solution$
本年的单调性问题01
首先令$j\le i$ 因为另一半倒过来再做一遍就行了
然后有 $a_j-a_i+\sqrt{i-j} \le p$
然后就有$p=max{a_j+\sqrt{i-j}}-a[i]$
显然决策单调

所以我们可以用一个队列维护一段元素,队列中的每一个元素都有一个区间,代表这个区间中的数都可以用他来进行转移
每进行到一次转移,我们将队头元素的区间左端点+1,若左端点>右端点就出队

然后考虑当前决策点,如果他比队尾优,那么我们就可能可以将它加入队列,比较方法就是用最后一个元素a[n]比较算出的p的大小。因为我们在队列中维
护的元素会覆盖整个[1,n]的元素,所以一旦当前元素比队尾优我们一定用不到队尾的元素了

然后进一步比较,比较队尾的左端点时的答案
一旦i比队尾的左端点的答案都优了,那么队尾就真废了,出队,知道有一个队尾的左端点不虚,那么我们在他的决策区间中查询到一个位置使得在这个位
置上队尾又虚了,那么后面的所有转移就都由i这个点来完成了,入队

###2217: [Poi2011]Lollipop
$Description$
有一个长度为n的序列a1,a2,...,an。其中ai要么是1("W"),要么是2("T")。
现在有m个询问,每个询问是询问有没有一个连续的子序列,满足其和为q。
$Solution$
我们先维护一个前缀和,然后如果有和为q的就直接输出【废话
然后要是没有怎么办,发现权值不是1就是2,所以一定存在一个q+1
然后我们将这个区间平移,显然前面+2后面-2一定和还是q+1,他就在数轴上默默地平移,知道前面或者后面遇到了一个可爱的1,或者,他掉出去了
直接挪肯定GG,记录一个连续的2的个数就行了
好像还可以像我一样直接把答案都预处理一下

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1000000+5;
using namespace std;
 
int sum[N];
char str[N];
int ext[N];
int l[2*N],r[2*N];
 
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 main()
{
    int n,m;
    cin >> n >> m;
    scanf("%s",str+1);
    register int  i = 1;
    for(i=1;i<=n;++i) sum[i] = sum[i-1] + (str[i] == 'W' ?  1 : 2);
    for(i=n;i;--i)
    {
        ext[i] = ext[i+1] + 1;
        if(str[i] == 'W') ext[i] = 0;
    }
    for(i=1;i<=n;++i)
    {
        l[sum[i]] = 1;
        r[sum[i]] = i;
        if(str[i] == 'T')
        {
            if(ext[1] < ext[i])
                l[sum[i]-1] = ext[1] + 2, r[sum[i]-1] = i + ext[1];
            else if(i+ext[i] <= n)
                l[sum[i]-1] = ext[i] + 1, r[sum[i]-1] = i + ext[i];
        }
    }
    for(i=1;i<=m;++i)
    {
        int x = read();
        if(!l[x])
            puts("NIE");
        else
            printf("%d %d\n",l[x],r[x]);
    }
}

###2276: [Poi2011]Temperature
$Description$
某国进行了连续n天的温度测量,测量存在误差,测量结果是第i天温度在$[l_i,r_i]$范围内。
求最长的连续的一段,满足该段内可能温度不降。
$Solution$
本年的单调性问题02
首先要明确一个事情,假设现在有一段区间$[l,r]$是和法的,$[l,r+1]$是合法的当且仅当$MIN_{[l,r]}$比他的上端点小,就是一段区间的最小值比他的上面的点还小
然后这个区间最大值可以用单调队列维护一下

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
const int N = 1000000+5;

using namespace std;

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 L[N],R[N];

int q[N];

int main()
{
    int n = read();
    for(int i=1;i<=n;++i) L[i] = read() , R[i] = read();
    int l = 1,r = 0,ans = 1;L[0] = -1e9;R[n+1] = 1e9;
    int i = 1,j = 1;q[1] = 1;
    for(i=1;i<=n;++i)
    {
        if(j==i) ++j;
        if(q[l] == i-1) ++l;
        while(j<=n && L[q[l]] <= R[j])
        {
            while(l<=r && L[q[r]] <= L[j]) --r;
            q[++r] = j ++;
        }
        ans = max(ans,j-i);
    }
    cout << ans << endl;
}

###2277: [Poi2011]Strongbox
$Description$
有一个密码箱,0到n-1中的某些整数是它的密码。且满足,如果a和b都是它的密码,那么(a+b)%n也是它的密码(a,b可以相等)
某人试了k次密码,前k-1次都失败了,最后一次成功了。
问:该密码箱最多有多少不同的密码。
$Solution$
首先这是一道数学题
我们考虑a是密码,b是,a+b是。这样的话a+2b也是
令$t = gcd(a,b)$
$a=xt,b=yt$
然后$x+y,x+2y,x+3y...2x+y,3x+y,4x+y....$
所以是他俩的gcd倍数的数就都是密码了。
所以假如x是密码,则所有gcd(x,n)的倍数就一定是密码,反之则一定不是
最后一次试出来了说明x|gcd(a[k],n)
且x又不能整除gcd(a[i],n),其中i<k
暴力枚举所有可能的x.然后直接检验是否满足不能整除gcd(a[i],n)就可以了
复杂度不会算

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
long long a[250001],cnt;
bool check(long long x)
{
    long long i;
    for(i=1;i<=cnt;i++)
        if(a[i]%x==0) 
            return false;
    return true;
}
long long gcd(long long a,long long b)
{
    if(a==0) return b;
    return gcd(b%a,a);
}
int main()
{
    long long n,k; cin >> n >> k;
    for(int i=1;i<=k;i++)
        scanf("%lld",&a[i]);
    long long ans=n;
    long long i = 1;
    for(i=1;i<=k;i++)
        a[i]=gcd(n,a[i]);
    sort(a+1,a+k);
    for(i=1;i<k;i++)
        if(a[i]!=a[i-1])
            a[++cnt] = a[i];

    for(i=1;i<=sqrt(a[k]);i++)
        if(a[k]%i==0)
        {
            if(check(i)) {ans=n/i;break;}
            else if(check(a[k]/i)) ans=n/a[k]*i;
        }
    cout << ans << endl;
}

###2278: [Poi2011]Garbage
$Description$
某国的街道很脏,可以开一些清理车去清理它们。
每次清理车走的路是一个环,清理完之后环上所有的街道改变状态(脏->不脏,不脏->脏)
给出初始状态和终止状态,求一个合法的清理车清理方案。
$Solution$
首先,一定存在一种方案使得一条边最多走一次
大概可以这样感性理解一下


黑色是原有的路径,绿色和红色分别的车的两次行驶路线
首先一条边走了两次相当于没走
那么红绿在一起的部分相当于没动
对于这种方案我们可以让第一个绿色在红绿交界处直接走红的,再交接的时候 走绿的
红的同理
然后就保证一条边走一次了

所以这题其实就是想让你吧不用变的去掉玩一个欧拉回路

然后写暴搜
然后T
??????【黑人问号
woc数据好强,他竟然玩出了一个5w个褶的菊花。
然后我们扫一条边删一条边
过了

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <bitset>
using namespace std;
#define N 131072
#define M 2100000
#define LEN 1<<20
 
bitset <N> vis;
bitset <N> du;
bitset <M> ban;
using namespace std;
int to[M],next[M],head[N],ce=1;
int cnt;
 
inline char getc()
{
    static char *S,*T,buf[LEN];
    if(S==T)
    {
        T=(S=buf)+fread(buf,1,LEN,stdin);
        if(S==T)
            return EOF;
    }
    return *S++;
}
 
inline int read()
{
    static char ch;
    static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0';isdigit(ch=getc());)
        D=D*10+ch-'0';
    return D;
}
 
namespace ans
{
    int val[M],next[M],head[N<<1],size[N<<1],ce;
    void add(int x,int y)
    {
        size[x]++;
        val[++ce]=y;
        next[ce]=head[x];
        head[x]=ce;
    }
}
 
void add(int x,int y)
{
    to[++ce]=y;
    next[ce]=head[x];
    head[x]=ce;
}
 
int dfs(int x,int pre)
{
    vis[x]=1;
    int i,y;
    for(i=head[x];i;i=next[i])
    {
        if(ban[i]||(i^1)==pre)  continue;
        if(!vis[to[i]])
        {
            y=dfs(to[i],i);
            ans::add(cnt,x);
            ban[i]=ban[i^1]=1;
            head[x]=next[i];
            if(x!=y)
            {
                vis[x]=0;
                return y;
            }
        }
        else
        {
            cnt++;
            ans::add(cnt,to[i]);
            ans::add(cnt,x);
            ban[i]=ban[i^1]=1;
            head[x]=next[i];
            vis[x]=0;
            return to[i];
        }
    }
    vis[x]=0;
    return 0;
}
int main()
{
    int n,m,k,x,y,z,w;
    register int i,j;
    n=read(),m=read();
    for(i=1;i<=m;i++)
    {
        x=read(),y=read(),z=read(),w=read();
        if(z!=w)
            add(x,y),add(y,x),du[x]=!du[x],du[y]=!du[y];
    }
 
    for(i=1;i<=n;i++) if(du[i]){puts("NIE");return 0;}
    for(i=1;i<=n;i++)if(head[i])dfs(i,0);
 
    cout << cnt << endl;
    for(i=1;i<=cnt;i++)
    {
        printf("%d ",ans::size[i]-1);
        for(j=ans::head[i];j;j=ans::next[j])
        {
            printf("%d ",ans::val[j]);
        }
        puts("");
    }
    return 0;
}

###2526: [Poi2011]Inspection
$Desription$
首先选定一个行动中心S,并且检查S。
从S出发前往任意一个未检查的点(沿树上两点的唯一最短路走),检查该节点,然后返回S。
特别地,检查完最后一个节点后不需要返回。
检查节点不需要时间,走过一条路的时间为1。
为了不暴露身份,Byteasar规定相邻两次检查所经过的道路不允许有重复。
也就是说,除第一次检查之外,他每次从S出发走过的第一条边不能和上一次出发相同。
输入:
第一行是一个整数N。(1<=n<=1000000)
接下来N-1行每行有2个整数A,B,表示A和B之间有一条边。
输出:
N行,第I行表示如果以I作为行动中心,Byteasar检查完所有车站需要的最小时间。如果不可能做到,该行输出-1。
$Solution$
对于一个点来说,答案肯定是深度和*2-过当前根节点的最长路
对于不同的节点肯定是扭一扭就行啊,求一条最长一条次长,最长链转移细节随便判断一下就行啊
然后对于深度和的扭一扭普及组小孩都会啊
然后无解的判定,肯定一棵子树>n/2就一定不合法
噼里啪啦码完,交上去GG
??????????【我真的是老年OI选手了 么,这都错了?????
看了半天,丝毫不像有问题的样子
一个点的特判???还是什么奇怪的事情??难道我最长链求错了??别吓我
随便调整几个细节,接着wa
下数据,仔细观察发现了这样一个景观:一棵子树大小恰好为n/2且n是偶数 ,lemon告诉我我错了 【完了一定是老年选手了
手画一下,woc我知道为啥了,子树大小为n/2,必须先走他,然后再走其他的,最后还得走他
最后还得走他!!!
最后还得走他!!!
最后还得走他!!!
最后是停在他这的!!!加最长路加他的最长路,坑死啦!!!!

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 1000010;
const int M = N << 1;
typedef long long LL;
using namespace std;
 
int head[N];
int fa[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 fir[N],sec[N];
int mx[N],size[N];
LL tot[N];
 
void DFS1(int x)
{
    size[x] = 1;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa[x])
        {
            fa[edge[i].to] = x;
            DFS1(edge[i].to);
            tot[x] += size[edge[i].to] + tot[edge[i].to];
            size[x] += size[edge[i].to];
            sec[x] = max(sec[x],fir[edge[i].to]+1);
            if(fir[x] < sec[x]) swap(fir[x],sec[x]);
            mx[x] = max(mx[x],size[edge[i].to]);
        }
}
 
int n;
LL ans[N];
 
void DFS2(int x,int lg,LL tmp)
{
    if(max(mx[x],n-size[x]) > n/2) ans[x] = -1;
    else if(max(mx[x],n-size[x]) == n/2 && (n%2) == 0)
    {
        if(n-size[x] == n/2) ans[x] = 2*tot[x]+tmp-lg;
        else
            for(int i=head[x];i;i=edge[i].next)
                if(size[edge[i].to] == mx[x])
                    ans[x] = 2*tot[x] + tmp - fir[edge[i].to] - 1;
    }
    else
        ans[x] = 2*tot[x]+tmp-max(fir[x],lg);
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa[x])
        {
            if(fir[x] == fir[edge[i].to] + 1)
                DFS2(edge[i].to,max(sec[x],lg)+1,tmp+2*(tot[x]-tot[edge[i].to]+n-2*size[edge[i].to]));
            else
                DFS2(edge[i].to,max(fir[x],lg)+1,tmp+2*(tot[x]-tot[edge[i].to]+n-2*size[edge[i].to]));
        }
} 
 
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()
{
    n = read();
    for(int i=1;i<n;++i)
    {
        int x = read(),y = read();
        add(x,y);
    }
 
    DFS1(1);
    DFS2(1,0,0);
    for(int i=1;i<=n;++i) 
        printf("%lld\n",ans[i]);
}

###2527: [Poi2011]Meteors
$Description$
这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。
BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家,它需要在第几次陨石雨之后,才能收集足够的陨石。
输入:
第一行是两个数N,M。
第二行有M个数,第i个数Oi表示第i段轨道上有第Oi个国家的太空站。
第三行有N个数,第i个数Pi表示第i个国家希望收集的陨石数量。
第四行有一个数K,表示BIU预测了接下来的K场陨石雨。
接下来K行,每行有三个数Li,Ri,Ai,表示第K场陨石雨的发生地点在从Li顺时针到Ri的区间中(如果Li<=Ri,就是Li,Li+1,...,Ri,否则就是Ri,Ri+1,...,m-1,m,1,...,Li),向区间中的每个太空站提供Ai单位的陨石样本。
输出:
N行。第i行的数Wi表示第i个国家在第Wi波陨石雨之后能够收集到足够的陨石样本。如果到第K波结束后仍然收集不到,输出NIE。
数据范围:
数据范围:
1<=n,m,k<=3*10^5
1<=Pi<=10^9
1<=Ai<10^9

$Solution$
首先可以想到二分答案,每一次On验证妥妥被卡
然后想要快速验证
然后主席树
MLE
调小一点
RE
………………
还是只能二分,但是这一次我们把对应时刻的询问放在一起处理就行了
然后每次询问的时候线段树乱玩一下就行了,线段树直接维护lazy就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 300000+5;
const int M = N << 2;
using namespace std;

#define min(a,b) ((a)<(b)?(a):(b))
  
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 lazy[M];

inline void down(int k,int l,int r)
{
    int tmp = lazy[k];
    if( l==r || !tmp) return;
    lazy[k<<1] += tmp;
    lazy[k<<1] = min(lazy[k<<1],(int)1e9);
    lazy[k<<1|1] += tmp;
    lazy[k<<1|1] = min(lazy[k<<1|1],(int)1e9);
    lazy[k] = 0;
}

void change(int k,int l,int r,int x,int y,int z)
{
    if(l==x && r==y)
    {
        lazy[k] += z;
        if(lazy[k] > 1e9)
            lazy[k] = 1e9;
        return;
    }
    down(k,l,r);
    int mid = (l+r)>>1;
    if(y <= mid) change(k<<1,l,mid,x,y,z);
    else if(x > mid) change(k<<1|1,mid+1,r,x,y,z);
    else change(k<<1,l,mid,x,mid,z),change(k<<1|1,mid+1,r,mid+1,y,z);
}

int Task(int k,int l,int r,int pos)
{
    if(l==r)
        return min(lazy[k],(int)1e9);
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(pos <= mid)return Task(k<<1,l,mid,pos);
    else return Task(k<<1|1,mid+1,r,pos);
}

struct q
{
    int l,r;
    int need;
    int x;
    void out()
    {
        printf("now = %d l = %d r = %d need = %d\n",x,l,r,need);
    }
}ask[M];

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

int mp[N];

inline void countryadd(int x,int y)
{
    static int cnt = 0;
    tmp[++cnt] = country(mp[x],y);
    mp[x] = cnt;
}

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

int head[N];
int cnt = 0;

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

int tmpcnt;
int tmphead[N];

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

inline void tmpadd(int x,int y)
{
    tmpedge[++tmpcnt] = tmpdata(tmphead[x],y);
    tmphead[x] = tmpcnt;
}

int T[N];

struct oper
{
    int l,r;
    int z;
}opt[N];

int ans[N];

int main()
{
//  freopen("16.in","r",stdin); 
    int n = read(), m =read();
    for(int i=1;i<=m;++i)
    {
        int tt = read();
        countryadd(tt,i);
    }
    for(int i=1;i<=n;++i) T[i] = read();
    int k = read();
    for(int i=1;i<=k;++i) opt[i].l = read(),opt[i].r = read(),opt[i].z = read();

    int tttt = k + 1 ;
    tttt >>= 1;
    for(int i=1;i<=n;++i)
    {
        ask[i].x = i;
        ask[i].l = 1;
        ask[i].r = k + 1;
        ask[i].need = T[i];
        add(tttt,i);
    }

    int tot = 21;
    while(tot--)
    {
//      cout << tot << endl;
        memset(lazy,0,sizeof lazy);
        cnt = tmpcnt = 0;
        for(int i=1;i<=k;++i)
        {
            if(opt[i].l <= opt[i].r)
                change(1,1,m,opt[i].l,opt[i].r,opt[i].z);
            else change(1,1,m,1,opt[i].r,opt[i].z),change(1,1,m,opt[i].l,m,opt[i].z);
            for(int j=head[i];j;j=edge[j].next)
            {
                int sum = 0;
                int now = edge[j].to;
    //          ask[now].out();
                if(ask[now].l == ask[now].r)
                {
                    ans[now] = i;
                    head[i] = edge[j].next;
                    continue;
                }

                for(int l=mp[now];l;l=tmp[l].next)
                {
                    sum = sum + Task(1,1,m,tmp[l].to);
                    if(sum > 1e9) sum = 1e9;
                }

                int nowmid ;
                if(sum >= ask[now].need)
                {
                    ask[now].r = i;
                    nowmid = (ask[now].r + ask[now].l) >> 1;
                    tmpadd(nowmid,ask[now].x);
                }

                else{
                    ask[now].l = i + 1;
                    nowmid = (ask[now].r + ask[now].l) >> 1;
                    tmpadd(nowmid,ask[now].x);  
                }
            }
        }

        memcpy(head,tmphead,sizeof tmphead);
        for(int i=1;i<=tmpcnt;++i)
            edge[i].next = tmpedge[i].next,edge[i].to = tmpedge[i].to;
        memset(tmphead,0,sizeof tmphead);
    }
    for(int i=1;i<=n;++i)
    {
        if(ans[i])
            printf("%d\n",ans[i]);
        else puts("NIE");
    }
} 

###2529: [Poi2011]Sticks
$Description$
给出若干木棍,每根木棍有特定的颜色和长度。问能否找到三条颜色不同的木棍构成一个三角形。
(注意这里所说的三角形面积要严格大于0)
$Solution$
枚举最长的那根木棍,
由于三角形能成立的条件是两短边之和大于第三遍,因此短边越长越好.因此维护$[1,i]$集合中最长的三根颜色不同的木棍即可

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

const int N = 1e6+5;
using namespace std;

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;
}

struct Lux
{
    int len,col;
    Lux () {}
    bool operator < (const Lux &z)const
    {
        return len ^ z.len ? len < z.len : col < z.col;
    }
}stack[N],a[3];

int main()
{
    int k = read(), n, i, j, tmp = 0;
    for(i=1;i<=k;++i)
    {
        n = read(),tmp += n;
        for(j=1;j<=n;++j) stack[i].len = read(),stack[i].col = i;
    }
    sort(stack+1,stack+tmp+1);
    n = tmp ;
    for(int i=1;i<=n;++i){
        for(j=0;j<3;++j)
            if(stack[i].col == a[j].col)
                {a[j] = stack[i];break;}
        if(j==3) a[0] = stack[i];
        sort(a,a+3);
        if(a[0].col)
        {
            if(a[0].len + a[1].len > a[2].len)
            {
                printf("%d %d %d %d %d %d\n",a[0].col,a[0].len,a[1].col,a[1].len,a[2].col,a[2].len);
                return 0;
            }
        }
    }
    puts("NIE");
    return 0;
}

###2530: [Poi2011]Party
$Description$
给定一张N(保证N是3的倍数)个节点M条边的图,并且保证该图存在一个大小至少为2N/3的团。
请输出该图的任意一个大小为N/3的团。 一个团的定义为节点的一个子集,该子集中的点两两有直接连边。 输入: 第一行是两个整数N,M。 接下来有M
行,每行两个整数A,B,表示A和B有连边。保证无重边。 输出: N/3个整数,表示你找到的团。3<=N<=3000
$Solution$
构造题
开始的时候想了半个小时选哪些点,半个小时之后得到的结论是不可行
然后就想如何删边。一下子就会了
首先如果两个点不连通,我一定可以直接删掉两个点,由于有一个大小为2/3的团,所以必然会有2/3的点两两连边,因而最多去1/3次,一次去掉两个,剩下的随便找1/3输出一下就行了……肯定都在里面

#include <bitset>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 3000+5;
using namespace std;
 
bool vis[N],mp[N][N];
 
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(), m = read(),x,y;
    register int i,j;
 
 
    for(i=1;i<=m;++i)
    {
        x = read(), y = read();
        mp[x][y] = mp[y][x] = 1;
    }   
 
    for(i=1;i<=n;++i)
        if(!vis[i])
            for(j=i+1;j<=n;++j)
                if(!vis[j] && !mp[i][j])
                {
                    vis[i] = vis[j] = 1;
                    break;
                }
 
 
    int cnt = 0;
    int tt = n / 3;
 
    for(int i=1;i<=n;++i)
        if(!vis[i])
        {
            ++cnt;if(cnt!=tt) printf("%d ",i);
            else {printf("%d\n",i);break;}
        }
}
Title - Artist
0:00

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

TOP