本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-12-03 18:37:52
1452E Two Editorialsbrute force, dp, greedy, sortings, two pointers Submit Add to favourites 2500 x1324
1452D Radio Towerscombinatorics, dp, math Submit Add to favourites 1600 x7063
1452C Two Bracketsgreedy Submit Add to favourites 800 x17468
1452B Toy Blocksbinary search, greedy, math, sortings Submit Add to favourites 1400 x12923
1452A Robot Programmath Submit Add to favourites 800
CF1452B
1.总和必需为（n-1)的倍数S 2. 找出最大的ai maxa和次大的maxaa, 如果这个数不是最大值，那么其余的数要补到最大值 如果这书数式最大值，那么其余的数补到次大值。 选任意盒子都行，实际不需要次大值。
#include<bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,a[N],maxa,s1,s2,s3;
void work(){
maxa=-1;
s1=s2=s3=0;
cin>>n;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
s1+=a[i];
if(a[i]>maxa)maxa=a[i];
}
s2=s1;
if(s1%(n-1)!=0)s2=s1+(n-1)-s1%(n-1);
s3=maxa*(n-1);
cout<<max(s3,s2)-s1<<endl;
}
int main(){
int t;
cin>>t;
while(t--)
work();
}
CF1542D
注意读题审题，每个点只能被一个信号控制 4:1 3:2 f(4)=f(3) +f(1) 5：1 4:2 3:3 f(5)=f(4) +f(2)+f(0)
f(6)=f(5)+f(3)+f(1)=f(5)+f(4); f(7)=f(6)+f(4)+f(2)+f(0)=f(6)+f(5) 斐波那契 每种方案都是等概率的
#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=2e5+9;
ll f[N];
ll qpow(ll a,ll b) {
ll ans=1;
while(b) {
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b\/=2;
}
return ans;
}
signed main() {
int n;
cin >> n;
f[1]=1,f[2]=1;f[3]=2;
for (int i = 3; i <= n; ++i) {
f[i]=(f[i-1]+f[i-2])%mod;
}
cout <<qpow(qpow(2, n), mod - 2) * f[n] %mod;
return 0;
}
递推的初值为：
f[0]=f[1]=f[2]=0
鲁ICP备2025150228号