Product
C - Product (atcoder.jp)
一共N层,对于每一层的每个数,都遍历上一层更新过后的结果,更新为新的结果,
比如样例:
2 40 3 1 8 4 2 10 5
动态数组a表示储存上一层除后留下来的数,
第一次a数组中只有40;
然后40/1=40 , 40/8=5, 40/4=10;
第二次动态数组a中只有40 5 10;
然后到第二层
40/10=4,40/5=8
5/5=1;
10/10=1;
统计一层一的个数;
#include<bits/stdc++.h>
using namespace std ;
#define int long long
int cnt=0;
int b[100005];
vector<int>a;
vector<int>c;
signed main(){int n,x;cin>>n>>x;a.push_back(x);for(int j=1;j<=n;j++){cnt=1;int l;cin>>l;for(int i=1;i<=l;i++){cin>>b[i];}for(auto p:a){for(int i=1;i<=l;i++){if(p%b[i]==0){c.push_back(p/b[i]);}}}a.clear();a=c;c.clear();}int ans=0;for(auto p:a){if(p==1)ans++;}cout<<ans<<endl;return 0;
}
Dice Sum
C - Dice Sum (atcoder.jp)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int dp[55][5000];
signed main(){int n,m,k;cin>>n>>m>>k;dp[0][0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=k;j++){for(int h=1;h<=m;h++)if(j-h>=0){dp[i][j]=(dp[i][j]+dp[i-1][j-h])%mod;}}}int ans=0;for(int i=0;i<=k;i++)ans=(ans+dp[n][i]+mod)%mod;cout<<ans%mod<<endl;return 0;
}
[ABC178C] Ubiquity - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Ubiquity
简单的容斥原理,我们只要将所有可能减掉没有9的可能和没有1的可能,这两个可能中包含了既没有9又没有0的组合,在加回来就行,总共n位数,每一位可以出现0 1 2 3 4 5 6 7 8 9 这10种数字,
所以总共就是10的n次方种可能。后面没有9或则没有0的情况就是只能选 0 1 2 3 4 5 6 7 8或者0 1 2 3 4 5 6 7 8 这9个数字,所以组合数就是9的n次方,后面既没有0又没有1就是8的n次方。
然后用快速幂算出即可;
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int q(int a,int b) //快速幂算法
{int ans = 1;while(b){if(b & 1){ans = ans * a % mod; }b >>= 1;a = a * a % mod;}return ans;
}
signed main(){int n;cin>>n;int ans=(q(10,n)-q(9,n)-q(9,n)+q(8,n))%mod;cout<<(ans+mod)%mod<<endl;return 0;
}
Left Right Operation
[ABC263D] Left Right Operation - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
前缀和+后缀和
先拿前缀和挨个比较,看看是全部变为 l 更小还是原本的更小,
记录每个位置的最小值,然后用前缀和加上后面全为r看看是多一个r更少还是原来的更少。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200005];
int sum,ans;
int hou[200005];
signed main(){int n,l,r;cin>>n>>l>>r;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}for(int i=1;i<=n;i++){hou[i]=min(hou[i-1]+a[i],i*l); }int ans=sum;for(int i=n+1;i>=1;i--){ans=min(ans,hou[i-1]+(n-i+1)*r);}cout<<ans<<endl;return 0;
}