dd's site \#

Posted on In ,

题意 给你一个只有0, 1的数组 有这些操作

  1. 将[a, b]区间的所有数都改为0

  2. 将[a, b]区间的所有数都改为1

  3. 将[a, b]区间的所有数都取反 即与1异或

  4. 输出区间[a, b]中1的个数 即所有数的和

  5. 输出区间[a, b]中最大连续1的长度

对于所有的3, 4操作输出对应的答案

单个的操作都很简单 但搞在一起就有点恶心了 还好数组里的数只有0和1

线段树维护9个值 对应区间0, 1的最大长度len[i] 对应区间左端点为起点的最大0, 1长度lle[i] 对应区间右端点为终点的最大0, 1长度 对应区间的1的个数sum 对应区间的置值标记setv 对应区间的取反标记opp

成段更新时有两种操作 取反 (opp) 和置值 (setv) 取反操作时因为是0, 1互换 将维护的对应的信息也交换就行了 sum就变成长度减去sum了 置值操作比较简单 但是要注意置值操作前的所有取反操作都是没有意义的 所以置值的时候要将对应区间的取反标记去掉

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <cstdio>
#include <algorithm>
#define lc p<<1, s, mid
#define rc p<<1|1, mid+1, e
#define lp p<<1
#define rp p<<1|1
#define mid ((s+e)>>1)
using namespace std;
const int N = 100005, M = N * 4;
//最大连续i的长度 左端连续长度 右端连续长度
int len[2][M], lle[2][M], lri[2][M];
int opp[M], setv[M], sum[M];

void swap01(int p)  //将p对应区间的01信息交换
{
    swap(len[0][p], len[1][p]);
    swap(lle[0][p], lle[1][p]);
    swap(lri[0][p], lri[1][p]);
}

void setAll(int p, int i, int v) //将p对应的区间全部置为i
{
    int j = 1 - i;
    len[i][p] = lle[i][p] = lri[i][p] = v;
    len[j][p] = lle[j][p] = lri[j][p] = 0;
}

void pushup(int p, int s, int e)
{
    sum[p] = sum[lp] + sum[rp];
    for(int i = 0; i < 2; ++i)
    {
        len[i][p] = max(len[i][lp], len[i][rp]);
        lle[i][p] = lle[i][lp], lri[i][p] = lri[i][rp];
        if(lri[i][lp] && lle[i][rp]) //左右孩子边界可连接
        {
            len[i][p] = max(len[i][p], lri[i][lp] + lle[i][rp]);
            if(lle[i][lp] == mid + 1 - s) lle[i][p] += lle[i][rp];
            if(lri[i][rp] == e - mid) lri[i][p] += lri[i][lp];
        }
    }
}

void build(int p, int s, int e)
{
    opp[p] = 0;
    setv[p] = -1;
    if(s == e)
    {
        scanf("%d", &sum[p]);
        int i = sum[p];
        setAll(p, i, 1);
        return;
    }
    build(lc);
    build(rc);
    pushup(p, s, e);
}

void pushdown(int p, int s, int e)
{
    if(setv[p] != -1)
    {
        int i = setv[lp] = setv[rp] = setv[p];
        opp[lp] = opp[rp] = 0;
        sum[lp] = i * (mid + 1 - s);
        sum[rp] = i * (e - mid);

        setAll(lp, i, mid + 1 - s);
        setAll(rp, i, e-mid);
        setv[p] = -1;
    }

    if(opp[p])
    {
        opp[lp] ^= 1;
        opp[rp] ^= 1;
        sum[lp] = mid + 1 - s - sum[lp];
        sum[rp] = e - mid - sum[rp];

        swap01(lp);
        swap01(rp);
        opp[p] = 0;
    }
}

void update(int p, int s, int e, int l, int r, int v)
{
    if(l <= s && e <= r)
    {
        if(v == 2)
        {
            opp[p] ^= 1;
            sum[p] = e - s + 1 - sum[p];
            swap01(p);

        }
        else
        {
            int i = setv[p] = v;
            opp[p] = 0;
            sum[p] = v * (e - s + 1);
            setAll(p, i, e - s + 1);
        }
        return;
    }
    pushdown(p, s, e);
    if(l <= mid) update(lc, l, r, v);
    if(r > mid) update(rc, l, r, v);
    pushup(p, s, e);
}

int query(int p, int s, int e, int l, int r, int op)
{
    if(l <= s && e <= r) return op == 3 ? sum[p] : len[1][p];
    pushdown(p, s, e);
    int ret = 0;
    if(op == 3)  //the number of '1's
    {
        if(l <= mid) ret += query(lc, l, r, op);
        if(r > mid) ret += query(rc, l, r, op);
    }
    else  // the length of '1's
    {
        ret = max(ret, min(r, mid + lle[1][rp]) - max(l, mid + 1 - lri[1][lp]) + 1);
        if(l <= mid) ret = max(ret, query(lc, l, r, op));
        if(r > mid) ret = max(ret, query(rc, l, r, op));
    }
    return ret;
}

int main()
{
    int T, n, m, a, b, op;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        build(1, 0, n - 1);
        while(m--)
        {
            scanf("%d%d%d", &op, &a, &b);
            if(op < 3) update(1, 0, n - 1, a, b, op);
            else
                printf("%d\n", query(1, 0, n - 1, a, b, op));
        }
    }
    return 0;
}
//Last modified :  2015-08-12 09:10 CST

Sequence operation

Problem Description

lxhgww got a sequence contains n characters which are all ‘0’s or ‘1’s.
We have five operations here:
Change operations:
0 a b change all characters into ‘0’s in [a , b]
1 a b change all characters into ‘1’s in [a , b]
2 a b change all ‘0’s into ‘1’s and change all ‘1’s into ‘0’s in [a, b]
Output operations:
3 a b output the number of ‘1’s in [a, b]
4 a b output the length of the longest continuous ‘1’ string in [a , b]
Input

T(T<=10) in the first line is the case number.
Each case has two integers in the first line: n and m (1 <= n , m <= 100000).
The next line contains n characters, ‘0’ or ‘1’ separated by spaces.
Then m lines are the operations:
op a b: 0 <= op <= 4 , 0 <= a <= b < n.
Output

For each output operation , output the result.
Sample Input

1 10 10 0 0 0 1 1 0 1 0 1 1 1 0 2 3 0 5 2 2 2 4 0 4 0 3 6 2 3 7 4 2 8 1 0 5 0 5 6 3 3 9
Sample Output

5 2 6 5

Posted on In ,

题意 给你一个数组 有更新值和查询两种操作 对于每次查询 输出对应区间的最长连续递增子序列的长度

基础的线段树区间合并 线段树维护三个值 对应区间的LCIS长度(lcis) 对应区间以左端点为起点的LCIS长度(lle) 对应区间以右端点为终点的LCIS长度(lri) 然后用val存储数组对应位置的值 当val[mid + 1] > val[mid] 的时候就要进行区间合并操作了

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
#include <cstdio>
#include <algorithm>
#define lc lp, s, mid
#define rc rp, mid+1, e
#define lp p<<1
#define rp p<<1|1
#define mid ((s+e)>>1)
using namespace std;
const int N = 100005, M = N * 4;
int lcis[M], lle[M], lri[M], val[N];

void pushup(int p, int s, int e)
{
    lcis[p] = max(lcis[lp], lcis[rp]);
    lle[p] = lle[lp], lri[p] = lri[rp];
    if(val[mid + 1] > val[mid]) //合并条件
    {
        lcis[p] = max(lcis[p], lri[lp] + lle[rp]);
        if(lle[lp] == mid + 1 - s) lle[p] += lle[rp];
        if(lri[rp] == e - mid) lri[p] += lri[lp];
    }
}

void build(int p, int s, int e)
{
    if(s == e)
    {
        lcis[p] = lle[p] = lri[p] = 1;
        scanf("%d", &val[s]);
        return;
    }
    build(lc);
    build(rc);
    pushup(p, s, e);
}

void update(int p, int s, int e, int x, int v)
{
    if(s == e)
    {
        val[s] = v;
        return;
    }
    if(x <= mid) update(lc, x, v);
    else if(x > mid) update(rc, x, v);
    pushup(p, s, e);
}

int query(int p, int s, int e, int l, int r)
{
    if(l <= s && e <= r) return lcis[p];
    int ret = 0;
    if(val[mid + 1] > val[mid])
        ret = min(r, mid + lle[rp]) - max(l, mid + 1 - lri[lp]) + 1;
    if(l <= mid)  ret = max(ret, query(lc, l, r));
    if(r > mid)  ret = max(ret, query(rc, l, r));
    return ret;
}

int main()
{
    int T, n, m, a, b;
    char op[5];
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        build(1, 0, n - 1);
        while(m--)
        {
            scanf("%s%d%d", op, &a, &b);
            if(op[0] == 'Q')
                printf("%d\n", query(1, 0, n - 1, a, b));
            else update(1, 0, n - 1, a, b);
        }
    }
    return 0;
}

LCIS

Problem Description

Given n integers.
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
Input

T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=10 5).
The next line has n integers(0<=val<=10 5).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=10 5)
OR
Q A B(0<=A<=B< n).
Output

For each Q, output the answer.
Sample Input

1 10 10 7 7 3 3 5 9 9 8 1 8 Q 6 6 U 3 4 Q 0 1 Q 0 5 Q 4 7 Q 3 5 Q 0 2 Q 4 6 U 6 10 Q 0 9
Sample Output

1 1 4 2 3 1 2 5

Posted on In ,

题意 令**G(n) = sum{gcd(i, j) | 0 < i < n, i < j <= n}**给你一个n 输出G(n)

令F(n) = sum{gcd(i, n) | 0 < i < n}

那么有递推式G(n) = G(n-1) + F(n) , G(0) = 0

也就是说只用求出F(n) 就能递推求出 G(n）了 而求F(n)就比较容易了

对于i 设x < i , gcd(x,i) = 1即x, n 互质

则**gcd(2/*x, 2/*i) = 2, gcd(3/*x, 3/*i) = 3, …, gcd(k/x, k/i) = k

这样的x的个数就是i的欧拉函数值 那么我们求出i的欧拉函数后 所有的F(k/*i) 都加上k 这样筛一下就能求出一定范围内所有的F函数值了 然后累加上去就是G的函数值了

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
#include<cstdio>
const int N = 4000005;
typedef long long ll;
int phi[N];
ll g[N];

void init() //O(N*logN) 筛欧拉函数
{
    for(int i = 2; i < N; ++i) phi[i] = i;
    for(int i = 2; i < N; i ++)
    {
        if(phi[i] == i) //i是素数
        {
            for(int j = i; j < N; j += i)
                phi[j] = phi[j] / i * (i - 1);
            //需要从j中删除一个素因子i  因为phi(p^k) = (p-1) * p^(k-1)
        }
        for(int j = 1; j * i < N; j ++)
            g[j * i] += j * phi[i];
        //phi[i]是小于i且与i互质的数的个数 j * i < N 时 j * x 肯定也小于n
    }
    for(int i = 1; i < N; i ++) g[i] += g[i - 1];
}

int main()
{
    init();
    int n;
    while(scanf("%d", &n), n)
        printf("%lld\n", g[n]);
    return 0;
}

Posted on In ,

题意 给你一个数n 求满足lcm(a, b) == n， a <= b 的 (a,b) 的个数

容易知道 n 是a, b的所有素因子取在a, b中较大指数的积

先将n分解为素数指数积的形式 n = π(pi^ei) 那么对于每个素因子pi pi在a,b中的指数ai, bi 至少有一个等于pi， 另一个小于等于pi

先不考虑a, b的大小 对于每个素因子pi

  1. 在a中的指数 ai == ei 那么 pi 在 b 中的指数可取 [0, ei] 中的所有数 有 ei + 1 种情况

  2. 在a中的指数 ai < ei 即 ai 在 [0, ei) 中 那么 pi 在 b 中的指数只能取 ei 有 ei 种情况

那么对与每个素因子都有 2/ei + 1种情况 也就是满足条件的 (a, b) 有 π(2/ei + 1)个 考虑大小时 除了 (n, n) 所有的情况都出现了两次 那么满足a<=b的有(***π(2/ei + 1)) / 2 + 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7 + 5;
int pme[N / 10], m;
bool vis[N];

void initPrime() //线性筛
{
    m = 0;
    for(int i = 2; i < N; ++i)
    {
        if(!vis[i]) pme[m++] = i;
        for(int j = 0; j < m && pme[j] * i < N; ++j)
        {
            vis[pme[j] * i] = 1;
            if(i % pme[j] == 0) break;
        }
    }
}

int main()
{
    initPrime();
    ll n, ans, c;
    int T, cas = 0;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%lld", &n);
        ans = 1;
        for(int i = 0; i < m; ++i)
        {
            if(ll(pme[i])*pme[i] > n) break;
            c = 0;
            while( n % pme[i] == 0)
            {
                n /= pme[i];
                ++c;
            }
            if(c) ans *= c * 2 + 1;
        }
        if(n > 1) ans *= 3;

        printf("Case %d: %lld\n", ++cas, ans / 2 + 1);
    }

    return 0;
}

1236 - Pairs Forming LCM
Find the result of the following code:
long long pairsFormLCM( int n ) {
long long res = 0;
for( int i = 1; i <= n; i++ )
for( int j = i; j <= n; j++ )
if( lcm(i, j) ==n ) res++; // lcm means least common multiple
return res;
}

A straight forward implementation of the code may time out. If you analyze the code, you will find that the code actually counts the number of pairs (i, j) for which lcm(i, j) = n and (i ≤ j).

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 1014).

Output

For each case, print the case number and the value returned by the function ‘pairsFormLCM(n)’.

Sample Input

Output for Sample Input 15

2

3

4

6

8

10

12

15

18

20

21

24

25

27

29

Case 1: 2

Case 2: 2

Case 3: 3

Case 4: 5

Case 5: 4

Case 6: 5

Case 7: 8

Case 8: 5

Case 9: 8

Case 10: 8

Case 11: 5

Case 12: 11

Case 13: 3

Case 14: 4

Case 15: 2

Posted on In ,

题意 你记录了[0, 59]这个时间段内到达你所在站牌的所有公交的到这个站牌的时间 对于每路公交

  1. 同一路公交的到站时间间隔是相同的

  2. 每路公交在这个时间段至少到达两次

  3. 最多有17路公交

  4. 两个不同路的公交的第一次到站时间和到站时间间隔都可能是相同滴

  5. 你在这个时间段内的记录是完整的

求最少用多少路公交可以让你的记录合法

由于每路公交至少到站两次 那么第一次到站时间是肯定小于30的 而且到站时间间隔肯定要大于第一次到站的时间 那么可以根据你的记录生成所有可能合法的公交线路 最后dfs找出最少的公交线路 使这些线路刚好完全覆盖你的记录 注意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
68
69
70
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1505;
int cnt[N], n, m, ans;

struct route //定义公交线路结构体
{
    int start, interval, times;
    route() {}
    route(int s, int i, int t): start(s), interval(i), times(t) {}
    bool operator< (const route &r) const {
        return times > r.times;
    }
} r[N];

bool ok(int time, int inter)
{
    while(time < 60)
    {
        if(!cnt[time]) return false;
        time += inter;
    }
    return true;
}

//从第k条线路开始匹配 当前已经匹配num个记录  用了sum个公交线路
void dfs(int k, int num, int sum)
{
    if(num == n)
    {
        if(sum < ans) ans = sum;
        return;
    }

    for(int i = k; i < m; ++i)
    {
        if(sum + (n - num) / r[i].times >= ans) return;
        //剪枝 r是按趟数从大到小排序的  所以最少还需要(n - num) / r[i].times个线路
        if(!ok(r[i].start, r[i].interval)) continue;
        for(int j = r[i].start; j < 60; j += r[i].interval) --cnt[j];
        dfs(i, num + r[i].times, sum + 1);
        //i之前的线路之前已经搜索过了
        for(int j = r[i].start; j < 60; j += r[i].interval) ++cnt[j]; //回溯
    }
}

int main()
{
    int t;
    while(~scanf("%d", &n))
    {
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < n; ++i)
            scanf("%d", &t), ++cnt[t]; //记录每个时刻出现多少公交

        m = 0;//生成以时刻i为首班  两班间隔时间为j的所有满足的公交线路
        for(int i = 0; i < 30; ++i)
            for(int j = i + 1; j < 60 - i; ++j)
                if(ok(i, j)) r[m++] = route(i, j, 1 + (59 - i) / j);

        sort(r, r + m);
        ans = 17;
        dfs(0, 0, 0);
        printf("%d\n", ans);
    }
    return 0;
}

The Buses

Description
A man arrives at a bus stop at 12:00. He remains there during 12:00-12:59. The bus stop is used by a number of bus routes. The man notes the times of arriving buses. The times when buses arrive are given.

Find the schedule with the fewest number of bus routes that must stop at the bus stop to satisfy the input data. For each bus route, output the starting time and the interval.

Input

Your program is to read from standard input. The input contains a number n (n <= 300) telling how many arriving buses have been noted, followed by the arrival times in ascending order.

Output

Your program is to write to standard output. The output contains one integer, which is the fewest number of bus routes.

Sample Input

17 0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53

Sample Output

3

Source

IOI 1994

Posted on In ,

题意 你要从第1个城市到第N个城市去 有m条路 每条路用a, b, c, p, r 表示 你从第a个城市到第b个城市时 若之前经过或现在位于第c个城市 过路费就是p元 否则就是r元 求你到达第N个城市最少用多少过路费

由于最多只有10个城市 10条路 这个题就变得很简单了 直接暴力dfs就行 可以用状态压缩来存储已经走过了哪些城市 由于最多只有10条路 从某个城市出发要一条 回这个城市也要一条 所以一个城市最多经过5次 这个可以作为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 <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 11, INF = 2333333;
int n, m, ans, vis[N];
struct road{
    int a, b, c, p, r;
} rd[N];

//当前所在城市, 到过哪些城市, 当前已经用了多少过路费
void dfs(int p, int s, int v)
{
    if(vis[p] > 5) return;
    s = s | 1 << (p - 1);
    if(p == n)
    {
        ans = min(ans, v);
        return;
    }

    for(int i = 0; i < m; ++i)
    {
        if(rd[i].a != p) continue;
        ++vis[rd[i].b];
        if(s & 1 << (rd[i].c - 1)) //到过城市c
            dfs(rd[i].b, s, v + rd[i].p);
        else dfs(rd[i].b, s, v + rd[i].r);
        --vis[rd[i].b]; //回溯
    }
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 0; i < m; ++i)
            scanf("%d%d%d%d%d", &rd[i].a, &rd[i].b, &rd[i].c, &rd[i].p, &rd[i].r);

        ans = INF;
        memset(vis, 0, sizeof(vis));
        dfs(1, 0, 0);
        if(ans == INF) puts("impossible");
        else printf("%d\n", ans);
    }

    return 0;
}

Paid Roads

Description

A network of m roads connects N cities (numbered from 1 to N). There may be more than one road connecting one city with another. Some of the roads are paid. There are two ways to pay for travel on a paid road i from city ai to city bi:

The payment is Pi in the first case and Ri in the second case.

Write a program to find a minimal-cost route from the city 1 to the city N.

Input

The first line of the input contains the values of N and m. Each of the following m lines describes one road by specifying the values of ai, bi, ci, Pi, Ri (1 ≤ i≤ m). Adjacent values on the same line are separated by one or more spaces. All values are integers, 1 ≤ m, N ≤ 10, 0 ≤ Pi , Ri ≤ 100, Pi ≤ Ri (1 ≤ i≤ m).

Output

The first and only line of the file must contain the minimal possible cost of a trip from the city 1 to the city N. If the trip is not possible for any reason, the line must contain the word ‘impossible’.

Sample Input

4 5 1 2 1 10 10 2 3 1 30 50 3 4 3 80 80 2 1 2 10 10 1 3 2 10 50

Sample Output

110

Source

Northeastern Europe 2002, Western Subregion

Posted on In ,

题意 给你一个数组 你每次可以从中删掉2到k个数 然后把删掉的数的积加入到原数组 直到最后只剩一个数 求这样能得到的最大值和最小值的差

每次选的数值越小 选的数量越少 最后得到的结果肯定越大 因为这样大的数可以乘以最大的倍数 运算的次数也是最多从而使+1的次数最多 这显然是有利于最后结果的增大的

同理 每次选的数越大 选的数越多 最后得到的结果越小

这样最大值就是每次取最小的两个数 最大值就是每次取最大的k个数了 很容易用优先队列实现 结果会很大 用Java的BigInteger实现比较方便

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
import java.math.BigInteger;
import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int N = 105;

		PriorityQueue<BigInteger> inc = new PriorityQueue<BigInteger>();
		//优先队列默认小的优先 是增序队列
		PriorityQueue<BigInteger> dec = new PriorityQueue<BigInteger>(N,
				new Comparator<BigInteger>() {
					public int compare(BigInteger o1, BigInteger o2) {
						return -o1.compareTo(o2);
					}
				}); //匿名实现Comparator接口  降序大的优先

		int n, k;
		BigInteger a, b, one = BigInteger.ONE;
		List<BigInteger> list = new ArrayList<BigInteger>();

		while (in.hasNext()) {
			n = in.nextInt();
			k = in.nextInt();

			list.clear();
			for (int i = 0; i < n; ++i) {
				a = in.nextBigInteger();
				list.add(a);
			}

			inc.addAll(list);
			while (inc.size() > 1) {
				a = inc.poll();
				b = inc.poll();
				inc.add(a.multiply(b).add(one));
			}

			dec.addAll(list);
			while (dec.size() > 1) {
				a = one;
				for (int i = 0; i < k; ++i)
					if (dec.size() > 0)
						a = a.multiply(dec.poll());
				a = a.add(one);
				dec.add(a);
			}
			System.out.println(inc.poll().subtract(dec.poll()));
		}

		in.close();
	}
}

ZOJ Problem Set - 3447
Doraemon’s Number Game Time Limit:2 Seconds Memory Limit:65536 KB

Doraemon and Nobita are playing a number game. First, Doraemon will give Nobita N positive numbers. Then Nobita can deal with these numbers for two rounds. Every time Nobita can delete i (2 ≤ i ≤ K) numbers from the number set. Assume that the numbers deleted is a[ 1 ], a[ 2 ] … a[ i ]. There should be a new number X = ( a[ 1 ] /* a[ 2 ] /* … /* a[ i ] + 1 ) to be inserted back into the number set. The operation will be applied to the number set over and over until there remains only one number in the set. The number is the result of round. Assume two results A and B are produced after two rounds. Nobita can get |A - B| scores.

Now Nobita wants to get the highest score. Please help him.

Input

Input will contain no more than 10 cases. The first line of each case contains two positive integers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ 50). The following line contains N positive integers no larger than 50, indicating the numbers given by Doraemon.

Output

For each case, you should output highest score in one line.

Sample Input

6 3 1 3 4 10 7 15

Sample Output

5563

Hint

For most cases, N ≤ 20

Posted on In ,

题意 多啦A梦有一个超电磁炮 然后要打死n堆敌人 在同一条射线上的敌人只有先打死前面的一堆才能打后面的一堆 给你打死某堆敌人需要的时间和这堆敌人的人数 问你在T0时间内最多打死多少个敌人

分组背包问题 先要把同一条射线上的敌人放到一个分组里后面的敌人的时间和人数都要加上前面所有的 因为只有前面的都打完了才能打后面的 然后每组最多只能选择一个判断共线用向量处理 然后去背包就行了

注意给你的样例可能出现t=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
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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 505;
int vis[N], dp[10086];

struct enemy
{
    ll x, y;
    int t, w;
} e[N];


bool cmp(enemy a, enemy b)  //按与原点的距离排序
{
    return a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;
}

bool aLine(int i, int j) //判断是否在同一条射线上·
{
    if(e[i].x * e[j].y == e[i].y * e[j].x)
        return e[i].x * e[j].x >= 0 &&  e[i].y * e[j].y >= 0;
    return 0;
}

int main()
{
    ll x, y, x0, y0;
    int n, t0;
    while(~scanf("%lld%lld%d%d", &x0, &y0, &n, &t0))
    {
        for(int i = 0; i < n; ++i)
        {
            scanf("%lld%lld%d%d", &x, &y, &e[i].t, &e[i].w);
            e[i].x = x - x0;
            e[i].y = y - y0;
        }
        sort(e, e + n, cmp);  //按与原点的距离排序

        vector<enemy> em[N];  //把在一条射线上的放到一个分组里
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; ++i)
        {
            if(vis[i]) continue;  //i已经在别的组里了
            em[i].push_back(e[i]);
            for(int j = i + 1; j < n; ++j)
            {
                if(!aLine(i, j)) continue;
                int k = em[i].size() - 1;
                vis[j] = 1;
                if(e[j].t == 0)  //把耗时为0的敌人放到上一个里
                {
                    em[i][k].w += e[j].w;
                    continue;
                }

                em[i].push_back(e[j]);
                em[i][k + 1].w += em[i][k].w;
                em[i][k + 1].t += em[i][k].t;
            }
        }

        memset(dp, 0, sizeof(dp)); //分组背包
        for(int i = 0; i < n; ++i)
        {
            int k = em[i].size();
            for(int v = t0; v >= 0; --v)
                for(int j = 0; j < k && em[i][j].t <= v; ++j)
                    dp[v] = max(dp[v], dp[v - em[i][j].t] + em[i][j].w);
        }
        printf("%d\n", dp[t0]);
    }

    return 0;
}

Doraemon’s Railgun Time Limit:2 Seconds Memory Limit:65536 KB toaru-dorano-railgun

Doraemon’s city is being attacked again. This time Doraemon has built a powerful railgun in the city. So he will use it to attack enemy outside the city.

There are N groups of enemy. Now each group is staying outside of the city. Group i is located at different (Xi, Yi) and contains Wi soldiers. After T0 days, all the enemy will begin to attack the city. Before it, the railgun can fire artillery shells to them.

The railgun is located at (X0, Y0), which can fire one group at one time, The artillery shell will fly straightly to the enemy. But in case there are several groups in a straight line, the railgun can only eliminate the nearest one first if Doraemon wants to attack further one. It took Ti days to eliminate group i. Now please calculate the maximum number of soldiers it can eliminate.

Input

There are multiple cases. At the first line of each case, there will be four integers, X0, Y0, N, T0 (-1000000000 ≤ X0, Y0 ≤ 1000000000; 1 ≤ N ≤ 500; 1 ≤ T0 ≤ 10000). Next N lines follow, each line contains four integers, Xi, Yi, Ti, Wi (-1000000000 ≤ Xi, Yi ≤ 1000000000; 0 ≤ Ti, Wi ≤ 10000).

Output

For each case, output one integer, which is the maximum number of soldiers the railgun can eliminate.

Sample Input

0 0 5 10 0 5 2 3 0 10 2 8 3 2 4 6 6 7 3 9 4 4 10 2

Sample Output

20

Posted on In ,

题意 给你p个商品名称 然后输入q个字符串查询 对每个查询输出含有查询串为子串的商品个数

Trie能很快的求出字典中以某个串为前缀的串的个数 但现在要查的是以某个串为子串的串的个数 可以发现

一个串的任何子串肯定是这个串某个后缀的前缀如”ri”是“Trie” 的子串 是后缀 “rie” 的前缀

那么我们在向Trie中插入时可以把这个串的所有后缀都插入 插入时要注意来自同一个串的后缀的相同前缀只能统计一次 如 “abab” 这个串 “ab” 既是后缀 “abab” 的前缀 也是后缀 “ab” 的前缀 但是只能统计一次 这用一个id数组标记就行了

这样最后Trie中以查询串为前缀的串的个数就是原始串中以查询串为子串的串的的个数了

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
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e6 + 5;
int trie[N][26], cnt[N], id[N], L;

void insertTrie(char s[], int iid)
{
    int r = 0, i = 0, j;
    while(s[i])
    {
        j = s[i++] - 'a';
        if(!trie[r][j])
            trie[r][j] = L++;
        r = trie[r][j];
        if(id[r] != iid) ++cnt[r];
        id[r] = iid;//标记当前前缀id 保证来自相同串的只自增一次
    }
}

int searchTrie(char s[])
{
    int r = 0, i = 0, j;
    while(s[i])
    {
        j = s[i++] - 'a';
        if(!trie[r][j])
            return 0;
        r = trie[r][j];
    }
    return cnt[r];
}

int main()
{
    L = 1;//初始化Trie
    char s[30];
    int p, q;
    scanf("%d", &p);
    for(int i = 1; i <= p; ++i)
    {
        scanf("%s", s); //插入s的所有后缀
        for(int j = 0; s[j]; ++j)
            insertTrie(s + j, i);
    }

    scanf("%d", &q);
    while(q--)
    {
        scanf("%s", s);
        printf("%d\n", searchTrie(s));
    }

    return 0;
}
//Last modified :   2015-07-28 08:33

Repository

Problem Description

When you go shopping, you can search in repository for avalible merchandises by the computers and internet. First you give the search system a name about something, then the system responds with the results. Now you are given a lot merchandise names in repository and some queries, and required to simulate the process.
Input

There is only one case. First there is an integer P (1<=P<=10000)representing the number of the merchanidse names in the repository. The next P lines each contain a string (it’s length isn’t beyond 20,and all the letters are lowercase).Then there is an integer Q(1<=Q<=100000) representing the number of the queries. The next Q lines each contains a string(the same limitation as foregoing descriptions) as the searching condition.
Output

For each query, you just output the number of the merchandises, whose names contain the search string as their substrings.
Sample Input

20 ad ae af ag ah ai aj ak al ads add ade adf adg adh adi adj adk adl aes 5 b a d ad s
Sample Output

0 20 11 11 2

Posted on In ,

题意 给你一组电话号码 判断其中是否有某个电话是另一个电话的前缀

字典树的基础应用 可以先把所有电话存进Trie 标记每个电话的结束字符 然后再查询每个号码 看中途是否有结束标记 有的话就说明有号码是这个号码的前缀了

实际上 插入完成就能知道是否有号码是另一个号码的前缀了 假设A是B的前缀

若A在B之前插入 那么插入B的时候会遇到A的结束标记

弱A在B之后插入 那么A插入完成之后的结点还有非空的孩子结点

这样就只用在每次插入时判断就行了 可以省掉查询这一步

指针和动态内存分配实现字典更容易些 但在有多组样例的时侯不释放内存会导致MLE 释放内存又要多花费不必要的时间 可能导致TLE 所以用数组实现比较好

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
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 10005;
char tel[N][12];
int trie[N * 10][10], L;
bool end[N * 10], flag;

void initTrie()  //清空Trie
{
    L = 1;
    memset(trie, 0, sizeof(trie));
    memset(end, 0, sizeof(end));
}

void insertTrie(char s[])  //插入
{
    int r = 0, i = 0, j;
    while(s[i])
    {
        if(end[r]) flag = false;  //遇到其它号码的结束标记
        j = s[i++] - '0';
        if(!trie[r][j])
            trie[r][j] = L++;
        r = trie[r][j];
    }
    for(int i = 0; i < 10; ++i)  //插入完成的节点还有孩子节点
        if(trie[r][i]) flag = false;
    end[r] = true;
}

int main()
{
    int T, n;
    scanf("%d", &T);

    while(T--)
    {
        initTrie();
        scanf("%d", &n);
        flag = true;
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", tel[i]);
            insertTrie(tel[i]);
        }
        puts(flag ? "YES" : "NO");
    }

    return 0;
}
//Last modified :   2015-07-27 19:36

Phone List

Problem Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:

  1. Emergency 911
  2. Alice 97 625 999
  3. Bob 91 12 54 26
    In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.
    Input

The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.
Output

For each test case, output “YES” if the list is consistent, or “NO” otherwise.
Sample Input

2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
Sample Output

NO YES

0%