15年-ICPC长春-网络赛
2024-08-24 16:36:50
ID | name | status | one word |
POJ 5437 | Alisha’s Party | 赛后AC、 | 优先队列,模拟。对时间t排序 |
POJ 5438 | Ponds | 赛后AC | 循环链表 |
POJ 5439 | Aggregated Counting | ||
POJ 5440 | Clock Adjusting | ||
POJ 5441 | Travel | 赛后AC | 并查集+离线化。注音可以休息、 |
POJ 5442 | Favorite Donut | ||
POJ 5443 | The Water Problem | 题如其名,水题。 | ..........就是水。 |
POJ 5444 | Elven Postman | 赛后AC | 二叉树建和遍历。 |
POJ 5445 | Food Problem | ||
POJ 5446 | Unknown Treasure | ||
POJ 5447 | Good Numbers | ||
POJ 5448 | Marisa’s Cake | ||
POJ 5449 | Robot Dog |
很多题就是想不到思路。其实是可以做的。第一场只过了1道。。。。。。。。。人艰不拆。。。。。。
poj 5437
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std; struct Node {
char name[];
int val;
int t;
bool operator < (const Node &a) const {
if (a.val != val)
return a.val > val;
else return a.t < t;
}
}node[]; struct Open {
int t, per;
}open[]; bool cmp(Open a, Open b) {
return a.t < b.t;
} Node rem[];
priority_queue<Node>que; int main() {
int k, m, q;
int t;
scanf("%d", &t);
while (t--) {
memset(open, , sizeof(open));
memset(rem, , sizeof(rem));
scanf("%d%d%d", &k, &m, &q);
for (int i=; i<k; ++i) {
scanf("%s%d", node[i].name, &node[i].val);
node[i].t = i;
} for (int i=; i<m; ++i) {
scanf("%d%d", &open[i].t, &open[i].per);
}
while (!que.empty()) {
que.pop();
}
sort(open, open+m, cmp); int cnt = ;
int t = ;
for (int i=; i<m; ++i) {
if (t < open[i].t) {
for (int j=t; j < open[i].t; ++j) {
que.push(node[j]);
}
t = open[i].t;
}
int num = ;
while(num < open[i].per && !que.empty() && cnt < k) {
rem[cnt++] = que.top();
num++;
que.pop();
}
} if (open[m-].t < k) {
for (int i=open[m-].t; i<k; ++i) {
que.push(node[i]);
}
} while(!que.empty() && cnt < k) {
rem[cnt++] = que.top();
que.pop();
} int a;
for (int i=; i<q; ++i) {
scanf("%d", &a);
if (i == )
printf("%s", rem[a-].name);
else printf(" %s", rem[a-].name);
}
printf("\n");
}
return ;
}
poj 5438
#include <queue>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std; #define maxn 100000+50 // 边的个数
#define maxm 10000+50 // 节点个数
int t, p, m, a, b; int val[maxm];
int head[maxm];
int deg[maxm];
bool vis[maxm];
long long ans, temp;
int num; struct Edge {
int v, next;
}edge[maxn]; int totEdge;
queue<int>que; void addEdge(int a, int b) {
edge[totEdge].v = b;
edge[totEdge].next = head[a];
head[a] = totEdge++;
} void init() {
memset(head, -, sizeof(head));
memset(edge, , sizeof(edge));
memset(val, , sizeof(val));
memset(vis, , sizeof(vis));
memset(deg, , sizeof(deg));
totEdge = ;
ans = ;
while(!que.empty())
que.pop();
} void topSort() {
for (int i=; i<=p; ++i) {
if (deg[i] == )
vis[i] = true;
if (deg[i] == ) {
vis[i] = true;
que.push(i);
}
} while(!que.empty()) {
int top = que.front();
//cout << top << "===\n";
que.pop();
for (int i=head[top]; i!=-; i=edge[i].next) {
int v = edge[i].v;
//cout << v << "----\n";
deg[v]--;
if (!vis[v]) {
if (deg[v] == )
vis[v] = true;
else if (deg[v] == ) {
vis[v] = true;
que.push(v);
}
}
}
//cout << "***\n";
}
} void Dfs(int u, int fa) {
// cout << val[u] << "===" << u << endl;;
num += ;
temp += val[u];
vis[u] = true;
for (int i=head[u]; i!=-; i=edge[i].next) {
int v = edge[i].v;
if (!vis[v] && v != fa) {
Dfs(v, u); // u开头的这条链上的最后一个子节点,如果是u ,就说明到环的开始了。
}
}
} int main() {
cin >> t;
while (t--) {
init();
cin >> p >> m; for (int i=; i<=p; ++i) {
cin >> val[i];
} for (int i=; i<m; ++i) {
cin >> a >> b;
addEdge(a, b);
addEdge(b, a);
deg[a]++;
deg[b]++;
}
topSort();
for (int i=; i<=p; ++i) {
num = ;
temp = ;
if (!vis[i])
Dfs(i, );
if (num & ) {
ans += temp;
}
}
cout << ans << endl;
}
return ;
}
poj 5441
// 先对边按权值排序,然后对询问按照权值排序。
// 每次在满足当前条件下,遍历。把两个端点所在的集合
// 并起来。此时增加的pair数就是2*num1*num2.
// 因为已经对询问按照权值排序。所以后面的集合一定会覆盖前面的、
// 所以只要一直询问下去。记录就可以了。
// 有一点并查集离线查询的地方。 #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std; #define maxn 201000 // 节点数
#define maxm 51000 // 询问数
#define tot 1001000 // 边数 int t, n, m, q;
int num[maxn]; // 维护每个节点当前所在集合的节点个数、
int ans[maxm]; // 保存每次询问的结果、
int fa[maxn]; // 并查集 struct Node {
int st, ed, dis;
}node[tot]; int cmp(Node a, Node b) {
return a.dis < b.dis;
} struct Querry{
int id, ask;
}que[maxm]; void init() {
for (int i=; i<=n; ++i) {
fa[i] = i;
num[i] = ;
}
memset(ans, , sizeof(ans));
} int cmp2(Querry a, Querry b) {
return a.ask < b.ask;
} int find_(int i) {
if (fa[i] == i) return i;
else return fa[i] = find_(fa[i]);
} int main() {
int a, b, d;
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &n, &m, &q);
init();
for (int i=; i<=m; ++i) {
scanf("%d%d%d", &a, &b, &d);
node[i].st = a;
node[i].ed = b;
node[i].dis = d;
}
sort(node+, node++m, cmp);
for (int i=; i<q; ++i) {
scanf("%d", &que[i].ask);
que[i].id = i+;
}
sort(que, que+q, cmp2); int now = ;
int tempans = ;
int flag = ; for (int i=; i<q; ++i) {
flag = que[i].id;
for(; node[now].dis<=que[i].ask && now<=m; now++) {
int t1 = node[now].st;
int t2 = node[now].ed;
if (t1 == t2) {
continue;
}
if (find_(t1) == find_(t2)) {
continue;
}
else if (find_(t1) != find_(t2)) {
tempans += *num[find_(t1)]*num[find_(t2)];
num[find_(t1)] += num[find_(t2)];
fa[find_(t2)] = find_(t1);
}
}
ans[flag] += tempans;
}
for (int i=; i<=q; ++i) {
printf("%d\n", ans[i]);
}
}
return ;
}
poj 5444
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std; struct Tree {
int l, r;
}node[]; bool flag; void init() {
memset(node, , sizeof(node));
} void addNode(int u, int c) {
if (node[u].l== && u<c) {node[u].l = c;return;}
else if (node[u].r== && u>c) {node[u].r = c;return;}
else if (u<c) addNode(node[u].l, c);
else addNode(node[u].r, c);
} void find(int u, int c) {
if (u == c)
return;
else if (u<c) {
cout << 'W';
find(node[u].l, c);
}
else if (u > c) {
cout << 'E';
find(node[u].r, c);
}
} int main() {
int t, n, q, r, c;
cin >> t;
while(t--) {
init();
cin >> n;
cin >> r;
node[r].l = node[r].r = ; for (int i=; i<n; ++i) {
cin >> c;
addNode(r, c);
}
cin >> q;
for (int i=; i<q; ++i) {
flag = true;
cin >> c;
find(r, c);
cout << endl;
}
}
return ;
}
最新文章
- Netbeans配置Xdebug
- nios II--实验4——按键中断硬件部分
- [设计模式] javascript 之 建造者模式
- 乐在其中设计模式(C#) - 代理模式(Proxy Pattern)【转】
- tomcat maxConnections和maxThreads区别
- cf413E Maze 2D
- opencv之haar特征+AdaBoos分类器算法流程(二)
- 页面跳转后样式丢失js失效
- C++ Primer 5 CH6 函数
- 201521123038 《Java程序设计》 第七周学习总结
- [SinGuLaRiTy] 复习模板-高精度模板
- git基本用法
- centos7系统下配置jdk环境变量
- 2018-2019-2 20175311 实验一《Java开发环境的熟悉》实验报告
- MySQL Backup myloader
- uoj233/BZOJ4654/洛谷P1721 [Noi2016]国王饮水记 【dp + 斜率优化】
- HyperLedger/Fabric JAVA-SDK with 1.1
- Splash resource_timeout 属性
- 数字模型制作规范(转自Unity3D群)
- 【LeetCode】153. Find Minimum in Rotated Sorted Array (3 solutions)
热门文章
- poj 1274 The Prefect Stall - 二分匹配
- Duilib Edit编辑框禁止输入中文的方法
- Python3基础 str lstrip 去掉字符串左边的空格
- Django组件(二) Django之Form
- HDU1698 Just a Hook(线段树&;区间覆盖)题解
- POJ 3687 Labeling Balls(拓扑排序)题解
- icpc 2017北京 J题 Pangu and Stones 区间DP
- 论文笔记之:Human-level control through deep reinforcement learning
- C# ashx接收ContentType=";text/xml";类型值
- Codeforces Beta Round #94 div 2 C Statues dfs或者bfs