ABC061
ABC061
[ABC061B] Counting Roads
题面翻译
题意简述：
有N个城市和M条道路。
第i条道路（1 <= i <= M）双向连接两个城市ai和bi（1 <= ai，bi <= N），
可能有多条道路连接同一对的两个城市。
对于每个城市，有多少条道路连接到它？
输入：N，M，每条道路的情况；
输出：连接到每个城市的道路条数。
样例输入：
4 3
1 2
2 3
1 4
样例输出：
2
2
1
1
样例解释：
共有4个城市，3条道路
1号——2号
2号——3号
1号——4号
有2条道路连接到1号，2条连接到2号，1条连接到3号，1条连接到4号。
注意：
所有道路都是双向的。
题目描述
$ N $ 個の都市があり、$ M $ 本の道路があります。
$ i(1≦i≦M) $ 番目の道路は、都市 $ a_i $ と 都市 $ b_i $ $ (1≦a_i,b_i≦N) $ を双方向に結んでいます。
同じ $ 2 $ つの都市を結ぶ道路は、$ 1 $ 本とは限りません。
各都市から他の都市に向けて、何本の道路が伸びているか求めてください。输入格式
入力は以下の形式で標準入力から与えられる。
$ N $ $ M $ $ a_1 $ $ b_1 $ $ : $ $ a_M $ $ b_M $
输出格式
答えを $ N $ 行に出力せよ。
$ i(1≦i≦N) $ 行目には、都市 $ i $ から他の都市に向けて、何本の道路が伸びているかを出力せよ。样例 #1
样例输入 #1
1 2
2 3
1 4样例输出 #1
2
1
1样例 #2
样例输入 #2
1 2
2 1
1 2
2 1
1 2样例输出 #2
5样例 #3
样例输入 #3
1 2
3 4
1 5
2 8
3 7
5 2
4 1
6 8样例输出 #3
3
2
2
2
1
1
2提示
制約
- $ 2≦N,M≦50 $
- $ 1≦a_i,b_i≦N $
- $ a_i ≠ b_i $
- 入力は全て整数である。
Sample Explanation 1
- 都市 $ 1 $ からは $ 1 $ 番目と $ 3 $ 番目の道路が伸びています。 - 都市 $ 2 $ からは $ 1 $ 番目と $ 2 $ 番目の道路が伸びています。 - 都市 $ 3 $ からは $ 2 $ 番目の道路が伸びています。 - 都市 $ 4 $ からは $ 3 $ 番目の道路が伸びています。
思路
直接用邻接表模拟即可
|
[ABC061C] Big Array
题面翻译
题目翻译
题目描述
有一个数组S，一开始是空的。接下来对这个数组进行N次插入操作. 第ii次操作会向数组中加入\(b_i\) 个整数\(a_i\) ，然后将整个数组从小到大排一次序。 求N次操作后, 数组中的第K个数。 例如S={1,2,2,3,3,3}时, 从小到大排序后第4个数是3。
输入格式
第1行, 包含两个整数N,K用空格分隔.
第2行到第N+1行, 每行包含两个整数 \(a_i\),\(b_i\)
输出格式
输出N次操作后集合中第K小的数.
说明/提示
数据范围
1≦N≦$10^5$1≦$a_i$ ,$b_i$ ≦$10^5$1≦K≦$b_1$+...+$b_n$所有输入值都是整数。
题目翻译者UID：370640
题目描述
空の配列が $ 1 $ つあります。
この配列に、整数を配列に挿入する操作を $ N $ 回行います。
$ i(1≦i≦N) $ 回目の操作では、配列に整数 $ a_i $ を $ b_i $ 個挿入します。
$ N $ 回の挿入操作後の配列の中で、$ K $ 番目に小さい数を求めてください。
例えば、配列が $ {1,2,2,3,3,3} $ の時、$ 4 $ 番目に小さい数は $ 3 $ となります。输入格式
入力は以下の形式で標準入力から与えられる。
$ N $ $ K $ $ a_1 $ $ b_1 $ $ : $ $ a_N $ $ b_N $
输出格式
$ N $ 回の挿入操作後の配列の中で、$ K $ 番目に小さい数を出力せよ。
样例 #1
样例输入 #1
1 1
2 2
3 3样例输出 #1
样例 #2
样例输入 #2
1 100000
1 100000
1 100000
1 100000
1 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000样例输出 #2
提示
制約
- $ 1≦N≦10^5 $
- $ 1≦a_i,b_i≦10^5 $
- $ 1≦K≦b_1…+…b_n $
- 入力は全て整数である。
Sample Explanation 1
操作後の配列は、問題文に書かれている例と同じです。
思路
不开long long见祖宗。
|
[ABC061D] Score Attack
题面翻译
给定一个有 \(n\) 个点和 \(m\) 条边的简单有向图。其中第 \(i\) 条边从点 \(a_i\) 连向点 \(b_i\) ，且具有权值 \(c_i\)。
我们在图上进行以下游戏。一开始，一个棋子被放置在点 \(1\) 。玩家可以进行如下操作：
- 当棋子位于点 \(a_i\) 时，可以通过边 \(i\) 将棋子移动到点 \(b_i\) ，且让分数增加 \(c_i\)。
当棋子位于点 \(n\) 时，玩家可以选择让游戏结束。假设玩家一直按最优策略操作，求出游戏结束后可以增加分数的最大值。如果分数可以无限增加，输出
inf。题目描述
$ N $ 頂点 $ M $ 辺の重み付き有向グラフがあります。
$ i(1≦i≦M) $ 番目の辺は 頂点 $ a_i $ から 頂点 $ b_i $ を重み $ c_i $ で結びます。
このグラフと駒を利用して、次の1人ゲームを行います。最初、駒を頂点 $ 1 $ に置いて、プレイヤーのスコアを $ 0 $ とします。
プレイヤーは、次の条件で駒を繰り返し移動させることができます。
- 頂点 $ a_i $ に駒があるとき、$ i $ 番目の辺を利用して頂点 $ b_i $ に移動する。移動後にプレイヤーのスコアが $ c_i $ 加算される。
頂点 $ N $ に駒があるときのみ、ゲームを終了できます。
なお、与えられる有向グラフの上で頂点 $ 1 $ から頂点 $ N $ に移動できることは保障されています。プレイヤーがゲーム終了時のスコアを出来るだけ大きくするような行動を取ったとき、ゲーム終了時のスコアはいくつになるでしょうか?
ゲーム終了時のスコアをいくらでも大きくできる場合はinfと出力してください。输入格式
入力は以下の形式で標準入力から与えられる。
$ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ : $ $ a_M $ $ b_M $ $ c_M $
输出格式
もし、ゲーム終了時のスコアをいくらでも大きくできる場合は
inf、そうでない場合はゲーム終了時のスコアの最大値を出力せよ。样例 #1
样例输入 #1
1 2 4
2 3 3
1 3 5样例输出 #1
样例 #2
样例输入 #2
1 2 1
2 1 1样例输出 #2
样例 #3
样例输入 #3
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000样例输出 #3
提示
制約
- $ 2≦N≦1000 $
- $ 1≦M≦min(N(N-1),2000) $
- $ 1≦a_i,b_i≦N (1≦i≦M) $
- $ a_i≠b_i (1≦i≦M) $
- $ a_i≠a_j $ または $ b_i≠b_j (1≦i < j≦M) $
- $ -109≦c_i≦109 (1≦i≦M) $
- $ c_i $ は整数である。
- 与えられるグラフには、頂点 $ 1 $ から頂点 $ N $ への経路が存在する。
Sample Explanation 1
駒を頂点 $ N=3 $ に移動できる経路は以下の $ 2 $ 通りです。 - 頂点 $ 1 $ → 頂点 $ 2 $ → 頂点 $ 3 $ : スコア $ 4+3=7 $ - 頂点 $ 1 $ → 頂点 $ 3 $ : スコア $ 5 $ したがって、ゲーム終了時のスコアの最大値は $ 7 $ となります。
Sample Explanation 2
頂点 $ 1 $ → 頂点 $ 2 $ → 頂点 $ 1 $ → 頂点 $ 2 $ … と移動することで、ゲーム終了時のスコアをいくらでも増やせます。
思路
思路参考自：题解 ABC 061 D - 洛谷专栏 (luogu.com.cn)
很显然，题目让我们找最长路或者找正环
可以边权转负，所以就变成了找最短路+找负环。用SPFA即可。
然后你会发现 WA 了，我们的思路好像并没有问题，再读一遍题：
If it is possible to increase the score indefinitely, print
inf.如果分数可以无限增加，输出
inf。分数无限增加一定是有正环，但有正环分数就一定会无限增加么？
如果有一个正环，但从\(1\)到\(n\)的路径上并不会经过，那么他对答案是没有影响的，
所以开始时说的“找正环”是不对的，应该是 找最长路径上是否经过正环，
这样我们只需要判断\(n\)是否在正环上就可以了。
|
