题意 给你一个字典 输出字典中能表示成两个单词连接的所有单词

最基础的字典树应用 先把所有单词加入字典树中 标记每个结点是否为某个单词的结尾 然后查找每个单词 在树上查询过程中遇到单词结尾时 如果剩下的后缀也是一个单词 那当前查询的单词就可以是两个单词的连接了

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

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 50005;
int n;
char ss[N][20];

struct Trie
{
    Trie *chi[26];
    bool isEnd;
    Trie()
    {
        isEnd = false;
        memset(chi, NULL, sizeof(chi));
    }
}*root;

void insertTrie(Trie *r, char s[])
{
    int i = 0, j;
    while(s[i])
    {
        j = s[i++] - 'a';
        if(r->chi[j] == NULL)
            r->chi[j] = new Trie();
        r = r->chi[j];
    }
    r->isEnd = true;
}

//op标记这次查询是查询后缀还是查询整个
bool searchTrie(Trie *r, char s[], int op)
{
    int i = 0, j;
    while(s[i])
    {
        j = s[i++] - 'a';
        if(r->chi[j] == NULL)
            return false;
        r = r->chi[j];
        if(!op && r->isEnd && s[i])//前缀是一个单词
        {
            if(searchTrie(root, s + i, 1))
                return true; //查询后缀是否是一个单词
        }
    }
    return op ? r->isEnd : op;
}

int main()
{
    int m = 0;
    root = new Trie();
    while(~scanf("%s", ss[m]))
        insertTrie(root, ss[m++]);

    for(int i = 0; i < m; ++i)
        if(searchTrie(root, ss[i], 0)) puts(ss[i]);

    return 0;
}

Hat’s Words

Problem Description

A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
You are to find all the hat’s words in a dictionary.
Input

Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
Only one case.
Output

Your output should contain all the hat’s words, one per line, in alphabetical order.
Sample Input

a ahat hat hatword hziee word
Sample Output

ahat hatword

题意 把一个数替换为这个数相邻数字差组成的数 知道这个数只剩一位数 若最后的一位数是7 则称原来的数为 July Number 给你一个区间 求这个区间中July Number的个数

从7开始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

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int july[N], n;
set<int> ans;

int pw[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
//剩余长度, 当前位要填的数，通过什么数来搜索, 路径
void dfs(int len, int d, int bas, int cur)
{
    if(d < 0 || d > 9) return;  //要填的数不合法
    if(!len)
    {
        july[n++] = cur * 10 + d;
        return;
    }
    int k = pw[len - 1];
    dfs(len - 1, d - bas / k, bas % k, cur * 10 + d);
    dfs(len - 1, d + bas / k, bas % k, cur * 10 + d);
}

int main()
{
    ans.insert(7);
    set<int>::iterator it;
    for(int l = 2; l < 10; ++l)
    {
        n = 0;
        for(it = ans.begin(); it != ans.end(); ++it)
            for(int i = 1; i < 10; ++i)
                dfs(l - 1, i, *it, 0);
        for(int i = 0; i < n; ++i) ans.insert(july[i]);
        //printf("%d\n", ans.size());
    }

    int a, b = n = 0;
    for(it = ans.begin(); it != ans.end(); ++it) 
        july[n++] = *it;
    while(~scanf("%d%d", &a, &b))
        printf("%d\n", upper_bound(july, july + n, b) - lower_bound(july, july + n, a));

    return 0;
}

July Number Time Limit:2 Seconds Memory Limit:65536 KB

The digital difference of a positive number is constituted by the difference between each two neighboring digits (with the leading zeros omitted). For example the digital difference of 1135 is 022 = 22. The repeated digital difference, or differential root, can be obtained by caculating the digital difference until a single-digit number is reached. A number whose differential root is 7 is also called July Number. Your job is to tell how many July Numbers are there lying in the given interval [a, b].

Input

There are multiple cases. Each case contains two integers a and b. 1 ≤ a ≤ b ≤ 109.

Output

One integer k, the number of July Numbers.

Sample Input

1 10

Sample Output

1
Author: HE, Ningxu
Contest: ZOJ Monthly, November 2010

题意 Watashi发明了一种蛋疼(eggache) 语言 你要为这个语言实现一个 array slicing 函数 这个函数的功能是 有一个数组初始为空 每次给你一个区间[ l, r) 和一些数 你要输出数组中下标在[l, r) 之间的数 然后删除这些数 然后把给你的那些数插入到数组的下标为 l 的位置

签到模拟题 一直没看懂题意 看了Watashi的scanf高端用法 弱到连scanf都不会用了 强行到cpp预习了一下 先记录一下那些并不了解的scanf用法吧

int scanf ( const char /* format, … );

format 由这些内容组成

• 空白字符: scanf在读入时会忽略下一个非空白字符之前的所有空白字符 空白字符包含 ‘ ‘’\t’, ‘\n’, ‘\v’, ‘\f’, ‘\r
  /* 表示这个格式说明符所对应的内容读而不存 也不用为其指定参数 (注意区别 printf /* 需要一个整型参数 表示至少输出多少位 不足用空格代替)

width 表示最多读取多少位字符
length 有的话一定是这几个之一 hh , h , l , ll , j , z , t , L 对应同种数据的不同位数类型如 int(d) 和 long long(lld) 重点是 specifier specifier 描述 Characters extracted i Integer Any number of digits, optionally preceded by a sign (+ or -).
Decimal digits assumed by default (0-9), but a 0 prefix introduces octal digits (0-7), and 0x hexadecimal digits (0-f).
Signed argument. d or u
Decimal integer Any number of decimal digits (0-9), optionally preceded by a sign (+ or -).
d is for a signed argument, and u for an unsigned. o Octal integer Any number of octal digits (0-7), optionally preceded by a sign (+ or -).
Unsigned argument. x Hexadecimal integer Any number of hexadecimal digits (0-9, a-f, A-F), optionally preceded by 0x or 0X, and all optionally preceded by a sign (+ or -).
Unsigned argument. f, e, g Floating point number A series of decimal digits, optionally containing a decimal point, optionally preceeded by a sign (+ or -) and optionally followed by the e or E character and a decimal integer (or some of the other sequences supported by strtod).
Implementations complying with C99 also support hexadecimal floating-point format when preceded by

1

0x

or

1

0X

. a c Character The next character. If a width other than 1 is specified, the function reads exactly widthcharacters and stores them in the successive locations of the array passed as argument. No null character is appended at the end. s String of characters Any number of non-whitespace characters, stopping at the first whitespace character found. A terminating null character is automatically added at the end of the stored sequence. p Pointer address A sequence of characters representing a pointer. The particular format used depends on the system and library implementation, but it is the same as the one used to format %p in fprintf. [characters] Scanset Any number of the characters specified between the brackets.
A dash (-) that is not the first character may produce non-portable behavior in some library implementations. [^characters] Negated scanset Any number of characters none of them specified as characters between the brackets. n Count No input is consumed.
The number of characters read so far from stdin is stored in the pointed location. % % A % followed by another % matches a single %.
除了 n 之外 specifier至少匹配一个输入的字符 否则读入会在当前字符终止 n需要一个指向int的参数 保存在这之前读取了多少位字符

1
2
3
4
5
6
7
8
9
10

int main()
{
    char s[500];
    int n;
    scanf("%s%n", s, &n);
    printf("%s  %d\n", s, n);
    //输入hello
    //输出hello 5
    return 0;
}

printf中也可以使用%n表示这条语句这之前输出了多少位字符

1
2
3
4
5
6
7
8

int main()
{
    int n;
    printf("hello%n", &n);
    printf(" %d\n", n);
    //输出hello 5
    return 0;
}

specifier可以是[…]、[^…]这两种正则表达式

[…]表示读取括号中包含的字符 遇到其他字符就结束这个specifier

1
2
3
4
5
6
7
8
9
10
11
12

int main()
{
    char s[500];
    int n;
    scanf(" %[0-9]%n", s, &n);//%[0-9]只读取数字  遇到非数字结束
    printf("%s %d\n", s, n);
    scanf(" %[ab]%n", s, &n);
    printf("%s %d\n", s, n);
    //输入"   12345abc"  前面有三个空格
    //输出12345 8  ab 2
    return 0;
}

[^…]表示读取除括号中字符之外的所有字符 遇到括号中的字符就结束这个specifier

当然这些东西sscanf也适用

感觉预习了scanf之后这个题的输入就很好处理了 直接用list的splice函数就行了

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

#include <bits/stdc++.h>
using namespace std;
char s[5000], *ps;

int main()
{
    list<int> a, b;
    int l, r, n, v;
    list<int>::iterator it;
    while(~scanf(" [ %d : %d ]%[^\n]", &l, &r, s))
    {
        b.clear();
        ps = s;
        while(sscanf(ps, "%*[^-0-9]%d%n", &v, &n) > 0)
        {
            //过滤掉非'-'和数字再读入一个数
            //n记录scanf读了多少个字符
            ps = ps + n;  //读了n个字符所以要前进n位
            b.push_back(v);
        }

        advance(it = a.begin(), l);
        while(l < r)
        {
            printf("%d%s", *it, l < r - 1 ? ", " : "");
            it = a.erase(it);
            l++;
        }
        puts("");
        a.splice(it, b);
    }
    return 0;
}

Array Slicing Time Limit:2 Seconds Memory Limit:65536 KB

Array slicing is an operation that extracts certain elements from an array and packages them as another array. Now you’re asked to implements the array slicing operations for a new programming language – eggache/* (pronounced “eggache star”). The grammar of array slicing in eggache/* is:
[ begin : end ] = x1, x2, …, xk, …
where begin ≤ end are indices indicating the range of slice. Redundant whitespaces should be ignored. For each operation, the original slice should be printed first, then these elements will be replaced with the new elements provided. See sample for more details.

Input

There is only one case for this problem, which contains about 50 lines of array slicing operations. It’s guaranteed that all operations are valid and the absolute values of all integers never exceed 100. The array is empty ([]) before the first operation.

Output

The output produced by array slicing operations in the eggache/* programming language.

Sample Input

[ 0 : 0] = 1 2 3 4 5 6 7 8 9 [ 1 : 1] = -1 [ 1 : 1] = [ 0 : 8] = 9 8 7 6 5 4 3 2 1 [ 2 : 8] = -2, -3, -5, -7 [ 0 : 9] = 000 [ 0 : 1] = 1, 2, 8 [ 2 : 2] = 4 [ 0 : 4] =

Sample Output

1, -1, 2, 3, 4, 5, 6, 7 7, 6, 5, 4, 3, 2 9, 8, -2, -3, -5, -7, 1, 8, 9 0 1, 2, 4, 8

题意 中文

最基础的数位DP 这题好像也可以直接暴力来做 令dp[i][j]表示以 j 开头的 i 位数有多少个满足条件

那么很容易有状态转移方程dp[i][j] = sum{ dp[i-1][k] }, k = 0…9, j != 4 && !( j == 6 && k == 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

#include <bits/stdc++.h>
using namespace std;
int dp[8][10];

int dfs(int i, int j) //记忆化搜索统计以 j 开头的 i 位数满足条件的个数
{
    if(dp[i][j] > -1) return dp[i][j];

    dp[i][j] = 0;
    for(int k = 0; k < 10; ++k)
    {
        if(j == 4 || (j == 6 && k == 2)) continue;
        dp[i][j] += dfs(i - 1, k);
    }
    return dp[i][j];
}

int getNum(int a) //统计[0,a)这个区间满足条件的数的个数
{
    int s[10] = {0};
    int i = 0, ret = 0;
    while(a)
    {
        s[i++] = a % 10;
        a /= 10;
    }

    while(i--)
    {
        for(int j = 0; j < s[i]; ++j)
            if(!(j == 2 && s[i + 1] == 6))
                ret += dfs(i + 1, j);
        if(s[i] == 4 || (s[i] == 2 && s[i + 1] == 6))
            break;    //已经不满足条件了
    }
    return ret;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < 10; ++i) dp[1][i] = (i != 4); //边界

    int n, m;
    while(scanf("%d%d", &n, &m), n || m)
        printf("%d\n", getNum(m + 1) - getNum(n));

    return 0;
}
//Last modified :   2015-07-22 15:22

不要62

Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input

输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。
Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
Sample Input

1 100 0 0
Sample Output

80

题意 在坐标系中有n条平行于y轴的线段 当一条线段与另一条线段之间可以连一条平行与x轴的线不与其它线段相交 就视为它们是可见的 问有多少组三条线段两两相互可见

先把所有线段存下来 并按x坐标排序 线段树记录对应区间从右往左当前可见的线段编号(1…n) 超过一条就为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
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

#include <cstdio>
#include <algorithm>
#include <cstring>
#define lc p<<1, s, mid
#define rc p<<1|1, mid+1, e
#define mid ((s+e)>>1)
using namespace std;
const int N = 8005;
int top[N * 8];
bool g[N][N];

struct seg
{
    int y1, y2, x;
} line[N];

bool cmp(seg a, seg b)
{
    return a.x < b.x;
}

void build()
{
    memset(g, 0, sizeof(g));
    memset(top, 0, sizeof(top));
}

void pushup(int p)
{
    top[p] = (top[p << 1] == top[p << 1 | 1]) ? top[p << 1] : 0;
}

void pushdown(int p)
{
    if(top[p])
    {
        top[p << 1] = top[p << 1 | 1] = top[p];
        top[p] = 0;
    }
}

void update(int p, int s, int e, int l, int r, int v)
{
    if(l <= s && e <= r)
    {
        top[p] = v;
        return;
    }
    pushdown(p);
    if(l <= mid) update(lc, l, r, v);
    if(r > mid) update(rc, l, r, v);
    pushup(p);
}

void query(int p, int s, int e, int l, int r, int x)
{
    if(top[p]) //p对应的区间已经只可见一条线段
    {
        g[top[p]][x] = 1;
        return;
    }
    if(s == e) return;
    if(l <= mid) query(lc, l, r, x);
    if(r > mid) query(rc, l, r, x);
}

int main()
{
    int T, n, l, r;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d%d%d", &line[i].y1, &line[i].y2, &line[i].x);
        sort(line + 1, line + n + 1, cmp);

        build();
        for(int i = 1; i <= n; ++i)
        {
            //点化为区间会丢失间隔为1的区间  所以要乘以2
            l = (line[i].y1) * 2;
            r = (line[i].y2) * 2;
            query(1, 0, N * 2, l, r, i);
            update(1, 0, N * 2, l, r, i);
        }

        int ans = 0;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = i + 1; j <= n; ++j)
            {
                if(g[i][j])
                    for(int k = j + 1; k <= n; ++k)
                        if(g[j][k] && g[i][k]) ++ans;
            }
        }

        printf("%d\n", ans);
    }
    return 0;
}
//Last modified :   2015-07-15 15:33

Horizontally Visible Segments

Description
There is a number of disjoint vertical line segments in the plane. We say that two segments are horizontally visible if they can be connected by a horizontal line segment that does not have any common points with other vertical segments. Three different vertical segments are said to form a triangle of segments if each two of them are horizontally visible. How many triangles can be found in a given set of vertical segments?
Task
Write a program which for each data set:
reads the description of a set of vertical segments,
computes the number of triangles in this set,
writes the result.

Input

The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 20. The data sets follow.
The first line of each data set contains exactly one integer n, 1 <= n <= 8 000, equal to the number of vertical line segments.
Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:
yi’, yi’’, xi - y-coordinate of the beginning of a segment, y-coordinate of its end and its x-coordinate, respectively. The coordinates satisfy 0 <= yi’ < yi’’ <= 8 000, 0 <= xi <= 8 000. The segments are disjoint.

Output

The output should consist of exactly d lines, one line for each data set. Line i should contain exactly one integer equal to the number of triangles in the i-th data set.

Sample Input

1 5 0 4 4 0 3 1 3 4 2 0 2 2 0 2 3

Sample Output

1

Source

Central Europe 2001

题意 n个人顺时针围成一圈玩约瑟夫游戏 每个人手上有一个数val[i] 开始第k个人出队 若val[k] < 0 下一个出队的为在剩余的人中向右数 -val[k]个人 val[k] > 0 时向左数val[k]个 第m出队的人可以得到m的约数个数个糖果 问得到最多糖果的人是谁

约瑟夫环问题 n比较大 直接模拟会超时 通过线段树可以让每次出队在O(logN)时间内完成 类似上一道插队的题 线段树维护对应区间还有多少个人没出队 那么当我们知道出队的人在剩余人中排第几个也就可以通过线段树知道他在原始环中排第几个了

至于第几个出队的人糖果最多就是求1…n中约数最多的数 可以利用反素数相关知识

对于任何正整数x 其约数的个数记做g(x) 例如g(1)=1 g(6)=4 如果某个正整数x满足 对于任意i(0<i<x) 都有g(i)<g(x) 则称x为反素数

我直接用的别人的反素数表

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

#include <cstdio>
#define lc p<<1, s, mid
#define rc p<<1|1, mid + 1, e
#define mid ((s+e)>>1)
using namespace std;
const int N = 5e5 + 5;
int tot[N * 4], val[N];
//tot维护对应区间还有多少人没出去
char name[N][20];

int ip[] = {1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720,
            840, 1260, 1680, 2520, 5040, 7560, 10080, 15120, 20160,
            25200, 27720, 45360, 50400, 55440, 83160, 110880,
            166320, 221760, 277200, 332640, 498960, 500001
           }; //反素数

int div[] = {1, 2, 3, 4, 6, 8, 9, 10, 12, 16, 18, 20, 24, 30, 32, 36,
             40, 48, 60, 64, 72, 80, 84, 90, 96, 100, 108, 120,
             128, 144, 160, 168, 180, 192, 200
            };//反素数对应的约数个数

void pushup(int p)
{
    tot[p] = tot[p << 1] + tot[p << 1 | 1];
}

void build(int p, int s, int e)
{
    if(s == e)
    {
        tot[p] = 1;
        return;
    }
    build(lc);
    build(rc);
    pushup(p);
}

int update(int p, int s, int e, int x)
{
    int ret;
    if(s == e)
    {
        tot[p] = 0;
        return s;
    }
    if(x <= tot[p << 1]) ret = update(lc, x);
    else ret = update(rc, x - tot[p << 1]);
    pushup(p);
    return ret;
}

int main()
{
    int n, k, m, r, ans, pos;
    while(scanf("%d%d", &n, &k) != EOF)
    {
        build(1, 1, n);
        for(int i = 1; i <= n; ++i)
            scanf("%s%d", name[i], &val[i]);

        for(int i = 0; ip[i] <= n; ++i)
        {
            m = ip[i];   //m为小于等于n的第一个反素数
            ans = div[i];  //ans对应m的约数个数
        }

        r = n; //还剩r个人
        for(int i = 0; i < m; ++i)
        {
            r--;
            pos = update(1, 1, n, k);
            //pos为剩余序列中排第k的人在原始队列中的位置
            if(!r) break;
            if(val[pos] >= 0)   //顺时针
                k = (k - 1 - 1 + val[pos]) % r + 1;
            //第一个-1是把1开始转换为0开始
            //第二个是删除第k个后现在位于第k-1个 要前进val[pos]步
            //后面的+1是把0开始换回1开始
            else                //逆时针
                k = ((k - 1 + val[pos]) % r + r) % r + 1;
            //逆时针删除第k个后现在还位于第k个 要后退-val[pos]步
        }
        printf("%s %d\n", name[pos], ans);
    }

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

Who Gets the Most Candies?

Description
N children are sitting in a circle to play a game.

The children are numbered from 1 to N in clockwise order. Each of them has a card with a non-zero integer on it in his/her hand. The game starts from the K-th child, who tells all the others the integer on his card and jumps out of the circle. The integer on his card tells the next child to jump out. Let A denote the integer. If A is positive, the next child will be the A-th child to the left. If A is negative, the next child will be the (−A)-th child to the right.

The game lasts until all children have jumped out of the circle. During the game, the p-th child jumping out will get F(p) candies where F(p) is the number of positive integers that perfectly divide p. Who gets the most candies?

Input

There are several test cases in the input. Each test case starts with two integers N (0 < N ≤ 500,000) and K (1 ≤ K ≤ N) on the first line. The next Nlines contains the names of the children (consisting of at most 10 letters) and the integers (non-zero with magnitudes within 108) on their cards in increasing order of the children’s numbers, a name and an integer separated by a single space in a line with no leading or trailing spaces.

Output

Output one line for each test case containing the name of the luckiest child and the number of candies he/she gets. If ties occur, always choose the child who jumps out of the circle first.

Sample Input

4 2 Tom 2 Jack 4 Mary -1 Sam 1

Sample Output

Sam 3

题意 n个人排队 每个人都有个属性值 依次输入n个pos[i] val[i] 表示第i个人直接插到当前第pos[i]个人后面 他的属性值为val[i] 要求最后依次输出队中各个人的属性值

从头到尾看的话 队列是动态的 无法操作 但是反过来看时 pos[i]就可以表示第i个人前面有多少个空位了 然后想到了用线段树做就简单了 线段树维护对应区间还有多少个空位 每次把i放到前面刚好有pos[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

#include <cstdio>
#define lc p<<1, s, mid
#define rc p<<1|1, mid+1, e
#define mid ((s+e)>>1)

using namespace std;
const int N = 2e5 + 5;
int tot[N * 4], ans[N];
//tot维护对应区间还能放多少人
int pos[N], val[N];
//pos[i] 保存第i个人进队时前面有多少人
//val[i] 保存第i个人的val

void pushup(int p)
{
    tot[p] = tot[p << 1] + tot[p << 1 | 1];
}

void build(int p, int s, int e)
{
    //tot维护对应区间还能放多少人
    if(s == e)
    {
        tot[p] = 1;
        return;
    }
    build(lc);
    build(rc);
    pushup(p);
}

//第i个人插入
void update(int p, int s, int e, int i)
{
    if(s == e)
    {
        tot[p] = 0;
        ans[e] = val[i];
        return;
    }
    if(tot[p << 1] > pos[i])
        update(lc, i);  //左区间的空位足够
    else
    {
        pos[i] -= tot[p << 1];
        update(rc, i);
    }
    pushup(p);
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        build(1, 1, n);
        for(int i = 1; i <= n; ++i)
            scanf("%d%d", &pos[i], &val[i]);

        for(int i = n; i > 0; --i) //倒着更新
            update(1, 1, n, i);

        for(int i = 1; i < n; ++i)
            printf("%d ", ans[i]);

        printf("%d\n", ans[n]);
    }

    return 0;
}
//Last modified :   2015-07-13 11:13

题意 已知LCM(a, b, c) = L 和 a、b、L 求最小的满足等式的c.

把数展开为素因子积的形式后

GCD(a,b)就是a,b的公共素因子取在a、b中的较小指数

LCM(a,b)就是a,b的所有素因子取在a、b中的较大指数

令m = LCM(a,b) 那么问题转化为了求最小的c满足 LCM(m, c) = L

那么最小的c就是L中不在m中的素因子和L中指数大于m中指数的素因子取在L中的指数即积

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int T;
    ll a, b, l, c, d, m;
    scanf("%d", &T);
    for(int cas = 1; cas <= T; ++cas)
    {
        printf("Case %d: ", cas);
        scanf("%lld%lld%lld", &a, &b, &l);
        m = a * b / gcd(a, b); //m为a,b的最大公约数

        if(l % m) puts("impossible");
        else
        {
            //要使lcm(c,m) = l  c中至少要有l中不在m中的素因子和l中指数大于m中的素因子取在l中的指数
            c = l / m;   //现在c中包含了l中不在m中的素因子取l中指数 和 l中指数大于m中的素因子取指数差
            //那么现在c还需要乘上c和m的公共素因子取m中的指数
            while((d = gcd(c, m)) != 1) //gcd(c,m) 取c,m公共素因子的小指数积
            {
                c = c * d, m = m / d;
                d = gcd(c, m);
            }
            printf("%lld\n", c);
        }
    }
    return 0;
}

1215 - Finding LCM
LCM is an abbreviation used for Least Common Multiple in Mathematics. We say LCM (a, b, c) = L if and only if L is the least integer which is divisible by a, band c.

You will be given a, b and L. You have to find c such that LCM (a, b, c) = L. If there are several solutions, print the one where c is as small as possible. If there is no solution, report so.

Input

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

Each case starts with a line containing three integers a b L (1 ≤ a, b ≤ 106, 1 ≤ L ≤ 1012).

Output

For each case, print the case number and the minimum possible value of c. If no solution is found, print ‘impossible’.

Sample Input

Output for Sample Input 3

3 5 30

209475 6992 77086800

2 6 10

Case 1: 2

Case 2: 1

Case 3: impossible

题意 机器调度问题 有两个机器A，B A有n种工作模式0…n-1 B有m种工作模式0…m-1 然后又k个任务要做 每个任务可以用A机器的模式i或b机器的模式j来完成 机器开始都处于模式0 每次换模式时都要重启 问完成所有任务机器至少重启多少次

最基础的二分图最大匹配问题 对于每个任务把i和j之间连一条边就可以构成一个二分图 那么每个任务都可以对应一条边 那么现在就是要找最少的点 使这些点能覆盖所有的边 即点覆盖数 又因为二分图的点覆盖数 = 匹配数 那么就是裸的求二分图最大匹配问题了 两边的点数都不超过100直接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

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int g[N][N], a[N], b[N], vis[N];
int n, m, k, ans;

int dfs(int i)   //DFS增广
{
    for(int j = 1; j < m; ++j)
    {
        if(g[i][j] && !vis[j])
        {
            vis[j] = 1;
            if( b[j] == -1 || dfs(b[j]))
            {
                //机器a的模式i与机器b的模式j匹配
                a[i] = j;
                b[j] = i;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int u, v, t;
    while(scanf("%d", &n), n)
    {
        memset(g, 0, sizeof(g));
        scanf("%d%d", &m, &k);
        for(int i = 0; i < k; ++i)
        {
            scanf("%d%d%d", &t, &u, &v);
            g[u][v] = 1;
        }

        ans = 0;
        memset(a, -1, sizeof(a));
        memset(b, -1, sizeof(b));
        //状态0不需要重启  所以可以忽略0
        for(int i = 1; i < n; ++i)
        {
            if(a[i] == -1)  //i没被匹配 以i为起点找一条增广路
            {
                memset(vis, 0, sizeof(vis));
                ans += dfs(i);  //
            }
        }

        printf("%d\n", ans);
    }
    return 0;
}
//Last modified :   2015-07-10 14:50

Machine Schedule Time Limit:2 Seconds Memory Limit:65536 KB

As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature of the constraints that must be satisfied and the type of schedule desired. Here we consider a 2-machine scheduling problem.
There are two machines A and B. Machine A has n kinds of working modes, which is called mode_0, mode_1, ��, mode_n-1, likewise machine B has m kinds of working modes, mode_0, mode_1, �� , mode_m-1. At the beginning they are both work at mode_0.
For k jobs given, each of them can be processed in either one of the two machines in particular mode. For example, job 0 can either be processed in machine A at mode_3 or in machine B at mode_4, job 1 can either be processed in machine A at mode_2 or in machine B at mode_4, and so on. Thus, for job i, the constraint can be represent as a triple (i, x, y), which means it can be processed either in machine A at mode_x, or in machine B at mode_y.
Obviously, to accomplish all the jobs, we need to change the machine’s working mode from time to time, but unfortunately, the machine’s working mode can only be changed by restarting it manually. By changing the sequence of the jobs and assigning each job to a suitable machine, please write a program to minimize the times of restarting machines.

Input
The input file for this program consists of several configurations. The first line of one configuration contains three positive integers: n, m (n, m < 100) and k (k < 1000). The following k lines give the constrains of the k jobs, each line is a triple: i, x, y.
The input will be terminated by a line containing a single zero.

Output
The output should be one integer per line, which means the minimal times of restarting machine.

Sample Input

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

Sample Output

3

题意 桌上有n个球 a球撞击b球时 a球停在b球位置 b球保持a球运动 若b球前面再没有球 b球就会掉下桌子 给你n个球的坐标 你可以多次选择某个撞击方向前面还有球的球撞击 问最后桌上至少还剩多少球 并输出你的撞击过程

可以把x坐标或y坐标相同的点当作是连通的 因为可以通过撞击一个球使另一个球掉下桌面

那么容易发现 一个连通块内的m个球总可以经过m-1次撞击后变成只剩一个球 这个球可以是当前连通块中的任意一个 有多少个连通块最后就最少剩下多少球 然后就可以通过一次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

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int x[N], y[N], vis[N];
int dir[N], p[N], n, m;

void dfs(int i)
{
    vis[i] = 1;
    for(int j = 0; j < n; ++j)
    {
        if(!vis[j] && (x[j] == x[i] || y[j] == y[i]))
        {
            dfs(j);    //j和i属于一个连通块且j还没被访问 对j深搜
            if(x[j] == x[i])  //记录路径 上下左右分别用0，1，2，3表示
                dir[j] = y[j] < y[i] ? 0 : 1;
            else dir[j] = x[j] < x[i] ? 3 : 2;
            p[m++] = j;
        }
    }
}

int main()
{
    while(~scanf("%d", &n))
    {
        for(int i = 0; i < n; ++i)
            scanf("%d%d", &x[i], &y[i]);

        memset(vis, 0, sizeof(vis));
        int cnt = m = 0;
        for(int i = 0; i < n; ++i)
            if(!vis[i]) ++cnt, dfs(i);

        printf("%d\n", cnt);
        char sdir[][10] = {"UP", "DOWN", "LEFT", "RIGHT"};
        for(int i = 0; i < m; ++i)
        {
            int j = p[i];
            printf("(%d, %d) %s\n", x[j], y[j], sdir[dir[j]]);
        }
    }

    return 0;
}
//Last modified :   2015-07-10 08:26

Easy billiards Time Limit:2 Seconds Memory Limit:65536 KB Special Judge

Edward think a game of billiards is too long and boring. So he invented a new game called Easy billiards.

Easy billiards has N balls on a brimless rectangular table in the beginning, and your goal is try to make the number of balls on the table as least as possible by several hit under the following rules:

1: The direction you hit the balls should parallel to the tables border.

2: If ball A crashed into ball B, ball B will moves in the same direction of ball A before the crashing, and ball A will stop in the place of ball B before the crashing.

3: If ball C is moving and there are no balls in front of ball C, it will runs out of the tables border, that means ball C is out of the table.

4: You can choose arbitrary ball on the table to hit, but on a hit, you can’t let the ball you choose to hit runs out of the tables border. In another word, a ball could runs out of the table if and only if it was crashed by another ball in a hitting.

Now, Edward wants to know the least number of balls remained on the table after several hits, and how.

There are multiple test cases. For each test cases, in the first line, there is an integer N, which means the number of the balls on the table. There are following N lines, each line contains two integers Xi and Yi, which means the coordinate of ball I. (0<=N<=2000, 0<=Xi, Yi<=10^8)

Output

For each test cases, you should output the least number of balls on the first line. And you should output several lines to show the order of hits following the first line, each line should contains the coordinate of the ball you choose to hit and the direction you hit. (LEFT,RIGHT,UP,DOWN).

Sample Input

4 0 0 2 0 4 0 2 2 9 1 1 2 1 3 1 1 2 2 2 3 2 1 3 2 3 3 3

Sample output

1 (2, 2) DOWN (4, 0) LEFT (2, 0) LEFT 1 (1, 3) DOWN (1, 2) DOWN (2, 3) DOWN (2, 2) DOWN (3, 3) DOWN (3, 2) DOWN (3, 1) LEFT (2, 1) LEFT