长春网络赛小记 hdu 4274 hdu 4268

最终四题，100多名，没什么好说的，水水的。。。。

就是1006被坑的有点夸张，导致没有时间去搞其他题，不过好像很多队也被这题的题意坑了

比赛开始时我就瞄准了A题，肯定是线段树，但是怎么搞呢，线段树要开的空间好大啊，正犹豫中，队友树状数组1A - -

然后我看1002，问你Alice最多有多少的卡片可以覆盖Bob的卡片，每场卡片是a*b规格的，a b不可互换，开始想到的是先将Bob的所有卡片收集起来，放进线段树中，a这一维当做区间域，b当做值，然后将Alice的卡片排好序，一个个计算过去，找一张a值比它小的b值最大的卡片覆盖掉，但是立刻发现，这个操作无法完成，因为b值不具备单调性，于是瞬间想到只在b值上做文章，用平衡树维护b的单调性（线段树也可以，只不过我懒得离散化），具体做法是，对两个人的卡片分别排序，枚举Alice的卡片x，将bob的卡片中a值小于等于x.a的元素都依次加进平衡树（插入的是卡片的b值），然后就询问一下有没有小于等于x.b的节点存在，存在的话ans++，删除小于等于x.b的最大的b值，即平衡树中x.b的前驱节点

最后一题搜索在1002A了之后经过几次Wa也顺利AC了，刚好排50 - -！，形势一片大好。

然后就有了1006的出现，题意都错了还坚持说对的（然后人民群众肯定是相信admin的话喽），怪不得有人爆粗口。

然后各种造数据，各种对，就是找不出错。。。。

然后在被坑了许久之后怒A！！！！

然后就没有然后了。。。。。。。

其实还有两道题都挺简单的，跟树有关，想法都有了，一道是树DP+分组背包，另一道模拟一遍就好

献上B题代码

#include<cstdio>#include<cstring>#include<vector>#include<algorithm>using namespace std;const __int64 inf = 1000000000;const int maxn = 10010;vector<int> edge[maxn];bool ans;__int64 L[maxn],R[maxn];struct node{    char op[5];    int w;}hehe[maxn];vector<node> dd[maxn];bool dfs(int u){    int sz=edge[u].size();    for(int i=0;i<sz;i++)    {        int v=edge[u][i];        if(!dfs(v)) return false;    }    L[u]=1;R[u]=inf;    for(int i=0;i<sz;i++)    {        int v=edge[u][i];        L[u]+=L[v];        R[u]+=R[v];    }    int size=dd[u].size();    for(int i=0;i<size;i++)    {         if(dd[u][i].op[0]=='>')         {             if(L[u] < dd[u][i].w+1)              L[u]=dd[u][i].w+1; if(L[u]>R[u]) return false;         }         else if(dd[u][i].op[0]=='<')          {             if(R[u]>dd[u][i].w-1)             R[u]=dd[u][i].w-1; if(L[u]>R[u]) return false;         }         else          {             if(L[u]>dd[u][i].w || R[u]<dd[u][i].w) return false;             L[u]=R[u]=dd[u][i].w;         }    }    return true;}int main(){    int n,m;    while(scanf("%d",&n)!=EOF)    {        int fa;        for(int i=1;i<=n;i++) edge[i].clear(),dd[i].clear();        for(int i=2;i<=n;i++)        {            scanf("%d",&fa);            edge[fa].push_back(i);        }        scanf("%d",&m);        int u,w;        char op[5];        for(int i=1;i<=m;i++)        {            node tmp;            scanf("%d",&u);            scanf("%s%d",tmp.op,&tmp.w);            dd[u].push_back(tmp);        }        ans=dfs(1);        if(ans) printf("True\n");        else printf("Lie\n");    }    return 0;}

1楼woshi250hua昨天 00:20

1002用平衡树写，牛逼啊....n ---ZeroClock

Re: haha593572013昨天 00:22

回复woshi250huan刚好接着网络赛测试下模板，呵呵

Re: woshi250hua昨天 00:24

回复haha593572013:呵呵，cf能赢你就要这模版了...洗洗睡了，明天，错了，今天继续加油