[POI2007]TET-Tetris Attack

摘要

题意:给定一个长度为 的序列, 各出现两次,可以交换相邻两项,两个同样的数相邻会消失,求把所有数对消的最小交换次数,输出方案。 .

一看就是一个树状数组的问题,关键是代价的分析。对于两个数对的相对位置关系有 , , 三种情况。第一种情况两个区间是相离的,因此合并的代价互不相关;第二种情况两区间相交,先合并 的效果是等价的;第三种情况 被包含,显然先合并 更优.

因此我们只需要贪心地合并距离小的区间即可。每次合并完了,我们要把这两个数从原序列删除。这样的贪心策略同时可以保证不会出现第三种情况。考虑如何贪心,使用排序过于麻烦,事实上我们可以直接从左到右扫描序列,扫到一个区间的右端点就对这个区间进行合并。对于包含在内的区间一定会先被扫到,因此贪心策略的正确性得以保证。

最后考虑维护删除元素操作。我们只需要能迅速求出在下标 中有多少个元素被删除,就能知道第 个元素的确切位置。这个显然可以用树状数组维护. 找到确切位置后就可以记录方案了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;

int n,a[N*2];

int c[N*2];
void add(int p,int v){for(int i=p;i<=n*2;i+=(i&-i))c[i]+=v;}
int pre(int p,int v=0){for(int i=p;i>0;i-=(i&-i))v+=c[i];return v;}

int pos[N];//i 的左端点下标
int ans[N*2],ant;
int main(){scanf("%d",&n);
    for(int i=1;i<=n*2;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n*2;i++){if(pos[a[i]]){int l=pos[a[i]]-pre(pos[a[i]]),r=i-pre(i);// 真实坐标
            for(int j=l;j<r-1;j++)ans[++ant]=j;// 记录方案
            add(pos[a[i]],1),add(i,1);
        }
        else pos[a[i]]=i;// 第一次扫到
    }
    printf("%d\n",ant);
    for(int i=1;i<=ant;i++)printf("%d\n",ans[i]);
    return 0;
}

 上一篇
[POI2014]KUR-Couriers [POI2014]KUR-Couriers
摘要 给一个数列,每次询问一个区间内有没有一个数出现次数严格超过一半. . 复习一下主席树~ 区间 对应版本 的权值线段树的差。每次查询当前结点的左右儿子结点的大小
2019.04.05
下一篇 
[POI2011]LIZ-Lollipop [POI2011]LIZ-Lollipop
摘要 题意:给一个只有 1 和 2 的序列,每次询问有没有一个子串的和为 x. . 一道很考人的思维题。暴力的思路就是直接预处理前缀和,然后每次 查询前缀和的差. 注意到这个序列只有 0 和 1
2019.04.05
  目录