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吗？

热门新闻

周热门

傅里叶变换（三）采样与离散序列