hihoCoder 1123-好配对 #1123 : 好配对 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 给定两个序列a和b，每个序列中可能含有重复的数字。 一个配对(i,j)是一个好配对当从第一个序列中选出一个数ai，再从第二个序列中选出一个数bj且满足ai>bj。 给出两个序列，问存在多少个好配对。 输入 输入包含多组数据，数据第一行一个整数T，表示数据组数。(T<=5) 每组数据第一行包含两个整数n和m。(0<n,m<=$$10^5$$) 接下来n行，每行两个整数x和y，表示在第一个序列中有y个x。 接下来m行，每行两个整数x和y，表示在第二个序列中有y个x。(0<x<=$$10^9$$,0<y<=$$10^4$$) 输出 对于每组数据，输出一行一个整数，表示好配对的数量 样例输入 1 2 2 3 2 4 1 3 1 2 3 样例输出 10
此题最先想到的解法是类似桶排序的思路，用空间来换时间，但是看到x的范围是$$10^9$$，显然不行，于是牺牲时间来换空间，构造： [cpp] typedef struct Ele { int value; int num; bool operator < (const Ele& e) const { return value < e.value; } }; [/cpp] 依次输入两个序列，并按value从小到大排序；两个序列从头开始遍历，计算好配对的个数。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; typedef struct Ele { int value; int num; bool operator < (const Ele& e) const { return value < e.value; } }; vector<Ele> first_seq, second_seq; int main() { int t,m,n,x,y; long long ans; scanf("%d", &t); while (t–) { scanf("%d %d", &n, &m); first_seq.clear(); first_seq.resize(n); second_seq.clear(); second_seq.resize(m); for (int i = 0; i < n; i++) scanf("%d %d", &first_seq[i].value, &first_seq[i].num); for (int i = 0; i < m; i++) scanf("%d %d", &second_seq[i].value, &second_seq[i].num); sort(first_seq.begin(), first_seq.end()); sort(second_seq.begin(), second_seq.end()); ans = 0; int i = 0, j = 0; long long sum2 = 0; while (i < n && j < m) { while (j < m && second_seq[j].value < first_seq[i].value) { sum2 += second_seq[j].num; j++; } ans += (first_seq[i].num*sum2); i++; } while (i < n) { ans += (first_seq[i].num*sum2); i++; } printf("%lldn", ans); } return 0; } [/cpp] 本代码提交AC，用时193MS，内存11MB。]]>
Another sample test case.
其中包含3个组，分别为{(1,2),(2,3),(3,1)},{(4,5),(5,6),(4,6)},{(3,4)}。对{(1,2),(2,3),(3,1)}而言，和该组边相关联的有{1,2,3}三个服务器：当1宕机后，仍然有2-3可以连接2和3；当2宕机后，仍然有1-3可以连接1和3；当3宕机后，仍然有1-2可以连接1和2。
老师把整个网络的情况告诉了小Hi和小Ho，希望小Hi和小Ho统计一下一共有多少个分组。
提示：点的双连通分量
输入
第1行：2个正整数，N,M。表示点的数量N，边的数量M。1≤N≤20,000, 1≤M≤100,000
第2..M+1行：2个正整数，u,v。第i+1行表示存在一条边(u,v)，编号为i，连接了u,v两台服务器。1≤u<v≤N
保证输入所有点之间至少有一条连通路径。
输出
第1行：1个整数，表示该网络的连接组数。
第2行：M个整数，第i个数表示第i条连接所属组内，编号最小的连接的编号。比如分为{(1,2)[1],(2,3)[3],(3,1)[2]},{(4,5)[5],(5,6)[7],(4,6)[6]},{(3,4)[4]}，方括号内表示编号，则输出{1,1,1,4,5,5,5}。
样例输入
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
样例输出
3
1 1 1 4 5 5 5
图中每个点表示一个草场，上部分数字表示编号，下部分表示草场的牧草数量w。
在1吃完草之后，小Hi和小Ho可以选择把牛羊群赶到2或者3，假设小Hi和小Ho把牛羊群赶到2：
吃完草场2之后，只能到草场4，当4吃完后没有可以到达的草场，所以小Hi和小Ho就把牛羊群赶回家。
若选择从1到3，则可以到达5，6：
选择5的话，吃完之后只能直接回家。若选择6，还可以再通过6回到3，再到5。
所以该图可以选择的路线有3条：
1->2->4 total: 11
1->3->5 total: 9
1->3->6->3->5 total: 13
所以最多能够吃到的牧草数量为13。
本题改编自USACO月赛金组
提示：强连通分量
输入
第1行：2个正整数，N,M。表示点的数量N，边的数量M。1≤N≤20,000, 1≤M≤100,000
第2行：N个正整数，第i个整数表示第i个牧场的草量w[i]。1≤w[i]≤100,000
第3..M+2行：2个正整数，u,v。表示存在一条从u到v的单向路径。1≤u,v≤N
输出
第1行：1个整数，最多能够吃到的牧草数量。
样例输入
6 6
2 4 3 5 4 4
1 2
2 4
1 3
3 5
3 6
6 3
样例输出
13
其中包含2个组，分别为{1,2,3},{4,5,6}。对{1,2,3}而言，当1-2断开后，仍然有1-3-2可以连接1和2；当2-3断开后，仍然有2-1-3可以连接2和3；当1-3断开后，仍然有1-2-3可以连接1和3。{4,5,6}这组也是一样。
老师把整个网络的情况告诉了小Hi和小Ho，小Hi和小Ho要计算出每一台服务器的分组信息。
提示：边的双连通分量
输入
第1行：2个正整数，N,M。表示点的数量N，边的数量M。1≤N≤20,000, 1≤M≤100,000
第2..M+1行：2个正整数，u,v。表示存在一条边(u,v)，连接了u,v两台服务器。1≤u<v≤N
保证输入所有点之间至少有一条连通路径。
输出
第1行：1个整数，表示该网络的服务器组数。
第2行：N个整数，第i个数表示第i个服务器所属组内，编号最小的服务器的编号。比如分为{1,2,3},{4,5,6}，则输出{1,1,1,4,4,4}；若分为{1,4,5},{2,3,6}则输出{1,2,2,1,1,2}
样例输入
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
样例输出
2
1 1 1 4 4 4
]]>
每两个点之间至少有一条路径连通，当切断边(3,4)的时候，可以发现，整个网络被隔离为{1，2，3}，{4，5，6}两个部分：
若关闭服务器3，则整个网络被隔离为{1，2}，{4，5，6}两个部分：
小Hi和小Ho想要知道，在学校的网络中有哪些连接和哪些点被关闭后，能够使得整个网络被隔离为两个部分。
在上面的例子中，满足条件的有边(3,4)，点3和点4。
提示：割边&割点
输入
第1行：2个正整数，N,M。表示点的数量N，边的数量M。1≤N≤20,000, 1≤M≤100,000
第2..M+1行：2个正整数，u,v。表示存在一条边(u,v)，连接了u,v两台服务器。1≤u<v≤N
保证输入所有点之间至少有一条连通路径。
输出
第1行：若干整数，用空格隔开，表示满足要求的服务器编号。从小到大排列。若没有满足要求的点，该行输出Null
第2..k行：每行2个整数，(u,v)表示满足要求的边，u<v。所有边根据u的大小排序，u小的排在前，当u相同时，v小的排在前面。若没有满足要求的边，则不输出
样例输入
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
样例输出
3 4
3 4
主要要理解上面的递推公式。首先理解dfn和low的含义，dfn[u]记录节点u在DFS过程中被遍历到的次序号，low[u]记录节点u或u的子树通过非父子边追溯到最早的祖先节点（即DFS次序号最小）。
上图的第一个式子，当(u,v)为树边时，low[u]表明u能追溯到的最早节点，low[v]表明u的子树（v就是u的子树的根）能追溯到的最早节点，所以根据low[u]的定义有low[u]=min(low[u],low[v])。
上图的第二个式子，当(u,v)为回边时，因为low[u]的定义就是u通过非父子边（回边）追溯最早的节点，所以既然(u,v)为回边，自然的low[u]=min(low[u],dfn[v])。
另外注意输出格式，点要从小到大排列；边(u,v)保证u<v，以u从小到大排列，再以v从小到大排列。完整代码如下：
[cpp]
#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
const int kMaxN = 20005;
int n, m;
typedef struct edge
{
int x, y;
bool operator<(const edge& p)const//如果要加入到set中，需要重载<
{
return (this->x<p.x) || ((this->x == p.x) && (this->y<p.y));
}
};
set<int> points;
set<edge> edges;
vector<vector<int>> graph;
int visit[kMaxN];
int dfn[kMaxN];
int low[kMaxN];
int parent[kMaxN];
void dfs(int u) {
//记录dfs遍历次序
static int counter = 0;
//记录节点u的子树数
int children = 0;
visit[u] = 1;
//初始化dfn与low
dfn[u] = low[u] = ++counter;
for (int i = 0; i < graph[u].size();i++) {
int v = graph[u][i];
//节点v未被访问，则(u,v)为树边
if (visit[v]==0) {
children++;
parent[v] = u;
dfs(v);
low[u] = min(low[u], low[v]);
//case (1)
if (parent[u] == 0 && children > 1) {
points.insert(u);
}
//case (2)
if (parent[u] != 0 && low[v] >= dfn[u]) {
points.insert(u);
}
//bridge
if (low[v] > dfn[u]) {
edge e;
e.x = u;
e.y = v;
if (u > v)
{
e.x = v;
e.y = u;
}
edges.insert(e);
}
}
//节点v已访问，则(u,v)为回边
else if (v != parent[u]) {
low[u] = min(low[u], dfn[v]);
}
}
}
int main()
{
scanf("%d %d", &n, &m);
graph.resize(n + 1);
int u, v;
while (m–)
{
scanf("%d %d", &u, &v);
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(1);
if (points.size() == 0)
printf("Null\n");
else
{
set<int>::iterator it = points.begin();
while (it != points.end())
{
printf("%d ", *it);
it++;
}
printf("\n");
}
if (edges.size() > 0)
{
set<edge>::iterator it = edges.begin();
while (it != edges.end())
{
printf("%d %d\n", (*it).x, (*it).y);
it++;
}
}
return 0;
}
[/cpp]
本代码提交AC，用时76MS，内存7MB。]]>
这个机关是一个圆环，一共有2^N个区域，每个区域都可以改变颜色，在黑白两种颜色之间切换。
小Ho控制主角在周围探索了一下，果然又发现了一个纸片：
机关黑色的部分表示为1，白色的部分表示为0，逆时针连续N个区域表示一个二进制数。打开机关的条件是合理调整圆环黑白两种颜色的分布，使得机关能够表示0~2^N-1所有的数字。
我尝试了很多次，终究没有办法打开，只得在此写下机关破解之法。
——By 无名的冒险者
小Ho：这什么意思啊？
小Hi：我给你举个例子，假如N=3，我们通过顺时针转动，可以使得正下方的3个区域表示为：
因为黑色表示为1，白色表示为0。则上面三个状态分别对应了二进制(001),(010),(101)
每转动一个区域，可以得到一个新的数字。一共可以转动2^N次，也就是2^N个数字。我们要调整黑白区域的位置，使得这2^N个数字恰好是0~2^N-1
小Ho：我懂了。若N=2，则将环上的黑白色块调整为”黑黑白白”，对应了”1100″。依次是”11″,”10″,”00″,”01″四个数字，正好是0~3。那么这个”黑黑白白”就可以打开机关了咯？
小Hi：我想应该是的。
小Ho：好像不是很难的样子，我来试试！
提示：有向图欧拉回路
输入
第1行：1个正整数，N。1≤N≤15
输出
第1行：1个长度为2^N的01串，表示一种符合要求的分布方案
样例输入
3
样例输出
00010111
因为相亲总是在男女之间进行的，所以每一条边的两边对应的人总是不同性别。假设表示男性的节点染成白色，女性的节点染色黑色。对于得到的无向图来说，即每一条边的两端一定是一白一黑。如果存在一条边两端同为白色或者黑色，则表示这一条边所表示的记录有误。由于我们并不知道每个人的性别，我们的问题就转化为判定是否存在一个合理的染色方案，使得我们所建立的无向图满足每一条边两端的顶点颜色都不相同。那么，我们不妨将所有的点初始为未染色的状态。随机选择一个点，将其染成白色。再以它为起点，将所有相邻的点染成黑色。再以这些黑色的点为起点，将所有与其相邻未染色的点染成白色。不断重复直到整个图都染色完成。(如下图)
在染色的过程中，我们应该怎样发现错误的记录呢？相信你一定发现了吧。对于一个已经染色的点，如果存在一个与它相邻的已染色点和它的颜色相同，那么就一定存在一条错误的记录。(如上图的4，5节点)到此我们就得到了整个图的算法：选取一个未染色的点u进行染色
遍历u的相邻节点v：若v未染色，则染色成与u不同的颜色，并对v重复第2步；若v已经染色，如果 u和v颜色相同，判定不可行退出遍历。
若所有节点均已染色，则判定可行。
接下来就动手写写吧！
输入
第1行：1个正整数T(1≤T≤10)
接下来T组数据，每组数据按照以下格式给出：
第1行：2个正整数N,M(1≤N≤10,000，1≤M≤40,000)
第2..M+1行：每行两个整数u,v表示u和v之间有一条边
输出
第1..T行：第i行表示第i组数据是否有误。如果是正确的数据输出”Correct”，否则输出”Wrong”
样例输入
2
5 5
1 2
1 3
3 4
5 2
1 5
5 5
1 2
1 3
3 4
5 2
3 5
样例输出
Wrong
Correct
此图有两个连通分量，且两个分量都可以相亲成功，但如果只从第1点开始BFS，则不能遍历到第二个分量，导致失败。所以需要对每一个还未染色的点都开始BFS，如果都尝试过了还有点未染色，二分图判定失败；否则成功。
完整代码如下：
[cpp]
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n, m;
vector<int> colored;
vector<vector<int>> path;
bool BFS(int start)
{
colored[start] = 0;
int num_colored = 1;
queue<int> point;
point.push(start);
while (!point.empty())
{
int current = point.front();
point.pop();
for (int i = 0; i < path[current].size(); i++)
{
if (colored[path[current][i]] == -1)
{
if (colored[current] == 0)
colored[path[current][i]] = 1;
else if (colored[current] == 1)
colored[path[current][i]] = 0;
num_colored++;
point.push(path[current][i]);
}
else if (colored[current] == colored[path[current][i]])
return false;
}
}
return true;
}
bool Check()
{
for (int i = 1; i <= n; i++)
if (colored[i] == -1)
if (!BFS(i))
return false;
return true;
}
int main()
{
int t,u,v;
scanf("%d", &t);
while (t–)
{
scanf("%d %d", &n, &m);
colored.clear();
colored.resize(n + 1, -1);
path.clear();
path.resize(n + 1);
for (int i = 0; i < m; i++)
{
scanf("%d %d", &u, &v);
path[u].push_back(v);
path[v].push_back(u);
}
if (Check())
printf("Correctn");
else
printf("Wrongn");
}
return 0;
}
[/cpp]
本代码提交AC，用时134MS，内存6MB。
]]>
主角继续往前走，面前出现了一座石桥，石桥的尽头有一道火焰墙，似乎无法通过。
小Hi注意到在桥头有一张小纸片，于是控制主角捡起了这张纸片，只见上面写着：
将M块骨牌首尾相连放置于石桥的凹糟中，即可关闭火焰墙。切记骨牌需要数字相同才能连接。
——By 无名的冒险者
小Hi和小Ho打开了主角的道具栏，发现主角恰好拥有M快骨牌。
小Ho：也就是说要把所有骨牌都放在凹槽中才能关闭火焰墙，数字相同是什么意思？
小Hi：你看，每一块骨牌两端各有一个数字，大概是只有当数字相同时才可以相连放置，比如：
小Ho：原来如此，那么我们先看看能不能把所有的骨牌连接起来吧。
提示：Fleury算法求欧拉路径
输入
第1行：2个正整数，N,M。分别表示骨牌上出现的最大数字和骨牌数量。1≤N≤1,000，1≤M≤5,000
第2..M+1行：每行2个整数，u,v。第i+1行表示第i块骨牌两端的数字(u,v)，1≤u,v≤N
输出
第1行：m+1个数字，表示骨牌首尾相连后的数字
比如骨牌连接的状态为(1,5)(5,3)(3,2)(2,4)(4,3)，则输出”1 5 3 2 4 3″
你可以输出任意一组合法的解。
样例输入
5 5
3 5
3 2
4 2
3 4
5 1
样例输出
1 5 3 4 2 3