首页 > 其他分享 >2023冲刺国赛模拟19

2023冲刺国赛模拟19

时间:2023-06-15 20:24:00浏览次数:54  
标签:typedef 19 ll 国赛 int maxn long 2023 getchar

A. 矩阵

正解是二维分块

image

但是二维树状数组跑的飞快

code
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

ll read(){
	ll x = 0; bool f = false; char c = getchar();
	while(!isdigit(c))f = c == '-', c = getchar();
	do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
	return f ? -x : x;
}

const int maxn = 1005;
int n, m, q;
struct BIT{
	ll t[maxn][maxn];
	#define lowbit(x) (x & -x)
	void add(int x, int y, ll val){
		for(; x <= n; x += lowbit(x))
			for(int b = y; b <= m; b += lowbit(b))
				t[x][b] += val;
	}
	ll query(int x, int y){
		ll ans = 0;
		for(; x; x -= lowbit(x))
			for(int b = y; b; b -= lowbit(b))
				ans += t[x][b];
		return ans;
	}
}T;
int main(){
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	n = read(), m = read(), q = read();
	for(int i = 1; i <= q; ++i){
		int op = read(), a = read(), b = read();
		if(op & 1)T.add(a, b, read());
		else{
			int c = read(), d = read();
			printf("%lld\n",T.query(c, d) - T.query(c, b - 1) - T.query(a - 1, d) + T.query(a - 1, b - 1));
		}
	}
	return 0;
}

B. 种草

费用流建图 + Primal-Dual 原始对偶算法

建边 \((i, i + 1, a[i], 0)\) (特别的 \((n, t, a[n], 0)\))

\((s, i, a[i] - a[i - 1], 0)\)

对于 \((l, r, w)\) 建边 \((l, r + 1, 1, w)\)

跑最大费用最大流

Primal-Dual 原始对偶算法

就是给每个点一个势能,使得任意边权非负,然后就能用 \(dijstra\) 了

初始势能是源点到每个点的最短路,新边权就是 \(h[u] - h[v] + w[u][v]\)

每一轮增广后,势能加上本次的最短路,证明可以见 \(rval\) 学长的经典博客

code
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, int> pli;

int read(){
	int x = 0; char c = getchar();
	while(!isdigit(c))c = getchar();
	do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
	return x;
}
const ll inf = 1e15;
const int maxn = 1e5 + 55;
int n, m, a[maxn];
struct MCMF{
	int s, t;
	int head[maxn], tot = 1;
	struct edge{int to, net; ll val, cost;}e[maxn * 4];
	void add(int u, int v, int w, int c){
		e[++tot].net = head[u];
		head[u] = tot;
		e[tot].to = v;
		e[tot].val = w;
		e[tot].cost = c;
	}
	void link(int u, int v, int w, int c){add(u, v, w, c); add(v, u, 0, -c);}
	ll h[maxn]; bool vis[maxn];
	void spfa(){
		h[s] = 0;
		for(int x = 1; x <= n; ++x)
			for(int i = head[x]; i; i = e[i].net){
				int v = e[i].to;
				if(e[i].val && h[v] > h[x] + e[i].cost)
					h[v] = h[x] + e[i].cost;
			}
	}
	ll dis[maxn]; int pre[maxn], pe[maxn];
	bool dij(){
		priority_queue<pli>q;
		for(int i = 1; i <= t; ++i)dis[i] = inf;
		for(int i = 1; i <= t; ++i)vis[i] = false;
		dis[s] = 0; q.push(pli(0, s));
		while(!q.empty()){
			int x = q.top().second; q.pop();
			if(vis[x])continue; vis[x] = true;
			for(int i = head[x]; i; i = e[i].net){
				int v = e[i].to; ll nc = e[i].cost + h[x] - h[v];
				if(e[i].val && dis[v] > dis[x] + nc){
					dis[v] = dis[x] + nc;
					pre[v] = x; pe[v] = i;
					if(!vis[v])q.push(pli(-dis[v], v));
				}
			}
		}
		return dis[t] != inf;
	}
	ll flow, cost;
	void mcmf(){
		spfa();
		while(dij()){
			ll f = inf;
			for(int i = 1; i <= t; ++i)h[i] += dis[i];
			for(int i = t; i != s; i = pre[i])f = min(f, e[pe[i]].val);
			for(int i = t; i != s; i = pre[i]){
				e[pe[i]].val -= f;
				e[pe[i] ^ 1].val += f;
			}
			flow += f; cost += f * h[t];
		}
	}
	void init(){
		n = read(), m = read();
		for(int i = 1; i <= n; ++i)a[i] = read();
		s = n + 1, t = s + 1;
		for(int i = 1; i <= n; ++i)if(a[i] != a[i - 1])link(s, i, a[i] - a[i - 1], 0);
		for(int i = 1; i < n; ++i)link(i, i + 1, a[i], 0); link(n, t, a[n], 0);
		for(int i = 1; i <= m; ++i){
			int l = read(), r = read(), w = read();
			link(l, r == n ? t : r + 1, 1, -w);
		}
		mcmf(); printf("%lld\n",-cost);
	}
}w;

int main(){
	// freopen("weed.in","r",stdin);
	// freopen("weed.out","w",stdout);
	w.init();
	return 0;
}

C. 基环树

考虑一棵树怎么做, \(f_{x, 0 / 1 / 2}\)

表示考虑完 \(x\) 子树内的,与 \(x\) 相连的链长度为 \(0 / 1 / 2\) 的最大价值

转移把 \(1 / 2\) 分别看成 \(+1 / -1\) 就是一个背包,而且只需要 \(-1 / 0 / 1\) 处的取值

随机化儿子顺序,这样只需要长度为根号级别的数组来做背包

考虑基环树,实际上随便找环上一条边断开然后当树做,分讨去掉的这条边是否使用,使用时两侧的链长,然后 \(DP\) 时候特殊处理一下即可

code
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int read(){
	int x = 0; char c = getchar();
	while(!isdigit(c))c = getchar();
	do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
	return x;
}
const int maxn = 1e5 + 55;
const ll inf = 1e18;
mt19937 rd((ull)&maxn);
int n, m, ru, rv, rw, type;
vector<pii>e[maxn];
bool vis[maxn];
bool find_edge(int x, int fa){
	vis[x] = true;
	for(pii v : e[x]){
		if(v.first == fa)continue;
		if(vis[v.first]){ru = x, rv =  v.first, rw = v.second; return true;}
		if(find_edge(v.first, x))return true;
	}
	vis[x] = false; return false;
}
ll f[maxn][3], g[maxn], h[maxn];
void solve(int x, int fa){
	for(pii v : e[x])if(v.first != fa && (min(x, v.first) != min(ru, rv) || max(x, v.first) != max(ru, rv)))
		solve(v.first, x);
	int len = sqrt(e[x].size()) * 4 + 10, base = len >> 1;
	for(int i = 0; i <= len; ++i)g[i] = h[i] = -inf;
	g[base] = 0;
	for(pii v : e[x])if(v.first != fa && (min(x, v.first) != min(ru, rv) || max(x, v.first) != max(ru, rv))){
		for(int i = 0; i <= len; ++i)h[i] = g[i] + max(f[v.first][0], f[v.first][2] + v.second);
		for(int i = 0; i <= len; ++i)h[i + 1] = max(h[i + 1], g[i] + f[v.first][0] + v.second);
		for(int i = 1; i <= len; ++i)h[i - 1] = max(h[i - 1], g[i] + f[v.first][1] + v.second);
		for(int i = 0; i <= len; ++i)g[i] = h[i];
	}
	if(x == rv){
		if(type == 1)for(int i = 0; i <= len; ++i)h[i + 1] = g[i] + rw;
		if(type == 2)for(int i = 1; i <= len; ++i)h[i - 1] = g[i] + rw;
		if(type == 3)for(int i = 0; i <= len; ++i)h[i] = g[i] + rw;
		if(type == 4)h[base] = max(0ll, h[base]);
		for(int i = 0; i <= len; ++i)g[i] = h[i];
	}
	f[x][0] = g[base]; f[x][1] = g[base + 1]; f[x][2] = g[base - 1];
}
int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n = read();
	for(int i = 1; i <= n; ++i){
		int u = read(), v = read(), w = read();
		e[u].push_back(pii(v, w));
		e[v].push_back(pii(u, w));
	}
	for(int i = 1; i <= n; ++i)shuffle(e[i].begin(), e[i].end(), rd);
	find_edge(1, 0); ll ans = 0;
	type = 1; solve(ru, 0); ans = max(ans, f[ru][0]);
	type = 2; solve(ru, 0); ans = max(ans, f[ru][1]);
	type = 3; solve(ru, 0); ans = max(ans, f[ru][2]);
	type = 4; solve(ru, 0); ans = max(ans, f[ru][0]);
	printf("%lld\n",ans);
	return 0;
}

标签:typedef,19,ll,国赛,int,maxn,long,2023,getchar
From: https://www.cnblogs.com/Chencgy/p/17484024.html

相关文章

  • (2023.6.15)linux下can的调试工具交叉编译
    //源码包路径:https://public.pengutronix.de/software/libsocketcan/libsocketcan-0.0.11.tar.bz2https://public.pengutronix.de/software/socket-can/canutils/v4.0/canutils-4.0.6.tar.bz2//编译命令./configure--host=arm-linux-gnueabihf--prefix=/home/fangzeli/work/......
  • 2023-6-15 面试笔试复盘总结
    四川君迪能源后端笔试2023-6-15简答题:线程和进程的区别本质区别:进程是操作系统资源分配的基本单位,而线程是处理器任务调度和执行的基本单位。包含关系:一个进程至少有一个线程,线程是进程的一部分,所以线程也被称为轻权进程或者轻量级进程。资源开销:每个进程都有独立的地址空......
  • 2023冲刺国赛模拟 19.1
    T1矩阵正解做法是二维分块,然而直接上树状数组跑的飞快,不过我写的根号重构,加Fastio后可过。code#include<cstdio>#include<algorithm>#include<ctime>#include<iostream>usingnamespacestd;charbuf[1<<21],*p1,*p2;inlinechargc(){if(__builti......
  • 欧奈儿行业 RPS 排名,一图览全貌 2023-06-15
    自动复盘2023-06-15k线图是最好的老师,点击详情图可以看到行业20日RPS的排名,最底下子图是行业rps走势线跟踪板块总结:成交额超过100亿排名靠前,macd柱由绿转红成交量要大于均线有必要给每个行业加一个上级的归类,这样更能体现主流方向rps有时候比较滞后,但不少是欲......
  • IP段是什么意思?杭州高防服务器103.219.30.X
    IP段就是网段,一般指一个计算机网络中使用同一物理层设备(传输介质,中继器,集线器等)能够直接通讯的那一部分。例如,从103.219.30.1到103.219.30.255这之间就是一个网段。在同一网段,要求网络标识相同。网络标识就是用IP的二进制与子网掩码的二进制数据作'与'运算(可用WINDOWS计算器算二进......
  • C/C++《数据结构》课程设计指导书[2023-06-15]
    C/C++《数据结构》课程设计指导书[2023-06-15]《数据结构》课程设计指导书适用专业:计算机2022级编写人:李玉龙2023年5月《数据结构》课程设计指导书一、设计目的1、训练学生灵活应用所学数据结构知识,独立完成问题分析,结合数据结构理论知识,编写程序求解指定问题;2.初步掌握软......
  • C/C++器材信息管理系统[2023-06-15]
    C/C++器材信息管理系统[2023-06-15]使用C++程序设计语言,完成一个项目,项目名为:器材信息管理系统,要实现的功能如下,且每项功能具有数据校对验证:1、实现新器材的录入,包括器材的名称、录入日期、购买价钱等信息;2、当有器材借用需求时,进行借用登记,主要流程为:查询器材数量,若库存数量大......
  • 2023年6月中国数据库排行榜:OceanBase 连续七月踞榜首,华为阿里谋定快动占先机
    群雄逐鹿,酣战墨坛。 2023年6月的 墨天轮中国数据库流行度排行 火热出炉,本月共有273个数据库参与排名。本月排行榜前十变动不大,可以用一句话概括为:OTO组合连续两月开局,传统厂商GBase南大通用乘势而上,其余数据库暂居原位。本月排行榜解读文章 「专家观点」 板块邀请到科大讯......
  • 2023年第一季度,中国云服务支出增长6%
    2023年第一季度,中国大陆的云基础设施服务支出同比增长6%,达到77亿美元,占全球整体云支出的12%。企业对于上云的需求仍然低迷,整体市场连续三个季度保持着个位数的增长。随着疫情限制的放宽,远程办公和在线会议的需求有所消退。企业对其IT预算仍持谨慎态度。存量市场的云计算消费放缓,增......
  • 12篇CVPR 2023 最佳论文候选
    前言 CVPR2023开幕在即,官方公布了12篇最佳论文候选,快来看看都是什么内容吧!本文转载自我爱计算机视觉仅用于学术分享,若侵权请联系删除欢迎关注公众号CV技术指南,专注于计算机视觉的技术总结、最新技术跟踪、经典论文解读、CV招聘信息。CV各大方向专栏与各个部署框架最全教程......