题意 动态查询第K大的数

用小数在前优先队列维护K个数 每要插入一个数时 若这个数小于队首元素那么就不用插入了 否则队首元素出队 这个数入队 每次询问只用输出队首元素就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<cstdio>
#include<queue>
using namespace std;
int main()
{
    int n, a, k;
    char op[5];
    while(~scanf("%d%d", &n, &k))
    {
        priority_queue<int,vector<int>,greater<int> > pq;
        while(n--)
        {
            scanf("%s", op);
            if(op[0] == 'I')
            {
                scanf("%d",&a);
                if(pq.size()<k) pq.push(a);
                else if(a > pq.top()) pq.push(a),pq.pop();
            }
            else printf("%d\n", pq.top());
        }
    }
    return 0;
}

The kth great number

Problem Description

Xiao Ming and Xiao Bao are playing a simple Numbers game. In a round Xiao Ming can choose to write down a number, or ask Xiao Bao what the kth great number is. Because the number written by Xiao Ming is too much, Xiao Bao is feeling giddy. Now, try to help Xiao Bao.
Input

There are several test cases. For each test case, the first line of input contains two positive integer n, k. Then n lines follow. If Xiao Ming choose to write down a number, there will be an “ I” followed by a number that Xiao Ming will write down. If Xiao Ming choose to ask Xiao Bao, there will be a “Q”, then you need to output the kth great number.
Output

The output consists of one integer representing the largest number of islands that all lie on one line.
Sample Input

8 3 I 1 I 2 I 3 Q I 5 Q I 4 Q
Sample Output

1 2 3

HintXiao Ming won’t ask Xiao Bao the kth great number when the number of the written number is smaller than k. (1=<k<=n<=1000000).

题意 中文

动态区间和问题 只会更新点 最基础的树状数组 线段树的应用

树状数组代码

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

#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
int c[N], n, m;

void add(int p, int x)
{
    while(p <= n)
        c[p] += x, p += p & -p;
}

int getSum(int p)
{
    int ret = 0;
    while(p > 0)
        ret += c[p], p -= p & -p;
    return ret;
}

int main()
{
    int u, v, t, cas;
    char op[20];
    scanf("%d", &cas);
    for(int k = 1; k <= cas; ++k)
    {
        printf("Case %d:\n", k);
        scanf("%d", &n);
        memset(c, 0, sizeof(c));
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &t);
            add(i, t);
        }

        while(scanf("%s", op), op[0] != 'E')
        {
            scanf("%d%d", &u, &v);
            if(op[0] == 'Q')
                printf("%d\n", getSum(v) - getSum(u - 1));
            else add(u, op[0] == 'A' ? v : -v);
        }
    }
    return 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

#include <bits/stdc++.h>
#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 = 50005;
int sum[N * 4];

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

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

void update(int p, int s, int e, int a, int b)
{
    if(s == e && e == a)
    {
        sum[p] += b;
        return;
    }
    if( a <= mid) update(lc, a, b);
    else update(rc, a, b);
    pushup(p);
}

int query(int p, int s, int e, int l, int r)
{
    if(s >= l && e <= r) return sum[p];
    if(r <= mid) return query(lc, l, r);
    if(l > mid) return query(rc, l, r);
    return query(lc, l, mid) + query(rc, mid + 1, r);
}

int main()
{
    int cas, n, a, b;
    char c[20];
    scanf("%d", &cas);
    for(int k = 1; k <= cas; ++k)
    {
        printf("Case %d:\n", k);
        scanf("%d", &n);
        build(1, 1, n);
        while(scanf("%s", c), c[0] != 'E')
        {
            scanf("%d%d", &a, &b);
            if(c[0] == 'Q') printf("%d\n", query(1, 1, n, a, b));
            else if(c[0] == 'A') update(1, 1, n, a, b);
            else update(1, 1, n, a, -b);
        }
    }
    return 0;
}

敌兵布阵

Problem Description

C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:”你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说：”我知错了。。。”但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.
Input

第一行一个整数T，表示有T组数据。
每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;
每组数据最多有40000条命令
Output

对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
Sample Input

1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End
Sample Output

Case 1: 6 33 59
Author

Windbreaker

题意 房子里有n个人走进来 编号1~n 每个人走进来时房子里所有空闲的人都会和他招手 空闲的某三个人可以选择一起去打比赛 当然打比赛就变得不空闲了 给你每个人进来时和他招手的人的数量 要求输出一种可能的进房间顺序 没有可能的就输出Impossible

这题放在d就比较简单了 直接贪心就可以 把招手数量为i对应的人都保存到栈s[i]里 第一个进房间的人肯定是s[0]里的 然后让i从0开始 s[i]非空时 让s[i]的栈顶的人进入房间 然后i++ 否则让s[i-1],s[i-2],s[i-3]都出栈一个 再让i=i-3 也就是有3个人去打比赛了 一直这样循环下去直到所有人都进入房间或者i<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

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int q[N], n;
stack<int> s[N];

int main()
{
    int a;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a), s[a].push(i);

    int p = 0, i = 0;
    while(1)
    {
        if(!s[i].empty())  q[p++] = s[i++].top();
        else
        {
            //出栈三个人去打比赛
            if(i < 3) break;
            s[--i].pop(), s[--i].pop(), s[--i].pop();
        }
    }

    if(p == n)
    {
        puts("Possible");
        for(int i = 0; i < n - 1; ++i)
            printf("%d ", q[i]);
        printf("%d\n", q[n - 1]);
    }
    else puts("Impossible");
    return 0;
}
//Last modified :   2015-04-13 01:57

D. Handshakes
On February, 30th n students came in the Center for Training Olympiad Programmers (CTOP) of the Berland State University. They came one by one, one after another. Each of them went in, and before sitting down at his desk, greeted with those who were present in the room by shaking hands. Each of the students who came in stayed in CTOP until the end of the day and never left.

At any time any three students could join together and start participating in a team contest, which lasted until the end of the day. The team did not distract from the contest for a minute, so when another student came in and greeted those who were present, he did not shake hands with the members of the contest writing team. Each team consisted of exactly three students, and each student could not become a member of more than one team. Different teams could start writing contest at different times.

Given how many present people shook the hands of each student, get a possible order in which the students could have come to CTOP. If such an order does not exist, then print that this is impossible.

Please note that some students could work independently until the end of the day, without participating in a team contest.

Input

The first line contains integer n (1 ≤ n ≤ 2·105) — the number of students who came to CTOP. The next line contains n integersa1, a2, …, a**n (0 ≤ a**i < n), where a**i is the number of students with who the i-th student shook hands.
Output

If the sought order of students exists, print in the first line “Possible” and in the second line print the permutation of the students’ numbers defining the order in which the students entered the center. Number i that stands to the left of number j in this permutation means that the i-th student came earlier than the j-th student. If there are multiple answers, print any of them.

If the sought order of students doesn’t exist, in a single line print “Impossible”.

Sample test(s)

input 5 2 1 3 0 1

output Possible 4 5 1 3 2
input 9 0 2 3 4 1 1 0 2 2

output Possible 7 5 2 1 6 8 3 4 9
input 4 0 2 1 1

output Impossible

题意 你在路上走 每秒钟的开始都可以改变自己的速度(改变速度都是瞬间完成的) 知道你开始的速度v1 结束时的速度v2 整个过程所用时间t 以及每秒最多改变的速度d 求这段时间内你最多走了多远

最优的肯定是先把速度从v1升到最大 然后从最大减到v2 使得用的时间不会超多t 因为肯定是足够从v1减为或升到v2的 那么我们只用从两端往中间靠 哪边的速度小 哪边就加上d 知道两边相邻 这样就能保证每次改变的速度都最大 而且最后两端的速度差也不会大于d 也就是最优答案了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int v[N];
int main()
{
    int v1, v2, t, d, k;
    while(~scanf("%d%d%d%d", &v1, &v2, &t, &d))
    {
        v[0] = v1, v[t - 1] = v2;
        int le = 0, ri = t - 1, ans = 0;
        while(le < ri - 1)
        {
            if(v[le] < v[ri]) v[le + 1] = v[le++] + d;
            else v[ri - 1] = v[ri--] + d;
        }
        for(int i = 0; i < t; ++i) ans += v[i];
        printf("%d\n", ans);
    }
    return 0;
}
//Last modified :   2015-04-13 00:27

B. Covered Path

The on-board computer on Polycarp’s car measured that the car speed at the beginning of some section of the path equals v1 meters per second, and in the end it is v2 meters per second. We know that this section of the route took exactly t seconds to pass.

Assuming that at each of the seconds the speed is constant, and between seconds the speed can change at most by d meters per second in absolute value (i.e., the difference in the speed of any two adjacent seconds does not exceed d in absolute value), find the maximum possible length of the path section in meters.
Input

The first line contains two integers v1 and v2 (1 ≤ v1, v2 ≤ 100) — the speeds in meters per second at the beginning of the segment and at the end of the segment, respectively.

The second line contains two integers t (2 ≤ t ≤ 100) — the time when the car moves along the segment in seconds, d (0 ≤ d ≤ 10) — the maximum value of the speed change between adjacent seconds.

It is guaranteed that there is a way to complete the segment so that:

Output

Print the maximum possible length of the path segment in meters.
Sample test(s)

input 5 6 4 2

output 26
input 10 10 10 0

output 100

Note

In the first sample the sequence of speeds of Polycarpus’ car can look as follows: 5, 7, 8, 6. Thus, the total path is 5 + 7 + 8 + 6 = 26meters.

In the second sample, as d = 0, the car covers the whole segment at constant speed v = 10. In t = 10 seconds it covers the distance of 100 meters.

题意 求费波拉契数列第N项 1≤N≤100,000,000

通过矩阵的幂 可以把一维递推的时间复杂度减小到O(logN) 主要就是快速幂的思想

对于m^n 若n=2^a1+2^a2+…+2^ak那么**m^n = m^(2^a1) /****m^(2^a2) / … /*****m^(2^ak)**那么只用看n转换为二进制后哪些位为1就可以快速求出m^n了

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;  
typedef long long LL;  
const int N = 2;  
const LL MOD = 19999997;  
  
//将矩阵a*b的结果放入c  
void matMul(LL a[][N], LL b[][N], LL c[][N])  
{  
    LL ret[N][N] = {0};  
    for(int i = 0; i < N; ++i)  
        for(int j = 0; j < N; ++j)  
            for(int k = 0; k < N; ++k)  
                ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % MOD;  
    memcpy(c, ret, sizeof(ret));  
}  
  
//将a^n放入a  
void matPow(LL a[][N], int n)  
{  
    LL ret[N][N] = {0};  
    for(int i = 0; i < N; ++i) 
        ret[i][i] = 1;  
    while(n)  
    {  
        if(n & 1) matMul(ret, a, ret);  
        matMul(a, a, a);  
        n >>= 1;  
    }  
    memcpy(a,ret,sizeof(ret));
}  
  
int main()  
{  
    int n;  
    while(~scanf("%d", &n))  
    {  
        LL a[N][N] = {0, 1, 1, 1};  
        matPow(a, n);  
        printf("%lld\n", a[1][1] % MOD);  
    }  
    return 0;  
}

时间限制: 10000ms

单点时限: 1000ms
内存限制: 256MB

描述

骨牌，一种古老的玩具。今天我们要研究的是骨牌的覆盖问题：
我们有一个2xN的长条形棋盘，然后用1x2的骨牌去覆盖整个棋盘。对于这个棋盘，一共有多少种不同的覆盖方法呢？
举个例子，对于长度为1到3的棋盘，我们有下面几种覆盖方式：

提示：骨牌覆盖

提示：如何快速计算结果

输入

第1行：1个整数N。表示棋盘长度。1≤N≤100,000,000

输出

第1行：1个整数，表示覆盖方案数 MOD 19999997
样例输入 62247088 样例输出 17748018

题意 给你一个数组求其中逆序对**(i<j&&a[i]>a[j])**的个数

我们来看一个归并排序的过程:
给定的数组为[2, 4, 5, 3, 1]，二分后的数组分别为[2, 4, 5], [1, 3]，假设我们已经完成了子过程，现在进行到该数组的“并”操作：
a: [2, 4, 5] b: [1, 3] result:[1] 选取b数组的1 a: [2, 4, 5] b: [3] result:[1, 2] 选取a数组的2 a: [4, 5] b: [3] result:[1, 2, 3] 选取b数组的3 a: [4, 5] b: [] result:[1, 2, 3, 4] 选取a数组的4 a: [5] b: [] result:[1, 2, 3, 4, 5] 选取a数组的5 在执行[2, 4, 5]和[1, 3]合并的时候我们可以发现，当我们将a数组的元素k放入result数组时，result中存在的b数组的元素一定比k小。
在原数组中，b数组中的元素位置一定在k之后，也就是说k和这些元素均构成了逆序对。
那么在放入a数组中的元素时，我们通过计算result中b数组的元素个数，就可以计算出对于k来说，b数组中满足逆序对的个数。
又因为递归的过程中，a数组中和k满足逆序对的数也计算过。则在该次递归结束时，[2, 4, 5, 3, 1]中所有k的逆序对个数也就都统计了。
同理对于a中其他的元素也同样有这样的性质。

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

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 500005;
int a[N], t[N], n;
long long cnt;

void merge(int l, int m, int r)
{
    int pl = l, pr = m + 1, p = 0;
    while(pl <= m && pr <= r)
    {
        if(a[pl] <= a[pr]) t[p++] = a[pl++];
        else
        {
            t[p++] = a[pr++];
            cnt += m + 1 - pl;
        }
    }
    while(pl<=m) t[p++] = a[pl++];
    while(pr<=r) t[p++] = a[pr++];
    memcpy(a + l, t, sizeof(int)*p);
}

void mergeSort(int l, int r)
{
    if(l >= r) return;
    int	m = (l + r) >> 1;
    mergeSort(l, m);
    mergeSort(m + 1, r);
    merge(l, m, r);
}

int main()
{
    while(scanf("%d", &n), n)
    {
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        cnt = 0;
        mergeSort(0, n - 1);
        printf("%lld\n", cnt);
    }
    return 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 500005;
int a[N], r[N], n;

bool cmp(int i, int j) //离散化排序用的比较函数
{
    return a[i] < a[j];
}

void add(int x, int v)
{
    while(x <= n)
    {
        a[x] += v;
        x += x & -x;
    }
}

int sum(int x)
{
    int ret = 0;
    while(x)
    {
        ret += a[x];
        x -= x & -x;
    }
    return ret;
}

int main()
{
    while(scanf("%d", &n), n)
    {
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]), r[i] = i;
        sort(r + 1, r + n + 1, cmp); //离散化 用数排序后的下标代替数

        long long ans = 0;
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= n; ++i)
        {
            ans += sum(n) - sum(r[i]);
            add(r[i], 1);
        }
        printf("%lld\n", ans);
    }

    return 0;
}

Ultra-QuickSort

Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 – the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

5 9 1 0 5 4 3 1 2 3 0

Sample Output

6 0

题意 有n个m列的转盘 每个转盘的某一列为1或0 你每次可以将某个转盘转动一格 问至少转多少次使得某一列n个转盘上的数都是1

把每个转盘的所有列转为1所需要的最小时间都存起来 可以以某一个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

#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 10005;
int d[M], t[M], n, m;
char g[N][M];

void gett(int r, int c)
{
    int p = (c + 1) % m, cnt = t[c] = 0;
    while(p != c) //顺时针转一圈
    {
        if(g[r][p] == '1') cnt = -1;
        t[p] = ++cnt;
        p = (p + 1) % m;
    }

    p = (p + m - 1) % m, cnt = 0;
    while(p != c) //逆时针转一圈
    {
        if(g[r][p] == '1') cnt = -1;
        if(t[p] > cnt + 1) t[p] = cnt + 1;
        d[p] += t[p], ++cnt;
        p = (p + m - 1) % m;
    }
}

int main()
{
    int i, j;
    while(~scanf("%d%d", &n, &m))
    {
        memset(d, 0, sizeof(d));
        for(i = 0; i < n; ++i) scanf("%s", g[i]);

        for(i = 0; i < n; ++i)
        {
            for(j = 0; j < m; ++j)
                if(g[i][j] == '1') gett(i, j), j = m;
            if(j == m) break;
        }
        sort(d, d + m);
        printf("%d\n", i < n ? -1 : d[0]);
    }
    return 0;
}

C. Shifts
You are given a table consisting of n rows and m columns. Each cell of the table contains a number, 0 or 1. In one move we can choose some row of the table and cyclically shift its values either one cell to the left, or one cell to the right.

To cyclically shift a table row one cell to the right means to move the value of each cell, except for the last one, to the right neighboring cell, and to move the value of the last cell to the first cell. A cyclical shift of a row to the left is performed similarly, but in the other direction. For example, if we cyclically shift a row “00110” one cell to the right, we get a row “00011”, but if we shift a row “00110” one cell to the left, we get a row “01100”.

Determine the minimum number of moves needed to make some table column consist only of numbers 1.

Input

The first line contains two space-separated integers: n (1 ≤ n ≤ 100) — the number of rows in the table and m (1 ≤ m ≤ 104) — the number of columns in the table. Then n lines follow, each of them contains m characters “0” or “1”: the j-th character of the i-th line describes the contents of the cell in the i-th row and in the j-th column of the table.

It is guaranteed that the description of the table contains no other characters besides “0” and “1”.
Output

Print a single number: the minimum number of moves needed to get only numbers 1 in some column of the table. If this is impossible, print -1.

Sample test(s)

input 3 6 101010 000100 100000

output 3
input 2 3 111 000

output -1

题意 求分段函数的最低点 每个点函数值为n个 a/*x^2 + b/*x +c (a>=0, |b|<5000, |c|<5000) 函数的最大值

由于a是不小于0的 所以此分段函数的函数图像只可能是类似’V’形的 可以画图观察出来 那么求最小值就可以用三分来解决了

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

#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
const double eps = 1e-9;
int a[N], b[N], c[N], n;

double getr(double x)
{
    double r = a[0] * x * x + b[0] * x + c[0], t;
    for(int i = 1; i < n; ++i)
    {
        t = a[i] * x * x + b[i] * x + c[i];
        if(t > r) r = t;
    }
    return r;
}

int main()
{
    int cas;
    scanf("%d", &cas);
    while(cas--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d%d%d", &a[i], &b[i], &c[i]);

        double l = 0, r = 1000, m, mm;
        while(l + eps < r)
        {
            m = (l + r) / 2;
            mm = (m + r) / 2;
            if(getr(m) < getr(mm)) r = mm;
            else l = m;
        }
        printf("%.4f\n", getr(l));
    }
    return 0;
}

Error Curves

Problem Description

Josephina is a clever girl and addicted to Machine Learning recently. She
pays much attention to a method called Linear Discriminant Analysis, which
has many interesting properties.
In order to test the algorithm’s efficiency, she collects many datasets.
What’s more, each data is divided into two parts: training data and test
data. She gets the parameters of the model on training data and test the
model on test data. To her surprise, she finds each dataset’s test error curve is just a parabolic curve. A parabolic curve corresponds to a quadratic function. In mathematics, a quadratic function is a polynomial function of the form f(x) = ax2 + bx + c. The quadratic will degrade to linear function if a = 0.
It’s very easy to calculate the minimal error if there is only one test error curve. However, there are several datasets, which means Josephina will obtain many parabolic curves. Josephina wants to get the tuned parameters that make the best performance on all datasets. So she should take all error curves into account, i.e., she has to deal with many quadric functions and make a new error definition to represent the total error. Now, she focuses on the following new function’s minimum which related to multiple quadric functions. The new function F(x) is defined as follows: F(x) = max(Si(x)), i = 1…n. The domain of x is [0, 1000]. Si(x) is a quadric function. Josephina wonders the minimum of F(x). Unfortunately, it’s too hard for her to solve this problem. As a super programmer, can you help her?
Input

The input contains multiple test cases. The first line is the number of cases T (T < 100). Each case begins with a number n (n ≤ 10000). Following n lines, each line contains three integers a (0 ≤ a ≤ 100), b (|b| ≤ 5000), c (|c| ≤ 5000), which mean the corresponding coefficients of a quadratic function.
Output

For each test case, output the answer in a line. Round to 4 digits after the decimal point.
Sample Input

2 1 2 0 0 2 2 0 0 2 -4 2
Sample Output

0.0000 0.5000

题意 在n/*m个格子组成的草地上 你可以选择两个是草(‘/#’)的格子点燃 每个点燃的格子在下一秒其四个相邻的是草的格子也会被点燃 问点燃所有的草至少需要多少秒

DFS和BFS的综合 如果’/#‘连通块的数量大于2个是肯定不能点燃所有的 先dfs判断连通块个数 再bfs找出选哪两个格子可以最快把草烧完

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 <map>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 12;
int x[] = {0, 0, -1, 1};
int y[] = { -1, 1, 0, 0};
char g[N][N] , v[N][N];
int  n, m, nu, cnt, ret;
pair<int, int> q[N * N], p[N * N];

void dfs(int r, int c)
{
    if(g[r][c] != '#') return;
    p[nu++] = make_pair(r, c), g[r][c] = cnt;
    for(int i = 0; i < 4; ++i)
        if(r + x[i] >= 0 && c + y[i] >= 0)
            dfs(r + x[i], c + y[i]);
}

void bfs(int r, int c, int cr, int cc)
{
    int le = 0, ri = 0;
    q[ri++] = make_pair(r, c);
    q[ri++] = make_pair(cr, cc);
    memset(v, 0, sizeof(v)), v[r][c] = v[cr][cc] = 1;
    while(le < ri)
    {
        cr = q[le].first, cc = q[le++].second, ret = v[cr][cc];
        for(int i = 0; i < 4; ++i)
        {
            r = cr + x[i], c = cc + y[i];
            if (r >= 0 && r < n && c >= 0 && c < m && g[r][c] != '.' && !v[r][c])
                q[ri++] = make_pair(r, c), v[r][c] = v[cr][cc] + 1;
        }
    }
}

int main()
{
    int cas, ans, r1, c1, r2, c2;
    scanf("%d", &cas);
    for(int k = 1; k <= cas; ++k)
    {
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; ++i)
            scanf("%s", g[i]);
        printf("Case %d: ", k);

        nu = cnt = ans = 0;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                if(g[i][j] == '#') ++cnt, dfs(i, j);

        if(cnt < 3)
        {
            ans = n * m;
            for(int i = 0; i < nu; ++i)
                for(int j = 0; j < nu; ++j)
                {
                    r1 = p[i].first, c1 = p[i].second;
                    r2 = p[j].first, c2 = p[j].second;
                    if(cnt == 2 && g[r1][c1] == g[r2][c2]) continue;
                    bfs(r1, c1, r2, c2);
                    if(ret < ans) ans = ret;
                }
        }
        printf("%d\n", ans - 1);
    }
    return 0;
}

Problem 2150 Fire Game

Problem Description

Fat brother and Maze are playing a kind of special (hentai) game on an N/*M board (N rows, M columns). At the beginning, each grid of this board is consisting of grass or just empty and then they start to fire all the grass. Firstly they choose two grids which are consisting of grass and set fire. As we all know, the fire can spread among the grass. If the grid (x, y) is firing at time t, the grid which is adjacent to this grid will fire at time t+1 which refers to the grid (x+1, y), (x-1, y), (x, y+1), (x, y-1). This process ends when no new grid get fire. If then all the grid which are consisting of grass is get fired, Fat brother and Maze will stand in the middle of the grid and playing a MORE special (hentai) game. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.)

You can assume that the grass in the board would never burn out and the empty grid would never get fire.

Note that the two grids they choose can be the same.

Input

The first line of the date is an integer T, which is the number of the text cases.

Then T cases follow, each case contains two integers N and M indicate the size of the board. Then goes N line, each line with M character shows the board. “/#” Indicates the grass. You can assume that there is at least one grid which is consisting of grass in the board.

1 <= T <=100, 1 <= n <=10, 1 <= m <=10

Output

For each case, output the case number first, if they can play the MORE special (hentai) game (fire all the grass), output the minimal time they need to wait after they set fire, otherwise just output -1. See the sample input and output for more details.

Sample Input

4

3 3
./#.

/#/#/#
./#.

3 3
./#.

/#./#
./#.

3 3
…

/#./#
…

3 3
/#/#/#

../#
/#./#

Sample Output

Case 1: 1

Case 2: -1
Case 3: 0

Case 4: 2

题意 n/*m的迷宫中有一些着火点 每个着火点上下左右相邻的非墙点下一秒也将成为一个着火点 Joe每秒能向相邻的点移动一步 给你所有着火点的位置和Joe的位置 问Joe逃离这个迷宫所需的最小时间

可以先一遍bfs把每个点的最早着火时间存起来 只有Joe到达该点的时间小于这个时间Joe才能走这个点 只需要对Joe所在的点为起点再来一次bfs就行了 需要注意的是开始可能有多个着火点 我开始以为只有一个着火点被坑了好久

v[i][j]第一遍bfs记录点i,j的最早着火时间 第二遍bfs记录Joe到达该点的时间

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 <bits/stdc++.h>
using namespace std;
const int N = 1005;
int x[] = {0, 0, -1, 1};
int y[] = { -1, 1, 0, 0};
int v[N][N], n, m, ans, le, ri;
pair<int, int> q[N * N];
char g[N][N];

void bfs()
{
    int cr, cc, r, c;
    while(le < ri)
    {
        cr = q[le].first, cc = q[le++].second;
        for(int i = 0; i < 4; ++i)
        {
            r = cr + x[i], c = cc + y[i];
            if(r < 0 || r >= n || c < 0 || c >= m)
                ans = ans ? ans : v[cr][cc];
            else if(g[r][c] == '.' && (!v[r][c] || v[cr][cc] + 1 < v[r][c]))
                v[r][c] = v[cr][cc] + 1, q[ri++] = make_pair(r, c);
        }
    }
}

int main()
{
    int cas, jr, jc;
    scanf("%d", &cas);
    while(cas--)
    {
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; ++i)
            scanf("%s", g[i]);

        memset(v, 0, sizeof(v));
        le = ri = 0;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                if(g[i][j] == 'F')
                    q[ri++] = make_pair(i, j), v[i][j] = 1;
                else if(g[i][j] == 'J') jr = i, jc = j;
        bfs();
        le = ri = ans = 0, v[jr][jc] = 1;
        q[ri++] = make_pair(jr, jc);
        bfs();
        if(ans) printf("%d\n", ans);
        else puts("IMPOSSIBLE");
    }
    return 0;
}

题目链接 http://uva.onlinejudge.org/external/116/11624.pdf