2020-10-17

The 17th Zhejiang Provincial Collegiate Programming Contest

字数统计: 2.6k字 | 阅读时长: 14分

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

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

REPLY ：由于自己的读题失误给队友造成了很大的麻烦，抱歉。-Sstee1XD

比赛链接

A. AD 2020

solved by Tryna & Sstee1XD. 1:44(+1)

题意给你起始日期和终止日期，问你其中有多少个日期构成的字符串中包含202。

题解预处理下前缀和，然后处理下边边角角。

AC代码

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

#define endl "\n"

int num[10005], y1, m1, d1, y2, m2, d2;

int checkY(int y) {
    if (y / 1000 == 2 && y / 100 % 10 == 0 && y / 10 % 10 == 2) return 1;
    if (y / 100 % 10 == 2 && y / 10 % 10 == 0 && y % 10 == 2) return 1;
    return 0;
}

int checkLeap(int y) {return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0;}

void init() {
    for (int i = 2000; i <= 9999; ++i) {
        if (checkY(i)) {
            num[i] = 365 + checkLeap(i);
        }
        else if (i % 10 == 2) num[i] = 29 + checkLeap(i);
        else num[i] = 2;
        num[i] += num[i - 1];
    }
}

int add(int y, int m, int d) {
    int res = 0;
    if (checkY(y)) {
        for (int i = 1; i < m; ++i) {
            if (i == 1 || i == 3 || i == 5 || i == 7 || i == 8 || i == 10) res += 31;
            else if (i == 2) res += 28 + checkLeap(y);
            else res += 30;
        }
        res += d;
        return res;
    }
    if (y % 10 == 2) {
        if (m > 2) res += 28 + checkLeap(y);
        if (m == 2) res += d;
        if (m == 12) res += (d >= 2);
        return res;
    }
    if (m > 2) res += 1;
    if (m == 2) res += (d >= 2);
    if (m == 12) res += (d >= 2);
    return res;
}

void solve() {
    int ans = 0;
    cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2;
    ans = num[y2 - 1] - num[y1 - 1];
    ans += add(y2, m2, d2) - add(y1, m1, d1);
    if (checkY(y1) || (y1 % 10 == 2 && m1 == 2) || (m1 == 2 && d1 == 2) || (m1 == 12 && d1 == 2)) ans += 1;
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    init();
    int _T;
    cin >> _T;
    while (_T--) solve();
    return 0;
}

B. Bin Packing Problem

solved by Sstee1XD. (-)

题意：给你 $n$ 个物品和它们的体积，还有容量为 $C$ 的集装箱，要求按它给你的顺序放在集装箱里。现有两种方案。

第一种：每次在现有的集装箱里从左到右扫一遍，放到第一个能放进去的集装箱里，如果没有则在最右边加一个集装箱放。
第二种：每次在现有的集装箱里选择剩余容量最接近当前物品的集装箱，如果没有则在最右边加一个集装箱放。

输出两种方案下使用集装箱的数量。

题解：对于两种方案来说，遍历肯定会超时。对于第一种方案，因为要找能放下的最左边的箱子，所以用线段树来维护区间最大值，每次都优先去左子树。
对于第二种方案，我们要找容量大于等于当前物品体积且最接近的集装箱，很容易想到去二分顺序排列的容器来实现。为了实现有序，选择用multiset来存储数据，比在 $set$ 里用结构体会方便很多。

AC代码

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

#define endl "\n"

const int maxn = 1e6 + 7;

int n, c, ans, a[maxn];
multiset<int> st;

struct SEG{
	int t[maxn << 2];

	void up(int id) {
		t[id] = max(t[id << 1], t[id << 1 | 1]);
	}

	void build(int id , int l , int r) {
		t[id] = c;
		if (l == r) return;
		int mid = l + r >> 1;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid + 1,  r);
	}

	void modify(int id, int l, int r, int v) {
		if (l == r) {
			if (t[id] == c) ans++;
			t[id] -= v;
			return;
		}
		int mid = l + r >> 1;
		if (t[id << 1] >= v) modify(id << 1, l, mid, v);
		else modify(id << 1 | 1, mid + 1, r, v);
		up(id);
	}
}seg;

void solve() {
	cin >> n >> c;
	ans = 0;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	seg.build(1, 1, n);
	for (int i = 1; i <= n; ++i) {
		seg.modify(1, 1, n, a[i]);
	}
	st.clear();
	multiset<int> :: iterator it;
	st.insert(c - a[1]);
	for (int i = 2; i <= n; ++i) {
		it = st.lower_bound(a[i]);
		if (it == st.end()) {
			st.insert(c - a[i]);
			continue;
		}
		int v = *it - a[i];
		st.erase(it);
		st.insert(v);
	}
	cout << ans << " " << st.size() << endl;
}

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

C. Crossword Validation

solved by SsteelXD. (-)

题意：给你一个 $n * n$ 的矩阵和m个单词以及单词的权值，问矩阵中横着和竖着的，有#隔开的极长单词是否都在给你 $m$ 个单词中出现过，以及它们的权值和是多少。

题解：用字典树来记录 $m$ 个单词以及它们的权值，之后遍历矩阵查找。

AC代码

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

typedef long long ll;

const int maxn=4e6+10;

char maps[1010][1010], tmp[1010];
int n, m;

struct Trie {
    struct node {
        int nx[26];
        int v;
        int cnt;
        void init() {
            memset(nx, -1, sizeof nx);
            v = 0;
            cnt = 0;
        }    
    }t[maxn];
    int root, tot;
    int newnode() {
        ++tot;
        t[tot].init();
        return tot;
    }
    void init() {
        tot = 0;
        root = newnode();
    }
    void insert(char *s, int v) {
        int len = strlen(s);
        int now = root;
        for (int i = 0; i < len; ++i) {
            if (t[now].nx[s[i] - 'a'] == -1) {
                t[now].nx[s[i] - 'a'] = newnode();
            }
            now = t[now].nx[s[i] - 'a'];
        }
        t[now].v += v;
        t[now].cnt++;
    }
    int query(char *s) {
        int len = strlen(s);
        int now = root;
        for (int i = 0; i < len; ++i) {
            int ch = s[i] - 'a';
            if (t[now].nx[ch] == -1) return -1;
            now = t[now].nx[ch];
        }
        if (t[now].cnt == 0) return -1;
        return t[now].v;
    }
}trie;


ll gao() {
    ll res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int len = 0;
            if (maps[i][j] == '#') continue;
            while (maps[i][j] != '#' && j <= n) {
                tmp[len++] = maps[i][j++];
            }
            tmp[len] = 0;
            ll now = trie.query(tmp);
            if (now == -1) return -1;
            res += now;
        }
    }
    for (int j = 1; j <= n; ++j) {
        for (int i = 1; i <= n; ++i) {
            int len = 0;
            if (maps[i][j] == '#') continue;
            while (maps[i][j] != '#' && i <= n) {
                tmp[len++] = maps[i++][j];
            }
            tmp[len] = 0;
            ll now = trie.query(tmp);
            if (now == -1) return -1;
            res += now;
        }
    }
    return res;
}

void solve() {
    trie.init();
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%s", maps[i] + 1);
    for (int i = 1, v; i <= m; ++i) {
        scanf("%s %d", tmp, &v);
        trie.insert(tmp, v);
    }
    printf("%lld\n", gao());
}

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

E. Easy DP Problem

sloved by Tryna. (-)

题解: 根据dp公式，容易得出最后的答案为 $\sum_{i=1}^{r-l+1} i^2$ + 前k大之和，前面一个平方和为 $n * (n + 1) * (2n + 1) / 6$ ，后面前k大之和可以用主席树维护

AC代码

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
const int N = 1e5 + 10;
int a[N], t, n, q;
vector<int> v;
int cnt, root[N];
 
struct Node {
    int l, r;
    ll sum;
    int num;
    int val;
}hjt[N * 40];
 
int getid(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; }
 
void insert(int pre, int &now, int l, int r, int p, int val) {
    now = ++cnt;
    hjt[now] = hjt[pre];
    hjt[now].num++; hjt[now].sum += val;
    if(l == r) {
        hjt[now].val = val;
        return ;
    }
    int m = (l + r) >> 1;
    if(p <= m) insert(hjt[pre].l, hjt[now].l, l, m, p, val);
    else insert(hjt[pre].r, hjt[now].r, m + 1, r, p, val);
}
 
ll query(int L, int R, int l, int r, int k) {
    if(l == r) return hjt[R].val * k;
    int m = (l + r) >> 1;
    int tmp = hjt[hjt[R].r] .num - hjt[hjt[L].r].num;
    if(k <= tmp) return query(hjt[L].r, hjt[R].r, m + 1, r, k);
    else return hjt[hjt[R].r].sum - hjt[hjt[L].r].sum + query(hjt[L].l, hjt[R].l, l, m, k - tmp);
}
 
void init(int n) {
    v.clear();
    cnt = 0;
    for(int i = 1;i <= n; i++) {
        scanf("%d",&a[i]);
        v.push_back(a[i]); root[i] = 0;
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}
 
void run() {
	scanf("%d", &n);
	init(n);
	for(int i = 1;i <= n; i++) {
        int t = getid(a[i]);
        insert(root[i - 1], root[i], 1, n, t, a[i]);
    }
	scanf("%d", &q);
	while(q--) {
		int l, r, k;
		scanf("%d%d%d", &l, &r, &k);
		int u = r - l + 1;
		ll ans = query(root[l - 1], root[r], 1, n, k);
		printf("%lld\n", (1ll) * u * (u + 1) * (2 * u + 1) / 6 + ans);
	}
}
 
 
int main(){
	scanf("%d", &t);
	while(t--)
		run();
	return 0;
}

K. Killing the Brute-force

solved by Tryna.00:14(+)

签到题

AC代码

#include<bits/stdc++.h>
using namespace std;    
const double pi = acos((double)(-1));
#define inf 0x3f3f3f3f
#define ll long long
#define eps 1e-8
const int maxn = 1010;
const int mod = 1e9 + 7;
#define endl "\n"
int moven1[10][5] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}}; 
int moven2[10][5] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int t, n, a[maxn], b[maxn];  
int main(){
	// ios::sync_with_stdio(false);
    // cin.tie(0);cout.tie(0);
    scanf("%d", &t);
    while(t--){
        scanf("%d",&n);
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            a[i] = a[i] * 3;
        }
        int p = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d", &b[i]);
            if(p) continue;
            if(a[i] < b[i]) p = i;
        }
        if(p) printf("%d\n", p);
        else printf("-1\n");
    }
	return 0;
}

I.Invoking the Magic

solved by lllllan.01:28(+1)

题意： 现有 $n$ 双袜子，但是被混合起来了，即一组袜子中可能是两只不同的袜子。宝宝有魔法能够将 $k$ 组袜子重新匹配，使得这 $k$ 组袜子中相同的袜子分到一起。要求是这 $k$ 组中的袜子必须能够匹配，不能出现单只独一无二的袜子。求能够将所有袜子重新匹配的最小 $k$ 。

题解： 只有 $1e5$ 双袜子，但是袜子的编号却是叛逆的 $2^{30}$ ，所以需要离散化一下，当时的第一反应就是用 $map$ 来重新赋予编号，交一发就直接 $T$ 了嘞。最后靠队友改成了 $unordered\_map$ 就过了.

AC代码

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

int _T, n, a, b, maxsize;
unordered_map<int, int> s, num;

void init() {	maxsize = 0; s.clear(), num.clear();}

int find(int x) {	return s[x] == x ? x : s[x] = find(s[x]);}

void check(int a) {	if(s[a] == 0) { s[a] = a; num[a] = 1;}}

void un(int a, int b) {
	a = find(a), b = find(b);
	if(a == b)	return ;
	s[b] = a, num[a] += num[b];
	if(num[a] > maxsize) maxsize = num[a];
}

void run() {
	init();
	scanf("%d", &n);
	while(n--) {
		scanf("%d%d", &a, &b);
		check(a);
		check(b);
		un(a, b);
	}
	printf("%d\n", maxsize);
}

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