牛客练习赛 65 （待补E-网络流）

A.最值序列

排序后，前一半加后一半乘即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=500010; const ll mod=998244353; ll a[N]; int n; int main() {IO;int T=1;//cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);ll res=0;for(int i=1;i<=n;i++){if(i<=n/2) res=(res+a[i])%mod;elseres=res*a[i]%mod;}cout<<res<<'\n';}return 0; }

B.多重序列

注意$a_{i,j}=k^{b_j}，(b\ge 0)$
那么容易发现$$\prod _{j=1}^m{a}_{i,j}=k^{{\sum }_{j=1}^m{b}_j}$$
由此我们只需要统计每组的${\sum }_{j=1}^m{b}_j$的大小，取个最大的然后快速幂求一下结果即可。
注意精度问题：乱搞精度瞎胡近位即可
当然也可以手写求$log$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<cmath> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=2010; //const ll mod=998244353; int n,m,k; ll mod; ll qmi(ll a,ll b,ll p) {ll res=1;a%=p;while(b) {if(b&1) res=res*a%p;b>>=1;a=a*a%p;}return res; } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>m>>k>>mod;if(k==1) cout<<1%mod<<'\n';else{ll cnt=0;for(int i=1;i<=n;i++){ll now=0;for(int i=1;i<=m;i++){ll a;cin>>a;now+=ll(log(double(a))/log(double(k))+0.5);//dt的精度问题}cnt=max(cnt,now);}cout<<qmi(k,cnt,mod)<<'\n';}}return 0; }

C.二维动点

不难发现最终答案一定是$\{-1,0,1,2,3\}$这几个值中的一个。
对于答案是$\{-1,0,1\}$很容易判断，这里只简要说明答案是$3$的情况。
首先$n=2$，并且四个点（原点、给的两个点、所求点）构成一个平行四边形答案就是$3$否则答案就是$2$。
如果输入或者所求点是$(0,0)$直接跳过即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<map> #include<cmath> #include<iostream> #include<algorithm> #define x first #define y second using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=100010; const ll mod=998244353; int n,q; map<pii,int> mp; pii a[N]; int gcd(int a,int b) {return b?gcd(b,a%b):a; } bool check(pii a,pii b,pii c,pii d)// a-b是否//c-d {return 1ll*(a.x-b.x)*(c.y-d.y)==1ll*(c.x-d.x)*(a.y-b.y); } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>q;int cnt=0;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;if(a[i].x==0&&a[i].y==0){n--,i--;continue;}int d=gcd(a[i].x,a[i].y);mp[{a[i].x/d,a[i].y/d}]++;}while(q--){int x,y;cin>>x>>y;if(x==0&&y==0) {cout<<0<<'\n';continue;}int d=gcd(x,y);if(mp.count({x/d,y/d})) cout<<1<<'\n';else if(mp.size()<=1) cout<<-1<<'\n';else if(n==2){pii p1={0,0},p2=a[1],p3=a[2],p4={x,y};bool ok=0;if(check(p1,p2,p3,p4)){if(check(p2,p3,p1,p4)||check(p1,p3,p2,p4)) ok=1;}if(check(p1,p3,p2,p4)){if(check(p1,p2,p3,p4)||check(p2,p3,p1,p4)) ok=1;}if(ok) cout<<3<<'\n';else cout<<2<<'\n';}else cout<<2<<'\n';}}return 0; }

D.最小公倍数

参考大佬题解
总结下这个题的几个性质
①拆出来的数不一样一定相对较优：相同的数说明这个数没用
②拆出来的数一定是质数或者一个质数的次幂：我们知道一个数可以分解质因数假设拆出来的数不满足前者条件，我们不妨假设一个数$b=p_1^{a_1}\times p_2^{a_2}$，分析可知该数对答案的贡献和这两个数的效果相同$p_1^{a_1},p_2^{a_2}$，并且先然由于$p_1^{a_1}\times p_2^{a_2}<p_1^{a_1}+p_2^{a_2}$，后者选择方案更优。
③不同质数的地位相同，我们优先选择小的质数。
④考虑一个质数我们选择$\{p^{a_1},p^{a_2},\dots ,p^{a_i}\}$，如果设$a_1<a_2<\cdots <a_i$一定有$a_1=1,a_2=2,a_i=i$，即连续选择，如果$a_j=k>j$那么让$a_j=j$结果一定更优。

根据上面几个性质，先线性筛素数，然后跑分组背包即可。
每个质数是一个物品，如果选择$p_i^1,p_i^2,\dots ,p_i^k$，那么体积$v$是$p_i^1+p_i^2+\cdots +p_i^k$，对答案的贡献是$f[j-v]\times (k+1)$
由于本题数据需要取模，而取模后大小会发生改变，这题最秒的是用$log$代替乘积。那么价值$w$变为$log(k+1)$。
$f[j]$是一个$pair$，第一个值记录$log$，第二个值记录原答案（取模），由于$pair$比较按照一个数，直接比较即可
注意：以下代码dp体积从大到小枚举优化了空间。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<cmath> #include<iostream> #include<algorithm> #define x first #define y second using namespace std; typedef long long ll; typedef pair<double,ll> pdl; const int N=100010; const ll mod=1e9+7;; int prime[N],cnt; bool st[N]; pdl f[N]; int n; void init(int n) {for(int i=2;i<=n;i++){if(!st[i]) prime[++cnt]=i;for(int j=1;prime[j]<=n/i;j++){st[prime[j]*i]=1;if(i%prime[j]==0) break;}} } int main() {IO;int T=1;//cin>>T;init(100000);while(T--){cin>>n;f[0]={0,1};ll now=0;for(int i=1;i<=cnt;i++){for(int j=n;j;j--){ll p=prime[i];ll s=prime[i];for(int k=1;s<=j;k++,p*=prime[i],s+=p)f[j]=max(f[j],{f[j-s].x+log2(k+1),f[j-s].y*(k+1)%mod});}now+=prime[i];if(now>n) break;}pdl res={0,0};for(int i=0;i<=n;i++) res=max(res,f[i]);cout<<res.y<<'\n';}return 0; }

此题让我想到反素数这题。我是数论渣渣啊

E.游走配对

未学习待补~
要加油哦~

总结

以上是生活随笔为你收集整理的牛客练习赛 65 （待补E-网络流）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。