ZR20秋季普转提day1

毒瘤T4

按照题意进行模拟

但是你会发现我们最后朝向可能有点问题,就是他可能没有朝向一个和开头一样正确的方向

那么我们多做几遍把它转到开头一样,然后把这个当做循环节蹦跶就好了

复杂度 $O(n)$


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e6 + 7;
const ll dx[] = {0, 1, 0, -1};
const ll dy[] = {1, 0, -1, 0};
int n, T, a[MAXN];

int main() {
	scanf("%d%d", &n, &T);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	ll nx = 0, ny = 0, nd = 0, qwq = 0;
	do {
		for(int i = 1; i <= n; ++i) {
			nx += dx[nd] * a[i];
			ny += dy[nd] * a[i];
			(nd += a[i] % 4) %= 4;
		}
		++qwq;
	} while(nd != 0);
	nx *= T / qwq;
	ny *= T / qwq;
	for(int i = 1; i <= T % qwq; ++i) {
		for(int i = 1; i <= n; ++i) {
			nx += dx[nd] * a[i];
			ny += dy[nd] * a[i];
			(nd += a[i] % 4) %= 4;
		}
	}
	nx = nx < 0 ? -nx : nx;
	ny = ny < 0 ? -ny : ny;
	printf("%lld\n", nx + ny);
	return 0;
}

会发现我们可以找出他走的路径是什么样子的

那么就是走到某个餐馆停下然后之前进去过某些餐馆

所以我们枚举到哪个餐馆停下来,然后用一个线段树二分去解决前面最多可以选择多少可行的餐馆即可

注意m是longlong!!!

像m,n这样的数需要开ll我老是忘!

时间复杂度 $O(nlogn)$



#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5 + 7;
const int MAXT = (1 << 18) + 1;
int n, vis[MAXN], ans;
struct rec {
	ll x, t;
	int id;
	bool operator<(const rec &w)const {
		return x == w.x ? t > w.t : x < w.x;
	}
} a[MAXN], b[MAXN];
bool cmp(const rec &x, const rec &y) {
	return x.t < y.t;
}
ll m;
struct BIT {
#define lowbit(x) (x&(-x))
	ll tr[MAXT];
	inline void modify(int x, ll V) {
		for(; x < MAXT; x += lowbit(x))tr[x] += V;
	}
	inline ll query2(int x) {
		ll ret = 0;
		for(; x; x -= lowbit(x))ret += tr[x];
		return ret;
	}
	inline ll query1(ll S) {
		int l = 0, r = MAXT - 1;
		while(l + 1 != r) {
			int mid = (l + r) >> 1;
			if(tr[mid] > S)r = mid;
			else S -= tr[mid], l = mid;
		}
		return l;
	}
} t1, t2;

int main() {
	scanf("%d%lld", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%lld%lld", &a[i].x, &a[i].t);
		a[i].id = i;
		b[i] = a[i];
	}
	sort(a + 1, a + n + 1);//枚举数组
	sort(b + 1, b + n + 1, cmp);//下标数组
	for(int i = 1; i <= n; ++i) {
		vis[b[i].id] = i;
	}
	ll S = 0;
	for(int i = 1; i <= n; ++i) {
		S = m - a[i].t - a[i].x;
		if(S < 0)continue;
		int pos = t1.query1(S);
		int res = t2.query2(pos);
		ans = max(res + 1, ans);
		t1.modify(vis[a[i].id], a[i].t);
		t2.modify(vis[a[i].id], 1);
	}
	printf("%d\n", ans);
	return 0;
}

结论:只要我们选择的数弹出次数总和少于n就一定可行

证明....好像很显然...

因为我们首先一定存在第一个可以弹出的,否则我们个数一定大于n

然后把第一个弹出,我们第一个之前的那个也一定能弹出,就这样把能弹的弹下去即可

问题变成背包

$O(n^2)$

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 7;
ll n, L[MAXN], D[MAXN], f[MAXN];

int main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%lld", &L[i]);
	}
	for(int i = 1; i <= n; ++i) {
		scanf("%lld", &D[i]);
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = n; j >= L[i]; --j) {
			f[j] = max(f[j], f[j - L[i]] + D[i]);
		}
	}
	printf("%lld\n", f[n]);
	return 0;
}

唯一有质量的一道题/se

思想是我们只维护可能成为答案的,然后就能做到分离限制

首先我们第i个只能选i个的限制,可以考虑用一个 $mulitiset$ 维护前i大的,再用一个维护所有的,然后我们插入一个数分类讨论我们这个前i大的满没满,如果满了,我们看他能不能替代最小的那个,如果可以我们就把最小的那个弹出换成他

然后删除也是一样,如果我们能够删除的这个数在bst集合里,我们就看能不能从整体集合中拿出一个填入bst集合

具体分类讨论可以看看代码,非常非常的细节毒瘤

然后我们就能知道哪些元素是最优的了

问题变成了带修前k大的和,平衡树解决

当然好像也可以线段树二分实现这个qwq不过我喜欢显然

~~wyz的线段树二分还比我慢!~~

$O(nlogn)$


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 3e5 + 7;
const int MAXT = 6e5 + 7;
int siz[MAXT], rs[MAXT], ls[MAXT], rnd[MAXT];
ll val[MAXN], sum[MAXN];
int T, cnt, n, x, y, z, p, a, root;

inline int read() {
	int x = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar())if(c == '-')f = -1;
	for(; isdigit(c); c = getchar())x = x * 10 + c - '0';
	return x * f;
}

inline void update(int x) {
	siz[x] = 1 + siz[ls[x]] + siz[rs[x]];
	sum[x] = sum[ls[x]] + sum[rs[x]] + val[x];
}

inline int nw_(int x) {
	siz[++cnt] = 1;
	val[cnt] = x;
	sum[cnt] = x;
	rnd[cnt] = rand();
	return cnt;
}

inline int merge(int A, int B) {
	if(!A || !B)return A + B;
	if(rnd[A] < rnd[B]) {
		rs[A] = merge(rs[A], B);
		update(A);
		return A;
	} else {
		ls[B] = merge(A, ls[B]);
		update(B);
		return B;
	}
}

inline void split(int now, int k, int &x, int &y) {
	if(!now)x = y = 0;
	else {
		if(val[now] <= k) {
			x = now;
			split(rs[now], k, rs[now], y);
		} else {
			y = now;
			split(ls[now], k, x, ls[now]);
		}
		update(now);
	}
}

inline ll ksum(int nw, int k) {
	ll ret = 0;
	if(k >= siz[nw])return sum[nw];
	while(nw) {
		if(k <= siz[rs[nw]]) {
			nw = rs[nw];
		} else if(k == siz[rs[nw]] + 1) {
			return ret + val[nw] + sum[rs[nw]];
		} else {
			k -= siz[rs[nw]] + 1;
			ret += sum[rs[nw]] + val[nw];
			nw = ls[nw];
		}
	}
	return ret;
}

char s[20];

inline void del(ll a) {
	split(root, a, x, z);
	split(x, a - 1, x, y);
	y = merge(ls[y], rs[y]);
	root = merge(merge(x, y), z);
}

inline void ins(ll a) {
	split(root, a, x, y);
	root = merge(merge(x, nw_(a)), y);
}

multiset<int> hve[MAXN], bst[MAXN];

int main() {
	srand((unsigned)time(NULL));
	n = read();
	T = read();
	int t, x;
	while(T-- > 0) {
		scanf("%s", s);
		scanf("%d%d", &t, &x);
		if(s[0] == 'B') {//借入
			//考虑我们顶替掉一个,然后对应点删
			if((int)bst[t].size() < t) {
				bst[t].insert(x);
				ins(x);
			} else {
				auto u = (bst[t].begin());
				if(*u < x) {
					del(*u);
					bst[t].erase(u);
					bst[t].insert(x);
					ins(x);
				}
			}
			hve[t].insert(x);
		} else {//删除QAQ
			auto u = hve[t].find(x);
			hve[t].erase(u);
			if((int)bst[t].size() < t || (int)hve[t].size() == t - 1) {
				auto u = bst[t].find(x);
				del(*u);
				bst[t].erase(u);
			} else {
				auto y = (bst[t].begin());
				if(*y <= x) {//x在bst里面
					auto z = *(--hve[t].lower_bound(*y));
					auto u = (bst[t].find(x));
					del(*u);
					bst[t].erase(u);
					bst[t].insert(z);
					ins(z);
				}
			}
		}
		printf("%lld\n", ksum(root, n));
	}
	return 0;
}

夏晓光(loveJY)的博客

注意m是longlong!!!

P3648 [APIO2014]序列分割