A层省选4

article6/8/2023 12:10:20 AM/文章来源:https://www.cnblogs.com/Chencgy/p/16589545.html

场均一题放弃

A. 我

我切题了

发现图上有环可以不停的转,让空位到我们需要的地方去,而环的具体形态并不重要,我们只需要知道环的大小(\(size\))和环内元素个数(\(cnt\))即可

所以使用\(tarjan\)缩点,然后转化为一个\(DAG\)上的问题

发现环的大小等于元素个数时,我们必须先移走一个元素,然后可以加入新的元素,但原来的那个元素不能留下

\(DAG\)转移中,我们不清楚在有多条可选择的路径中应该选择哪一条

考虑使用网络流,拆点

入点连汇点边权为\(size\)

入点连出点\(inf\),出点连\(DAG\)上后继点的入点

\(size == cnt\)时源点向入点连\(cnt - 1\),向出点连\(1\),其他情况直接连入点

这样存在最后一个小问题,当\(size == cnt == 1\)时,如果该点没有出度,那么这个孤点没有移动的理由,不应该扔掉

所以在建图前特判即可

code
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 5005;
const int mx = 62;
const int inf = 2147383647;
char c[maxn];
int m, flag[maxn];
int id(char x){
	if(x >= '0' && x <= '9') return x - '0' + 1;
	if(x >= 'a' && x <= 'z') return x - 'a' + 10 + 1;
	return x - 'A' + 10 + 26 + 1;
}
vector<int> g[maxn];
int size[maxn], cnt[maxn], sd[maxn], dt;
struct wll
{
	int head[maxn], tot = 1;
	struct edge{
		int net, to, val;
	} e[maxn << 1 | 1];
	void add(int u, int v, int w){
		e[++tot].net = head[u];
		e[tot].val = w;
		head[u] = tot;
		e[tot].to = v;
	}
	void link(int u, int v, int w){
		add(u, v, w);
		add(v, u, 0);
	}
	int s, t;
	int now[maxn], dep[maxn];
	bool bfs(){
		queue<int> q;
		memset(dep, 0, sizeof(dep));
		dep[s] = 1;
		now[s] = head[s];
		q.push(s);
		while (!q.empty()){
			int x = q.front();
			q.pop();
			if(x == t) return true;
			for(int i = head[x]; i; i = e[i].net){
				int v = e[i].to;
				if(!dep[v] && e[i].val > 0){
					now[v] = head[v];
					dep[v] = dep[x] + 1;
					q.push(v);
				}
			}
		}
		return false;
	}
	int dfs(int x, int from){
		if(x == t || from <= 0)return from;
		int res = from, i;
		for(i = now[x]; i; i = e[i].net){
			int v = e[i].to;
			if(e[i].val > 0 && dep[v] == dep[x] + 1){
				int k = dfs(v, min(res, e[i].val));
				if(k <= 0) dep[v] = 0;
				res -= k;
				e[i].val -= k;
				e[i ^ 1].val += k;
				if(res <= 0) break;
			}
		}
		now[x] = i;
		return from - res;
	}
	int work(){
		int ans = 0;
		while (bfs()) ans += dfs(s, inf);
		return ans;
	}
	int cd[maxn];
	int init(){
		for(int i = 1; i <= dt + dt + dt; ++i)head[i] = 0;
		int ans = 0;
		tot = 1;
		for(int i = 1; i <= dt; ++i)cd[i] = 0;
		s = dt + dt + 1, t = s + 1;
		for(int i = 1; i <= mx; ++i)for(int v : g[i])if(sd[i] != sd[v])link(sd[i] + dt, sd[v], inf), ++cd[sd[i]];
		for(int i = 1; i <= dt; ++i)if(cd[i] == 0 && cnt[i] == 1)ans += cnt[i], cnt[i] = 0, --size[i];
		for(int i = 1; i <= dt; ++i)link(i, t, size[i]);
		for(int i = 1; i <= dt; ++i)link(i, i + dt, inf);
		for(int i = 1; i <= dt; ++i){
			if(size[i] > cnt[i])link(s, i, cnt[i]);
			else link(s, i, cnt[i] - 1), link(s, i + dt, 1);
		}
		return work() + ans;
	}
}w;
int dfn[maxn], low[maxn], tim, sta[maxn], top;
bool vis[maxn];
void tarjan(int x){
	low[x] = dfn[x] = ++tim;
	sta[++top] = x; vis[x] = 1;
	for(int v : g[x])
		if(!dfn[v]) tarjan(v), low[x] = min(low[x], low[v]);
		else if(vis[v]) low[x] = min(low[x], low[v]);
	if(dfn[x] == low[x]){
		int y; ++dt;
		do{
			y = sta[top--];
			cnt[dt] += flag[y];
			++size[dt];
			sd[y] = dt;
			vis[y] = 0;
		} while (y != x);
	}
}
queue<int> q;
void work(){
	for(int i = 1; i <= mx; ++i) dfn[i] = 0;
	for(int i = 1; i <= mx; ++i) low[i] = 0;
	for(int i = 1; i <= mx; ++i) size[i] = 0;
	for(int i = 1; i <= mx; ++i) cnt[i] = 0;
	for(int i = 1; i <= mx; ++i) sd[i] = 0;
	tim = 0, top = 0, dt = 0;
	for(int i = 1; i <= mx; ++i) if(!dfn[i]) tarjan(i);
	printf("%d\n",w.init());
}
int main()
{
	freopen("graph.in", "r", stdin);
	freopen("graph.out","w",stdout);
	int t; scanf("%d", &t);
	for(int i = 1; i <= t; ++i){
		for(int i = 0; i <= mx; ++i) flag[i] = 0;
		for(int i = 0; i <= mx; ++i) g[i].clear();
		scanf("%s", c + 1);
		int len = strlen(c + 1);
		for(int i = 1; i <= len; ++i)flag[id(c[i])] = 1;
		scanf("%d", &m);
		for(int i = 1; i <= m; ++i)scanf("%s", c), g[id(c[0])].push_back(id(c[1]));
		work();
	}
	return 0;
}

B. 想不出

平面欧拉定理

可以想象翻转了坐标轴,向左或者下射线,存在一条折线,其左上都向下,右下都向左

然后,不会了,看上届学长的题解,作法是看左侧交点多还是下方交点多来定向,不是很理解很是不理解

code
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<set>
#include<vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
inline int max(int x, int y){return x > y ? x : y;}
inline int min(int x, int y){return x < y ? x : y;}
inline void swap(int &x, int &y){x ^= y, y ^= x, x ^= y;}
const int maxn = 2005;
const int inf = 2147383647;
int n;
struct node{
	int x,y;
	double k1, b1, k2, b2;
	bool operator < (const node &b)const{return x == b.x ? y < b.y : x < b.x;}
}d[maxn];
int dir[maxn], vis[maxn];
bool check(int x, int y){
	double a = (d[y].b1 - d[x].b2) / (d[x].k2 - d[y].k1);
	return d[x].x <= a && a <= d[y].x;
}
int main(){
	freopen("surface.in","r",stdin);
	freopen("surface.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1; i <= n; ++i)scanf("%d%d",&d[i].x, &d[i].y);
	sort(d + 1, d + n + 1);
	for(int i = 1; i <= n; ++i){
		d[i].k1 = (double) sqrt(3);
		d[i].k2 = -d[i].k1;
		d[i].b1 = d[i].y - d[i].k1 * d[i].x;
		d[i].b2 = d[i].y - d[i].k2 * d[i].x;
	}
	for(int i = 1; i <= n; ++i){
		int c1 = 0, c2 = 0;
		for(int j = 1; j < i; ++j)if(check(j, i))++c1;
		for(int j = n; j > i; --j)if(check(i, j))++c2;
		dir[i] = c1 < c2 ? 1 : 0;
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i)
		if(dir[i]){
			int now = -1;
			for(int j = i + 1; j <= n; ++j)if(!dir[j])
				if(check(i, j)){if(!vis[j])vis[j] = 1; else ++now;}
			ans += max(now, 0);
		}
	printf("%d\n",ans);
	return 0;
}

C. 题目名称

不要被数据范围吓到,背包有\(45pts\)

正解不会
image

45
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<set>
#include<vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
inline int max(int x, int y){return x > y ? x : y;}
inline int min(int x, int y){return x < y ? x : y;}
inline void swap(int &x, int &y){x ^= y, y ^= x, x ^= y;}
inline ll read(){
	ll x = 0; char c = getchar();
	while(c < '0' || c > '9')c = getchar();
	do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >= '0');
	return x;
}
const int maxn = 1000005;
const int inf = 2147383647;
const int mod = 998244353;
ll n, s;
ll f[5][maxn];
int vis[maxn];
void work(int l, int r){
	for(int i = l; i <= r; ++i){
		if(vis[i]){i = vis[i];continue;} vis[i] = r;
		for(int k = 3; k >= 0; --k)
			for(int j = 0; j <= s - i; ++j)
		 		f[k + 1][j + i] = (f[k + 1][j + i] + f[k][j]) % mod;
	}
}
int main(){
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	n = read(), s = read();
	f[0][0] = 1;
	for(int i = 1; i <= n; ++i){
		int l = read(), r = read();
		work(l, r);
	}
	printf("%lld\n",f[4][s]);
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.wtld.cn/a/66.html

如若内容造成侵权/违法违规/事实不符,请联系方塘网进行投诉反馈,一经查实,立即删除!

相关文章

fa

\[ax+by\equiv X_i \]$$\texttt{--END--}$$我的博客: $\texttt{1Liu}$ 本文链接: https://www.cnblogs.com/OLiuO/p/16589553.html 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!