只做出了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) HNCPC 2014" 是对标题的补充,再次强调了这是2014年湖南计算机程序设计竞赛(可能的缩写为HNCPC,即 Hunan National Collegiate Programming Contest)...
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 增加...
| <a href="http://www.82340777.com/contactus.asp">联络我们</a> | <a href="http://www.82340777.com/hr.asp">人才招聘</a></div><div class="copyright">版权所有©2013 Rujia Co.,Ltd All Rights Reserved....
自述 此自述文件通常会记录启动和运行应用程序所需的任何步骤。 您可能想要涵盖的内容: Ruby版 系统依赖 配置 数据库创建 数据库初始化 如何运行测试套件 服务(作业队列、缓存服务器、搜索引擎等) ...
这是Su Jiya,Feng Zhang,Weifeng Liu,Bingsheng He,Ruuoan Wu,Du Xiaoyong Du,Wang Rujia Wang于2020年发表的题为“ CapelliniSpTRSV:GPU上无线程级同步的稀疏三角求解”的论文的源代码。 有两个版本,即...
3. **Kongzi Rujia Wenhua(孔子儒家文化)**:孔子是中国古代伟大的哲学家和教育家,儒家学派的创始人,其思想对中国文化影响深远。儒家文化强调道德修养、仁爱和谐,是中华文化的核心之一。 4. **Liyi(礼仪)**...
本源码是采用住哪API程序、连锁酒店单品牌版本,只有如家酒店单品牌预订功能,代码更简练,维护更容易,更适用于地方站长用于做品牌类酒店预订的站长们,占用空间不到100M,也就是说只要你有空间,支持asp和access,...
“Kongzi Rujia Wenhua”(孔子儒家文化)涵盖了教育、伦理、政治等多个方面,其核心是人与人之间的和谐关系以及个人的道德修养。儒家主张通过自我教育和实践,提升个人品德,以达到社会的和谐稳定。孔子的教育理念...