2014 Hdu 多校赛第三场

发表于   |   分类于

Hdu 4889 Scary Path Finding Algorithm

Scary Path Finding Algorithm
hdu 4889

题意

给了一段程序，但这段程序有bug，给定一个C,求一组测试数据，使得程序会输出’doge’

分析

代码中只要所有点出队列的总次数大于C,就会输出 ‘doge’
但是C最大到 23333333,而顶点数n不超过100，
那么肯定要使出队列总次数达到指数级才行，即肯定有顶点会重复进入多次
如上图所示，设p为奇数顶点，p+2可由 p或p+1到达，
由 p 可到达 p+1,p+2，要保证 p+2 多次进入队列，必须由p+1点开始松弛前出队列，
才能再次进入,将图中看成有多个包含p,p+1,p+2的小三角形，

权值为 $a_{i}$, 权值为 $b_{i}$,权值为 $c_{i}$
则 $c_{i} < a_{i} $
这样松弛p点时，会把p+2放在队首，p+1放在队尾，p+2会先出队列

松弛p+1点时 要保证p+2再次进入队列 则 w(p->p+2)>w(p->p+1->p+2)
即 $ a_{i}+b_{i}<c_{i} $

p+2点要由 p点再次进入，则
$a_{i} + b_{i} + c_{i+1} < c_{i} + a_{i+1} + b_{i+1}$
即$ ( a_{i} + b_{i}- c_{i} ) + ( c_{i+1} - a_{i+1} -b_{i+1} )< 0 $
假设 第一个括号内 得 -2x ，第二个括号内得 x,则等式恒成立，
即可取 $ a_i =2a_{i+1}, b_i =2b_{i+1}, c_i =2c_{i+1} $
综合上诉三个不等式得 若共有N个三角形，
第i个三角形 $ a_i =0, b_i =-2^{N-i+1}, c_i = -2^{N-i} $

设 f(i)为顶点 i进队列的次数 则 f(i+2)=2f(i)
设 F(i)为第1点到 2i+1点所有点的总次数 则F(i)>$ 1+2^1+2^2+…+2^i=2^{i+1} $
即当三角形个数 N=24，$ F(i)> 2^{25} -1 > 23333333 $ 即可
此时 顶点个数 n=2N+1, 边数 m=3N

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
const int N=24;
int main()
{
    int C;
    while(scanf("%d",&C)!=EOF){
        int n=N*2+1;
        int m=3*N;
        printf("%d %d\n",n,m);
        int j=N;
        for(int i=1;i<=n-2;i+=2,j--){
            printf("%d %d 0\n",i,i+1);
            printf("%d %d %d\n",i+1,i+2,-(1<<j));
            printf("%d %d %d\n",i,i+2,-(1<<(j-1)));
        }
    }
    return 0;
}

Hdu 4891 The Great Pan

链接

The Great Pan

题意

理解方法最少有一种，ans = 1
1.{}内的|个数为n，那么就是ans*=(n+1)
2.$$内的连续空格独立理解，每有一个连续的n个空格，ans*=(n+1)
3.输出理解方案数，超过100000输出doge
4.{}，$$不会有嵌套，要注意运算时ans可能超出int型，要用long long

分析

模拟即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<stdio.h>
const int MAX=100000;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        getchar();
        int enter=0;
        long long ans=1;
        bool space=false;
        while(enter<n){
            char c=getchar();
            if(c=='\n')
                enter++;
            else if(c=='{'){
                int cnt=0;
                while(ans<=MAX&&enter<n){
                    c=getchar();
                    if(c=='}'){
                        ans*=(cnt+1);
                        break;
                    }
                    if(c=='\n')
                        enter++;
                    else if(c=='|')
                        cnt++;
                }
            }
            else if(c=='$'){
                int cnt=0;
                while(ans<=MAX&&enter<n){
                    c=getchar();
                    if(c==' '){
                        cnt++;
                        space=true;
                    }
                    else if(space&&c!=' '){
                        ans*=(cnt+1);
                        cnt=0;
                        space=false;
                    }
                    if(c=='\n')
                        enter++;
                    else if(c=='$')
                        break;
                }
            }
        }
        if(ans<=MAX)
            printf("%I64d\n",ans);
        else
            printf("doge\n");
    }
    return 0;
}

Hdu 4893 Wow! Such Sequence!

链接

Wow! Such Sequence!

题意

有n个数，初始都是0，可以进行3种操作
1 k d - 即第k个数加d
2 l r - 查询区间 [l,r]的和
3 l r - 将ai改为最接近于它的斐波那契数(l<=i<=r),即 |fib[j]-ai| 最小
先要进行m次操作，对于第2种操作，输出给定区间和

分析

对于操作1,单点更新，比较简单,lgn时间即可
但是操作3，区间更新，如果不加优化的直接将需要结点全部更新，时间效率很低

解法1

可以加一个flag，用来标记结点对应区间是否都为fib数
如果某区间是fib数，再进行3操作时，其值肯定不需要变，因为fib数肯定和它本身最接近
这样对于以该结点为根的子树都不需要更新，时间复杂度会大大降低
若需要更新的区间不是fib数，则更新

解法2

延迟标记法
若父结点更新为fib数，对其标记表示子孩子还未更新，等到需要用到子孩子时再更新，
并把标记转移到子孩子结点
但是更新结点时，若每次遍历fib数去找最接近的值很费时，
可以另设一个sumF结点存某结点所表示的区间为最接近的fib数的总和

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define LL long long
const int N=100000;
using namespace std;
struct stu{
    LL sumA;     //某结点原数列的和
    bool mark;  //标记结点是否为fib数
}tree[N<<2];
LL fib[100],sum;
int len;
void init()
{
    fib[0]=1;
    fib[1]=1;
    len=92;
    for(int i=2;i<=len;i++)
        fib[i]=fib[i-1]+fib[i-2];
}
LL findFib(LL val)
{
    int key=lower_bound(fib, fib+len,val)-fib;
    if(key&&fib[key]-val>=val-fib[key-1])
        key--;
    return fib[key];
}
void pushUp(int node)
{
    tree[node].sumA=tree[node<<1].sumA+tree[node<<1|1].sumA;
	//若左右孩子都是fib数，则父结点也是fib数
    tree[node].mark=tree[node<<1].mark&tree[node<<1|1].mark;
}
void updateAdd(int l,int r,int node,int pos,LL val)
{
    if(l==r){
        tree[node].sumA+=val;
        tree[node].mark=false; //当原数增加一个值后，该区间不一定为fib数，标记取消
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)
        updateAdd(l,mid,node<<1,pos,val);
    else
        updateAdd(mid+1,r,node<<1|1,pos,val);
    pushUp(node);
}
void updateFib(int l,int r,int node,int upL,int upR)
{
    if(tree[node].mark)
        return ;
    if(l==r){
        tree[node].mark=true;   //该结点更新为fib数，mark标记为true
        tree[node].sumA=findFib(tree[node].sumA);
        return ;
    }
    int mid=(l+r)>>1;
    if(upL<=mid)
        updateFib(l,mid,node<<1,upL,upR);
    if(mid<upR)
        updateFib(mid+1,r,node<<1|1,upL,upR);
    pushUp(node);
}
void query(int l,int r,int node,int ql,int qr)
{
    if(ql<=l&&r<=qr){
        sum+=tree[node].sumA;
        return ;
    }
    int mid=(l+r)>>1;
    if(ql<=mid)
        query(l,mid,node<<1,ql,qr);
    if(mid<qr)
        query(mid+1,r,node<<1|1,ql,qr);
}
int main()
{
    int n,m;
    init();
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(tree,0,sizeof(tree));
        while(m--){
            int ope,l,r;
            scanf("%d%d%d",&ope,&l,&r);
            if(ope==1){
                updateAdd(1,n,1,l,r);
            }
            else if(ope==2){
                sum=0;
                query(1,n,1,l,r);
                printf("%I64d\n",sum);
            }
            else
                updateFib(1,n,1,l,r);
            //sum=0;
            //query(1,n,1,1,n);
            //printf("**%I64d\n",sum);
        }
    }
    return 0;
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<stdio.h>
#include<algorithm>
#define LL long long
const int N=100000;
using namespace std;
struct stu{
    LL sumA,sumF; //sumA为原数列的和，sumF为最接近的fib数的和
    bool mark;   //mark为延迟标记，标记该结点的孩子结点是否未更新
}tree[N<<2];
LL fib[100],sum;
int len;
void init()
{
    fib[0]=1;
    fib[1]=1;
    len=92;
    for(int i=2;i<=len;i++)
        fib[i]=fib[i-1]+fib[i-2];
}
LL findFib(LL val)
{
    int key=lower_bound(fib, fib+len,val)-fib;
    if(key&&fib[key]-val>=val-fib[key-1])
        key--;
    return fib[key];
}
void pushUp(int node)
{
    tree[node].sumA=tree[node<<1].sumA+tree[node<<1|1].sumA;
    tree[node].sumF=tree[node<<1].sumF+tree[node<<1|1].sumF;
}
void pushDown(int node)   //向下更新孩子结点
{
    if(tree[node].mark){
        tree[node<<1].mark=tree[node<<1|1].mark=true;  //将延迟标记转移到孩子结点
        tree[node<<1].sumA=tree[node<<1].sumF;       
        tree[node<<1|1].sumA=tree[node<<1|1].sumF;
        tree[node].mark=false;        //父结点延迟标记取消
    }
}
void build(int l,int r,int node)
{
    tree[node].sumA=0;
    tree[node].mark=false;
    if(l==r){
        tree[node].sumF=1;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,node<<1);
    build(mid+1,r,node<<1|1);
    pushUp(node);
}
void updateAdd(int l,int r,int node,int pos,LL val)
{
    if(l==r){
        if(tree[node].mark)
            tree[node].sumA=tree[node].sumF+val;
        else
            tree[node].sumA+=val;
        tree[node].sumF=findFib(tree[node].sumA);
        tree[node].mark=false;
        return ;
    }
    pushDown(node);
    int mid=(l+r)>>1;
    if(pos<=mid)
        updateAdd(l,mid,node<<1,pos,val);
    else
        updateAdd(mid+1,r,node<<1|1,pos,val);
    pushUp(node);
}
void updateFib(int l,int r,int node,int upL,int upR)
{
    if(upL<=l&&r<=upR){
        tree[node].mark=true;
        tree[node].sumA=tree[node].sumF;
        return ;
    }
    pushDown(node);
    int mid=(l+r)>>1;
    if(upL<=mid)
        updateFib(l,mid,node<<1,upL,upR);
    if(mid<upR)
        updateFib(mid+1,r,node<<1|1,upL,upR);
    pushUp(node);
}
void query(int l,int r,int node,int ql,int qr)
{
    if(ql<=l&&r<=qr){
        sum+=tree[node].sumA;
        return ;
    }
    pushDown(node);
    int mid=(l+r)>>1;
    if(ql<=mid)
        query(l,mid,node<<1,ql,qr);
    if(mid<qr)
        query(mid+1,r,node<<1|1,ql,qr);
}
int main()
{
    int n,m;
    init();
    while(scanf("%d%d",&n,&m)!=EOF){
        build(1,n,1);
        while(m--){
            int ope,l,r;
            scanf("%d%d%d",&ope,&l,&r);
            if(ope==1){
                updateAdd(1,n,1,l,r);
            }
            else if(ope==2){
                sum=0;
                query(1,n,1,l,r);
                printf("%I64d\n",sum);
            }
            else
                updateFib(1,n,1,l,r);
            //sum=0;
            //query(1,n,1,1,n);
            //printf("**%I64d\n",sum);
        }
    }
    return 0;
}