ACM Training Record - Always_Penalty

[NWPU2018]萌新第一次上課作業 - Virtual Judge?

vjudge.net

0. 綜述

這次的題目以貪心、枚舉為主

A. Clean Shift

題意：給出若干個閉區間，從中選出最少的區間數完整覆蓋閉區間

題解：非常經典的區間覆蓋問題，按照左端點排序，然後對於同一個左端點，取能取到的最長的區間，如果只能取有重疊的區間，那就取開頭最大的

#include <iostream> #include <cstdio> #include <algorithm> #define N 25100 using namespace std; struct Interval { int l, r; Interval() {} Interval(const int& l, const int& r) : l(l), r(r) {} } I[N]; struct cmp { inline bool operator () (const Interval& i1, const Interval& i2) const { return i1.l < i2.l || (i1.l == i2.l && i1.r > i2.r); } };

int n, t;

int main()
{
//freopen("test.in", "r", stdin);
scanf("%d%d", &n, &t); int ex = 0, ey = 0;
for (int i = 1, l, r; i <= n; ++i) {
scanf("%d%d", &l, &r), I[i] = Interval(l, r);
if (l == 1) ex = 1;
if (r == t) ey = 1;
}
if (!ex || !ey) return printf("-1"), 0;
sort(I + 1, I + n + 1, cmp());
int ret = 1, lst = 1, op = I[1].r, mx = I[1].r;
for (;;) {
for (; lst + 1 <= n && I[lst + 1].l <= op + 1; ) mx = max(mx, I[++lst].r);
if (mx != op) ++ret, op = mx;
else {
if (lst == n) return printf("%d", ret), 0;
else return printf("-1"), 0;
}
}
return 0;
}

B. 今年暑假不AC

題意：給出若干閉區間，選出儘可能多的不相交的區間。區間端點可以重複

題解：也是經典的區間覆蓋問題。按照右端點排序，然後對於每個右端點，選擇左端點儘可能大的

#include <iostream> #include <cstdio> #include <algorithm> #define N 110 using namespace std; struct Interval { int l, r; Interval() {} Interval(const int& l, const int& r) : l(l), r(r) {} } I[N]; struct cmp { inline bool operator () (const Interval& i1, const Interval& i2) const { return i1.r < i2.r || (i1.r == i2.r && i1.l < i2.l); } };

int n;

int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d", &n) == 1 && n) {
for (int i = 1, l, r; i <= n; ++i) scanf("%d%d", &l, &r), I[i] = Interval(l, r);
sort(I + 1, I + n + 1, cmp());
int ret = 0, lst = -1;
for (int i = 1; i <= n; ++i) if (I[i].l >= lst) ++ret, lst = I[i].r;
printf("%d
", ret);
}
return 0;
}

C. Highway

題意：給出若干段閉區間，在數軸上標出最少的點，使得每個區間內至少有一個點

題解：還是紫書裏經典的區間覆蓋問題。我們考察將每段區間最大利用，這個點肯定是在右端點上的。因此先把所有區間按照右端點排序，右端點相同時左端點靠後的優先。只要找到一個沒選點的區間，就把它的右端點上標一個點。其中，區間由下面的方法獲得：

#include <cstdio> #include <cmath> #include <algorithm> #define N 10010 using namespace std;

template <class T> struct Interval {
T l, r;
Interval() {}
Interval(const T& l, const T& r) : l(l), r(r) {}
};
template <class T> struct cmp {
inline bool operator () (const Interval<T>& i1, const Interval<T>& i2) const {
return i1.r < i2.r || (i1.r == i2.r && i1.l > i2.l);
}
};

int L, d, n;
Interval<double> I[N];

int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d", &L) == 1) {
scanf("%d%d", &d, &n);
for (int i = 1, x, y; i <= n; ++i) {
scanf("%d%d", &x, &y);
double l = 1.0 * x - sqrt(1.0 * d * d - y * y), r = 1.0 * x + sqrt(1.0 * d * d - y * y);
I[i] = Interval<double>(l, r);
}
sort(I + 1, I + n + 1, cmp<double>());
int ret = 1; double lst = I[1].r;
for (int i = 2; i <= n; ++i) {
lst = min(lst, 1.0 * L);
if (lst < I[i].l) ++ret, lst = I[i].r;
}
printf("%d
", ret);
}
return 0;
}

寫了一個區間的template

D. Subsequence

題意：給出若干個數，選一段和不小於的最短子區間

題解：因為保證是正整數，所以前綴和是單調增的。這樣每次枚舉右端點，在前綴和裏二分查找左端點，並且更新答案

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define N 100100 using namespace std;

int T, n, s, a[N];
long long sum[N];

int main()
{
//freopen("test.in", "r", stdin);
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &s); memset(sum, 0, sizeof(sum));
int ret = n + 1;
for (int i = 1; i <= n; ++i) scanf("%d", a + i), sum[i] = sum[i - 1] + 1LL * a[i];
for (int j = 1; j <= n; ++j) {
int a = sum[j] - s;
int i = upper_bound(sum + 1, sum + j, a) - (sum + 1);
if (i) ret = min(ret, j - i);
}
printf("%d
", ret == (n + 1) ? 0 : ret);
}
return 0;
}

這道題似乎還可以用尺取法，時間複雜度會少一個

E. 4 Values whose Sum is 0

題意：給出四個整數集，從每個集合中各選出一個數，使得

題解：的枚舉是最好想的，但是在的數據範圍下顯然力不從心。我們把式子移項得到，那麼我們可以考慮維護，然後枚舉個的值，在另外個裏二分查找，答案就是 $upper\_bound-lower\_bound$ ，複雜度是的

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define N 4050 using namespace std;

int n, A[N], B[N], C[N], D[N], S1[N * N], S2[N * N];

int main()
{
//freopen("test.in", "r", stdin);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d%d%d", A + i, B + i, C + i, D + i);
int cnt = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
S1[++cnt] = A[i] + B[j], S2[cnt] = C[i] + D[j];
int ret = 0; sort(S2 + 1, S2 + cnt + 1);
for (int i = 1; i <= cnt; ++i) {
int a = -S1[i];
ret += upper_bound(S2 + 1, S2 + cnt + 1, a) - lower_bound(S2 + 1, S2 + cnt + 1, a);
}
printf("%d", ret);
return 0;
}

一開始暴力寫了一發Treap，發現超時了，突然發現建樹的時候複雜度很大……

F. 校門外的樹

題意：太經典了，不說了

題解：這裡給出一種差分的做法。維護一個差分數組，每次對於一個區間，在的地方打一個的標記，在 $rt_{r+1}$ 的地方打一個的標記，然後前綴和一下，最後為零的位置就是有樹的

#include <cstdio> #define N 10010 using namespace std;

int L, M, rt[N];

int main()
{
//freopen("test.in", "r", stdin);
scanf("%d%d", &L, &M);
for (int i = 1, l, r; i <= M; ++i) scanf("%d%d", &l ,&r), ++rt[l], --rt[r + 1];
for (int i = 1; i <= L; ++i) rt[i] += rt[i - 1]; int ret = 0;
for (int i = 0; i <= L; ++i) if (!rt[i]) ++ret;
printf("%d", ret);
return 0;
}

如果數據範圍改成，那麼就需要把區間的兩個端點一起離散化掉，然後一整段一整段統計答案

G. Overlapping Squares

題意：有一個的網格，你可以用不超過張的正方形紙片在上面擺放圖案。現在給你一張圖，可以看見的正方形的邊緣用黑線標了出來，問合不合法

題解：喪病題。。。網上的題解大多都很草率，我在這裡詳細講一下。把輸入看成是一張（對於豎列，我們把網格線和空格分開）的網格，正方形紙片用|、_和表示，那麼我們看看一個正方形紙片能怎麼擺：

對於|，一定只能擺在的豎網格線上
對於和_，一定只能擺在的橫網格線上
對於，一定只能放在空格里

那麼我們在擺一個正方形的時候，枚舉奇數列：

放|
放_
放

下面是比較直觀的圖：

這裡有一個點就是為什麼空格擺成了一個「T」型，那是因為注意到我們剛剛的約定，那兩個位置是留給_的，然後就可以愉快地dfs了

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <vector> #define N 10 using namespace std;

int kase;
string TAT[N], QAQ[N];

inline bool check(string src[], string std[])
{
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 9; ++j)
if (src[i][j] != std[i][j]) return 0;
return 1;
}

bool vis[N];
inline bool dfs(int cur)
{
if (check(TAT, QAQ)) return 1;
if (cur > 6) return 0;
string cpy[N];
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 9; ++j)
cpy[i][j] = TAT[i][j];
for (int d = 0; d < 9; ++d) {
int r = d / 3 + 1, c = (d % 3) * 2 + 1;
if (vis[d]) continue; vis[d] = 1;
TAT[r][c - 1] = TAT[r + 1][c - 1] = TAT[r][c + 3] = TAT[r + 1][c + 3] = |;
TAT[r - 1][c] = TAT[r + 1][c] = TAT[r - 1][c + 2] = TAT[r + 1][c + 2] = _;
TAT[r][c] = TAT[r][c + 1] = TAT[r][c + 2] = TAT[r + 1][c + 1] = ;
if (dfs(cur + 1)) return 1;
vis[d] = 0;
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 9; ++j)
TAT[i][j] = cpy[i][j];
}
return 0;
}

int main()
{
//freopen("test.in", "r", stdin);
for (;;) {
for (int i = 0; i < 5; ++i) getline(cin, QAQ[i]);
if (QAQ[0][0] == 0) break; memset(vis, 0, sizeof(vis));
for (int i = 0; i < 5; ++i)
for (int j = 0; j < 9; ++j)
TAT[i][j] = ;
printf("Case %d: %s
", ++kase, dfs(1) ? "Yes" : "No");
}
return 0;
}

現在才知道getline只包含在頭文件<string>裏，難怪去年NOIP用這個被炸成0分

H. Weak Key

題意：找，使得或

題解：只考慮前一個關係的做法，後一個關係只需要把數組flip一下就可以了。顯然想到枚舉，但是直接枚舉也是不行的。考慮到是相間的，因此我們枚舉，然後在開區間裏找最大的，然後在開區間裏找一個比大的 .下面是對於這兩個信息的維護：

對於第一個信息，直接RMQ就可以了，快得一批
對於第二個信息，維護每個數之後有多少數比它大，然後二分查找

#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #define N 5050 #define INF 0x3f3f3f3f using namespace std;

int T, n, a[N], b[N];

struct RMQ {
int d[N][15];
inline void init(const int& n, int *a)
{
for (int i = 1; i <= n; ++i) d[i][0] = a[i];
for (int j = 1; (1 << j) <= n; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
}

inline int query(int l, int r)
{
int k = 0;
for (; (1 << (k + 1)) <= (r - l + 1); ++k);
return max(d[l][k], d[r - (1 << k) + 1][k]);
}

inline bool check(int n, int *a)
{
vector<int> v[N];
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j)
if (a[i] < a[j]) v[i].push_back(a[j]);
sort(v[i].begin(), v[i].end());
}
for (int i = 1; i <= n; ++i) {
for (int j = i + 2; j <= n; ++j) {
if (a[i] <= a[j]) continue;
int q = query(i, j - 1);
if (q <= a[j]) continue;
vector<int>::iterator it = lower_bound(v[j].begin(), v[j].end(), a[i]);
if (it == v[j].end()) continue;
if (*it < q) return 1;
}
}
return 0;
}
} solver[2];

int main()
{
//freopen("test.in", "r", stdin);
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a + i), b[n - i + 1] = a[i];
solver[0].init(n, a), solver[1].init(n, b);
if (solver[0].check(n, a) || solver[1].check(n, b)) printf("YES
");
else printf("NO
");
}
return 0;
}

I. Unique Snowflakes

題意：唯一的雪花

題解：維護一個滑動窗口，當出現重複的時候更新一次答案，然後把左端點向後移動，用std::set<int>維護就可以了

#include <cstdio> #include <cstring> #include <algorithm> #include <set> #define N 1000100 #define INF 0x3f3f3f3f using namespace std;

int T, n, a[N];
set<int> s;

int main()
{
//freopen("test.in", "r", stdin);
scanf("%d", &T);
while (T--) {
scanf("%d", &n); s.clear();
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
int l = 1, r = 2, ret = 0; s.insert(a[l]);
while (r <= n) {
while (r <= n && !s.count(a[r])) s.insert(a[r++]);
ret = max(ret, r - l);
s.erase(a[l++]);
}
printf("%d
", ret);
}
return 0;
}

J. Moving Tables

題意：如圖所示在一條走廊的兩側各有200個房間，現在給定一些成對的房間相互交換桌子，但是走廊每次只能通過一組搬運，也就是說如果兩個搬運過程有交叉是不能同時搬運的，要依次來，一次搬運10min，問完成所有的搬運的最少用時

題解：找交叉最多的路

#include <cstdio> #include <cstring> #define N 220 using namespace std;

template <class T> const T& max(const T& a, const T& b) { return a > b ? a : b; }

int T, n, r[N];

int main()
{
//freopen("test.in", "r", stdin);
scanf("%d", &T);
while (T--) {
scanf("%d", &n); int mx = 0;
memset(r, 0, sizeof(r));
for (int i = 1, op, ed; i <= n; ++i) {
scanf("%d%d", &op, &ed);
if (op > ed) op ^= ed, ed ^= op, op ^= ed;
for (int i = (op + 1) / 2; i <= (ed + 1) / 2; ++i) ++r[i];
}
for (int i = 1; i <= 200; ++i) mx = max(mx, r[i]);
printf("%d
", (mx << 1) + (mx << 3));
}
return 0;
}

K. FatMouse Trade

題意：和USACO的買牛奶差不多

題解：和USACO的買牛奶差不多

#include <cstdio> #include <cstring> #include <algorithm> #define N 1010 using namespace std; struct Trade { int j, f; Trade() {} Trade(const int& j, const int& f) : j(j), f(f) {} } t[N]; struct cmp { inline bool operator () (const Trade& t1, const Trade& t2) const { return 1.0 * t1.j / t1.f > 1.0 * t2.j / t2.f; } };

int n, m;

int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d%d", &m, &n) == 2 && m != -1 && n != -1) {
for (int i = 1, j, f; i <= n; ++i) scanf("%d%d", &j, &f), t[i] = Trade(j, f);
sort(t + 1, t + n + 1, cmp());
double ret = 0.0;
for (int i = 1; i <= n; ++i) {
if (m >= t[i].f) {
ret += 1.0 * t[i].j;
m -= t[i].f;
} else {
ret += (1.0 * t[i].j / t[i].f) * m;
break;
}
}
printf("%.3f
", ret);
}
return 0;
}

話說這題我在HDU三位一體特長生測試的時候碰到了……

L. 田忌賽馬

題意：田忌賽馬

題解：挺坑的一道題，直接排一遍序一一做是錯的，輸的話必須要用這隻馬去輸齊王最厲害的馬，參考了黃學長hzwer的blog

#include <cstdio> #include <cstring> #include <algorithm> #define N 10010 #define INF 0x3f3f3f3f using namespace std; struct cmp { inline bool operator () (const int& i, const int& j) const { return i > j; } };

int n, QAQ[N], QwQ[N];

int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d", &n) == 1 && n) {
for (int i = 1; i <= n; ++i) scanf("%d", QAQ + i);
for (int i = 1; i <= n; ++i) scanf("%d", QwQ + i);
sort(QAQ + 1, QAQ + n + 1, cmp());
sort(QwQ + 1, QwQ + n + 1, cmp());
int ret = 0;
for (int i = 1, l = 1, j = n, r = n; i <= j {
if (QAQ[i] > QwQ[l]) ret+= 200, ++i, ++l;
else if (QAQ[i] < QwQ[l]) ret -= 200, ++l, --j;
else {
if (QAQ[j] > QwQ[r]) ret += 200, --j, --r;
else {
if (QAQ[j] < QwQ[l]) ret -= 200;
--j, ++l;
}
}
}
printf("%d
", ret);
}
return 0;
}

M. DotA

題意：你有一個血量無限的大哥，dps是 .然後有若干血量是，dps是的英雄，問你把他們全部擊殺最少受到的攻擊是多少

題解：嘗試按照各種方法排序以後發現是要優先處理血量少攻擊大的英雄

#include <cstdio> #include <cstring> #include <algorithm> #define N 220 #define INF 0x3f3f3f3f using namespace std; struct DotA { int hp, dps; DotA() {} DotA(const int& hp, const int& dps) : hp(hp), dps(dps) {} } h[N]; struct cmp { inline bool operator () (const DotA& h1, const DotA& h2) const { return 1.0 * h1.dps / h1.hp > 1.0 * h2.dps / h2.hp; } };

int n;

int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d", &n) == 1) {
long long atk = 0;
for (int i = 1, hp, dps; i <= n; ++i)
scanf("%d%d", &dps, &hp), h[i] = DotA(hp, dps), atk += dps;;
sort(h + 1, h + n + 1, cmp()); long long ret = 0;
for (int i = 1; i <= n; ++i)
ret += 1LL * h[i].hp * atk, atk -= h[i].dps;
printf("%lld
", ret);
}
return 0;
}

一個寫成了 WA了八發，不愧是罰時隊的隊員……

N. 過河

題意：《一本通》上經典的過河問題

題解：好難啊p_q，樣例都看不懂……看了網上的解釋是要考慮最快的人和第二快的人那個方法更優……貪心果然像數學歸納法一樣玄學

#include <cstdio> #include <cstring> #include <algorithm> #define N 1010 #define INF 0x3f3f3f3f using namespace std;

int T, n, a[N];

inline int dfs(int n) {
if (n == 2) return a[2];
if (n == 3) return a[1] + a[2] + a[3];
int ret = 0;
for (int i = 2; i <= n; ++i) ret += a[i];
return min(ret + a[1] * (n - 2), a[1] + (a[2] << 1) + a[n] + dfs(n - 2));
}

int main()
{
//freopen("test.in", "r", stdin);
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
sort(a + 1, a + n + 1);
printf("%d
", n == 1 ? a[1] : dfs(n));
}
return 0;
}

O. Wooden Sticks

題意：有若干木棍，對於木棍，如果後者的長度和質量都大於前者，兩根木棍可以一起切。切一根木棍要花費一個單位時間，問最少的時間

題解：把木棍從小到大排序，對於每一根木棍，把能和它一起切的找到，否則就把它加進需要切割的木棍裏

upd：代碼放錯了，白天再補

#include <cstdio> #include <cstring> #include <algorithm> #define N 1010 #define INF 0x3f3f3f3f using namespace std;

int T, n, a[N];

P. NOIP2012國王遊戲

【P1080】國王遊戲 - 洛谷?

www.luogu.org

這個題通過嘗試以後是按照從小到大排序。聽說要寫高精度，就沒做了（逃

ACM Training Record - Always_Penalty

0. 綜述

A. Clean Shift

B. 今年暑假不AC

C. Highway

D. Subsequence

E. 4 Values whose Sum is 0

F. 校門外的樹

G. Overlapping Squares

I. Unique Snowflakes

J. Moving Tables

K. FatMouse Trade

L. 田忌賽馬

M. DotA

N. 過河

O. Wooden Sticks

P. NOIP2012國王遊戲

熱門新聞

週熱門

ACM Training Record - Always_Penalty

0. 綜述

A. Clean Shift

B. 今年暑假不AC

C. Highway

D. Subsequence

E. 4 Values whose Sum is 0

F. 校門外的樹

G. Overlapping Squares

I. Unique Snowflakes

J. Moving Tables

K. FatMouse Trade

L. 田忌賽馬

M. DotA

N. 過河

O. Wooden Sticks

P. NOIP2012國王遊戲

大學期間有必要參加ACM競賽等競賽嗎？

入門機器學習想要做題。有哪些習題網站/書籍（除了西瓜書）呢？

如何以最簡捷的方法求出兩個數之間的素數個數?

能否在O(nlogn)時間內實現大數的進位轉換？

【演算法】AC自動機

一文讓你徹底明白馬拉車演算法

大學四年，計算機類專業大神，可以達到什麼水平？

傅裏葉變換（三） 採樣與離散序列

77. Combinations

60. Permutation Sequence

2018 ACM博士論文獎公佈：伯克利博士獲獎，清華姚班馬騰宇榮譽提名

如何評價CSP J1/S1 2019?

NOIP省一大概是什麼水平？

想學信息學競賽，有什麼好的建議嗎？

2019年還辦noip嗎？

熱門新聞

週熱門

傅裏葉變換（三）採樣與離散序列