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

2020牛客暑期多校训练营(第二场)

Posted by GJ on July 13, 2020

两题 DCHJ FQZW CCHJ&YC

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 , 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

先每行单调队列滑动窗口,求出每k个的最大值,可以得到一个 $n \times (m-k+1)$的矩阵

再每列单调队列滑动窗口,求出每k个的最大值,直接把最大值加起来就好啦

标答题解:

20200713_F

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 && i - que[head] >= k) head++;
		while (tail >= head && a[i] > a[que[tail]]) tail--;
		tail++;
		que[tail] = i;
		ans += a[que[head]];
	}
}

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 && i - que[head] >= k) head++;
		while (tail >= head && a[i] > a[que[tail]]) tail--;
		tail++;
		que[tail] = i;
		mp[v][i - k + 1] = a[que[head]];
	}
	mp[v][m] = 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

无根树,所以选取一根

按dfs序对叶子节点进行排序,然后匹配 $i$ 与 $(叶子节点个数)/2+i-1$

叶子节点个数%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;
        add(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

就2000个点,那么,$n^2$复杂度得到每两点与原点组成的圆的圆心与半径,使用pair记录圆心与半径,并mp<pair<double,bouble»记录个数(懂了吧懂了吧(圆心和半径手算一下就行(懂了吧懂了吧(都除了的数就装作都不用除好啦为了精度(懂了吧懂了吧

坑点大概在于精度啥的

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;
}

J Just Shuffle

没有看懂标答题解(但是学弟事后补了(那就等学弟补完趴(嘿嘿嘿