2015 Hdu 多校赛第三场

发表于   |   分类于

感觉思维定式，有的题也想复杂了…下次继续加油！
XM

Hdu 5316 Magician

链接

Magician

题意

给定n个数，m次操作，操作有两种
(1)0 a b:输出区间[a,b]中美丽序列的最大和
区间[a,b]的美丽序列：[a,b]的子序列，且相邻元素的下标奇偶性不同
(2)1 a b:将下标为a的值改为b

分析

5316
最大和要求子序列的相邻元素下标奇偶性不同，即下标奇偶交替即可
则共有四种情况：子序列的开始下标和结尾下标为
奇奇(jj),奇偶(jo),偶偶(oo),偶奇(oj)
jj=jo+jj,jj=jj+oj,jo=jo+jo,jo=jj+oo
oo=oo+jo,oo=oj+oo,oj=oo+oj,oj=oj+oj
根据左右孩子推父结点时需要区间合并：(合并左右孩子)
父结点的jj为 max(lson.jj,rson.jj,lson.jo+rson.jj,lson.jj+rson.oj)
同样其他三种情况类推
查询时要注意同样是区间合并(合并ans和包含要查询的子区间的结点)，并不是单纯的取最大值
最后的最大和为 max(ans.jj,ans.jo,ans.oj,ans.oo);
因为题中存在负数，题中涉及到求最大值，相关的初始化要初始为负很大的数

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
#include<stdio.h>
#include<algorithm>
const int N=100000;
typedef long long LL;
const LL INF=0xffffffffffff;
using namespace std;
struct stu{
    LL jo,jj,oo,oj;
}tree[N<<2],ans;
LL a[N+10];
void mergeNode(stu& t,stu lson,stu rson) //合并区间
{
    //更新jo
    t.jo=max(lson.jo,rson.jo);
    t.jo=max(t.jo,lson.jo+rson.jo);
    t.jo=max(t.jo,lson.jj+rson.oo);
    //更新jj
    t.jj=max(lson.jj,rson.jj);
    t.jj=max(t.jj,lson.jo+rson.jj);
    t.jj=max(t.jj,lson.jj+rson.oj);
    //更新oo
    t.oo=max(lson.oo,rson.oo);
    t.oo=max(t.oo,lson.oo+rson.jo);
    t.oo=max(t.oo,lson.oj+rson.oo);
    //更新oj
    t.oj=max(lson.oj,rson.oj);
    t.oj=max(t.oj,lson.oo+rson.jj);
    t.oj=max(t.oj,lson.oj+rson.oj);
}
void build(int l,int r,int node)
{
    if(l==r){
        tree[node].jo=tree[node].oj=-INF;
        tree[node].oo=tree[node].jj=-INF;
        if(l&1) tree[node].jj=a[l];
        else tree[node].oo=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,node<<1);
    build(mid+1,r,node<<1|1);
    mergeNode(tree[node],tree[node<<1],tree[node<<1|1]);
}
void update(int l,int r,int node,int pos,int val)
{
    if(l==r){
        if(l&1) tree[node].jj=val;
        else tree[node].oo=val;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(l,mid,node<<1,pos,val);
    else update(mid+1,r,node<<1|1,pos,val);
    mergeNode(tree[node],tree[node<<1],tree[node<<1|1]);
}
void query(int l,int r,int node,int ql,int qr)
{
    if(ql<=l&&r<=qr){
        mergeNode(ans,ans,tree[node]); //将区间ans和tree[node]合并
        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 T,n,m;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%I64d",&a[i]);
        build(1,n,1);
        while(m--){
            int ope,a,b;
            scanf("%d%d%d",&ope,&a,&b);
            if(ope)
                update(1,n,1,a,b);
            else{
                ans.oo=ans.oj=ans.jj=ans.jo=-INF; //初始化
                query(1,n,1,a,b);
                LL maxAns=ans.oo;  //求四种情况下的最大值
                maxAns=max(maxAns,ans.oj);
                maxAns=max(maxAns,ans.jj);
                maxAns=max(maxAns,ans.jo);
                printf("%I64d\n",maxAns);
            }
        }
    }
    return 0;
}

Hdu 5317 RGCDQ

链接

RGCDQ

题意

给定一个区间[l,r],求GCD(F(i),F(j))的最大值 (L≤i<j≤R)
其中F(i)为i的不同素因子的个数，如12=2*2*3,则F(12)=2
GCD：最大公约数

分析

r最大到10^6,而10^6最多可写成7个不同的素因子相乘
可以先预处理求出[1,10^6]每个数的F(i)的值
再求出区间[1,i]素因子个数分别为[1,7]的个数
那么对于区间[l,r]的情况，可以用区间[1,r]-[1,l-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
#include<stdio.h>
#include<string.h>
const int N=1000000;
int a[N+10],s[N+10][8];
void prime()
{
    for(int i=2;i<=N;i++){
        if(a[i]==0)
            for(int j=i;j<=N;j+=i)
                a[j]++;
    }
    for(int i=2;i<=N;i++){
        s[i][a[i]]++;
        for(int j=1;j<=7;j++)
            s[i][j]+=s[i-1][j];
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    prime();
    while(T--){
        int l,r;
        scanf("%d%d",&l,&r);
        int num[8]={0};
        for(int i=1;i<=7;i++)
            num[i]=s[r][i]-s[l-1][i];
        bool flag=false;
        for(int i=7;i>=4;i--){
            if(num[i]>=2){
                printf("%d\n",i);
                flag=true;
                break;
            }
        }
        if(!flag){
            if((num[3]>=2)||(num[3]>=1&&num[6]>=1))
                printf("3\n");
            else if((num[2]>=2)||(num[2]>=1&&num[4]>=1)||(num[2]>=1&&num[6]>=1)||(num[4]>=1&&num[6]>=1))
                printf("2\n");
            else
                printf("1\n");
        }
    }
    return 0;
}

Hdu 5319 Painter

链接

Painter

题意

有一个矩形画板，有n行,给定n个字符串表示这n行画的情况
‘R’为这个格子画了一笔’\‘
‘B’为画了一笔’/‘
‘G’为画了一笔’/‘和一笔’\‘
‘.’表示没画
求最少需要几笔可以出给定的样子

分析

1.画板的行数n已给出,列数则为字符串的长度
2.若某些格画出的样子连成一条线，则可以视为1笔
3.为了保证笔画最小，则能一笔画的就视为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
#include<stdio.h>
#include<string.h>
char s[60][60];
int ans,n,m;
bool vis[60][60];
void solve(int row,int col,int dir)
{ 
    ans++;
    for(int k=0;;k++){
        int x=row+k;
        int y=col+dir*k;
        if(x<0||x>=n||y<0||y>=m)
            break;
        char c=s[x][y];
        bool flag=true;
        if(dir==1){
            if(c=='R')
                s[x][y]='.'; 
            else if(c=='G'&&!vis[x][y]){ 
                s[x][y]='B'; //'G'画完一笔'R'还需要画'B'
                vis[x][y]=true;
            }
            else
                flag=false;
        }
        else if(dir==-1){
            if(c=='B')
                s[x][y]='.';
            else if(c=='G'&&!vis[x][y]){
                s[x][y]='R'; //'G'画完一笔'B'还需要画'R'
                vis[x][y]=true;
            }
            else
                flag=false;
        }
        if(!flag)
            break;
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%s",s[i]);
        m=strlen(s[0]);
        memset(vis,0,sizeof(vis));
        ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
        //若(i,j)点为'R',则下一个能连起来的点为(i+1,j+1)
                if(s[i][j]=='R')
                    solve(i,j,1);
        //若(i,j)点为'B',则下一个能连起来的点为(i+1,j-1)
                else if(s[i][j]=='B')
                    solve(i,j,-1);
        //若(i,j)点为'G',可以将它分解为'R'和'B'两步
                else if(s[i][j]=='G'){
                    if(!vis[i][j]){
                        solve(i,j,1);
                        solve(i,j,-1);
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

Hdu 5323 Solve this interesting problem

链接

Solve this interesting problem

题意

给定一个区间[L,R],求一个最小的n，
使得以[0,n]为根结点的线段树包含区间为[L,R]的结点
若不存在，输出-1

分析

对于一个结点[L,R]，它可能是父结点的左孩子或右孩子，
不断的往上推父结点的区间，直到父结点的左区间为0为止(即推到了根结点)
如结点[L,R]为左孩子，父结点为[L,2*R-L]或[L,2*R-L+1]
若为右孩子，父结点为[2(l-1)-R,R]或[2(l-1)-R+1,R]
线段树左孩子的区间长度跟右孩子区间长度相等或比右孩子大1
当不符合该条件时，就不必继续往上推了
注意：要先递归为右孩子，否则会栈溢出，因为如果先dfs为左孩子
区间的左区间L不变，R会一直增大，递归到R>=INF才结束，会递归很多层
而我们要求的答案当L为0就可以，先递归右孩子，左区间会不断减小，
最多减小到0停止递归，不会栈溢出

参考代码

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
#include<stdio.h>
#define INF 0xfffffffffffffff
long long ans;
void dfs(long long L,long long R)
{
    if(L<0||R>=ans)
        return ;
    if(L==0){
        ans=R;
        return ;
    }
    if(R-L+1>L) //该区间长度比左区间长度大，不满足条件
        return ;
    dfs(2*(L-1)-R,R);  //结点为右孩子
    dfs(2*(L-1)-R+1,R);
    //注意要先dfs为右孩子
    dfs(L,2*R-L);      //结点为左孩子
    dfs(L,2*R-L+1);
}
int main()
{
    long long L,R;
    while(scanf("%I64d%I64d",&L,&R)!=EOF){
        ans=INF;
        dfs(L,R);
        if(ans==INF)
            ans=-1;
        printf("%I64d\n",ans);
    }
    return 0;
}

Hdu 5326 Work

链接

Work

题意

有n个员工，给定n-1组关系，A B，表示A是B的直接领导
求有多少人管理k个员工？

分析

要求管理k个员工的人数，这里的管理包括直接和间接管理
并且是刚好管理k人，对于每一个人，可以求出其直接管理的人数
然后再加上其间接管理的人数即可，间接管理的人数即为他直接管理
的人所管理的人数，将领导和直接被管理者之间连一条边，dfs即可

参考代码

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
#include<stdio.h>
#include<string.h>
const int N=120;
struct stu{
    int to,next;
}edge[N];
int n,k,m,head[N],du[N],cnt[N],ans;
void addEdge(int a,int b)
{
    edge[m].to=b;
    edge[m].next=head[a];
    head[a]=m++;
}
int dfs(int pos)
{   //cnt[pos]用来存pos总共管理的人数
    if(cnt[pos]!=-1) //若cnt[pos]的值已经求出过，就不用再求其值
        return cnt[pos];
    if(du[pos]==0){  //若pos直接管理的人为0，则其没有管理任何人
        cnt[pos]=0;
        return 0;
    } 
    cnt[pos]=du[pos];  //加上直接管理的人数
    for(int i=head[pos];i!=-1;i=edge[i].next)
        cnt[pos]+=dfs(edge[i].to);    //加上间接管理的人数
    return cnt[pos];
}
int main()
{
    while(scanf("%d%d",&n,&k)!=EOF){
        memset(du,0,sizeof(du));
        memset(head,-1,sizeof(head));
        m=1;
        int a,b;
        for(int i=1;i<n;i++){
            scanf("%d%d",&a,&b);
            du[a]++;   //统计直接管理的人数
            addEdge(a,b);  //加边
        }
        ans=0;
        memset(cnt,-1,sizeof(cnt));
        for(int i=1;i<=n;i++){
            dfs(i);
            if(cnt[i]==k)
                ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}