夏休みN天楽【試合編】――2019杭州電夏期多校訓練キャンプ(第六回)
12214 ワード
胡漢三はまた転びました。賞味期限が過ぎた問題もメモしてください。
以下の問題は以下の通りです。
\[1002[HU-635]\1005【HU-6368】\1006【HU-639】\1008【HU-641】\1012【HDU-645】
【1002】LIS+暴力HU-6365 Nonsense Time
http://acm.hdu.edu.cn/showproblem.php?pid=6635
参考:https://blog.csdn.net/henuyh/article/details/98845165
長さが「(n\)の2つの配列\(a,b\)を指定して、\(a\)の下に「(bui\)と表示されている数字は現在利用可能です。\(b ui\)に対応する\(a\)のLISを求めて、\(a\)の中に\(1,n)\)の全配列です。
データがランダムに生成されるので、LISの期待長さは\(\sqrt{n}\)であり、削除要素がLISにある確率は\(\\fraac{1}{\sqrt{n})であるため、全体の複雑度:\(o(n\sqrt{n}log(n)))である。先にすべてのLISを解いて、その後から前へ配列\(b\)を遍歴して、削除した要素がLISの中でもう一度求めます。LISの経路を記録する必要があります。
http://acm.hdu.edu.cn/showproblem.php?pid=6638
参考:https://blog.csdn.net/A_Thinking_Reed_/アート/detail/98778260
与えられた\(n(\leq 2000)\の点座標と対応する権利値は、最大の重みと行列を求める。
上下境界を列挙するたびに、線分樹に加点し、上下境界内の最大サブセグメントと「区間最大サブセグメントと」を維持します。境界上を移動する時、複数の点が現在の直線上にあります。同じように、境界上のすべての点を更新してから更新できます。
http://acm.hdu.edu.cn/showproblem.php?pid=6639
二次元の座標点(兵士)があります。彼らは共通の目的地を持っています。(x_{e}、y_{e}\)、知っています。(xue\)も\(yuue\)も範囲内にいると知っていますが、彼らは自分の位置しか知らないです。)\%k_{i}=t_{i}\今あなたにいくつの可能な目標があるか聞いてみます。
の絶対値を取り外すと、各点\((xui,yui)\)は平面を4つの部分に分割して、合計\(n^2\)の領域になります。各エリアを列挙して、そのエリア内の可能な終点の数を計算します。"(lcm(2,3,4,5)=60\)ですので、列挙\(xue\)と\(yue\)モデル60の余りが必要です。\(o(n)\)は実行可能かどうかを判断します。
http://acm.hdu.edu.cn/showproblem.php?pid=6641
チームメイトが書いたのはソースです。
http://acm.hdu.edu.cn/showproblem.php?pid=6645
競技の時になぜ位相を書きに行くのか分かりません。
順番を作って、一人で一つずつ分けたらいいです。
以下の問題は以下の通りです。
\[1002[HU-635]\1005【HU-6368】\1006【HU-639】\1008【HU-641】\1012【HDU-645】
【1002】LIS+暴力HU-6365 Nonsense Time
http://acm.hdu.edu.cn/showproblem.php?pid=6635
参考:https://blog.csdn.net/henuyh/article/details/98845165
長さが「(n\)の2つの配列\(a,b\)を指定して、\(a\)の下に「(bui\)と表示されている数字は現在利用可能です。\(b ui\)に対応する\(a\)のLISを求めて、\(a\)の中に\(1,n)\)の全配列です。
データがランダムに生成されるので、LISの期待長さは\(\sqrt{n}\)であり、削除要素がLISにある確率は\(\\fraac{1}{\sqrt{n})であるため、全体の複雑度:\(o(n\sqrt{n}log(n)))である。先にすべてのLISを解いて、その後から前へ配列\(b\)を遍歴して、削除した要素がLISの中でもう一度求めます。LISの経路を記録する必要があります。
#include
【1005】線分樹HU-6368 Snowy Smilehttp://acm.hdu.edu.cn/showproblem.php?pid=6638
参考:https://blog.csdn.net/A_Thinking_Reed_/アート/detail/98778260
与えられた\(n(\leq 2000)\の点座標と対応する権利値は、最大の重みと行列を求める。
上下境界を列挙するたびに、線分樹に加点し、上下境界内の最大サブセグメントと「区間最大サブセグメントと」を維持します。境界上を移動する時、複数の点が現在の直線上にあります。同じように、境界上のすべての点を更新してから更新できます。
#include
【1006】思惟HU-6369 Farawayhttp://acm.hdu.edu.cn/showproblem.php?pid=6639
二次元の座標点(兵士)があります。彼らは共通の目的地を持っています。(x_{e}、y_{e}\)、知っています。(xue\)も\(yuue\)も範囲内にいると知っていますが、彼らは自分の位置しか知らないです。)\%k_{i}=t_{i}\今あなたにいくつの可能な目標があるか聞いてみます。
の絶対値を取り外すと、各点\((xui,yui)\)は平面を4つの部分に分割して、合計\(n^2\)の領域になります。各エリアを列挙して、そのエリア内の可能な終点の数を計算します。"(lcm(2,3,4,5)=60\)ですので、列挙\(xue\)と\(yue\)モデル60の余りが必要です。\(o(n)\)は実行可能かどうかを判断します。
#include
【1008】数学HU-641 TDLhttp://acm.hdu.edu.cn/showproblem.php?pid=6641
チームメイトが書いたのはソースです。
#include
#include
#include
#include
#include
#include
#define lson node<<1
#define rson node<<1|1
using namespace std;
typedef long long ll;
const ll inf = 2e18;
const ll mod = 998244353;
const int maxn = 1e5 + 20;
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
ll k, m;
scanf("%lld%lld", &k, &m);
ll ans = inf;
int flag = 0;
for (int i = 1; i <= 2000; i++) {
ll n = k ^ i;
int cnt = 0;
int j = 1;
for (; j <= 1000; j++) {
if (gcd(j + n, n) == 1) {
cnt++;
if (cnt == m)
break;
}
}
if ((n + j) == (i + n)) {
ans = min(ans, n);
flag = 1;
}
}
if (flag)
printf("%lld
", ans);
else
printf("-1
");
}
}
【1012】水題HU-645 permutation 2http://acm.hdu.edu.cn/showproblem.php?pid=6645
競技の時になぜ位相を書きに行くのか分かりません。
順番を作って、一人で一つずつ分けたらいいです。
#include
転載先:https://www.cnblogs.com/Decray/p/11365864.html