test28

我用什么才能留住你liuzhuni

我當然知道正解符合人類直覺，但是任意錯解難道不符合很多人的直覺嗎，沒有大樣例好難啊好難啊。注意到最優解一定可以是某種田忌賽馬，不妨枚舉贏的斷點，來做一個暴力的對拍。

首先套路又直覺的，我們想辦法說明先最大化 \(+1\) 的貢獻不劣，用 \(man_i\) 表示一個等級為 \(i\) 的類入，用 \(bike_i\) 表示一個等級為 \(i\) 的車車。考慮最優情況下存在一個 \(bike_i\) 匹配 \(man_i\)，而后面有一個 \(man_{j(>i)}\) 被擁擠到不能 \(+1\)，那么讓 \(man_j\) 搶走 \(man_i\) 的車車貢獻是 \((1/2)-(0/1)\geq 0\)。

現在要想辦法在最大化 \(+1\) 的前提下最大化 \(+0\) 的數量，顯然確定了前者之后盡量 \(man_i\) 匹配 \(bike_i\) 即可，所以我們要思考什么樣的情況下這個東西最大呢。考慮 \(bike_i\) 可以給 \(man_{l},man_r\) 匹配即 \(i<l<r\)，那么匹配給 \(l\) 更優，因為剩下來的 \(bike\) 更容易給 \(man_r\) 匹配 \(1/0\) 的貢獻。而對于 \(bike_l,bike_r\) 可以匹配到 \(man_i\) 即 \(l<r<i\)，顯然匹配 \(r\) 更好。那么不妨按照 \(man\downarrow\) 的順序貪心 \(+1\) 的貢獻，每一次查找一個編號最大的車車，最后再補算 \(0/-1\) 的貢獻喵 qwq

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)

using namespace std;

const int N=300005;

int n, x[N], y[N], Ans, stk[N], top;

signed main() {
	freopen("liuzhuni.in","r",stdin); 
	freopen("liuzhuni.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	up(i,1,n) cin >> x[i];
	up(i,1,n) cin >> y[i];
	up(i,1,n) {
		while(top&&y[i]) {
			int j=stk[top];
			int k=min(y[i],x[j]);
			x[j]-=k, y[i]-=k, Ans+=k;
			if(!x[j]) --top;
		}
		stk[++top]=i;
	}
	up(i,1,n) {
		int k=min(x[i],y[i]);
		x[i]-=k, y[i]-=k, Ans-=y[i];
	}
	cout << Ans << '\n';
	return 0;
}

我給你瘦落的街道、絕望的落日、荒郊的月亮wogeini

設計一個函數 \(f(a)=\sum_{i\neq j} [情侶i,j相交但不包含]\)，顯然這個必須下降到 \(0\)，同時依次操作最多讓這個下降 \(2\)（如果你認為 \(i,j\) 是有序對，那么就是下降 \(1\)），又注意到任意時刻肯定有這樣的位置（符合直覺且容易反證），所以最優操作次數就很好求了。

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)

using namespace std;

const int N=1000005;

int n, a[N], lst[N], Ans, tr[N];

void add(int x,int v) {
	for( ; x<=n; x+=x&-x) tr[x]+=v;
}

int ask(int x) {
	int ret=0;
	for( ; x; x-=x&-x) ret+=tr[x];
	return ret;
}

signed main() {
	freopen("wogeini.in","r",stdin); 
	freopen("wogeini.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n, Ans=n=(n<<1);
	up(i,1,n) cin >> a[i];
	up(i,1,n) {
		if(!lst[a[i]]) {
			lst[a[i]]=i;
			add(i,1);
		}
        else {
		    int j=lst[a[i]];
		    add(j,-2), add(i,1);
		    Ans+=ask(i-1)-ask(j);
        }
	}
	cout << Ans/2 << '\n';
	return 0;
}

我給你一個one

我做過原題，且因為年代久遠，我完全只記得怎么做，所以我毫不知情怎么寫題解比較自然。在虛構推理的過程中，其實感覺有點像要直接 yy 出一組充要的東西，但是這個題目好想到的東西就那么點、湊起來又恰好是正解彌補了這一點。

DAG 圖上的問題我們我們一般希望分層處理，其實也就是按照拓撲序考慮了，經驗告訴我們用拓撲序當新標號很贊。那么對于一個 \(i\)，我們能用的邊分為 \(u/v<i,u/v>i,u<i<v\)，三種前兩種的貢獻可以直接處理成正/反圖上的最短路，單邊貢獻就是前后綴最大值惹，第三種剛好可以用來合并貢獻，即動態維護 \(\max_{u<i<v} \{f_u+g_v+1\}\)，這個顯然可以掃，來個 multiset 即可。

#include<bits/stdc++.h>
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pb push_back

using namespace std;

const int N=500005, inf=1e9;

int n, m, tot, in[N], f[N], g[N], pre[N], suf[N], p[N], pos, Ans=inf;
vector<int> F[N], G[N];
queue<int> q;
multiset<int> counter;

void eadd(int u,int v) {
	F[u].pb(v), G[v].pb(u), ++in[v];
}

signed main() {
	freopen("one.in","r",stdin); 
	freopen("one.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	while(m--) {
		int u, v;
		cin >> u >> v;
		eadd(u,v);
	}
	up(i,1,n) if(!in[i]) q.push(i);
	while(q.size()) {
		int x=q.front(); q.pop();
		p[++tot]=x;
		for(int y:F[x]) if(!--in[y]) q.push(y);
	}
	up(u,1,n) {
		int i=p[u];
		for(int j:F[i]) f[j]=max(f[j],f[i]+1);
		pre[u]=max(pre[u-1],f[i]);
	}
	dn(u,n,1) {
		int i=p[u];
		for(int j:G[i]) g[j]=max(g[j],g[i]+1);
		suf[u]=max(suf[u+1],g[i]);
	}
	up(u,1,n) {
		int i=p[u], Pluto=max(pre[u-1],suf[u+1]);
		for(int j:G[i]) {
			int val=f[j]+g[i]+1;
			counter.erase(counter.find(val));
		}
		if(counter.size()) Pluto=max(Pluto,*--counter.end());
		if(Pluto<Ans||Pluto==Ans&&i<pos) pos=i, Ans=Pluto; 
		for(int j:F[i]) {
			int val=f[i]+g[j]+1;
			counter.insert(val);
		}
	}
	cout << pos << ' ' << Ans << '\n';
	return 0;
}

久久地望著孤月的人的悲哀beiai

本質不同的子序列的求法，設 \(f_i\) 表示考慮到 \(i\) 且強制 \(a_i\) 選的方案數，枚舉不同的值 \(j\) 轉移其最后一個位置的 \(f\)，放到這個題目里面就是 \(f_i=\sum_{j=1}^i f_{i-j}\)，發現好改成前綴和減少轉移點數，\(s_i-s_{i-1}=s_{i-1}-s_{i-m-1}\) 也就是 \(s_i=2s_{i-1}-s_{i-m-1}\)。

想要來一點組合意義，就是可以 \(i\to i+1\) 乘上系數 \(2\)，或者可以 \(i\to i+(m+1)\) 乘上系數 \(-1\)，枚舉多少次第二種走，可以得到 \(Ans=\sum_{i=0}^{\lfloor\frac{n}{m+1}\rfloor}(-1)^i2^{n-(m+1)i\binom{n-mi}{i}}\)，上標求和是調和級數，暴力求解即可。

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)

using namespace std;

const int N=1000005, P=1e9+7;

int n, q, m, f[N], tag[N], Ans;
int pw[N], mul[N], inv[N];

inline int C(int n,int m) {
	if(m<0||n<m) return 0;
	return mul[n]*inv[m]%P*inv[n-m]%P;
}

int solve(int m) {
	if(tag[m]) return f[m];
	tag[m]=1, Ans=0;
	up(i,0,n/(m+1)) {
		int val=pw[n-(m+1)*i]*C(n-m*i,i)%P;
		if(i&1) Ans=(Ans-val)%P; else Ans=(Ans+val)%P;
	}
	return f[m]=(Ans%P+P)%P;
}

signed main() {
	freopen("beiai.in","r",stdin); 
	freopen("beiai.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	pw[0]=mul[0]=inv[0]=inv[1]=1;
	up(i,1,n) pw[i]=pw[i-1]*2%P;
	up(i,1,n) mul[i]=mul[i-1]*i%P;
	up(i,2,n) inv[i]=inv[P%i]*(P-P/i)%P;
	up(i,2,n) inv[i]=inv[i-1]*inv[i]%P;
	while(q--) {
		cin >> m;
		cout << solve(m) << '\n';
	}
	return 0;
}