复苏–堆排序

#include<stdio.h>
int p[123];
void swap(int l,int r)
{
    int t = p[l];
    p[l] = p[r];
    p[r] = t;
}
void sort(int left, int right, int p[]);
int main()
{
    int i, k, n, m;
    scanf("%d %d", &n, &m);
    for(i = 0; i< n; i++){
        scanf("%d", &k);
        if(i < m){
            p[i] = k;
        }
        else{
            int j, num = 0;
            for(j = 1; j < m; j++){
                if(p[num] > p[j])
                    num = j;
            }
            if(p[num] < k)
                p[num] = k;
        }
    }
    sort(0, m - 1, p);
    printf("%d", p[0]);
    for(i = 1; i < m; i++)
        printf(" %d", p[i]);
    printf("\n");
    return 0;
}
void sort(int left, int right, int p[])
{
    if(left >= right)
        return;
    int i, j;
    i = left, j = right;
    int k = p[left];
    while(i < j){
        while(i < j&&p[j] <= k)
            j--;
//        p[i] = p[j];
        while(i < j&&p[i] >= k)
            i++;
  //      p[j] = p[i];
       if(i<j)swap(i,i);
    }
    //p[i] = k;
    swap(i,left);
    sort(left, i - 1, p);
    sort(i + 1, right, p);
}
#include <stdio.h>   //头文件只有一个防超时

int h[1000002];//用来存放堆的数组
int m;     //堆的大小

//交换函数,用来交换堆中的两个元素的值
void Swap(int x, int y)
{
    int t;
    t = h[x];
    h[x] = h[y];
    h[y] = t;
}

//向下调整函数
void Siftdown(int i)  //传入一个需要向下调整的节点的编号i,这里传入1,即
//从堆顶开始向下调整;
{
    int t, flag=0;   //flag用来标记是否需要继续向下调整
    //当i结点有孩子(其实是至少有左孩子)并且有需要继续调整的时候循环就执行
    while(i*2 <= m && flag == 0)
    {
        //首先判断它和左孩子的关系,并用t记录值较小的结点的编号
        if(h[i] > h[i*2])
            t = i*2;
        else
            t = i;
        //如果它有右孩子,再对右孩子进行讨论
        if(i*2+1 <= m)
        {
            //假如右孩子的值更小,更新较小的节点编号
            if(h[t] > h[i*2+1])
                t = i*2+1;
        }
        //如果发现最小的结点编号不是自己,说明子节点中有比父节点更小的
        if(t != i)
        {
            Swap(t, i);   //交换他们
            i = t;        //更新i为刚才与它交换的孩子结点的编号,便于接下来继续向下调整
        }
        else
            flag = 1;     //否则说明当前的父节点已经比两个子节点都要小了,不需要再进行调整了
    }
}

void heapsort()     //堆排序
{
    while(m > 1)
    {
        Swap(m, 1);
        m--;
        Siftdown(m);
    }
}

int main()
{
    int num, n, i, j;
    scanf("%d%d", &num, &m);
    for(i = 1; i <= m; i++)
        scanf("%d", &h[i]);
    n = m;
    for(i = m/2; i >= 1; i--)    //建m个元素的最小堆
        Siftdown(i);
    for(i = m+1; i <= num; i++)  //然后从第m+1个元素开始,与堆顶元素比较,
        //如果比堆顶的元素小,那这个数就不要了,
    {
        int x;
        scanf("%d", &x);
        if(x > h[1])
        {
            //如果比堆顶的元素大,那就舍弃当前堆顶而
            //将这个数作为新的堆顶,并维护最小堆的性质
            h[1] = x;
            for(j = m/2; j >= 1; j--)//可以改进把此行删除
                Siftdown(j);
        }
    }
    heapsort();              //堆排序
    for(i = 1; i <= n; i++)
        if(i != n)
            printf("%d ", h[i]);
        else
            printf("%d\n", h[i]);
    return 0;
}
/*求前k个最大的数则建立k个数的最小堆

求前k个最小的数则建立k个数的最大堆

算法描述:我们首先取这N个元素中的前K个元素来建立一个由K个元素组成的小(大)顶堆,这样堆顶元素便是当前已读取元素中的第K大(小)者;然后,依次读取剩下的N-K个元素,而对于其中的每个元素x,若x大于(小于)当前的堆顶元素,则将堆顶元素替换为x,并自堆顶至向下调整堆;这样,在读取完所有元素后,堆中的K个元素即为这N个数中的前K个最大(小)元素,同时堆顶元素为这N个数中的第K大(小)元素。*/


/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 192ms
Take Memory: 104KB
Submit time: 2017-02-23 19:12:43
****************************************************/

ec – final 相关博文

http://unsmilecat.cn/2017/08/28/google-kickstart-round-e-problem-b-trapezoid-counting/
http://blog.csdn.net/qq_25716653/article/details/78220464?locationNum=5&fps=1
http://www.calvinneo.com/2017/11/06/Kickstart2017E/#more
梯形(trapezoid)是有且仅有一条平行边的凸(convex)四边形(quadrilateral),等腰(isosceles)梯形是两非平行边长相等的梯形。有一堆木条,要求从中选4个拼成一个等腰梯形,问有多少组方案。注意长度相等的两根木条仍然被认为是不同的木条。
很straightforward的题目了,首先梯形成立条件是短三边和大于最长边。然后讨论三种情况2i+1j1k2i+1j1k、2i+2j2i+2j(不可行由于是矩形)、3i+j3i+j。小数据挂了一发,因为3i+j3i+j没有判断梯形成立条件。
AC代码
后来看别人的题解发现其实O(n3)O(n3)是可以被卡掉的(Google还是比较仁慈的,毕竟不是ACM)。

#include <iostream> 
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <functional>
#include "stdlib.h" 
#include "time.h"
#include <set>
#include <map>
#include <numeric>
#include <cctype>
#include <cmath>

#define INF 0x3f3f3f3f
const int MAXN = 5050;
using namespace std;
#define LL long long
#define ULL unsigned long long
#define LD long double
typedef pair<int, int> pii;

int T, cas = 0;
int n;

LL arr[MAXN];
LL aa[MAXN];
LL cc[MAXN];

int main() {
    freopen("1.in", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        cas++;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            scanf("%lld", &arr[i]);
        }
        LL ans = 0;
        sort(arr, arr + n);
        LL prev = arr[0] - 1;
        LL c = 0;
        LL dn = -1;
        memset(aa, 0, sizeof aa);
        memset(cc, 0, sizeof cc);
        for (int i = 0; i < n; i++)
        {
            if (arr[i] != prev)
            {
                dn++;
                aa[dn] = arr[i];
                cc[dn] = 1;
                prev = arr[i];
            }
            else {
                cc[dn]++;
            }
        }
        dn++;
        for (int i = 0; i < dn; i++)
        {
            if (cc[i] < 2)
            {
                continue;
            }
            LL temp_ans = 0;
            for (int j = 0; j < dn; j++)
            {
                // 2i + 1j1k
                for (int k = j + 1; k < dn; k++)
                {
                    if (i != j && i != k && aa[j] + 2 * aa[i] > aa[k])
                    {
                        temp_ans += (cc[j] * cc[k]);
                    }
                }
            }
            // 2i + 2j is RECT!!
            LL mult = (cc[i] * (cc[i] - 1) / 2);
            temp_ans *= mult;
            ans += temp_ans;

            temp_ans = 0;
            if (cc[i] >= 3)
            {
                // 3i + 1j
                for (int j = 0; j < dn; j++)
                {
                    if (i != j && (3 * aa[i] > aa[j])) // must satisfy 3 * aa[i] > aa[j] here
                    {
                        ans += (cc[j] * (cc[i] * (cc[i] - 1) * (cc[i] - 2)) / 6);
                    }
                }
            }
        }
        printf("Case #%d: %lld\n", cas, ans);
    }

    return 0;
}

https://www.cnblogs.com/wttttt/p/6823831.html
https://codejam.withgoogle.com/codejam/contest/12234486/dashboard#s=a&a=1
https://zhuanlan.zhihu.com/p/28829564

Google Kickstart Round E Problem B. Trapezoid Counting


https://codejam.withgoogle.com/codejam/
http://blog.csdn.net/cl22333/article/details/5649132
http://www.cnblogs.com/wttttt/tag/%E7%AE%97%E6%B3%95/
http://blog.csdn.net/cy_93/article/details/23559909
https://www.zhihu.com/question/19964171
https://www.cnblogs.com/mj-liylho/p/6422283.html

梯形计数:分析

小数据集

最多只有50根棍棒,这意味着我们可以直接枚举所有不同的四根棍棒。

对于形成等腰梯形四条边的一组支杆,必须满足以下所有条件:

必须有一对长度相等的棍棒。调用这个长度C.
剩下的两根棍子长度不一样。把这些长度A中较短的一个和较长的一个称为B.
四根棍子必须能够实际连接形成一个等腰梯形,所以我们需要服从三角形不等式的等腰梯形:B <A + 2×C
那么我们只需要计算有多少个不同的四根棍棒符合这些条件。
大数据集

首先,我们可以创建一个包含所有唯一长度值的Length数组,以及一个包含每个值的Count数组。例如,对于长度为[3,4,1,4,2,6,3,1,3]的棒,我们将得到长度数组[1,2,3,4,6]和Count数组[2 ,1,3,2,1]。

考虑上面的不等式:B <A + 2×C有两种可能的情况可以形成有效的等腰梯形:

A等于C或B等于C.
A,B和C都是不同的值。(回想一下,我们不能有A等于B,否则形状不符合等腰梯形的问题定义。)
对于第一种情况,我们考虑所有可能的值C =长度[i],使得Count [i]≥3.对于每个这些,我们必须计算多少条长度小于3×C但不等于C.我们可以通过使用Count数组的前缀和(我们只需要创建一次)来快速完成此操作。然后我们加上这个数字,乘以(Count [i]选择3)到我们的答案。

对于第二种情况,我们考虑所有可能的值C = Length [i]使得Count [i]≥2.对于每个这些,我们考虑所有A = Length [j](其中i≠j)。对于这些(C,A)对中的每一对,我们需要计算有多少枝具有长度B,使得B≠C,A <B和B <A + 2×C。有效B的数目是计数到A + 2×C,减去计数直到A的前缀总和,如果在该范围内,可能减去C的计数。然后我们加上这个数字,乘以(Count [i]选择2)到我们的答案。

这种方法避免了双重计数的任何集合,它运行在O(Ñ 2)的时间,这是很容易足够快Ñ ≤5000。

#include <bits/stdc++.h>
using namespace std;
const int N = 202, inf = 1e8;
int main() {
time_t startt = clock();
int tt;
scanf(“%d”, &tt);
for (int tc = 1; tc <= tt; tc++) {
int n;
scanf(“%d”, &n);
map cnt;
long long ans = 0;
for (int i = 0; i < n; i++) {
long long l;
scanf(“%lld”, &l);
cnt[l]++;
}
for (auto it = cnt.begin(); it != cnt.end(); it++) {
if (it->second < 2) continue;
long long now = it->first;
long long mul = 1LL * it->second * (it->second – 1)/2, ccnt = 0;
long long mul3 = mul * (it->second – 2)/3;
for (map::iterator cur = cnt.begin(), last = cnt.begin(); cur != cnt.end(); cur++) {
if (cur->first == now) continue;
while (last != cur && (cur->first-last->first) >= now * 2) {
if (last->first != now)
ccnt -= last->second;
last++;
}
if (abs(cur->first-now) < now * 2)
ans += 1LL * mul3 * cur->second;
ans += 1LL * ccnt * mul * cur->second;
ccnt += cur->second;
}
}
printf(“Case #%d: %lld\n”, tc, ans);
cerr << “~ #” << tc << ” done! time : ” << (double)(clock()-startt) * 1000/CLOCKS_PER_SEC << ” ms” << endl;
}
return 0;
}

The 2016 ACM-ICPC Asia China-Final Contest

源地址

Problem H. Great Cells

Input file: Standard Input
Output file: Standard Ouptut
Time limit: 2 seconds

Mr. Panda likes playing puzzles with grid paper. Recently he invented a new rule to play with
the grid paper.

At the beginning, he grabs a grid paper with N rows and M columns. Then he fills each cell an
integer in the range of [1, K]. After filling all the cells, he starts finding Great cells in the grid. A
cell is called Great cell if and only if it meets the following 2 conditions:

• The value in the cell is strictly larger than other cells in the same row.
• The value in the cell is strictly larger than other cells in the same column.
Now Mr. Panda is wondering how many different ways he can fill the grid paper so that there are
exactly g Great cells.
As Mr. Panda likes simple conclusion number, let’s just tell him the value
∑NM
g=0
(g + 1) · Ag mod (109 + 7)
Ag represents the number of different ways Mr. Panda can fill the grid paper such that there are
exactly g Great cells.

Input
The first line of the input gives the number of test cases, T. T lines follow.
Each line represents a test case containing 3 integers N, M representing the number of rows and
columns of the grid paper, K representing the range for filling numbers.

Output
For each test case, first output one line containing “Case #x: y”, where x is the test case number
(starting from 1), y is the simple conclusion number for Mr. Panda.

Limits
• 1 ≤ T ≤ 20.
• 1 ≤ N, M, K ≤ 200.

Sample input and output

3
2 2 2
2 3 2
3 4 5

Sample Input Sample Output
Case #1: 24
Case #2: 88
Case #3: 487890625
Note
For the first sample, A0 = 10, A1 = 4, A2 = 2, A3 = A4 = 0, thus the answer is 10+4×2+2×3 = 24.

code:

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int mod = 1000000007;

inline int QuickPow(int x, int r)
{
    int ret = 1;
    for (; r; r >>= 1)
    {
        if (r & 1) ret = (LL)ret * x % mod;
        x = (LL)x * x % mod;
    }
    return ret;
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int kase = 1; kase <= T; ++kase)
    {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        int mult = QuickPow(k, (n - 1) * (m - 1)), ans = 0;
        for (int i = 1; i <= k; ++i)
            ans = (ans + (LL)QuickPow(i - 1, n + m - 2) * mult) % mod;
        ans = (LL)ans * (n * m) % mod;
        ans = (ans + QuickPow(k, n * m)) % mod;
        printf("Case #%d: %d\n", kase, ans);
    }
    return 0;
}

2017icpc-final 比赛前组队赛 2016china-final

Problem D. Ice Cream Tower(2016 China-Final)【二分答案+贪心检验】
题意:这是2016 ACM-ICPC China-Final的D题,一共有N个冰淇淋球,做一个冰淇淋需要K个球,并且由于稳定性,这K个球还必须满足上下相邻的下面比上面大至少两倍。先给出N个球的质量,问最多能做出多少个冰淇淋?
思路:最开始以为就是简单的贪心,但是发现貌似不对,后来在现场题目讲解时才知道要用二分答案的方法,也就是对可以做多少个冰淇淋m做二分,每次检验是否能做出m个冰淇淋。
检验标准是:首先对B[]排序后将前m个取出来作为m个冰淇淋的顶端,也就是A[]的前m个=B[]的前m个,之后选A[i]时,贪心地去找满足B[p]>2×A[i-m]的B[p]作为A[i],这样p最多就只跑一遍(线性),如果能构成表示检验返回结果成功,反之返回结果失败。

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

LL b[300005],a[300005];  
int t,T,n,k;  

int judge(int m) //检验m个冰淇淋能否做出来  
{  
    for(int i=0;i<m;i++)  
        a[i]=b[i];  
    int p=m;  
    for(int i=m;i<m*k;i++)  
    {  
        while(b[p]<a[i-m]*2 && p<n) p++;  
        if(p==n) return 0;  
        a[i]=b[p];  
        p++;  
    }  
    return 1;  
}  

int Bisection(int l,int r)  //二分答案  
{  
    while(l<r)  
    {  
        int mid=(l+r+1)/2;  
        if(judge(mid)) l=mid;  
        else r=mid-1;  
    }  
    return l;  
}  
int main()  
{  
    scanf("%d",&T);  
    for(t=1;t<=T;t++)  
    {  
        scanf("%d%d",&n,&k);  
        for(int i=0;i<n;i++) scanf("%lld",&b[i]);  
        sort(b,b+n);  
        printf("Case #%d: %d\n",t,Bisection(0,n/k));  
    }  
    return 0;  
}