炼石 plan 10.5

chelsy_qwq 的 blog / 2024-10-08 / 原文

A. 最棒的玩具销售员

nth_element 宣传片。

直接套路二分 $t$ 去调整可以过题，注意带 $\log$ 的无法通过要弄一点 $O(n)$ 玩意儿。

然后写总结的时候发现这玩意儿怎么能过的题目，这哪里有二分的单调性了，但是仔细思考之后发现有三分的单调性 /fad

总和斜率 $k\uparrow$，这部分的前缀和是凸包，然后 $b$ 的影响不影响凸性。

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

using namespace std;

inline int read() {
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') flag=0; ch=getchar(); }
    while(ch>='0'&&ch<='9') { X=(X<<1)+(X<<3)+ch-'0'; ch=getchar(); }
    if(flag) return X;
    return ~(X-1);
}

const int N=1000005;

int n, m, s, k[N], b[N];
ll a[N];

inline bool check(int x) {
	up(i,1,n) a[i]=(ll)k[i]*x+b[i];
	nth_element(a+1,a+n-m+1,a+1+n);
	ll sum=0;
	up(i,n-m+1,n) sum+=max((ll)0,a[i]);
	return sum>=s;
}

signed main() {
	freopen("merchant.in","r",stdin);
	freopen("merchant.out","w",stdout);
	n=read(), m=read(), s=read();
	up(i,1,n) k[i]=read(), b[i]=read();
	int l=0, r=1e18, Ans;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) Ans=mid, r=mid-1;
		else l=mid+1;
	}
	cout << Ans;
	return 0;
}

B. 只因数分解

爆搜之后发现只因数总量不多，支持预处理顺便排个序。

查询就贪心每次拿最大的，正确性不会说但是这种很难不过吧。

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

using namespace std;

const int N=21;

int t, n, m, cnt[N];
vector<int> F[N];

bool P(int x) {
	up(i,2,x-1) if(x%i==0) return 0;
	return 1;
}

void dfs(int t,int x,int mul) {
	if(x>t) {
		F[t].pb(mul);
		return;
	}
	dfs(t,x+1,mul);
	up(i,1,cnt[x]) {
		mul*=x;
		dfs(t,x+1,mul);
	}
}

signed main() {
	freopen("end.in","r",stdin);
	freopen("end.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	up(t,1,20) {
		up(i,2,t) cnt[i]=0;
		up(i,2,t) if(P(i)) {
			up(j,1,t) {
				int tmp=j;
				while(tmp%i==0) tmp/=i, ++cnt[i];
			}
		}
		dfs(t,1,1);
		sort(F[t].begin(),F[t].end());
	} 
	cin >> t;
	while(t--) {
		cin >> n >> m;
		vector<int> Ans;
		while(m) {
			int i=upper_bound(F[n].begin(),F[n].end(),m)-F[n].begin()-1;
			m-=F[n][i], Ans.pb(F[n][i]);
		} 
		cout << Ans.size() << '\n';
		for(int x:Ans) cout << x << ' ';
		cout << '\n'; 
	}
	return 0;
}