# 『ACM-XCPC』2020暑期ZJNU组队训练2

## 2020牛客暑期多校训练营（第二场）

Posted by GJ on July 13, 2020

## D Duration

Description

Given two moments on the same day in the form of HH:MM:SS, print the number of seconds between the two moments.

Input

Input two lines each contains a string in the form of $$HH:MM:SS~(00 \leq HH \leq 23, 00 \leq MM,SS \leq 59)$$, denoting a given moment.

Output

Only one line containing one integer, denoting the answer.

Sample Input 1

12:00:00
17:00:00


Sample Output 1

18000


Sample Input 2

23:59:59
00:00:00


Sample Output 2

86399


Solution

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 5e3 + 10;
const ll mod = 998244353;
string s, t;

int main() {
O_O;
cin >> s >> t;
int a=0, b=0;
int flag = 1;
for (int i = 6; i < s.length(); i -= 3) {
a += flag * ((s[i] - '0') * 10 + s[i + 1] - '0');
b += flag * ((t[i] - '0') * 10 + t[i + 1] - '0');
flag *= 60;
}
cout << abs(a - b) << "\n";
return 0;
}



## F Fake Maxpooling

Description

Given a matrix of size $n\times m$ and an integer ${k}$, where $A_{i,j} = lcm(i, j)$, the least common multiple of ${i}$ and ${j}$. You should determine the sum of the maximums among all $k\times k$ submatrices.

Input

Only one line containing three integers $n,m,k~(1\leq n,m \leq 5000, 1 \leq k \leq \min{n, m})$.

Output

Only one line containing one integer, denoting the answer.

Sample Input

3 4 2


Sample Output

38


Tips

The given matrix is: 1 2 3 4 2 2 6 4 3 6 3 12 The maximums among all $2\times 2$ submatrices are ${2, 6, 6, 6, 6, 12}$ respectively, and their sum is ${38}$.

Solution

Code

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 5e3 + 10;
const ll mod = 998244353;
ll mp[maxn][maxn], que[maxn], a[maxn];
int n, m, k;
ll ans = 0;

ll gcd(ll x, ll y) {
return x == 0 ? y : gcd(y % x, x);
}

inline void init() {	//这步会超时，能AC是数据够水
for (register ll i = 1; i <= 5000; ++i)
for (register ll j = 1; j <= i; ++j)
mp[j][i] = mp[i][j] = i * j / gcd(i, j);
}

inline void getmaxl() {
int head = 1, tail = 1;
for (int i = 1; i < k; ++i) {
while (tail >= head && a[i] > a[que[tail]]) tail--;
tail++;
que[tail] = i;
}
for (int i = k; i <= n; ++i) {
while (tail >= head && a[i] > a[que[tail]]) tail--;
tail++;
que[tail] = i;
}
}

void getmaxh(int v) {
int head = 1, tail = 1;
for (int i = 1; i < k; ++i) {
while (tail >= head && a[i] > a[que[tail]]) tail--;
tail++;
que[tail] = i;
}
for (int i = k; i <= m; ++i) {
while (tail >= head && a[i] > a[que[tail]]) tail--;
tail++;
que[tail] = i;
mp[v][i - k + 1] = a[que[head]];
}
}

int main() {
O_O;
init();
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i) {
memset(a, 0, sizeof(a));
memset(que, 0, sizeof(que));
for (int j = 1; j <= m; j++) a[j] = mp[i][j];
getmaxh(i);
}
for (int i = 1; i <= m - k + 1; ++i) {
memset(a, 0, sizeof(a));
memset(que, 0, sizeof(que));
for (int j = 1; j <= n; ++j) a[j] = mp[j][i];
getmaxl();
}
cout << ans << "\n";
return 0;
}



## C Cover the Tree

Description

Given an unrooted tree, you should choose the minimum number of chains that all edges in the tree are covered by at least one chain. Print the minimum number and one solution. If there are multiple solutions, print any of them.

Input

The first line contains one integer $n~(1\leq n \leq 2\times10^5)$, denoting the size of the tree. Following ${n-1}$ lines each contains two integers $u,v~(1\leq u < v \leq n)$, denoting an edge in the tree. It’s guaranteed that the given graph forms a tree.

Output

The first line contains one integer ${k}$, denoting the minimum number of chains to cover all edges. Following ${k}$ lines each contains two integers $u,v~(1\leq u,v \leq n)$, denoting a chain you have chosen. Here ${u = v}$ is permitted, which covers no edge.

Sample Input

5
1 2
1 3
2 4
2 5


Sample Output

2
2 3
4 5


Tips

The tree in sample input is:

	1
/ \
2   3
/ \
4   5


It can be shown all edges are covered:

• edges 1 — 2, 1 — 3 are covered by chain 2 → 3
• edges 2 — 4, 2 — 5 are covered by chain 4 → 5

Solution

叶子节点个数%2==1 那么连接根与剩余节点

Code

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n, cnt = 0, nt = 0;
int hd[maxn];
int mp[maxn], vis[maxn];
int dfn[maxn];

struct node { int to, nxt; }edge[maxn << 1];
void add(int p, int q) {
edge[cnt] = { q,hd[p] }; hd[p] = cnt++;
edge[cnt] = { p,hd[q] }; hd[q] = cnt++;
}

void init() {
cnt = 0;
memset(hd, -1, sizeof(hd));
}
vector<int>v;

void dfs(int x,int fa) {
dfn[x]= ++nt;
for (int i = hd[x]; ~i; i = edge[i].nxt) {
int to = edge[i].to;
if (to == fa)continue;
dfs(to, x);
}
}

bool cmp(int a, int b) {
return dfn[a] < dfn[b];
}

int main() {
O_O;
init();
cin >> n;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
mp[a]++, mp[b]++;
}
int root = 1;
for (int i = 1; i <= n; i++) if (mp[i] >= 2) { root = i; break; }
for (int i = 1; i <= n; i++) if (mp[i] == 1) { v.push_back(i); }
dfs(root,-1);
sort(v.begin(), v.end(), cmp);
cout << (v.size() + 1) / 2<<"\n";
for (int i = 0; i < v.size()/ 2; i++)cout << v[i] << " " << v[v.size() / 2 + i] << endl;
if (v.size() % 2) cout << root << " " << v[v.size() -1 ] << "\n";
return 0;
}



## B Boundary

Description

Given ${n}$ points in 2D plane. Considering all circles that the origin point ${(0, 0)}$ is on their boundries, find the one with the maximum given points on its boundry. Print the maximum number of points.

Input

The first line contains one integer $n~(1 \leq n \leq 2000)$, denoting the number of given points. Following ${n}$ lines each contains two integers $x, y~(|x|,|y| \leq 10000)$, denoting a given point ${(x, y)}$. It’s guaranteed that the points are pairwise different and no given point is the origin point.

Output

Only one line containing one integer, denoting the answer.

Sample Input

4
1 1
0 2
2 0
2 2


Sample Output

3


Tips

Considering circle $(x-1)^2+(y-1)^2=2$, we can see that the origin point is on its boundry and that there are 3 given points ${(0,2),(2,0),(2,2)}$ on its boundry.

Solution

Code

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 5e3 + 10;
const ll mod = 998244353;
int n;
struct node{
double a, b,c;
}ed[maxn];
map<pair<double,double>, ll>p;
ll maxx = 0;

int main() {
O_O;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> ed[i].a >> ed[i].b;
ed[i].a*=2;
ed[i].b*=2;
ed[i].c = -(ed[i].a * ed[i].a + ed[i].b * ed[i].b);
}
for (int i = 1; i <= n; i++) {
p.clear();
for (int j = i + 1; j <= n; j++) {
double d = ed[i].a * ed[j].b - ed[i].b * ed[j].a;
if (d == 0) continue;
double x = ed[j].c * ed[i].b - ed[i].c * ed[j].b;
double y = ed[j].c * ed[i].a - ed[i].c * ed[j].a;
ll num = ++p[{(x*1.0/d),(y*1.0/d)}];
maxx = max(maxx, num);
}
}
cout << maxx+1 << "\n";
return 0;
}