UOJ309 UNR #2 排兵布阵

包含不小于$\sqrt n$列的只有不大于$\sqrt n$行,修改时这些行打标记,否则暴力更新,操作一列的时候暴力更新这些行。合并没啥影响直接搞就是了。更新需要访问位置,我用的是哈希表。期望复杂度$O(n\sqrt n)$。

不知道正解是啥……

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
int n2;
inline void upd2(int&a,int b){
	a<b?a=b:0;
}
struct vec{
	int s,d;
	gp_hash_table<int,int>w;
	vec(){s=d=0;}
	void ins(int i,int e){
		auto j=w.find(i);
		if(w.end()==j)w[i]=e-d;
		else
			upd2(j->second,e-d);
		upd2(s,e);
	}
};
gp_hash_table<int,vec>f[2];
gp_hash_table<int,int>g[2];
gp_hash_table<int,null_type>h[2];
void dev(int k,int x){
	auto&a=f[k][x];
	for(int y:h[k^1]){
		auto&b=f[k^1][y];
		auto i=b.w.find(x);
		if(b.w.end()!=i)
			a.ins(y,i->second+b.d);
	}
}
int sol5(int k,int x){
	if(h[k].end()==h[k].find(x))
		dev(k,x);
	return f[k][x].s;
}
int ask(int k,int x){
	return g[k].end()!=g[k].find(x)?sol5(k,g[k][x]):0;
}
void inc(int k,int x,int d){
	auto&a=f[k][x];
	if(h[k].end()==h[k].find(x)){
		dev(k,x);
		for(auto&e:a.w){
			e.second+=d;
			f[k^1][e.first].ins(x,e.second);
		}
	}else{
		a.d+=d;
		for(int y:h[k^1]){
			auto&b=f[k^1][y];
			auto i=b.w.find(x);
			if(b.w.end()!=i){
				i->second+=d;
				upd2(b.s,i->second+b.d);
			}
		}
	}
	a.s+=d;
}
void sol4(int k,int x,int nx){
	g[k][nx]=g[k][x];
	g[k].erase(x);
}
void sol3(int k,int x,int nx){
	auto&a=f[k][x],&b=f[k][nx];
	if(h[k].end()==h[k].find(x))
		dev(k,x);
	for(auto e:a.w){
		auto&c=f[k^1][e.first];
		upd2(c.w[nx],e.second+a.d-c.d);
		c.w.erase(x);
		b.ins(e.first,e.second+a.d);
	}
	if(h[k].erase(x)||b.w.size()>n2){
		h[k].insert(nx);
		dev(k,nx);
	}
}
void sol2(int k,int x,int nx){
	sol3(k,g[k][x],g[k][nx]);
	g[k].erase(x);
}
void sol1(int k,int x,int nx){
	if(f[k][g[k][x]].w.size()<=f[k][g[k][nx]].w.size())
		sol2(k,x,nx);
	else{
		sol2(k,nx,x);
		sol4(k,x,nx);
	}
}
void mov(int k,int x,int nx){
	if(x!=nx)
		(g[k].end()!=g[k].find(nx)?sol1:sol4)(k,x,nx);
}
int main(){
	int n,m,x,y,d;
	char o[8];
	scanf("%d",&n);
	n2=sqrt(n+.5);
	while(n--){
		scanf("%d%d%d",&x,&y,&d);
		f[0][x].ins(y,d);
		f[1][y].ins(x,d);
		g[0][x]=x;
		g[1][y]=y;
	}
	for(int k=0;k<2;++k)
		for(auto&e:f[k])
			if(e.second.w.size()>n2)
				h[k].insert(e.first);
	scanf("%d",&m);
	while(m--){
		scanf("%s%d",o,&x);
		int k=*o==‘Y‘;
		if(o[1]==‘Q‘)
			printf("%d\n",ask(k,x));
		else{
			scanf("%d",&d);
			if(g[k].end()!=g[k].find(x))
				o[1]==‘M‘?mov(k,x,x+d):inc(k,g[k][x],d);
		}
	}
}

  

时间: 07-12

UOJ309 UNR #2 排兵布阵的相关文章

HDU 4539 郑厂长系列故事――排兵布阵(状态压缩)

郑厂长系列故事--排兵布阵 Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1954    Accepted Submission(s): 701 Problem Description 郑厂长不是正厂长 也不是副厂长 他根本就不是厂长 事实上 他是带兵打仗的团长 一天,郑厂长带着他的军队来到了一个n*m的平原准备布阵. 根据以往的战

HDU 4539 郑厂长系列故事——排兵布阵 (状态压缩DP)

中文题,题意不再累赘. 思路:对于第 i 行的放士兵,影响它的只有第 i-1 行和 i-2 行,所以暴力枚举符合这三行的状态 state[i],state[j],state[k].  接下来就是二进制的巧妙应用了. 具体题解看代码注释!!! #include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<map> #include<cmath&

HDU 4539郑厂长系列故事――排兵布阵(状压DP)

HDU 4539  郑厂长系列故事――排兵布阵 基础的状压DP,首先记录先每一行可取的所哟状态(一行里互不冲突的大概160个状态), 直接套了一个4重循环居然没超时我就呵呵了 1 //#pragma comment(linker,"/STACK:102400000,102400000") 2 #include <map> 3 #include <set> 4 #include <stack> 5 #include <queue> 6 #i

HDU 4539 郑厂长系列故事——排兵布阵

http://acm.hdu.edu.cn/showproblem.php?pid=4539 郑厂长系列故事——排兵布阵 Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1708    Accepted Submission(s): 620 Problem Description 郑厂长不是正厂长 也不是副厂长 他根本就不是厂长 事实上

排兵布阵之线段树

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 42138    Accepted Submission(s): 17826 Problem Description C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了.A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就

[BJOI2019]排兵布阵

[BJOI2019]排兵布阵 题面 链接 题解 直接转化为分组背包 #include<bits/stdc++.h> using namespace std; inline int read() { int f = 1 , x = 0; char ch; do { ch = getchar(); if(ch=='-') f=-1; } while(ch<'0'||ch>'9'); do { x=(x<<3) + (x<<1) + ch - '0'; ch =

【BJOI2019】排兵布阵

二维背包,不是很难. 看第二个样例时想到,既然吃掉了每一个城堡的某一个人的分,那么所有比那个人派遣兵力小的都可以吃掉,所以就想到了用一维存城堡,二维存第几个玩家的兵力. 所以输入就是a[j][i];输完之后为了便于比较有多少个玩家派遣的兵力小于目前吃掉的,就要排一个序,因为兵力会比较多,所以答案的第二维就要开大一点,开小了居然是WA,不是RE. #include<bits/stdc++.h> using namespace std; int s,n,m; int ans[200][20050]

HDU ACM 4539 郑厂长系列故事——排兵布阵-&gt;状态压缩DP

分析:dp[i][j][k]表示第i行状态为j,i-1行状态为k时的客房士兵的最大值. 曼哈顿距离是指:|x1-x2|+|y1-y2|. 当前行不仅与前一行有关,还和前两行有关,所以开数组的时候还要记录前两行的状态,所以开设三维数组. 每行可压缩为二进制集合,状态dp[i][j][k]为第i行为集合j,第i-1行为集合k,则状态方程dp[i][j][k] = max{dp[i-1][k][r]+cnt[j]  | 状态i,j,k要能够共存}(cnt[j]为j在二进制下的1的个数,即士兵数).第一

HDU 4539 郑厂长系列故事――排兵布阵

/* 曼哈顿距离的定义是:两个点的坐标为(x1,y1),(x2,y2),两点的曼哈顿距离为|x1-x2|+|y1-y2| 题意:题上要求是两个士兵的距离不能是曼哈顿距离为2,意思就是这个点在同一行同一列不能相间,这个点的左上,左下,右上,右下角不能有 士兵. 思路:dp+状态压缩dp[i][j][k]定义的状态为i是当前行,j为当前行的状态,k为上一行的状态类似炮兵阵地 */ #include<stdio.h> #include<string.h> #define Max(a,b)