t1

題意

有 \(q\) 個(gè)人在一個(gè)神秘的迷宮中尋寶，每個(gè)人都從某一個(gè)位置開(kāi)始，尋找屬于自己的寶藏。

這個(gè)迷宮可以描述為一個(gè) \(n \times m\) 的網(wǎng)格圖，從上到下第 \(x\) 行，從左到右第 \(y\) 列的位置用 \((x, y)\) 表示。

每個(gè)人可以在迷宮中移動(dòng)若干次，每次可以向上下左右相鄰的格子進(jìn)行移動(dòng)，但是無(wú)法移動(dòng)到含有障礙物的格子。

除此以外，迷宮中還有 \(k\) 個(gè)傳送門，每當(dāng)一個(gè)人處在傳送門入口所在的位置，就可以選擇直接傳送到出口所在的位置，傳送門是單向的。

得知了迷宮的具體構(gòu)造之后，現(xiàn)在小X想知道，哪些人能夠成功找到自己的寶藏。

對(duì)于 \(100\%\) 的數(shù)據(jù)，滿足 \(n \times m \leq 50000\)，\(k \leq 100\)，\(q \leq 100000\)。

題解

先不考慮傳送門做一次 \(dfs\) 判斷連通性。然后發(fā)現(xiàn)傳送門比較少，用傳送門把聯(lián)通塊連起來(lái)。對(duì)于每一個(gè)詢問(wèn)跑一次 \(dfs\)，可以做到 \(O(nm+qk)\)。

但是我考場(chǎng)上做法比較獵奇，我沒(méi)看到傳送門這么少，我考慮對(duì)聯(lián)通塊做 \(tarjan\)，去掉環(huán)之后維護(hù)這個(gè) \(dag\) 的連通性，用 \(bitset\) 維護(hù)，時(shí)間復(fù)雜度 \(O(nm+\frac{n^2m^2}{w})\) 。

const int N=5e4+10;
int n,m,qq,k,T,a[N],fa[N],vis[N],ans[N];
int dfn[N],low[N],tot,col,scc[N],d[N];
vector<int> g[N],g1[N],g2[N];
vector<pii> qr[N];
int dx[5]={0,-1,0,1};
int dy[5]={-1,0,1,0};
string s[N];
bitset<N> bt[N];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
inline int idx(int x,int y){
	return (x-1)*m+y;
}
void dfs(int u,int f){
	fa[find(u)]=find(f);
	vis[u]=1;
	for(int v:g[u]){
		if(vis[v]) continue;
		dfs(v,u);
	}
}
stack<int> st;
void tar(int u){
	dfn[u]=low[u]=++tot;vis[u]=1;
	st.push(u);
	for(int v:g1[u]){
		if(!dfn[v]){
			tar(v);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}if(low[u]==dfn[u]){
		col++;
		while(1){
			int t=st.top();st.pop();
			vis[t]=0;scc[t]=col;
			if(u==t) break;
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
    cin>>n>>m>>k>>qq;
    rep(i,1,N-1) fa[i]=i;
    rep(i,1,n){
    	cin>>s[i];s[i]=" "+s[i];
	}rep(i,1,n){
		rep(j,1,m){
			if(s[i][j]=='#') continue; 
			rep(k,0,3){
				int fx=dx[k]+i;
				int fy=dy[k]+j;
				if(fx<1||fy<1||fx>n||fy>m) continue;
				if(s[fx][fy]=='#') continue; 
				g[idx(i,j)].pb(idx(fx,fy));
				g[idx(fx,fy)].pb(idx(i,j));
			}
		}
	}rep(i,1,n){
		rep(j,1,m){
			if(!vis[idx(i,j)]){
				dfs(idx(i,j),idx(i,j));
			}
		}
	}
	rep(i,1,k){
		int a,b,c,d;cin>>a>>b>>c>>d;
		g1[find(idx(c,d))].pb(find(idx(a,b)));
	}m(vis);
	rep(i,1,n){
		rep(j,1,m){
			if(!dfn[find(idx(i,j))]&&s[i][j]!='#') tar(find(idx(i,j)));
		}
	}
	rep(i,1,qq){
		int a,b,c,d;cin>>a>>b>>c>>d;
		qr[scc[find(idx(a,b))]].pb({scc[find(idx(c,d))],i});
	}rep(i,1,n){
		rep(j,1,m){
			for(int v:g1[find(idx(i,j))]){
				if(scc[find(idx(i,j))]!=scc[find(v)]){
					g2[scc[find(idx(i,j))]].pb(scc[find(v)]);
					d[scc[find(v)]]++;
				}
			}
		}
	}queue<int> q;
	rep(i,1,col) if(!d[i]) q.push(i);
	while(!q.empty()){
		int u=q.front();q.pop();
		bt[u][u]=1;
		for(pii t:qr[u]){
			int v=t.fi,id=t.se;
			if(bt[u][v]==1) ans[id]=1;
		}for(int v:g2[u]){
			d[v]--;bt[v]|=bt[u];
			if(!d[v]) q.push(v);
		}
	}rep(i,1,qq) cout<<ans[i]<<'\n';
	return 0;
}

t2

題意

小X曾經(jīng)有一個(gè)神奇的字符串 \(S\)，\(S\) 每一個(gè)字符都是一個(gè)非負(fù)整數(shù)。

將 \(S\) 的字符從 \(1\) 開(kāi)始依次編號(hào)，設(shè) \(n = |S|\)，用 \(S_{i, j}\) 表示 \(S\) 的第 \(i\) 個(gè)字符到第 \(j\) 個(gè)字符構(gòu)成的子串。

每條信息都是 \(x_i, y_i, z_i\) 的形式，表示 \(\operatorname{LCP}( x_i, y_i) = z_i\)。

現(xiàn)在小X只想你找到所有滿足條件的字符串中，字典序最小的一個(gè)。

第一行兩個(gè)整數(shù) \(n, m\)，表示字符串長(zhǎng)度，信息個(gè)數(shù)。

然后 \(m\) 行，每行三個(gè)整數(shù) \(x_i, y_i, z_i\)，描述一條信息。

對(duì)于所有數(shù)據(jù)點(diǎn)，滿足 \(1 \leq m \leq 1000\)。

題解

詐騙題。

時(shí)間復(fù)雜度是 \(O(n^2)\) 的，考慮限制個(gè)數(shù)。發(fā)現(xiàn)每個(gè) \(\operatorname{LCP}( x_i, y_i) = z_i\)，就是在告訴你 \((x_i,x_i+z_i-1)=(y_i,y_i+z_i-1)\)，和\((x_i+z_i,x_i+z_i)\ne(y_i+z_i,y_i+z_i)\)。

這個(gè)限制數(shù)也是 \(O(n^2)\) 的，所以可以并查集暴力維護(hù)出來(lái)所有位置顏色相不相同。然后就是貪心放每個(gè)顏色。具體的話用一個(gè) \(bitset\) 維護(hù)連通性就好了 \(O(n^2+\frac{n^3}{w})\)，實(shí)際上可以通過(guò)倍增+并查集來(lái)實(shí)現(xiàn)合并，不同的關(guān)系只有 \(m\) 條，可以直接暴力處理貪心。

const int N=1e3+10;
int n,m,k,T,a[N],vis[N],ans[N],fa[N];
bitset<N> f[N],now;
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}vector<pii> q;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
    cin>>n>>m;
    rep(i,1,n) fa[i]=i;
	rep(i,1,m){
		int x,y,z;cin>>x>>y>>z;
		rep(j,0,z-1){
			int fx=find(x+j),fy=find(y+j);fa[fx]=fy;
		}if(y+z<=n&&x+z<=n) q.pb({x+z,y+z});
	}for(pii t:q){
		int x=find(t.fi),y=find(t.se);
		if(x==y){
			cout<<-1;return 0;
		}f[x][y]=f[y][x]=1;
	}rep(k,0,n){
		now=0;
		rep(i,1,n){
			if(vis[i]||(now&f[find(i)])!=0) continue;
			ans[i]=k;vis[i]=1;now[find(i)]=1;
		}
	}rep(i,1,n) cout<<ans[i]<<" ";
	return 0;
}

t3

題意

小X有一臺(tái)容量為 \(c\)的割草機(jī)。他決定將草坪分成 \(n\) 條通道，編號(hào)從 \(0\) 到 \(n-1\)，他必須按此順序割草。每條通道 \(i\) 含有未割草的數(shù)量 \(v[i]\)，由于一些未知原因，小X推動(dòng)割草機(jī)經(jīng)過(guò)該通道需要 \(a[i]\) 秒。

在經(jīng)過(guò)幾條通道后，割草機(jī)可能會(huì)達(dá)到滿載狀態(tài)，此時(shí)它會(huì)停止割草，留下該通道上的一些草。每當(dāng)這種情況發(fā)生時(shí)，需要清空其收集箱，這需要 \(b\) 秒，并且只能在通道末尾進(jìn)行。如果收集箱在小X經(jīng)過(guò)通道 \(i\) 時(shí)裝滿，他需要繼續(xù)推動(dòng)割草機(jī)直到通道末尾，清空收集箱，然后再次經(jīng)過(guò)該通道（或根據(jù)需要多次）以割除剩余的草。例如，如果對(duì)于通道 \(i\) 我們需要通過(guò) \(3\) 次才能清除所有草，那將花費(fèi) \(a[i] + b + a[i] + b + a[i]\) 秒。在割完整個(gè)草坪后，必須清空割草機(jī)。

經(jīng)過(guò)大量思考和抱怨完成割草將花費(fèi)他太多時(shí)間后，小X得出結(jié)論，有時(shí)在收集箱達(dá)到滿載之前清空它可能更省時(shí)，但他不確定可以使用的最佳策略。因此，他請(qǐng)求你的幫助。

給定每條通道上的草量和推動(dòng)割草機(jī)經(jīng)過(guò)每條通道所需的時(shí)間，收集箱的容量和清空它所需的時(shí)間，找出小X以最短時(shí)間完成割草的最佳方式。

對(duì)于所有測(cè)試數(shù)據(jù)，滿足: \(1 \leq n \leq 200000\)，對(duì)于每個(gè) \(0 \leq i < n\)， \(1 \leq a[i], v[i] \leq 10^{9}\)， \(1 \leq b, c \leq 10^{9}\)，保證正確答案不超過(guò) \(10^{18}\)。

題解

假交互，真難題。

考慮一個(gè)顯然的 \(dp\)，\(f_{i,j}\) 表示割完前 \(i\) 個(gè)草坪剩下 \(j\) 時(shí)間的最小時(shí)間。發(fā)現(xiàn)狀態(tài)數(shù)很難下降，考慮如何快速轉(zhuǎn)移。

考慮 $a _ { i } $, 設(shè) \(s u m\) 表 示初始箱子余量為0時(shí)只考慮打掃完 \(a _ { i }\) 至少需要多少時(shí)間。

當(dāng) \(a _ { i }\) 為 \(c\) 的倍數(shù)時(shí)，顯然有 \(d p _ { i - 1 , 0 } + s u m \rightarrow d p _ { i , 0 } 。\)

對(duì)于 $1 \leq j \leq c - 1 $, 有 \(d p _ { i - 1 , j } + s u m + a _ { i } \rightarrow d p _ { i , j } ,\) 因?yàn)橄啾扰c余量 \(0\)，需要多向草坪跑一次清完最后一點(diǎn)。

當(dāng) \(a _ { i }\) 不為 \(c\) 的倍數(shù)時(shí)，對(duì)于 \(0 \leq j \leq c - \left( v _ { i } \bmod c \right) - 1 ,\) 有 \(dp_{i?1,j} + s???u???m\rightarrow dp_{i,j + (v_{i}~mod ~c)}\) , 因?yàn)榍逦锤畈荽螖?shù)相同。 對(duì)于 $j = c - \left( v _ { i } \bmod c \right) $，有 $d p _ { i - 1 , j } + s u m + b \to d p _ { i , 0 } $，相比上一項(xiàng)要多清理一次未割草。

對(duì)于 \(c - \left( v _ { i } \bmod c \right) + 1 \leq j \leq c - 1 ,\) 有 \(d p _ { i - 1 , j } + s u m + b + a _ { i } \rightarrow d p _ { i , j-c - \left( v _ { i } \bmod c \right) } ,\) 相比上一項(xiàng)多跑一次草坪。 最后就是 \(\min \left\{ d p _ { i , j } \right\} + b \rightarrow d p _ { i , 0 } ,\) 因?yàn)槿我馊萘慷伎梢郧蹇铡?/p>

我們發(fā)現(xiàn)這個(gè)轉(zhuǎn)移被分為了至多三段，于是可以動(dòng)態(tài)偏移下標(biāo) 的位置，再用上區(qū)間加，全局最小值和
單點(diǎn)查詢操作。

然后這些用線段樹(shù)就可以全部做完啦，時(shí)間復(fù)雜度\(O(n\log V)\) ，因?yàn)橐獎(jiǎng)討B(tài)開(kāi)點(diǎn)。

細(xì)節(jié)：

• 為什么可以動(dòng)態(tài)開(kāi)點(diǎn)，而且同時(shí)有些標(biāo)記沒(méi)有下傳：
  • 因?yàn)槟切┠壳皼](méi)有出現(xiàn)在可能的答案時(shí)一定不優(yōu)，證明為什么只在過(guò)完草坪后才清除未滿的草最優(yōu)即可。
  • 因?yàn)樗袇^(qū)間轉(zhuǎn)移的大小是相同的特點(diǎn)，所以可以采用優(yōu)化轉(zhuǎn)移這種做法。

#include "strategy.h"
#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
int n,c,b,sum,root=1,cnt=1;
const int N=1e6+10;
struct node{
	int ls,rs;
	long long minx,tag;
	inline node():minx(0x3f3f3f3f3f3f3f3f){}
	inline void addtag(long long x){
		minx+=x,tag+=x;
	}
}d[N<<2];
inline void push_down(int v){
	if(d[v].tag){
		if(d[v].ls)d[d[v].ls].addtag(d[v].tag);
		if(d[v].rs)d[d[v].rs].addtag(d[v].tag);
		d[v].tag=0;
	}
}
void modify1(int &v,int l,int r,int w,long long x){
	if(!v) v=++cnt;
	if(l==r){
		d[v].minx=min(x,d[v].minx);return;
	}int mid=(l+r)>>1;
	push_down(v);
	w<=mid?modify1(d[v].ls,l,mid,w,x):modify1(d[v].rs,mid+1,r,w,x);
	d[v].minx=min(d[d[v].ls].minx,d[d[v].rs].minx);
}
long long query(int &v,int l,int r,int w){
	if(l==r) return d[v].minx;	
	int mid=(l+r)>>1;push_down(v);
	if(w<=mid) return query(d[v].ls,l,mid,w);
	else return query(d[v].rs,mid+1,r,w);
}
inline void modify2(int L,int R,long long x,int v=1,int l=0,int r=c-1){
	if(!v) return;
	if(L==l&&R==r) return d[v].addtag(x),void();
	int mid=(l+r)>>1;
	push_down(v);
	if(L<=mid) modify2(L,min(R,mid),x,d[v].ls,l,mid);
	if(R>mid) modify2(max(L,mid+1),R,x,d[v].rs,mid+1,r);
	d[v].minx=min(d[d[v].ls].minx,d[d[v].rs].minx);
}
void modify(int l,int r,long long x){
	if(l>r) return;
	l=(l+sum)%c,r=(r+sum)%c;
	if(l>r) modify2(0,r,x),modify2(l,c-1,x);
	else modify2(l,r,x);
}
long long mow(int N,int C,int B,vector<int>&a,vector<int>&v){
	n=N,c=C,b=B;
	modify1(root,0,c-1,0,0);
	for(int i=0;i<n;i++){
		long long val=(v[i]-1)/c+1;
		if(v[i]%c==0){
			modify(0,0,val*(a[i]+b));
			modify(1,c-1,val*(a[i]+b)+a[i]);
		}else{
			modify(0,c-v[i]%c-1,val*(a[i]+b)-b);
			modify(c-v[i]%c,c-v[i]%c,val*(a[i]+b));
			modify(c-v[i]%c+1,c-1,val*(a[i]+b)+a[i]);
		}long long tmp=d[1].minx+b;sum=((sum-v[i])%c+c)%c;
		modify1(root,0,c-1,sum,tmp);
	}
    return query(root,0,c-1,sum);
}

t4

題意

有 \(n\) 種石子，第 \(i\) 種石子有 \(a_i\) 顆，保證 \(\sum a_i \equiv 0 \pmod{2}\)。

首先，Alice需要將石子分成數(shù)目相等的兩堆，即，兩堆石子大小均為 \(\frac{\sum a_i}{2}\)。

接著，第一輪中，在分出的第一堆石頭上，兩個(gè)人交替取石子，每次只能取一顆，Alice先取，直到石子被取完為止。

然后，第二輪中，在分出的第二堆石頭上，兩個(gè)人交替取石子，每次只能取一顆，Bob先取，直到石子被取完為止。

最終，Alice在每一輪結(jié)束后，分別根據(jù)這一輪自己手中持有的石子來(lái)計(jì)算分?jǐn)?shù)，然后求和。

每一輪具體的得分計(jì)算方法為:

• 對(duì)于第 \(i\) 種石子，若 Alice 手中有 \(c_i\) 顆，那么他將獲得 \(\left\lfloor\frac{c_i}{p_i}\right\rfloor \times val_i\) 的分?jǐn)?shù)。

Alice的目標(biāo)是讓自己的分?jǐn)?shù)總和盡可能高，而B(niǎo)ob想讓Alice的分?jǐn)?shù)總和盡可能低。你覺(jué)得這個(gè)游戲很有趣，你想要知道，若兩人都絕頂聰明，Alice最終將得到多少分。

對(duì)于所有數(shù)據(jù)，有 \(1 \leq n \leq 2000\)，\(\sum a_i \leq 2 \times 10^6\)，\(\sum p_i \leq 2000\)，\(val_i \leq 3000\)，\(\sum a_i \times val_i \leq 2 \times 10^9\)，保證 \(a_i, p_i, val_i \geq 1\)，保證 \(\sum a_i \equiv 0 \pmod{2}\)。

題解

Sub 1

直接計(jì)算即可。

時(shí)間復(fù)雜度 \(O ( 1 )\)

Sub 2

考慮枚舉第一個(gè)人怎么分，然后分出來(lái)以后暴力枚舉兩人的取石子方案做搜索，一堆石子量至多只有4 顆，因此可以輕松跑過(guò)。 時(shí)間復(fù)雜度 \(O ( ? )\)

Sub 3

仍然考慮枚舉第一個(gè)人怎么分，設(shè) \(d p [ s t a t e 1 ] [ s t a t e 2 ] [ 0 / 1 ]\) 表示當(dāng)前還剩下的石子為 $s t a t e 1 $, 第一個(gè)人拿了的石子狀態(tài)為 $s t a t e 2 $, 這一步該第一個(gè)人走/第二個(gè)人走，在這一步按照最優(yōu)決策方案的情況下第一個(gè)人最終會(huì)得多少分

考慮時(shí)間復(fù)雜度，由于石子種類數(shù)不會(huì)太大（至多為10），狀態(tài)數(shù)總量也只有2000000左右，于是進(jìn)行記憶化搜索的極限時(shí)間復(fù)雜度就是 $O ( 2 e 7 ) $, 可以跑過(guò)。 時(shí)間復(fù)雜度 \(O \left( \left( \prod \left( a _ { i } + 1 \right) \right) ^ { 2 } n \right)\)

Sub 4

我們來(lái)重新審視一下這個(gè)游戲。

假設(shè)一組分組方案分出的每種石頭分別有 \(b _ { i }\) 個(gè)。

我們稱一種石子是"特殊的”，當(dāng)且僅當(dāng) \(b _ { i } \equiv - 1 \left( \bmod 2 \times p _ { i } \right)\)
考慮到，如果每一次第二個(gè)人都復(fù)讀第一個(gè)人的策略，那么有如下的情況：

對(duì)于不特殊的石子，第二個(gè)人可以通過(guò)模仿第一個(gè)人的決策，來(lái)讓第一個(gè)人只拿到 \(\left| \frac { b _ { i } } { 2 p _ { i } } \right| \times v a l _ { i }\) 的分?jǐn)?shù)

而對(duì)于特殊的石子，如果讓第一個(gè)人取到了第一顆，則第一個(gè)人能獲得 \(\left( \left[ \frac { b _ { i } } { 2 p _ { i } } \right] + 1 \right) \times v a l _ { i }\) 的分?jǐn)?shù)， 否則第一個(gè)人只能拿到 \(\left| \frac { b _ { i } } { 2 p _ { i } } \right| \times v a l _ { i }\) 的分?jǐn)?shù)。

本質(zhì)上講，特殊石子就是第一個(gè)人拿沒(méi)拿到第一顆會(huì)影響第一個(gè)人獲得分?jǐn)?shù)的石子，而非特殊石子就是不論拿到第一顆的是先手還是后手都不會(huì)影響分?jǐn)?shù)的石子。 于是我們有這樣一種策略：

如果場(chǎng)上存在特殊的石子，那么優(yōu)先拿走一顆分?jǐn)?shù)最高的特殊的石子，這樣若當(dāng)前決策者為第一個(gè)人， 則能獲得的分?jǐn)?shù)最高（特殊石子就相當(dāng)于多出來(lái)的分?jǐn)?shù)），若當(dāng)前決策者為第二個(gè)人，則能阻止第一個(gè)人獲得的額外分?jǐn)?shù)最多；當(dāng)特殊的石子被拿掉一顆之后，我們就再也不認(rèn)為它屬于特殊石子了。

令特殊石子的收益從大到小排序以后為 $v _ { 1 } , v _ { 2 } , \cdots , v _ { n } $。 對(duì)于非特殊石子，以及被拿掉一顆的特殊石子，第一個(gè)人總能通過(guò)某種方法拿到每種石子中的一半石子，而第二個(gè)人也總能通過(guò)復(fù)讀阻止第一個(gè)人拿到超過(guò)一半石子。

所以，若一開(kāi)始是第一個(gè)人先手，第一個(gè)人將獲得 \(\sum \left[ \frac { b _ { i } } { 2 p _ { i } } \right] + v _ { 1 } + v _ { 3 } + v _ { 5 } + \cdots\) 的分?jǐn)?shù)，若一開(kāi)始是第二個(gè)人先手，第一個(gè)人將獲得 \(\sum \left[ \frac { b _ { i } } { 2 p _ { i } } \right] + v _ { 2 } + v _ { 4 } + v _ { 6 } + \cdots\) 的分?jǐn)?shù)。

將所有石子的 \(v a l\) 從大到小排序，這樣若當(dāng)前加入石子是特殊石子，那么這種石子一定是現(xiàn)存所有特殊石子中分?jǐn)?shù)最小的。

考慮設(shè) \(d p [ i ] [ j ] [ 0 / 1 ] [ 0 / 1 ] ]\) 表示分配了前 \(i\) 種 石子，當(dāng)前第一堆石子中總共有 \(j\) 顆石子，第一堆石子中的特殊石子的奇偶性是 $0 / 1 $, 第二堆石子中的特殊石子的奇偶性是 $0 / 1 $, 第一個(gè)人到目前能取得的最大分?jǐn)?shù)是多少。

轉(zhuǎn)移就是枚舉當(dāng)前這種石子放多少顆，然后按照上面的式子計(jì)算第一個(gè)人將從這堆石子得到的分?jǐn)?shù)是多少即可。 最后的答案就是 \(\max \left\{ d p [ n ] \left[ \sum a _ { i } / 2 \right] [ 0 / 1 ] [ 0 / 1 ] \right\} 。\)

時(shí)間復(fù)雜度為 \(O \left( \left( \sum a _ { i } \right) ^ { 2 } \right)\)

Sub 5

\(\sum a _ { i }\) 很大但是有一個(gè)奇怪的式子的和很小。
觀察到假設(shè)你向第一堆石子里放入了 \(b _ { i }\) 個(gè) 第 \(i\) 種石子，那么你向第一堆石子中放入 \(b _ { i } + 2 p _ { i }\) 個(gè)第 \(i\) 種石子是不會(huì)影響最終分?jǐn)?shù)的。

看到數(shù)據(jù)范圍中 \(\sum p _ { i }\) 比較小，不妨考慮將 \(d p\) 的第二維變成 \(" b _ { i } \bmod 2 \times p _ { i } ^ { n }\) 的和，這樣在做 \(d p\) 時(shí)我們就不需要考慮枚舉這種石頭放了多少個(gè)，而是枚舉這種石頭模 \(2 p _ { i }\) 余多少個(gè)。

設(shè)你向第一堆石子中放入了的第 \(i\) 種石子模上 \(2 \times p _ { i }\) 的余數(shù)為 \(r _ { i }\) (就是你 \(d p\) 枚 舉的東西)，而第 \(i\) 種石子一共有 \(a _ { i }\) 顆。

我們稱”一組第 \(i\) 種石子"為 \(2 \times p _ { i }\) 顆第 \(i\) 種石子，上文的結(jié)論就是：我們將一組石子從第一堆移動(dòng)到第二堆，第一個(gè)人能獲得的分?jǐn)?shù)是不變的。 那么，當(dāng) \(r _ { i } \leq a _ { i } \bmod \left( 2 \times p _ { i } \right)\) 的時(shí)候，你可以自由分配 \(\left| \frac { a _ { i } } { 2 p _ { i } } \right|\) 組石頭；

當(dāng) \(r > a _ { i } \bmod \left( 2 \times p _ { i } \right) ,\) 你就僅能自由分配 \(\left| \frac { a _ { i } } { 2 p _ { i } } \right| - 1\) 組石頭。
如果同時(shí)存在兩種情況，是很蛋疼的。不妨在枚舉 \(r _ { i }\) 的時(shí)候，當(dāng) \(r _ { i } \leq a _ { i } \bmod \left( 2 \times p _ { i } \right) ,\) 同時(shí)去考慮放入 \(r _ { i }\) 顆石子和 \(r _ { i } + 2 p _ { i }\) 顆石子的情況，這樣最后能自由分配的石頭就統(tǒng)一為 \(\left| \frac { a _ { i } } { 2 p _ { i } } \right| - 1\) 組了。 這前半段 \(d p\) 的復(fù)雜度是 \(O \left( \left( \sum p _ { i } \right) ^ { 2 } \right) 。\)

接著我們要解決的就是，有 \(n\) 種石頭，第 \(i\) 種 石頭可以使用0到 \(\left| \frac { a _ { i } } { 2 p _ { i } } \right| - 1\) 組，問(wèn)能不能湊出 \(0 , 1 , 2 , \cdots , \frac { \sum a _ { i } } { 2 }\) 顆石頭。

這是一個(gè)背包問(wèn)題，如果直接背包的話首先你要枚舉石頭的種類，接著你要枚舉已經(jīng)放了多少石子，這一維大小是 $\sum a _ { i } $, 最后你要枚舉當(dāng)前石頭放多少組，這一維大小是 $\frac { a _ { i } } { 2 p _ { i } } $。 因此最終時(shí)間復(fù)雜度為 \(O \left( \left( \sum p _ { i } \right) ^ { 2 } + \left( \sum a _ { i } \right) \left( \sum \frac { a _ { i } } { 2 p _ { i } } \right) \right)\)

結(jié)合Subtask4的算法可以得到60分。

Sub6

考慮繼續(xù)優(yōu)化Subtask5的第二部分的計(jì)算。
設(shè) \(f [ i ] [ j ]\) 表 示已經(jīng)使用了前 \(i\) 種石子，現(xiàn)在石子堆里已經(jīng)有了 \(j\) 個(gè) 石子，最少需要用到多少組第 \(i\) 種 石子。 若不能湊出 \(j\) 個(gè)石子，則 \(f [ i ] [ j ] = - 1\)

轉(zhuǎn)移顯然：若 $f [ i - 1 ] [ j ] \neq - 1 $, 則 $f [ i ] [ j ] = 0 $;
否則，若 \(f [ i ] \left[ j - 2 \times p _ { i } \right] < \left[ \frac { a _ { i } } { 2 p _ { i } } \right] - 1\) 且 \(f [ i ] \left[ j - 2 \times p _ { i } \right] \neq - 1 ,\) 則
[f [ i ] [ j ] = f [ i ] \left[ j - 2 \times p _ { i } \right] + 1 ;]
否則 $f [ i ] [ j ] = - 1 $。

這樣我們順利地將第二部分的 \(d p\) 優(yōu)化到了 \(O \left( n \times \sum a _ { i } \right) 。\)
結(jié)合Subtask4的算法可以得到70分。

或者還有這樣一種方法：

有一個(gè)經(jīng)典問(wèn)題是，有1000個(gè)蘋果，你有十個(gè)籃子，你需要將蘋果放進(jìn)這十個(gè)籃子里，使得你總能選出其中一些籃子，使得籃子里的蘋果個(gè)數(shù)和為 \(i , 1 \leq i \leq 1 0 0 0\) 這個(gè)問(wèn)題的解是將蘋果分成：1,2,4,8,16,32,64,128,256,489個(gè)，具體證明很簡(jiǎn)單，略。

所以你可以把 \(\frac { a _ { i } } { 2 p _ { i } }\) 按照類似的方式拆分成 \(\log g\) 個(gè)物品然后背包。
用bitset加速就可以通過(guò)
。時(shí)間復(fù)雜度是 \(O \left( \frac { n \left( \sum a _ { i } \right) \left( \log \sum a _ { i } \right) } { 3 2 } \right)\)

Sub 7

第一部分的計(jì)算已經(jīng)相當(dāng)優(yōu)秀了，無(wú)需優(yōu)化。
我們來(lái)繼續(xù)優(yōu)化第二部分的計(jì)算。
\(f\) 計(jì)算的瓶頸在于，對(duì)于每一種石頭，我們都需要去遍歷一遍之前放了多少石頭。
考慮將 \(p _ { i }\) 相同的石頭合并。
令人驚喜的是，不同的 \(p _ { i }\) 至多只有 \(\sqrt { \sum p _ { i } }\) 種。
對(duì)于同樣的 $p _ { i } $, 我們統(tǒng)計(jì)這些石子一共可以放多少組，然后像S u b t a s k 6一樣轉(zhuǎn)移 \(f\) 即可。
最終的時(shí)間復(fù)雜度為 \(O \left( \left( \sum p _ { i } \right) ^ { 2 } + \left( \sqrt { \sum p _ { i } } \sum a _ { i } \right) \right) ,\) 可以通過(guò) \(1 0 0 \%\) 的數(shù)據(jù)。
與Subtask6相同，同樣可以使用bitset,同樣可以通過(guò)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct P{
	int a,p,v;
}a[2005];
int n,f[2][8005][2][2],t[4005],b[40005],N,S=0,sum=0,o=0,c=1;
bitset<1000005> g;
int main(){
   freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
	cin>>n,memset(f,0xc0,sizeof(f)),f[0][0][1][0]=0;
	for(int i=1;i<=n;i++)cin>>a[i].a>>a[i].p>>a[i].v,S+=a[i].a;
	sort(a+1,a+n+1,[](P x,P y){return x.v>y.v;});
	for(int i=1;i<=n;i++,c^=1){
		memset(f[c],0xc0,sizeof(f[c]));
		int w=min(a[i].a%(2*a[i].p)+2*a[i].p,a[i].a);
		t[i]=(a[i].a-w)/(2*a[i].p),sum+=t[i]*a[i].v,o+=w;//有 t[i] 組自由分配 
		for(int j=0;j<=o;j++){
			for(int k=0;k<=w&&k<=j;k++){
				int p1=(k%(2*a[i].p)==2*a[i].p-1),p2=((w-k)%(2*a[i].p)==2*a[i].p-1);
				for(int x=0;x<2;x++){
					for(int y=0;y<2;y++){
						f[c][j][x][y]=max(f[c][j][x][y],f[c^1][j-k][x^p1][y^p2]+k/(2*a[i].p)*a[i].v
										  +(w-k)/(2*a[i].p)*a[i].v+p1*(x^p1)*a[i].v+p2*(y^p2)*a[i].v);
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		int j=1;
		while(j<t[i])b[++N]=2*j*a[i].p,t[i]-=j,j<<=1;
		b[++N]=2*t[i]*a[i].p;
	}
	g[0]=1;
	for(int i=1;i<=N;i++)g|=g<<b[i];
	int ans=0;
	for(int i=0;i<=S/2;i++)if(g[i]&&S/2-i<=o)for(int x=0;x<2;x++)for(int y=0;y<2;y++)ans=max(ans,f[c^1][S/2-i][x][y]);
	cout<<ans+sum;
}