2015 Hdu 多校赛第七场

发表于   |   分类于

Hdu 5372 Segment Game

链接

Segment Game

题意

给定n个操作，操作有两种
0 b 插入一条[b,b+i] ，并输出被这条线段完全覆盖的线段条数，其中i表示这条线段是第i次插入
1 b 删除第b次插入的线段

分析

对于新插入的线段，查询有多少个线段左端点大于等于该线段的左端点。再查询有多少个线段的右端点大于该线段右端点，两者之差就是答案。用两个树状数组搞定。时间复杂度 nlogn
若该线段为[l,r],也可以查询线段右端点小于等于r，线段左端点小于等于l-1,它们的差即为答案
题中插入线段的左端点$ |b|<10^9 $，数据很大存不开，需要将端点坐标离散化
用 $ unique() $函数去除重复的端点值,用 $ lowwer\_bound() $函数查询某端点离散化后的下标，
树状数组 c[i][0] 存的是线段左端点大于等于以i为下标的左端点的值
c[i][1] 存的是线段右端点大于等于以i为下标的右端点的值

参考代码

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 200100;
struct stu {
    int a, b;
} ope[N];
int c[N*2][2];
int cnt, m, b[N], id[N*2];
int lowbit(int n)
{
    return n & (-n);
}
int query(int n, int ope)
{
    int sum = 0;
    while (n>0) {
        sum += c[n][ope];
        n -= lowbit(n);
    }
    return sum;
}
void update(int pos, int ope, int val)
{
    while (pos < cnt) {
        c[pos][ope] += val;
        pos += lowbit(pos);
    }
}
int main()
{
    int n,k=1;
    while (scanf("%d", &n) != EOF) {
        printf("Case #%d:\n",k++);
        cnt = m = 1;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &ope[i].a, &ope[i].b);
            if (ope[i].a == 0){
                id[cnt++] = ope[i].b;
                id[cnt++] = ope[i].b + m;
                b[m++] = ope[i].b;
            }
        }
        sort(id + 1, id + cnt);
        cnt=unique(id+1,id+cnt)-id; //去重，下面注释的代码也可以
        //int num=2;
        //for(int i=2;i<cnt;i++)
            //if(id[i]!=id[i-1])
                //id[num++]=id[i];
        //cnt=num; 
        memset(c, 0, sizeof(c));
        m = 1;
        for (int i = 1; i <= n; i++) {
            if (ope[i].a == 0) {
                int posl = lower_bound(id + 1, id + cnt, ope[i].b) - id;
                int posr = lower_bound(id + 1, id + cnt, ope[i].b + m) - id;
                int l = query(posl-1, 0);  
                int r = query(posr, 1);
                printf("%d\n", r - l);
                update(posl, 0, 1);
                update(posr, 1, 1);
                m++;
            }
            else {
                int posl = lower_bound(id + 1, id + cnt, b[ope[i].b]) - id;
                int posr = lower_bound(id + 1, id + cnt, b[ope[i].b] + ope[i].b) - id;
                update(posl, 0, -1);
                update(posr, 1, -1);
            }
        }
    }
    return 0;
}

Hdu 5373 The shortest problem

链接

The shortest problem

题意

给定一个数n，每次将n各位数字的和插入数n的末尾的到新的数n,
求经过t此操作后的到的数能否被11整除。如 n=123,t=3, 123->1236->123612->12361215.

分析

能被11整除的数其奇数位数字的和和偶数位数字的和的差能被11整除
每次操作时，分别记录奇数为的和和偶数为的和，最后判断它们的差是否能被11整除

参考代码

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
#include<stdio.h>
#define mod 11
int odd,even,mark;
int bit[30],len;
int calSum(int num)
{
    int sum=0;
    len=0;
    while(num){
        bit[len++]=num%10;
        sum+=num%10;
        num/=10;
    }
    for(int i=len-1;i>=0;i--){
        if(mark&1) odd=(odd+bit[i])%mod;
        else even=(even+bit[i])%mod;
        mark^=1;
    }
    return sum;
}
int main()
{
    int T=0,t,n;
    while(scanf("%d%d",&n,&t)!=EOF){
        if(n==-1&&t==-1)
            break;
        T++;
        printf("Case #%d: ",T);
        odd=0,even=0,mark=1;
        int sum=calSum(n);
        while(t--)
            sum+=calSum(sum);
        int ans=((odd-even)%mod+mod)%mod;
        if(ans==0)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

Hdu 5375 Gray code

链接

Gray code

题意

给定用’1’,’0’,’?’表示的n位二进制数,和长度为n的序列{a1,a2…an}
若二进制对应的格雷码第i位为1,可得到ai分，求该二进制数最多能得多少分

分析

$若一个二进制数位 a_1a_2a_3…a_n$
$则其对应的格雷码为 a_1,a_1 xor a_2,…,a_{n-1} xor a_n$
0 xor 1 =1,1 xor 0 =1, 0 xor 0 =0, 1 xor 1 = 0
设dp[i][0]表示第i位为0可得的最大分数，dp[i][1]表示第i位为0可得的最大分数
则状态转移方程为
$dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i])$
$dp[i][1]=max(dp[i-1][1],dp[i-1][0]+a[i])$

参考代码

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
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=200100;
const int INF=0x3f3f3f3f;
char s[N];
int len,a[N],dp[N][2];
void solve()
{
    memset(dp,-INF,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=len;i++){
        if(s[i]!='0')
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+a[i]);
        if(s[i]!='1')
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i]);
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        scanf("%s",s+1);
        len=strlen(s+1);
        for(int i=1;i<=len;i++)
            scanf("%d",&a[i]);
        solve();
        int ans=max(dp[len][0],dp[len][1]);
        printf("Case #%d: %d\n",k,ans);
    }
    return 0;
}

Hdu 5379 Mahjong tree

链接

Mahjong tree

题意

有一个以结点1为根包含n个结点的树,给定这些结点间的n-1组关系ui vi,表示ui与vi相连
有n个不同的麻将标号为{1,2…n}，要将这些麻将放入树中，每个结点放一个麻将
且要求任意一个子树里的点编号连续，每一个点的儿子编号连续，求有多少种方案

分析

在一棵树上给所有点标号，要求任意一个子树里的点编号连续，每一个点的儿子编号连续。 那么，一个点的非叶子儿子应该是连续的，即一个点的非叶子儿子最多只有两个。 对于每一个点，我们把它的叶子儿子的个数记作S，所有儿子的方案数积为T。当非叶子儿子节点个数小于2的时候，方案数为2T*(S!). 当非叶子儿子节点数等于2的时候，这个点为根的子树合法方案数位T*（S!）. 这样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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#pragma comment(linker, "/STACK:102400000,102400000") //手动扩栈
#include <stdio.h>
#include <string.h>
#include <vector>
typedef long long LL;
using namespace std;
const int N = 100010;
const LL mod = 1000000007;
vector<int> edge[N];
bool vis[N];
int n;
LL fact(int n)
{
    LL f = 1;
    for (int i = 2; i <= n; i++)
        f = f * i % mod;
    return f;
}
LL dfs(int pos)
{
    int leaf = 0;
    LL temp, ans = 1;
    int m = edge[pos].size();
    for (int i = 0; i < m; i++) {
        int b = edge[pos][i];
        if (vis[b]) continue;
        vis[b] = true;
        if (edge[b].size() == 1)
            leaf++;
        else{
            temp = dfs(b);
            ans = ans * temp % mod;
        }
    } //edge[pos]中存了与pos相连的点，除根结点外，其中都包含其父亲结点
    if(pos!=1) m--;  //其孩子结点数为 m-1
    if (m - leaf < 2)
        return (2 * ans % mod) * fact(leaf) % mod;
    else if (m - leaf == 2)
        return ans * fact(leaf) % mod;
    else  //若子树中非叶子结点数大于2则无解
        return 0;
}
int main()
{
    int T;
    scanf("%d", &T);
    for (int k = 1; k <= T; k++) {
        scanf("%d", &n);
        int a,b;
        for (int i = 1; i < n; i++) {
            scanf("%d%d", &a, &b);
            edge[a].push_back(b);
            edge[b].push_back(a);
        }
        if(n==1){
            printf("Case #%d: 1\n", k);
            continue;
        }
        memset(vis, false, sizeof(vis));
        vis[1]=true;
        LL ans = dfs(1);
        printf("Case #%d: %I64d\n", k, ans);
        for(int i=1;i<=n;i++)
            edge[i].clear();
    }
    return 0；
}