2020-12-02

2019 JUST Programming Contest

字数统计: 4k字 | 阅读时长: 22分

solved	A	B	C	D	E	F	G	H	I	J	K	L
12 / 12	Ø	O	O	O	O	O	O	O	O	O	Ø	Ø

O：比赛时通过
Ø：赛后通过
!：比赛时尝试了未通过
·：比赛时未尝试

REPLY：

A题的RE戴了太久太久的痛苦面具，最后发现是板子的缺陷也算是有收获吧，至少更正了板子

比赛链接

A - On the Road to Happiness

solved by lllllan. (-)

题意： 要求将所有字符 $A$ 分别移动到所有字符 $H$ 的位置【一个 $A$ 对应一个 $H$ 】。在给定的无向图中，边 $u$ -> $v,w$ 表示可以将字符 $s_u$ 与字符 $S_v$ 交换并花费 $w$ 的费用。现在有了魔法棒，在交换字符的时候可以只花费割边的费用。求最小的总花费。

题解： 既然花费只针对割边，那么就通过tarjan对边双进行缩点。缩点之后记录每个节点的度数【节点含字符 $A$ 度数-1，含字符 $H$ 度数+1——同一个边双内的 $A$ 和 $H$ 可以自行消耗而不需要任何花费】。题目保证了图中没有孤立点，则可以从某个节点出发进行深搜【对应代码中的solve部分】，通过度数比较判断是否需要其中割边的花费【以及需要通过多少次这条割边】。

问题： 原来的tarjan缩点模板提交之后RE了，最后改了其中的dfs部分才能通过。【原来的缩点之后的编号并不连续，但是【应该】不会超出数据范围，总之就是RE，想不明白】

AC代码

#include<bits/stdc++.h>
using namespace std;
#define pII pair<int, int>
#define fi first
#define se second

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;

ll ans;
char s[N];
int _T, n, m;
int top, sta[N];
int tot, blo[N], deg[N];
int idx, low[N], dfn[N];
int cnt, head[N];
struct edge { int v, w, next;} e[N << 2];
vector<pII> G[N];

void addedge (int u, int v, int w) {
	e[++cnt] = {v, w, head[u]}; head[u] = cnt;
	e[++cnt] = {u, w, head[v]}; head[v] = cnt;
}

void init () {
	ans = top = tot = idx = cnt = 0;
	for (int i = 0; i < N; ++i) {
		G[i].clear();
		deg[i] = low[i] = dfn[i] = head[i] = 0;
	}
}

void dfs (int u, int fa) {
	sta[++top] = u;
	low[u] = dfn[u] = ++idx;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (!low[v]) {
			dfs(v, u);
			low[u] = min(low[u], low[v]);
		} else if (v != fa) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		++tot;
		int k;
		do {
			k = sta[top--];
			blo[k] = tot;
		} while (k != u);
	}
}

void tarjan () {
	for (int i = 1; i <= n; ++i) if (!low[i]) dfs(i, 0);
	for (int u = 1; u <= n; ++u) {
		for (int i = head[u]; i; i = e[i].next) {
			int v = e[i].v, w = e[i].w;
			if (blo[u] == blo[v]) continue;
			G[blo[u]].push_back({blo[v], w});
        }
	}
}

int solve (int u, int fa) {
	int num = deg[u];
	for (auto pii : G[u]) {
		int v = pii.fi, w = pii.se;
        if (v == fa) continue;
		int k = solve(v, u);
		num += k;
		ans += ll(abs(k)) * w;
    }
	return num;
}

void run () {
	init ();
	scanf("%d%d%s", &n, &m, s + 1);
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		addedge(u, v, w);
	}
	tarjan();
	for (int i = 1; i <= n; ++i) {
		if (s[i] == 'A') deg[blo[i]]--;
		if (s[i] == 'H') deg[blo[i]]++;
	}
	solve(1, 0);
	printf("%lld\n", ans);
}

int main () {
	scanf("%d", &_T);
	while (_T--) run();
    return 0;
}

B - Memory Management System

Solved by Tryna & Sstee1XD. 2:52(+3)

题意： 给你一段序列，已知其中一段序列的占用情况，每次询问输出最右边的一段没被占用的长度为 $k$ 的区间位置。

题解： 前面短的长度会被后面长的长度覆盖，所以我们从后往前寻找长度，如果之前有更大的长度出现了，就不用加入答案的考虑范围。因为询问次数较大，我们考虑在set里进行二分。

AC代码

#include<bits/stdc++.h>
using namespace std;

#define S_IT set<Node>::iterator
#define endl "\n"
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {	cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);}

inline int rd () {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n, m, q, mp[maxn], l, r, k;

struct Node{
	int v, r;
	Node () {}
	Node (int v, int r = 0) : v(v), r(r) {}
	bool operator < (const Node & a)const {
		return v < a.v;
	}
};

set<Node> st;

void gao(){
	S_IT it;
	for(int i = m; i >= 1; i--){
		if(mp[i] == 0) {
			int v = 0;
			int r = i;
			while (mp[i] == 0 && i >= 1) {
				v++;
				i--;
			}
			i++;
			it = st.lower_bound(Node(v));
			if (it == st.end()) {
				st.insert(Node(v, r));
			}
		}
	}
}

void run () {
	st.clear();
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i <= m; i++){
		mp[i] = 0;
	}
	while(n--){
		scanf("%d%d", &l, &r);
		for(int i = l; i <= r; i++) mp[i] = 1;
	}
	gao();
	while(q--){
		scanf("%d", &k);
		S_IT it = st.lower_bound(Node(k));
		if (it == st.end()) {
			printf("-1 -1\n");
		}
		else printf("%d %d\n", it->r - k + 1, it->r);
	}
}

int main () {
	int _T;
	_T = rd();
	while (_T--) run();
    return 0;
}

C - Large GCD

solved by Tryna. 0:38(+)

题解： 找一下规律发现n或m为偶数时答案为2，其余情况为12

AC代码

#include<bits/stdc++.h>
using namespace std;
int t, n, m;
void run () {
	scanf("%d", &t);
	while(t--){
		scanf("%d%d", &n, &m);
		if(n % 2 == 0 || m % 2 == 0) puts("2");
		else puts("12");
	}
}
 
int main () {
	run();
    return 0;
}

D - XOR Permutations

Solved by Tryna & Sstee1XD. 1:47(+5)

题意： 给你三个 $01$ 字符串，对于同一个字符串，可以任意交换两个元素的位置，问最终三个 $01$ 串异或的最大值。

题解： 我们算出三个 $01$ 串的 $1$ 的个数，然后考虑后面两个 $01$ 串异或后的 $1$ 的个数，然后再与第一个 $01$ 串一起处理。注意后两个 $01$ 串异或后的 $1$ 的个数应以 $2$ 为单位进行增长。

AC代码

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define endl "\n"
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {	cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);}

inline int rd () {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

typedef long long ll;
const int inf = 0x3f3f3f3f;
char s[30];
int a[4];
void run () {
	int cnt = 0;
	int tot = 0;
	for (int i = 1; i <= 3; ++i) {
		scanf("%s", s);
		cnt = 0;
		for (int j = 0; j < strlen(s); ++j) {
			cnt += s[j] - '0';	
		}
		a[i] = cnt;
	}
	int l = abs(a[2] - a[3]);
	int r = min(a[2] + a[3], 20 - a[2] - a[3]);
	for (int i = l; i <= r; i += 2) {
		int tmp = a[1] + i;
		if (tmp > 10) tmp = 20 - tmp;
		tot = max(tmp, tot);
	}
	for (int i = 1; i <= 10; ++i) {
		if (tot) {
			putchar('1');
			tot--;
		}
		else putchar('0');
	}
	puts("");
}

int main () {
	int _T = rd();
	while (_T--) run();
    return 0;
}

E - Building Strings

Solved by lllllan. 0:25(+)

题意： 求一个字符串在特定字符串中的最小权值和。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"

int _T, n, m;
string a, b, c;
void run () {
	map<char, int> mp;
	cin >> n >> m >> a >> b >> c;
	for (int i = 0; i < n; i++) {
		if (mp[a[i]]) mp[a[i]] = min(mp[a[i]], b[i] - '0' + 1);
		else mp[a[i]] = b[i] - '0' + 1;	// 不确定值是否会有0的情况，索性都加上1避免
	}
	int ans = 0;
	for (int i = 0; i < m; i++) {
		if (mp[c[i]] == 0) {
			ans = -1;
			break;
		}
		ans += mp[c[i]] - 1;
	}
	cout << ans << endl;
}

int main () {
	cin >> _T;
	while (_T--) run();
    return 0;
}

F - camelCase

solved by Tryna. 0:11(+)

题解： 判断首字母不能大写并且大写字母必须少于等于6个

AC代码

#include<bits/stdc++.h>
using namespace std;
int t;
string st;
void run () {
	cin>>t;
	while(t--){
		cin>>st;
		if(st[0] >= 'A' && st[0] <= 'Z'){
			puts("NO");
			continue;
		}
		int sum = 0;
		for(auto it : st){
			if(it >= 'A' && it <= 'Z') sum++;
		}
		if(sum <= 6) puts("YES");
		else puts("NO");
	}
}
 
int main () {
	run();
    return 0;
}

G - The Special King

solved by Tryna. 0:03(+)

题解： 求曼哈顿距离

AC代码

#include<bits/stdc++.h>
using namespace std;
int t, x1, x2, y1, y2; 
void run () {
	scanf("%d", &t);
	while(t--){
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		int sum = abs(x1 - x2) + abs(y1 - y2);
		printf("%d\n", sum);
	}
}
 
int main () {
	run();
    return 0;
}

H - The Universal String

Solved by Sstee1XD. 0:08(+)

题解： 判断一个字符串是不是以 $26$ 个字母的顺序循环。

AC代码

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define endl "\n"
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {	cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);}

inline int rd () {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 7;
char s[maxn];
void run () {
	scanf("%s", s);
	int nxt = s[0];
	for (int i = 0; i < strlen(s); ++i) {
		if (s[i] != nxt) {
			puts("NO");
			return;
		}
		nxt++;
		if (nxt > 'z') nxt = 'a';
	}
	puts("YES");
}

int main () {
	int _T;
	_T = rd();
	while (_T--) run();
    return 0;
}

I - Array Negations

Solved by Sstee1XD. 0:19(+)

题解： 正负分开sort一下，记录一下最小的绝对值，分情况处理一下。

AC代码

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define endl "\n"
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {	cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);}

inline int rd () {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e4 + 7;
int n, k;
int a[maxn], f;
int minn, sum;
void run () {
	n = rd();
	k = rd();
	f = 0;
	minn = inf;
	sum = 0;
	int t;
	for (int i = 1; i <= n; ++i) {
		t = rd();
		if (t < 0) {
			a[++f] = t;
		}
		else sum += t;
		minn = min(minn, abs(t));
	}
	sort(a + 1, a + 1 + f);
	if (f == 0) {
		if (k & 1)
		sum -= minn * 2;
	}
	else if (f >= k) {
		for (int i = 1; i <= k; ++i) {
			sum -= a[i];
		}
		for (int i = k + 1; i <= f; ++i) {
			sum += a[i];
		}
	}
	else {
		for (int i = 1; i <= f; ++i) {
			sum -= a[i];
		}
		k -= f;
		if (k & 1) sum -= minn * 2;
	}
	printf("%d\n", sum);
}

int main () {
	int _T;
	_T = rd();
	while (_T--) run();
    return 0;
}

J - Grid Beauty

Solved by lllllan. 0:36(+)

AC代码

#include<bits/stdc++.h>
using namespace std;
inline int rd () {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

const int N = 1e3 + 10;
map<int, int> mp[N];
void run () {
	for (int i = 0; i < N; i++) mp[i].clear();
	
	int ans = 0;
	int n = rd(), m = rd();
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			int x = rd();
			mp[i][x]++;
			if (mp[i - 1][x]) {
				mp[i - 1][x]--;
				ans++;
			}
		}
	}
	printf("%d\n", ans);
}

int main () {
	int _T = rd();
	while (_T--) run();
    return 0;
}

K - Subarrays OR

Solved by Sstee1XD. (-)

题解： 网上的代码看不懂，自己写了个时间复杂度极高的。用多个set记录每位出现的1的情况，最后都放进一个set里去重。

AC代码

#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define _for(i, a, b) for(int i = (a); i <= (b); ++i)
#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)
void err () {	cout << endl;}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' '; err(args...);}

inline int rd () {
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 7;
set<int> st[40];
int n, a[maxn];
set<int> go, ans;
void run () {
	ans.clear();
	for (int i = 0; i <= 30; ++i) {
		st[i].clear();
	}
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		for (int j = 0; j <= 30; ++j) {
			if ((a[i] >> j) & 1) st[j].insert(i);
		}
	}
	for (int i = 1; i <= n; ++i) {
		go.clear();
		int now = a[i];
		ans.insert(now);
		for (int j = 0; j <= 30; ++j) {
			go.insert(*(st[j].begin()));
			if (*(st[j].begin()) == i) st[j].erase(i);
		}
		for (auto v : go) {
			now |= a[v];
			ans.insert(now);
		}
	}
	printf("%d\n", ans.size());
}

int main () {
	int _T = 1;
	scanf("%d", &_T);
	while (_T--) run();
    return 0;
}

L - Median

Solved by Sstee1XD. (-)

题意： 求所有 $h*w$ 的子矩阵中的中位值的最小值。

题解： 被卡了时间复杂度较高的方法。我们考虑二分答案，对于矩阵里的值大于当前mid值的置 $1$ ，其余置 $0$ ，用二维前缀和去维护每个子矩阵中大于当前mid值的个数。当前mid值在别的子矩阵里是中位值的话，也是不合法的情况。

AC代码

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
typedef long long ll;
const int maxn = 1e3 + 7;
int n, m, h, w;
int a[maxn][maxn], pre[maxn][maxn];

bool in(int i, int j, int x, int y) {
    if (i >= x && i - h < x && j >= y && j - w < y) return true;
    return false;
}

bool check(int v) {
    int x, y;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i][j] > v) pre[i][j] = 1;
            else pre[i][j] = 0;
            pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
            if (a[i][j] == v) x = i, y = j;
        }
    }
    for (int i = h; i <= n; ++i) {
        for (int j = w; j <= m; j++) {
            int tmp = pre[i][j] - pre[i - h][j] - pre[i][j - w] + pre[i - h][j - w];
            if (!in(i, j, x, y)) {
                if (tmp == h * w / 2) return false;
            }
            if (tmp < h * w / 2) {
                return false;
            }
        }
        
    }
    return true;
}
void solve() {
    cin >> n >> m >> h >> w;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    int ans;
    int l = 1, r = 1000000, mid;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _T = 1;
    // cin >> _T;
    while (_T--) solve();
}