A 魔法
你有三个数 \(A,B,C\)。你有一种魔法，对三个数中的任何一个 \(x\) 使用一次魔法，可以使得这个数变成 \(\max(0,x-d)\)。其中，\(d\) 是固定的魔法参数。
你想把三个数变成优美的，也就是：
1、\(A,B,C\) 各不相同；
2、\(B\) 是最大的或是最小的；
你想知道，最少需要用几次魔法。
傻逼分讨。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int d,a,b,c,ans1,ans2;
signed main(){
cin>>d>>a>>b>>c;
if(d==0){
if(a==b||b==c||a==c)cout<<-1;
else if(a<b&&c<b)cout<<"0\n";
else if(a>b&&c>b)cout<<0<<"\n";
else cout<<-1;exit(0);
}
int minx=(a==c)?max(a-d,0ll):min(a,c);
if(minx==0)ans1=1e18;
else if(b<minx)ans1=(a==c);
else ans1=(b-minx)/d+1+(a==c);
if(b==0)ans2=1e18;
else{
if(b<=a)ans2+=(a-b)/d+1;
if(b<=c)ans2+=(c-b)/d+1;
int nowa=(b<=a)?max(a-((a-b)/d+1)*d,0ll):a,nowc=(b<=c)?max(c-((c-b)/d+1)*d,0ll):c;
if(nowa==nowc){
if(nowa==0)ans2=1e18;
else ans2++;
}
}
cout<<(min(ans1,ans2)==1e18?-1:min(ans1,ans2))<<"\n";
return 0;
}
B 募捐
慈善晚宴开始了，一共有 \(N\) 个人，总共要募捐 \(S\) 元。
募捐从第一个人开始，按照顺序依次进行，直到第 \(N\) 个人。由于这个顺序是按照社会地位来排的，后面的人总是要比前面的人多捐至少 \(K\) 元。第一个人没有限制，可以捐任意多钱，甚至可以捐 元。
你很好奇，想知道一共有多少种可能性，使得 \(N\) 个人正好捐了 \(K\) 元。
把第 \(i\) 个人的捐钱数减去 \(ki\)，记 \(s\) 是减去后的总和，那么题目转化为：
- 求有多少个长度为 \(n\)，单调不降的数列总和为 \(s\)。
那么我们将其差分后记为 \((a_1,a_2,\ldots a_n)\)，那么：
\[\sum_{i=1}^{n}a_i\times(n-i+1) \]为定值。
这样我们可以视作第 \(i\) 位的权值是 \(n-i+1\)，问每一位选若干次总和为 \(s\) 有多少种选法。
可以直接完全背包。
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,s,k,ans,dp[20005];
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>s>>k,s-=(n-1)*n/2*k;
if(s<0)cout<<"0",exit(0);
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=n-i+1;j<=s;j++)dp[j]+=dp[j-(n-i+1)],dp[j]%=mod;
}
cout<<dp[s];
return 0;
}
C 旅行
\(N\) 对夫妻去旅行，分成若干组，每组至少要有一对夫妻，问一共有多少种不同的分法。
两种分法不同，至少有一个组的成员不同。注意，分组是次序不相关的，例如以下两种分成两组的分法是相同的：\(\{Aa\}\{Bb\}\) 和 \(\{Bb\}\{Aa\}\)。
\[1\le N\le 600 \]标签：,cout,Bb,int,魔法,cin,募捐 From： https://www.cnblogs.com/DerrickLo/p/18161064