2020提高组十连测day2

按照 $a+b<b+a$ 排序即可,时间复杂度 $O(nlog^2n)$

弱者做法:

直接贪心是 $O(nm)$ 的,然后我们分析下复杂度瓶颈在哪

全局加数量
查询x要多少种才能凑齐

解决这个的显然做法就是分块啊

把所有操作排序后分成根号m段

全局加变成打标记

然后考虑对于第i块,如果我们完全取走都无法凑齐这个月的,就全部取走

反之,我们重构这个块

需要维护的标记:

加标记
清空标记

额外数组

每一块,每个月数量净收入
每一块,每个月价钱净收入

code:



#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+7;
int n,m;
ll c[MAXN];
struct rec {
	ll x,y;
	bool operator<(const rec &w)const {
		return x<w.x;
	}
} a[MAXN],b[MAXN];
ll sumn[MAXN],sumc[MAXN],addn[MAXN],sad[MAXN],sct[MAXN],qk[MAXN],hve[MAXN];
ll ans;
int sz,L[MAXN],R[MAXN],bel[MAXN],tot;
inline void init() {
	sz=sqrt(m);
	tot=1;
	L[tot]=1;
	for(int i=1; i<=m; ++i) {
		if(i%sz==0) {
			R[tot]=i-1;
			++tot;
			L[tot]=i;
		}
		bel[i]=tot;
	}
	R[tot]=m;
	for(int i=1; i<=m; ++i) {
		sad[bel[i]]+=a[i].y;
		sct[bel[i]]+=a[i].x * a[i].y;
	}

	return ;
}

inline void solve(int B,int q) {
	for(int i=L[B]; i<=R[B]; ++i) { //下穿标记
		if(qk[B]!=-1) {
			hve[i]=0;
		}
		hve[i]+=addn[B] * a[i].y;
	}
	qk[B]=-1;
	addn[B]=0;
	for(int i=L[B]; i<=R[B]; ++i) {
		if(hve[i]<q) {
			q-=hve[i];
			ans+=hve[i]*a[i].x;
			hve[i]=0;
		} else {
			hve[i]-=q;
			ans+=q*a[i].x;
			break;
		}
	}
	sumn[B]=0;
	sumc[B]=0;
	for(int i=L[B]; i<=R[B]; ++i) {
		sumn[B]+=hve[i];
		sumc[B]+=hve[i]*a[i].x;
	}
	return ;
}


namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
	inline char nc() {
		if(p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x=0,f=1;
		char s=nc();
		for(; !isdigit(s); s=nc())if(s=='-')f=-1;
		for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
		return x*f;
	}
}
using namespace fastIO;

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i) {
		c[i]=read();
	}
	for(int i=1; i<=m; ++i) {
		a[i].x=read();
		a[i].y=read();
		if(a[i].y==-1)a[i].y=1e7;
	}
	sort(a+1,a+m+1);
	int qwq=0;
	for(int i=1; i<=m; ++i) {
		if(a[i].x!=a[i-1].x) {
			b[++qwq]=a[i];
		} else {
			b[qwq].y+=a[i].y;
		}
	}
	m=qwq;
	for(int i=1; i<=m; ++i) {
		a[i]=b[i];
	}
	init();
	//分根号段
	//然后直接跳
	for(int u=1; u<=n; ++u) {
		for(int i=1; i<=tot; ++i) {
			sumn[i]+=sad[i];
			sumc[i]+=sct[i];
			addn[i]++;//多一天
		}
		for(int i=1; i<=tot; ++i) {
			if(sumn[i] > c[u]) {
				solve(i,c[u]);//暴力改块内
				break;
			} else {
				c[u]-=sumn[i];
				ans+=sumc[i];
				sumn[i]=0;
				sumc[i]=0;
				addn[i]=0;
				qk[i]=u;
				//第u天这个块卖空了
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}

好难难难难啊/kk

首先我们发现原题的眼睛,做过一个也是可以轮流开大招取走一些数然后nim游戏的题

这个是那个题的完全升级版,我们要把每个石子复制两堆,但是一次可以选择1或2个

然后 $3-nim$ ,也就是每个二进制位下 $%3==0$

$x_1....x_n \in (0,1,2)$

\sum_{bit} \sum x_i*ai_{bit}=0 (mod 3)

那么我们可以发现其实就是找到膜3意义下权值最大的线性无关组

这个和之前那个题就很相像了

可以考虑遍历线性基的每个位置,如果某个位置在线性基是空的,我们就直接加入

否则把当前向量和线性基中这个位置对应的向量中攻击力小的那个拿出来继续消元

显然是题解,我们想想怎么找QAQ

代码告诉我:我们对于每个二进制位维护一个是1还是2的b数组线性基

然后我们用一个三进制异或的东西,找到一个可行的答案

解释一下三进制异或吧:

$2+2||1+0||0+1 = 1$

$1+1||2+0||0+2 = 2$

然后QAQ....

好像本质上是我们考虑三进制的每一位他们都可以被两个二进制位表示一下

比如11->1,1,10->1,0

然后我们开两个二进制数,第一个表示我们第一位三进制位意义下,第二个表示我们第二个三进制位

然后显然一开始我们如果只用第一个三进制位就能得到纯二进制位的答案

然后自己抿了抿,完全不会了

update in 9/6/16:48

抓本质说话:我们本质上是维护一个三进制线性基

那么我们首先开一个 $b_1,b_2$ 数组,表示三进制下我哪些位是1哪些位是2

然后我们考虑正常的线性基过程:如果这一位有数我们就要异或一下

考虑三进制异或分开放在哪些位是1哪些位是2的数意义下面

对于二进制都是2的,我们有 $1+1||2+0||0+2 = 2$

对于二进制都为1的,我们有
$2+2||1+0||0+1 = 1$

其实就是代码中两个长的位运算式子

这样我们就维护了整个三进制操作的线性基,就可以套用之前那个nim游戏题的思想结束整个题了

注意代码里有一个 $swap(p,q)$ 你考虑我们线性操作包括取反向量(*-1)所以这个是可以的

复杂度 $O(nlogn)$

思考本题+读代码时间 : $2h30min$

~~浪费时间....~~

code:


#include<bits/stdc++.h>
#define mkp(x,y) (make_pair(x,y))
#define se second
#define fi first
#define ll long long
#define pii pair<int,int>
#define swap(x,y) (x^=y^=x^=y)
using namespace std;
const int P = 1e9 + 7;
int n;
ll b0[60], b1[60], b2[60], ans;

void ins(ll x, ll y, int z) {
	for(ll i = 59; i >= 0; --i) {
		if(x >> i & 1 || y >> i & 1) {
			if(!b1[i] && !b2[i]) {
				b1[i] = x;
				b2[i] = y;
				b0[i] = z;
				return ;
			}
			if(z > b0[i])
				swap(x, b1[i]), swap(y, b2[i]), swap(z, b0[i]);
			ll p = b1[i], q = b2[i];
			if((y ^ q) >> i & 1)swap(p, q);
            //对齐
			ll u = (x & ~(p | q)) | (y & p) | (~(x | y) & q);
			ll v = (y & ~(p | q)) | (~(x | y) & p) | (x & q);
			//得到三进制异或之后的b_1,b_2
			//然后新的u,v就是对应下一次的....
			x = u, y = v;
		}
	}
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		ll x;
		int y;
		scanf("%lld %d", &x, &y);
		x ^= ans;
		ins(x, 0, y);
		ans = 0;
		for(int i = 0; i < 60; ++i)
			ans += b0[i];
		printf("%lld\n", ans);
	}
	return 0;
}

夏晓光(loveJY)的博客

P2300 合并神犇