当前位置：网站首页>2020浙江省赛

2020浙江省赛

2022-07-07 07:09:00 【moyangxian】

2020浙江省赛

A - AD 2020 （前缀和）

题意：给出两个日期，问两个日期之间有多少天包含“202”这个子串。

题解：处理一下前缀和即可。

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define pi acos(-1.0)
#define int long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define lowbit(x) ((x)&-(x))
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n"
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;

const int N = 5e6 + 10;
int days[] = {
     0,31,28,31,30,31,30,31,31,30,31,30,31 };
int a[N], cnt;

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

void init() {
    
	for (int y = 2000; y < 10000; y++) {
    
		for (int m = 1; m <= 12; m++) {
    
			int d = days[m];
			if (check(y) && m == 2) d++;
			for (int i = 1; i <= d; i++) {
    
				int x = y * 10000 + m * 100 + i;
				string s = to_string(x);
				//debug(s);
				if (s.find("202") != s.npos) a[++cnt] = x;
			}
		}
	}
}

void solve() {
    
	int y1, m1, d1, y2, m2, d2;
	cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2;
	int x = y1 * 10000 + m1 * 100 + d1;
	int y = y2 * 10000 + m2 * 100 + d2;
	int p1 = lower_bound(a + 1, a + 1 + cnt, x) - a;
	int p2 = upper_bound(a + 1, a + 1 + cnt, y) - a;
	cout << p2 - p1 << endl;
}

signed main() {
    
	IOS
	init();
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}

B - Bin Packing Problem(二分，线段树)

题意：n个物品和它们的题记，按照题目给出两种方法放在容积为c的箱子里，问两个方法下使用箱子的数量。

1、每次放左边第一个能放进去的箱子。没有则在最右边加一个箱子放。

2、每次放箱子剩余容积最接近当前物品的箱子，没有测在最右边加一个箱子放。

题解：
1、用线段树维护区间最大值，每次优先去左子树，相当于二分的思想。

2、在multiset里二分即可。

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define pi acos(-1.0)
#define int long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define lowbit(x) ((x)&-(x))
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n"
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;

const int N = 1e6 + 10;
int n, c, ans;
int a[N];
multiset<int>st;
struct SEG {
    
	int t[N << 2];
	void up(int p) {
     t[p] = max(t[p << 1], t[p << 1 | 1]); }
	void build(int p, int l, int r) {
    
		t[p] = c;
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
	}
	void modify(int p, int l, int r, int v) {
    
		if (l == r) {
    
			if (t[p] == c)ans++;
			t[p] -= v;
			return;
		}
		int mid = (l + r) >> 1;
		if (t[p << 1] >= v)modify(p << 1, l, mid, v);
		else modify(p << 1 | 1, mid + 1, r, v);
		up(p);
	}
}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();
	st.insert(c - a[1]);
	for (int i = 2; i <= n; i++) {
    
		auto p = st.lower_bound(a[i]);
		if (p == st.end()) {
    
			st.insert(c - a[i]);
			continue;
		}
		int v = *p - a[i];
		st.erase(p);
		st.insert(v);
	}
	cout << ans << " " << st.size() << endl;
}

signed main() {
    
	IOS
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}

C - Crossword Validation （字典树）

题意：给出一个n*n的矩阵，问矩阵中所有单词的权值和。

题解：字典树记录一下给出m个单词的权值，然后遍历所有单词总计权值即可。

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define pi acos(-1.0)
//#define int long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define lowbit(x) ((x)&-(x))
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n"
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;

const int N = 1010, M = 4e6 + 10;

char a[N][N], t[N];
int n, m;

struct Trie {
    
	struct Node {
    
		int p[26];
		int v, cnt;
		void init() {
    
			memset(p, -1, sizeof(p));
			v = cnt = 0;
		}
	}t[M];
	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++) {
    
			int c = s[i] - 'a';
			if (t[now].p[c] == -1)
				t[now].p[c] = newNode();
			now = t[now].p[c];
		}
		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 c = s[i] - 'a';
			if (t[now].p[c] == -1) return -1;
			now = t[now].p[c];
		}
		if (t[now].cnt == 0) return -1;
		return t[now].v;
	}
}trie;

void solve() {
    
	trie.init();
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> (a[i] + 1);
	for (int i = 1; i <= m; i++) {
    
		int v;
		cin >> t >> v;
		trie.insert(t, v);
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
    
		for (int j = 1; j <= n; j++) {
    
			int len = 0;
			if (a[i][j] == '#') continue;
			while (a[i][j] != '#' && j <= n) {
    
				t[len++] = a[i][j];
				j++;
			}
			t[len] = 0;
			ll sum = trie.query(t);
			if (sum == -1) {
    
				cout << "-1" << endl;
				return ;
			}
			ans += sum;
		}
	}

	for (int j = 1; j <= n; j++) {
    
		for (int i = 1; i <= n; i++) {
    
			int len = 0;
			if (a[i][j] == '#') continue;
			while (a[i][j] != '#' && i <= n) {
    
				t[len++] = a[i][j];
				i++;
			}
			t[len] = 0;
			ll sum = trie.query(t);
			if (sum == -1) {
    
				cout << "-1" << endl;
				return;
			}
			ans += sum;
		}
	}
	cout << ans << endl;
}

signed main() {
    
	IOS
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}

D

E - Easy DP Problem（主席树前k大之和）

题意：每次取出一个连续子序列进行一次dp，问dp[m][k]的值。

题记：模拟一下样例可知最后答案一定会有1到m的平方和，所有可以把dp方程中的i2先忽略，这样dp方程就变成了一个前k大和的dp方程。用主席树维护前k大和，1到m的平方和可以预处理，吗，每次询问加上即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 9;
int n, q, a[N], rt[N], b[N], m;
struct Data {
    
	int ls, rs, val, siz;
};
struct SegmentTree {
    
	int tot;
	std::vector<Data> s;
	SegmentTree(int n) :
		tot(0), s(n << 5)
	{
    }
	int update(int rt, int pre, int L, int R, int pos, int val) {
    
		rt = ++tot;
		s[rt] = s[pre];
		s[rt].siz++;
		s[rt].val += val;
		if (L == R) return rt;
		int mid = (L + R) >> 1;
		if (pos <= mid) s[rt].ls = update(s[rt].ls, s[pre].ls, L, mid, pos, val);
		else s[rt].rs = update(s[rt].rs, s[pre].rs, mid + 1, R, pos, val);
		return rt;
	}
	int query(int rt1, int rt2, int L, int R, int k) {
    
		if (L == R) return b[L] * k;
		int siz = s[s[rt2].rs].siz - s[s[rt1].rs].siz;
		int val = s[s[rt2].rs].val - s[s[rt1].rs].val;
		int mid = (L + R) >> 1;
		if (k <= siz) return query(s[rt1].rs, s[rt2].rs, mid + 1, R, k);
		else return val + query(s[rt1].ls, s[rt2].ls, L, mid, k - siz);
	}
};

int s[N];

void solve() {
    
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
    
		scanf("%lld", &a[i]);
		b[i] = a[i];
		rt[i] = 0;
		s[i] = s[i - 1] + i * i;
	}
	std::sort(b + 1, b + 1 + n);
	m = std::unique(b + 1, b + 1 + n) - b - 1LL;
	SegmentTree segt(m);
	for (int i = 1; i <= n; i++) {
    
		int pos = std::lower_bound(b + 1, b + 1 + m, a[i]) - b;
		rt[i] = segt.update(rt[i], rt[i - 1], 1, m, pos, a[i]);
	}
	scanf("%lld", &q);
	while (q--) {
    
		int l, r, k;
		scanf("%lld%lld%lld", &l, &r, &k);
		int sum = segt.query(rt[l - 1], rt[r], 1, m, k);
		sum = sum + s[r - l + 1];
		printf("%lld\n", sum);
	}
	return;
}
signed main() {
    
	int T = 1;
	scanf("%lld", &T);
	while (T--)
		solve();
	return 0;
}

F

G - Gliding（最短路）

题意：略

题解：略

#include<bits/stdc++.h>
const int N = 4e3 + 9;
const int INF = 100000000;
int n;
int xs, ys, xe, ye;
int vf, vp, vh;
int xx[N], yy[N], vv[N];
int du[N];
double dis[N];
struct edge {
    
	int to; double w;
};
std::vector<edge> e[N];
double dist(int xa, int ya, int xb, int yb) {
    
	return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
}
void solve() {
    
	scanf("%d%d%d%d", &xs, &ys, &xe, &ye);
	scanf("%d%d%d", &vf, &vp, &vh);
	scanf("%d", &n); n++;
	for (int i = 1; i <= n; i++) {
    
		scanf("%d%d%d", &xx[i], &yy[i], &vv[i]);
		e[i].clear();
		du[i] = 0;
		dis[i] = INF;
	}
	e[n + 1].clear();
	du[n + 1] = 0;
	dis[n + 1] = INF;
	for (int i = 1; i <= n; i++) {
    
		if (vv[i] <= vp) continue;
		for (int j = 1; j <= n; j++) {
    
			if (i == j) continue;
			if (vv[j] <= vp) continue;
			if (vv[j] <= vv[i]) continue;
			double dis = dist(xx[i], yy[i], xx[j], yy[j]);
			double x = dis / vh;
			double h = x * vp;
			double y = h / (vv[i] - vp);
			e[i].emplace_back(edge{
     j, x + y });
			du[j]++;
		}
		double dis = dist(xx[i], yy[i], xe, ye);
		double x = dis / vh;
		double h = x * vp;
		double y = h / (vv[i] - vp);
		e[i].emplace_back(edge{
     n + 1, x + y });
		du[n + 1]++;
	}
	dis[1] = 0;
	std::queue<int> que;
	for (int i = 1; i <= n; i++) {
    
		if (du[i] == 0) {
    
			que.push(i);
		}
	}
	while (!que.empty()) {
    
		int u = que.front();
		que.pop();
		for (int i = 0; i < (int)e[u].size(); i++) {
    
			int v = e[u][i].to;
			double w = e[u][i].w;
			dis[v] = std::min(dis[v], dis[u] + w);
			du[v]--;
			if (du[v] == 0) {
    
				que.push(v);
			}
		}
	}

	printf("%.15lf\n", dis[n + 1]);
	return;
}
signed main() {
    
	int T = 1;
	std::cin >> T;
	while (T--)
		solve();
	return 0;
}

H - Huge Clouds（几何，差分求区间交）

题意：n个光源（点），m个板子（线段），问地面的阴影面积。

题解：对于每个点求出每个线段能造成阴影的区间，然后把区间并起来。最后将不同点对应的区间交起来就是答案。

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define pi acos(-1.0)
#define int long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define lowbit(x) ((x)&-(x))
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n"
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;

const double eps = 1e-8;
const double INF = 1e18;
const int N = 510;
int sgn(double x) {
    
	if (fabs(x) < eps) return 0;
	else return x < 0 ? -1 : 1;
}

struct Point {
    
	double x, y;
	Point() {
    }
	Point(double x, double y) :x(x), y(y) {
    }
	Point operator + (Point B) {
     return Point(x + B.x, y + B.y); }
	Point operator - (Point B) {
     return Point(x - B.x, y - B.y); }
	Point operator * (double k) {
     return Point(x * k, y * k); }
	Point operator / (double k) {
     return Point(x / k, y / k); }
};

struct Line {
    
	Point p1, p2;
	Line() {
    }
	Line(Point p1, Point p2) :p1(p1), p2(p2) {
    }
};
typedef Point Vector;

double Cross(Vector A, Vector B) {
     return A.x * B.y - A.y * B.x; }
double Dot(Vector A, Vector B) {
     return A.x * B.x + A.y * B.y; }

Point a[N], c[N * N];
Line b[N];

bool Point_on_seg(Point p, Line v) {
    
	return sgn(Cross(p - v.p1, v.p2 - v.p1)) == 0 && sgn(Dot(p - v.p1, p - v.p2)) <= 0;
}

Point Cross_point(Point a, Point b, Point c, Point d) {
    
	double s1 = Cross(b - a, c - a);
	double s2 = Cross(b - a, d - a);
	return Point(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
}

int Point_line_relation(Point p, Line v) {
    
	int c = sgn(Cross(p - v.p1, v.p2 - v.p1));
	if (c < 0) return 1;
	if (c > 0) return 2;
	return 0;
}

Point get(int x, int y) {
    
	if (Point_on_seg(a[x], b[y])) return Point(-INF, INF);
	//if(a[x].y<b[y].p1.y&&a[x].y<b[y].p2.y) return Point(-INF,INF);
	Line e(Point(0, 0), Point(INF, 0));
	if (a[x].y > b[y].p2.y) {
    
		Point l = Cross_point(a[x], b[y].p1, e.p1, e.p2);
		Point r = Cross_point(a[x], b[y].p2, e.p1, e.p2);
		if (l.x > r.x) swap(l, r);
		return Point(l.x, r.x);
	}
	else if (a[x].y > b[y].p1.y) {
    
		int v = Point_line_relation(a[x], b[y]);
		if (v == 0) return Point(-INF, INF);
		Point l = Cross_point(a[x], b[y].p1, e.p1, e.p2);
		if (v == 1) return Point(l.x, INF);
		else return Point(-INF, l.x);
	}
	else return Point(0, 0);
}

void solve() {
    
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i].x >> a[i].y;
	for (int i = 1; i <= m; i++) {
    
		cin >> b[i].p1.x >> b[i].p1.y >> b[i].p2.x >> b[i].p2.y;
		if (b[i].p1.y > b[i].p2.y) swap(b[i].p1, b[i].p2);
	}
	map<double, int> m1;
	for (int i = 1; i <= n; i++) {
    
		map<double, int> m2;
		for (int j = 1; j <= m; j++) {
    
			Point t = get(i, j);
			m2[t.x]++;
			m2[t.y]--;
		}
		int sum = 0;
		bool flag = false;
		double p = 0;
		for (auto x : m2) {
    
			sum += x.se;
			if (sum > 0 && !flag) {
    
				p = x.fi;
				flag = true;
			}
			else if (sum == 0 && flag) {
    
				m1[p]++;
				m1[x.first]--;
				flag = false;
			}
		}
	}
	int sum = 0;
	bool flag = false;
	double p = 0, ans = 0;
	for (auto x : m1) {
    
		sum += x.se;
		if (sum == n && !flag) {
    
			p = x.fi;
			flag = true;
		}
		else if (sum < n && flag) {
    
			ans += x.first - p;
			flag = false;
		}
	}
	if (ans > 1e9) printf("-1\n");
	else printf("%.10f\n", ans);
}

signed main() {
    
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}

I - Invoking the Magic （离散化，并查集）

题意：n双袜子两两配对，每次都可以操作k对袜子进行匹配（完美匹配），问最小的k。

题解：离散化一下然后用并查集处理一下即可。（map会超时）

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define pi acos(-1.0)
#define int long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define lowbit(x) ((x)&-(x))
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n"
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
unordered_map<int, int>mp;
int cnt;
const int N = 1e5 + 10;
int f[N], s[N];
int ans;
int getnum(int x) {
    
	if (mp[x] == 0) mp[x] = ++cnt;
	return mp[x];
}

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

void merge(int x, int y) {
    
	x = find(x), y = find(y);
	if (x != y) {
    
		f[y] = x;
		s[x] += s[y];
		ans = max(ans, s[x]);
	}
}

void solve() {
    
	mp.clear();
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		f[i] = i, s[i] = 1;
	ans = cnt = 0;
	for (int i = 1; i <= n; i++) {
    
		int x, y;
		cin >> x >> y;
		x = getnum(x);
		y = getnum(y);
		merge(x, y);
	}
	cout << ans << endl;
}

signed main() {
    
    IOS
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}

J

K - Killing the Brute-force（签到）

题意：略

题解：略

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define pi acos(-1.0)
#define int long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define lowbit(x) ((x)&-(x))
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n"
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 1e5 + 10;
int a[N], b[N];

void solve() {
    
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	int ans = -1;
	for (int i = 1; i <= n; i++) {
    
		if (b[i] > a[i] * 3) {
    
			ans = i;
			break;
		}
	}
	cout << ans << endl;
}

signed main() {
    
	IOS
		int T;
	cin >> T;
	while (T--) solve();
	return 0;
}

L

原网站

版权声明
本文为[moyangxian]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_45809826/article/details/117223322

边栏推荐

猜你喜欢

随机推荐