經(jīng)過 2025 HE 最強 Oier RETF 的講課，我開始去寫一些 Atcoder 的題目，發(fā)現(xiàn)很多題目確實很有意思，我做的題目都偏簡單，基本上都是 1200-2400 這個范圍的，再高我很難做出來了，而且我做題極其不穩(wěn)定，所以想隨便寫一寫。

之前寫過不少好題，有空慢慢寫。

[持續(xù)更新]

ABC393E

給定了 \(N\) 個數(shù)字。

詢問從 \(1～N\)，每次若必須選擇一個數(shù)字，總共選擇 \(K\) 個，這些數(shù)的 gcd 最大是多少。

\(A[i]\le 10^6;n,k\le 1.2*10^6\)

我們觀察答案上下界，發(fā)現(xiàn)不會超過 \(1e6\)，我們考慮從 1 開始枚舉。

枚舉的過程中我們求出來每一個數(shù)字的情況就行。

對于我們已經(jīng)枚舉到了這個 gcd 為 val， 我們用 \(cnt[x]\) 統(tǒng)計 \(x\) 在 \(N\) 個數(shù)字中的出現(xiàn)次數(shù)。

我們枚舉這個 val 的所有倍數(shù)，判斷有幾個，如果大于 k，我們就嘗試將這些倍數(shù)的答案取 max 于這個 gcd。

代碼下

#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace BaiBaiShaFeng{
	const int MN=2e6+116;
	int n, a[MN], cnt[MN], k, ans[MN];
	void sol(){
		cin>>n>>k; for(int i=1; i<=n; ++i) cin>>a[i];
		for(int i=1; i<=n; ++i) cnt[a[i]]++;
		for(int i=1; i<MN; ++i){
			int sum=0;
			for(int j=i; j<MN; j+=i) sum+=cnt[j];
			if(sum>=k) for(int j=i; j<MN; j+=i)
				ans[j]=max(ans[j],i);
		}
		for(int i=1; i<=n; ++i) cout<<ans[a[i]]<<'\n';
		return;
	}
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	BaiBaiShaFeng::sol(); return 0;
}

ABC390F

給了一個長度為 \(N\) 的序列 \(A\)。

我們規(guī)定 \(f(L,R)\) 代表著我們先取出來序列中的 \(A_L\) 到 \(A_R\) 這一部分。

對這些選出來的序列做以下操作，這個函數(shù)值就是最小的操作次數(shù)。

選定 \(l,r\)，前提是序列中仍然在 \([l,r]\) 范圍內(nèi)每個位置都有出現(xiàn)次數(shù)。

刪除 \([l,r]\) 范圍內(nèi)的所有次數(shù)。

詢問我們 \(\sum_{l=1}^{N}\sum_{r=l}^{N}f(l,r)\)。

不難發(fā)現(xiàn)，這個問題就是問我們一個區(qū)間中有多少個聯(lián)通塊，我們考慮枚舉位置，統(tǒng)計它的左邊有多少個地方可以是區(qū)間左端點，右邊的地方有多少可以是右端點，為了避免算重的問題，所有值的考慮以第一次為準(zhǔn)，考慮沒有后趨的情況，這樣是不會重復(fù)的。

我們維護pre[i]和nxt[i]。

pre[i] 代表的是在 \(i\) 左側(cè)最大的位置滿足它是 \(A[i]\) 或者 \(A[i]+1\) 。

nxt[i] 代表的是在 \(i\) 右側(cè)最小的位置滿足它是 \(A[i]+1\)。

這樣我們算出一共有幾個也很簡單

就是 (i-(pre[i]+1)+1)*((nxt[i]-1)-i+1)。

直接做就好啦

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+116;
int n, a[MN], pos[MN], pre[MN], nxt[MN], ans;
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n; for(int i=1; i<=n; ++i) cin>>a[i];
	for(int i=1; i<=n+1; ++i) pos[i]=0;
	for(int i=1; i<=n; ++i){
		pre[i]=max(pos[a[i]],pos[a[i]+1]);
		pos[a[i]]=i;
	}
	for(int i=1; i<=n+1; ++i) pos[i]=n+1;
	for(int i=n; i>=1; --i){
		nxt[i]=pos[a[i]+1];
		pos[a[i]]=i;
	}
	for(int i=1; i<=n; ++i) ans+=(nxt[i]-i)*(i-pre[i]);
	cout<<ans<<'\n';
	return 0;
}

ABC364F

大概題意很簡單。

一共有 \(N+Q\) 個點，給定了 \(Q\) 個區(qū)間 \([l_i,r_i]\)， 每個區(qū)間有一個值 \(c_i\)。

第 \(i\) 個區(qū)間對應(yīng)第 \(i\) 個點。

第 \(i\) 個點有一條連向區(qū)間 \(N+[l_i,r_i]\) 的權(quán)值為 \(c_i\)。

我們按照 \(c_i\) 從小到大，枚舉每一個區(qū)間。

我們使用并查集維護每一個已經(jīng)連好的聯(lián)通塊的右端點，這樣的時間復(fù)雜度就是正確的。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+116;
int father[MN], n, q, ans=0;
int find(int x){
	if(father[x]!=x) father[x]=find(father[x]);
	return father[x];
}
struct Node{
	int val, l, r;
	bool operator < (const Node &o)const{
		return val<o.val;
	}
}save[MN];
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>q; for(int i=1; i<=n+q; ++i) father[i]=i;
	for(int i=1; i<=q; ++i) cin>>save[i].l>>save[i].r>>save[i].val;
	sort(save+1,save+q+1);
	for(int i=1; i<=q; ++i){
		int val=save[i].val, l=save[i].l, r=save[i].r;
		ans+=val; while(find(l)!=find(r)){
			ans+=val; father[find(l)]=find(l)+1;
		}
	}
	int cnt=0;
	if(find(1)!=find(n)) cout<<-1<<'\n';
	else cout<<ans<<'\n';
	return 0;
}

ABC366F

個人認(rèn)為比較好的題目。

給定 \(N\) 個一次函數(shù) \(f_1, f_2, \ldots, f_N\)，其中 \(f_i(x) = A_i x + B_i\)。

對于由 \(K\) 個 \(1\) 到 \(N\) 之間互不相同的整數(shù)構(gòu)成的長度為 \(K\) 的數(shù)列 \(p = (p_1, p_2, \ldots, p_K)\)，請你求出 \(f_{p_1}(f_{p_2}(\ldots f_{p_K}(1)\ldots ))\) 能取得的最大值。

\(N\le 2\times 10^5\)

\(K\le 10\)

這個大家很容易想到動態(tài)規(guī)劃吧，明顯的，我們沒有一個直接策略使得全局是最優(yōu)的...我們發(fā)現(xiàn)有的函數(shù)可以造成很大影響，但是我們并不清楚它在那個位置才能發(fā)揮最大效益。

所以我們考慮動態(tài)規(guī)劃，但是看著龐大的數(shù)據(jù)范圍我們陷入了沉思...

這個狀態(tài)自然是好設(shè)計的，按照考慮到第 \(i\) 個函數(shù)為階段，附加一維到現(xiàn)在選擇了 \(j\) 個作為狀態(tài)。

\(dp[i][j]\) 就是考慮到第 \(i\) 個數(shù)字時，選擇了 \(j\) 的最大值。

這個看上去沒什么問題，事實上也沒有什么問題。

唯一的問題在于我們并不知道怎么進行轉(zhuǎn)移了......

因為我們新加入一個時，當(dāng)前狀態(tài)最佳的并不是直接按照這個新加入的運算一次，有可能是套在里邊才會更大。

這可怎么辦啊.... 如果我們可以保證每新考慮一個函數(shù)，直接在后邊運算就是最優(yōu)該有多好...

誒！那我們想一個辦法保證直接在后邊運算最優(yōu)不就行了。

這種問題感覺想國王游戲一樣，我們試一試臨項交換。

我們不妨假設(shè)當(dāng)前 \(i>j\) 且 \(f_j(f_i(x))<f_i(f_j(x))\)，之后我們把這個不等式拆開。

\(A_j(A_ix+B_i)+B_j<A_i(A_jx+B_j)+B_i\)

乘開消去相同項后得到 \(A_jB_i+B_j<A_iB_j+B_i\)

之后觀察式子嘗試把擁有相同項的移到同側(cè)。

\(B_j-A_iB_j<B_i-A_jB_i\)

\(B_j(A_i-1)>B_i(A_j-1)\)

我們可以按照這個排序，這樣就可以保證每一次是最優(yōu)的。

剩下的就不必多說了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=4e5+415;
const int MK=20;
int n, k, dp[MN][MK];
struct Node{
	int a, b;
}save[MN];
bool cmp(Node i, Node j){
	return j.b*(i.a-1)<i.b*(j.a-1);
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>k; dp[0][0]=1;
	for(int i=1; i<=n; ++i) cin>>save[i].a>>save[i].b;
	sort(save+1,save+n+1,cmp);
	for(int i=1; i<=n; ++i){
		dp[i][0]=dp[i-1][0];
		for(int j=1; j<=k; ++j){
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]*save[i].a+save[i].b);
		}
	}
	cout<<dp[n][k]<<'\n';
	return 0;
}

ABC159F

給定一個長度為 \(N\) 的整數(shù)序列 \(A_1, A_2, \ldots, A_N\) 和一個正整數(shù) \(S\)。
對于所有滿足 \(1 \leq L \leq R \leq N\) 的整數(shù)對 \((L, R)\)，定義 \(f(L, R)\) 如下：

• \(f(L, R)\) 表示滿足 \(L \leq x_1 < x_2 < \cdots < x_k \leq R\) 且 \(A_{x_1} + A_{x_2} + \cdots + A_{x_k} = S\) 的整數(shù)序列 \((x_1, x_2, \ldots, x_k)\) 的個數(shù)。

請計算所有滿足 \(1 \leq L \leq R \leq N\) 的整數(shù)對 \((L, R)\) 的 \(f(L, R)\) 之和。由于答案可能非常大，請輸出其對 \(998244353\) 取模的結(jié)果。

• 輸入均為整數(shù)。
• \(1 \leq N \leq 3000\)
• \(1 \leq S \leq 3000\)
• \(1 \leq A_i \leq 3000\)

這個好像看起來不太可做？

計數(shù)問題先別著急開搞，我們發(fā)現(xiàn)可以枚舉 \(L,R\) 跑背包，但是復(fù)雜度是萬萬不可的。

既然我們似乎沒有辦法從 \(L,R\) 下手，我們只剩下考慮一個和為 \(S\) 的子序列的貢獻了。

我們發(fā)現(xiàn)如果知道這個子序列的起始位置和結(jié)束位置，我們叫做 \(l,r\)，那么顯然它可以貢獻 \(l(n-r+1)\)

看似可做了一些。

如果我們對于每一個位置都維護下以它為終點的，左邊那些 \(l\) 的總和，我們不就很簡單的可以直接計算了嘛？

這個一看就是一個 dp 好乏。

我們假設(shè) \(dp[i][j]\) 表示到目前的 \(i\) 為止，一共的和為 \(j\) 的，統(tǒng)共的 \(l\) 的和。

這個東西不就是一個 0/1 背包么？

從 i-1 考慮放一個不可重復(fù)利用的 \(a[i]\)，最后吧和是 \(a[i]\) 的直接加上 \(i\)。

考慮到這個地方就好做了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int MN=3555;
int dp[MN], n, s, a[MN], ans=0;
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>s; for(int i=1; i<=n; ++i) cin>>a[i];
    for(int i=1; i<=n; ++i){
    	for(int j=s; j>a[i]; --j)
    		dp[j]=(dp[j]+dp[j-a[i]])%mod;
    	dp[a[i]]=(dp[a[i]]+i)%mod;
    	ans=(ans+(n-i+1)*dp[s]%mod)%mod;
    	dp[s]=0;
    }
    cout<<ans<<'\n';
    return 0;
}

ABC385F

神秘題

一個小小貪心，不太好想。

考慮每一次僅僅取相鄰的答案。

只有下一個比當(dāng)前的高度小才是有意義的。

討論再往下會發(fā)現(xiàn)所有的貢獻都來自相鄰的。

代碼

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+116;
long double ans=-1e9;
int n;
struct Node{
	long double x, h;
	bool operator <(const Node &o)const{return x<o.x;}
}sav[MN];
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n; for(int i=1; i<=n; ++i) cin>>sav[i].x>>sav[i].h;
	sort(sav+1,sav+n+1);
	for(int i=2; i<=n; ++i){
		ans=max(ans,sav[i].h-(sav[i].h-sav[i-1].h)/(sav[i].x-sav[i-1].x)*sav[i].x);
	}
	if(ans>=0) cout<<fixed<<setprecision(10)<<ans<<'\n';
	else cout<<-1<<'\n';
	return 0;
}