`

Rujia Liu's Present 3: A datastructure contest celebrating the 100th anniversary

J# 
阅读更多

只做出了2题,其中一道还是STL水过的。

 

A题,并查集(类似08年杭州区域赛的并查集,考虑用用删点的思路把一个点添加到另一个集合,不用合并层优化,否则超时,坑死我了,我考虑了半天优化。。。)。

 

贴代码

#include <iostream>
#include <stdio.h>

#define N 200001
typedef struct {
    int fa;
    int cnt;
    unsigned long long sum;
	
}node_t;

node_t a[N];
int n;
int id[N];
int gn;
int father(int x)
{ 
    int i = id[x];
    while(a[i].fa != i )
     {
        i  = a[i].fa;
    }
    return i;
}

void merge(int x, int y, int xx, int yy)
{ 
	int t;
    if (a[x].cnt < a[y].cnt)
     {
        //int i = id[xx];
        //while( a[i].fa != i )
        //{
          //  a[i].fa = y;
        //}
        a[x].fa = y;

        a[y].sum += a[x].sum;
		a[y].cnt += a[x].cnt;
    }
    else
     {
        //int i = id[yy];
        //while( a[i].fa != i )
        //    a[i].fa = x;
        a[y].fa = x;
        a[x].sum += a[y].sum;
        a[x].cnt += a[y].cnt;
    }    
    
}

void add(int x, int y, int x1)
{
   a[x].cnt -= 1;
   a[x].sum -= x1;
   a[gn].fa = y;  
   id[x1] = gn++;
   a[y].sum += x1;
   a[y].cnt += 1;
}  
int total(int y)
{
    return a[id[y]].sum;
} 
int main()
{
    int q;
    int sno;
    int i;
    int x, y;
    while(scanf("%d%d", &n, &q) != EOF )
    {
        gn = n+1;
        for ( i = 1; i <= n; ++i )
        { 
			id[i] = i;
            a[i].fa = i;
		   	a[i].sum = i;
			a[i].cnt = 1;
        }
        for ( i = 0; i < q; ++i )
        { 
            scanf("%d", &sno);
            int x1, x2;
            int id;
            switch(sno)
            {
                case 1:// merge two set
                        scanf("%d%d", &x1, &x2);
                        x = father(x1);
                        y = father(x2); 
                        if ( x != y)
                            merge(x, y, x1, x2);
                        break;
                case 2: // merge p to q set
                        scanf("%d%d", &x1, &x2);
                        x= father(x1);
                        y = father(x2);
                        if ( x != y )
                         add(x,y, x1);
                        break;
                case 3:
                        scanf("%d", &x1);
                        id = father(x1);
                        printf("%d %llu\n", a[id].cnt, a[id].sum );
                       break;
           }
        }
    }

    return 0;
}
 

E题,说是给出10万个数,10万个询问,问第k个数字在序列的位置。

测试数据小于500k,也就是大概3万多个数字和询问。(我测10万,10万的数据是1.6M,所以猜测)

开始考虑用链表+数目标记---》果断超时

  然后用快排+扫描--》果断WA,思索半天,用自己写的测试数据找到了错误,快排不是稳定排序啊,位置交换了。。。

最后快要撤了,想到用STL,map<string, int>,string存关键字:"k_num"用下划线将第k个num转换成一个字符串,键值int存位置。所以查询只要构造相应字符串查询就行了。最后0.9S+险过。。

 

#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <hash_map>
#include <string>
#include <map>
using namespace std;

map <string, int> hmap;
int id[1000001];
int main()
{
    int n, q;
    int x, i, t,j;
	int gn;
	char buf[20];
	string tmp;
    while(scanf("%d%d", &n , &q) != EOF)
    {
		hmap.clear();
		memset(id,0,sizeof(id));
        for ( i = 1; i <= n; ++i )
        {
            scanf("%d", &x);

				++id[x];
				sprintf(buf, "%d_%d", id[x], x);
				tmp = buf;
				hmap[tmp] = i; 
        }

        for ( i = 0;i < q; ++i )
        {
            scanf("%d%d", &t, &x);
			sprintf(buf, "%d_%d", t, x);
			tmp = buf;
			if ( hmap[tmp] )		
				printf("%d\n", hmap[tmp]);
			else
				printf("0\n");	
        }
    }

    return 0;
}
 

 

 

 

分享到:
评论

相关推荐

    2014年湖南省第十届程序设计竞赛题目数据标程(by Rujia Liu)

    "2014年湖南省第十届程序设计竞赛题目数据标程(by Rujia Liu) HNCPC 2014" 是对标题的补充,再次强调了这是2014年湖南计算机程序设计竞赛(可能的缩写为HNCPC,即 Hunan National Collegiate Programming Contest)...

    UVa1318/LA2797 Monster Trap 《训练指南》习题源码

    UVa1318/LA2797 Monster Trap 《训练指南》代码仓库上Rujia Liu的源代码

    算法竞赛入门经典--训练指南,代码仓库最新版

    所有代码均通过了UVa/La的测试,但不能保证程序是正确的(比如数据可能不够强),有疑问请致信rujia.liu@gmail.com,或在googlecode中提出: http://code.google.com/p/aoapc-book/ [最新更新] 2013-04-23 增加...

    算法竞赛入门经典--训练指南,代码仓库

    所有代码均通过了UVa/La的测试,但不能保证程序是正确的(比如数据可能不够强),有疑问请致信rujia.liu@gmail.com,或在googlecode中提出: http://code.google.com/p/aoapc-book/ [最新更新] 2013-04-23 增加...

    wayos认证页面

    | &lt;a href="http://www.82340777.com/contactus.asp"&gt;联络我们&lt;/a&gt; | &lt;a href="http://www.82340777.com/hr.asp"&gt;人才招聘&lt;/a&gt;&lt;/div&gt;&lt;div class="copyright"&gt;版权所有©2013 Rujia Co.,Ltd All Rights Reserved....

    rujia-register

    自述 此自述文件通常会记录启动和运行应用程序所需的任何步骤。 您可能想要涵盖的内容: Ruby版 系统依赖 配置 数据库创建 数据库初始化 如何运行测试套件 服务(作业队列、缓存服务器、搜索引擎等) ...

    CapelliniSpTRSV:GPU上的无线程级同步的稀疏三角求解

    这是Su Jiya,Feng Zhang,Weifeng Liu,Bingsheng He,Ruuoan Wu,Du Xiaoyong Du,Wang Rujia Wang于2020年发表的题为“ CapelliniSpTRSV:GPU上无线程级同步的稀疏三角求解”的论文的源代码。 有两个版本,即...

    中国元素长城水墨画背景PPT模板.ppt

    3. **Kongzi Rujia Wenhua(孔子儒家文化)**:孔子是中国古代伟大的哲学家和教育家,儒家学派的创始人,其思想对中国文化影响深远。儒家文化强调道德修养、仁爱和谐,是中华文化的核心之一。 4. **Liyi(礼仪)**...

    如家酒店源码 v1.0

    本源码是采用住哪API程序、连锁酒店单品牌版本,只有如家酒店单品牌预订功能,代码更简练,维护更容易,更适用于地方站长用于做品牌类酒店预订的站长们,占用空间不到100M,也就是说只要你有空间,支持asp和access,...

    (2021-2022年)专题资料完美版中华经典.pptx

    “Kongzi Rujia Wenhua”(孔子儒家文化)涵盖了教育、伦理、政治等多个方面,其核心是人与人之间的和谐关系以及个人的道德修养。儒家主张通过自我教育和实践,提升个人品德,以达到社会的和谐稳定。孔子的教育理念...

Global site tag (gtag.js) - Google Analytics