2018 Multi-University Training Contest 1 Solution(Updating)
(还是因为*qi说要补题)
2018 Multi-University Training Contest 1 Solution
如果排版不好请看原题6298~6308
↑没有↑,我全是乱讲的
A.Maximum Multiple
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
Given an integer n, Chiaki would like to find three positive integers , and such that: and is maximum.
Input
There are multiple test cases. The first line of input contains an integer , indicating the number of test cases. For each test case:
The first line contains an integer .
Output
For each test case, output an integer denoting the maximum . If there no such integers, output instead.
Sample Input
3
1
2
3
Sample Output
-1
-1
1
由
得(绝对不选)
所以尽量取积最大的
还有不要忘记开long long
#include <cstdio>
using namespace std;
typedef long long LL;
int main() {
LL t;
scanf("%lld", &t);
while (t--) {
LL n;
scanf("%lld", &n);
if (n % 3 == 0) printf("%lld\n", n * n * n / 27);
else if (n % 4 == 0) printf("%lld\n", n * n * n / 32);
else printf("-1\n");
}
return 0;
}
B.Balanced Sequence
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
Chiaki has n strings s1,s2,…,sn consisting of (
and )
. A string of this type is said to be balanced:
- if it is the empty string
- if A and B are balanced, AB is balanced,
- if A is balanced, (A) is balanced.
Chiaki can reorder the strings and then concatenate them get a new string t. Let f(t) be the length of the longest balanced subsequence (not necessary continuous) of t. Chiaki would like to know the maximum value of f(t) for all possible t.
Input
There are multiple test cases. The first line of input contains an integer , indicating the number of test cases. For each test case:
The first line contains an integer – the number of strings.
Each of the next n lines contains a string consisting of (
and )
.
It is guaranteed that the sum of all |si| does not exceeds .
Output
For each test case, output an integer denoting the answer.
Sample Input
2
1
)()(()(
2
)
)(
Sample Output
4
2
对于任意一个串,把能匹配的括号都匹配掉之后,最后的形式一定是这样的 )))...)))(((...(((
只需考虑如何连接即可(dls讲的连接方法,详见operator)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;
struct Node{
int a, b;
bool operator <(const Node &y) const {
if (a >= b && y.a < y.b) return 0;
if (a < b && y.a >= y.b) return 1;
if (a >= b && y.a >= y.b) return b > y.b;
return a < y.a;
}
}q[N];
char st[N];
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
int ans = 0;
memset(q, 0, sizeof(q));
for (int i = 1; i <= n; ++i) {
scanf("%s", st);
int len = strlen(st);
for (int j = 0; j < len; ++j){
if (st[j] == '(') q[i].b++;
if (st[j] == ')') {
if (q[i].b > 0) q[i].b--, ans += 2;
else q[i].a++;
}
}
}
sort(q + 1, q + n + 1);
int r = 0;
for (int i = 1; i <= n; ++i) {
if (r < q[i].a) {
ans += r * 2;
r = 0;
}
else {
r -= q[i].a;
ans += q[i].a * 2;
}
r += q[i].b;
}
printf("%d\n", ans);
}
}
C.Triangle Partition
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 132768/132768 K (Java/Others)
Special Judge
Problem Description
Chiaki has 3n points . It is guaranteed that no three points are collinear.
Chiaki would like to construct n disjoint triangles where each vertex comes from the 3n points.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer – the number of triangle to construct.
Each of the next 3n lines contains two integers and .
It is guaranteed that the sum of all n does not exceed .
Output
For each test case, output n lines contain three integers each denoting the indices of points the -th triangle use. If there are multiple solutions, you can output any of them.
Sample Input
1
1
1 2
2 3
3 5
Sample Output
1 2 3
正解是凸包(不会,以后再补):
然而直接按极角排序过了,不知道是不是正解(还是因为数据太水)
#include<cstdio>
#include<algorithm>
#define N 3010
#define INF 1000000001
using namespace std;
typedef long long LL;
struct Node {
LL x, y, id;
}po[N];
bool cmp(Node x,Node y) {
return x.y * y.x < y.y * x.x;//极角排序
}
int main() {
LL t;
scanf("%lld", &t);
while(t--) {
LL n;
scanf("%lld", &n);
n *= 3;
for (LL i = 1; i <= n; ++i) {
scanf("%lld%lld", &po[i].x, &po[i].y);
po[i].x += INF;
po[i].y += INF;
po[i].id = i;
}
sort(po + 1, po + n + 1, cmp);
for(LL i = 1; i * 3 <= n; ++i)
printf("%lld %lld %lld\n", po[i * 3 - 2].id, po[i * 3 - 1].id, po[i * 3].id);
}
return 0;
}
D.Distinct Values
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
Chiaki has an array of n positive integers. You are told some facts about the array: for every two elements ai and aj in the subarray , holds.
Chiaki would like to find a lexicographically minimal array which meets the facts.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and m – the length of the array and the number of facts. Each of the next m lines contains two integers and .
It is guaranteed that neither the sum of all n nor the sum of all exceeds .
Output
For each test case, output n integers denoting the lexicographically minimal array. Integers should be separated by a single space, and no extra spaces are allowed at the end of lines.
Sample Input
3
2 1
1 2
4 2
1 2
3 4
5 2
1 3
2 4
Sample Output
1 2
1 2 1 2
1 2 3 1 1
用set维护从左往右贪心
本来是水题,我写的好丑好丑,调了好久好久
加了金牌选手zzy的卡常头文件才过
这是我的代码:
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <cstdio>
#include <set>
#include <string.h>
#define N 100010
using namespace std;
int be[N], en[N], ans[N], bee[N], enn[N];
set <int> al;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m, l, r;
scanf("%d%d", &n, &m);
memset(be, 0, sizeof(be));
memset(en, 0, sizeof(en));
memset(bee, 0, sizeof(bee));
memset(enn, 0, sizeof(enn));
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &l, &r);
if (l == r) continue;
if (be[l] || en[r]) {
if (be[l]) {
if (bee[l] < r) {
en[bee[l]] = 0;
enn[bee[l]] = 0;
bee[l] = r;
en[r] = i;
be[l] = i;
enn[r] = l;
}
continue;
}
else {
if (en[r] > l) {
be[enn[r]] = 0;
bee[enn[r]] = 0;
enn[r] = l;
be[l] = i;
en[r] = i;
bee[l] = r;
}
continue;
}
}
be[l] = i;
en[r] = i;
bee[l] = r;
enn[l] = l;
}
l = 0;
int cnt = 0;
al.clear();
for (int i = 1; i <= n; ++i)
al.insert(i);
for (int i = 1; i <= n; ++i) {
if (be[i]) {
++cnt;
if (cnt == 1) l = i;
}
if (cnt == 0) ans[i] = 1;
else {
ans[i] = *al.begin();
al.erase(al.begin());
}
if (en[i]) {
--cnt;
if (be[l] == en[i]) {
while (!be[l] || be[l] == en[i]) {
al.insert(ans[l]);
l++;
}
}
}
}
for (int i = 1; i < n; ++i) {
printf("%d ", ans[i]);
}
printf("%d\n", ans[n]);
}
return 0;
}
下面是简洁明了又不会TLE的美丽标程:
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
int main() {
int T;
scanf("%d", &T);
for (int cas = 1; cas <= T; ++cas) {
int n, m;
scanf("%d%d", &n, &m);
std::vector<int> ends(n, -1);
for (int i = 0; i < n; ++i) ends[i] = i;
for (int i = 0; i < m; ++i) {
int l, r;
scanf("%d%d", &l, &r);
ends[l - 1] = std::max(ends[l - 1], r - 1);
}
std::set<int> unused;
for (int i = 1; i <= n; ++i) {
unused.insert(i);
}
std::vector<int> ret(n);
int l = 0, r = -1;
for (int i = 0; i < n; ++i) {
if (r >= ends[i]) continue;
while (l < i) {
unused.insert(ret[l++]);
}
while (r < ends[i]) {
ret[++r] = *unused.begin();
unused.erase(ret[r]);
}
}
for (int i = 0; i < n; ++i) {
if (i) putchar(' ');
printf("%d", ret[i]);
}
puts("");
}
return 0;
}
我太蒻了
K.Time Zone
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
Chiaki often participates in international competitive programming contests. The time zone becomes a big problem.
Given a time in Beijing time (), Chiaki would like to know the time in another time zone s.
Input
There are multiple test cases. The first line of input contains an integer , indicating the number of test cases. For each test case:
The first line contains two integers a, b (0≤a≤23,0≤b≤59) and a string s in the format of “”, “”, “”, or “” .
Output
For each test, output the time in the format of (-hour clock).
Sample Input
3
11 11 UTC+8
11 12 UTC+9
11 23 UTC+0
Sample Output
11:11
12:12
03:23
简单的模拟,注意头是0的情况即可
#include <cstdio>
#include <cmath>
const int day = 1440;
int h, m, delta, bj, res, resh;
double t;
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d %d UTC%lf", &h, &m, &t);
t -= 8;
delta = floor(t * 60 + 0.1);
bj = h * 60 + m;
res = bj + delta;
if (res >= day) res -= day;
if (res < 0) res += day;
resh = res / 60, res %= 60;
if (resh < 10) putchar('0');
printf("%d:", resh);
if (res < 10) putchar('0');
printf("%d\n", res);
}
return 0;
}
推荐阅读
-
HDU 6038 Function(找规律)——2017 Multi-University Training Contest - Team 1
-
2018 Multi-University Training Contest 6 Werewolf(hdu6370 基环内向树)
-
2018 Multi-University Training Contest 6--HDU 6370 Werewolf(dfs+并查集)
-
2018 Multi-University Training Contest 3 C Dynamic Graph Matching(hdu 6321)(状压dp)
-
2018 Multi-University Training Contest 4 B Harvest of Apples(hdu 6333)(莫队)
-
2018 Multi-University Training Contest 7 1011 Swordsman
-
2018 Multi-University Training Contest 1
-
2018 Multi-University Training Contest 7 1010
-
2018 Multi-University Training Contest 4: B. Harvest of Apples(分块打表)
-
2018 Multi-University Training Contest 1 Solution(Updating)