学校校园网站,推广分享,网站内容页面怎么做,网站建设方案书备案设计图目录 1.蘑菇炸弹
2.构造数字
3.小蓝的金牌梦
4.合并石子加强版
5.简单的LIS问题
6.期望次数 1.蘑菇炸弹
我们直接依照题目 在中间位置的数进行模拟即可
void solve(){cinn;vectorint a(n1);for(int i1;in;i) cina[i];int ans0;for(int i2;i…目录 1.蘑菇炸弹
2.构造数字
3.小蓝的金牌梦
4.合并石子加强版
5.简单的LIS问题
6.期望次数 1.蘑菇炸弹
我们直接依照题目 在中间位置的数进行模拟即可
void solve(){cinn;vectorint a(n1);for(int i1;in;i) cina[i];int ans0;for(int i2;in;i){if(a[i]a[i-1]a[i1]) ans;}coutansendl;return ;
}
2.构造数字
我们需要构造的数字最大由于数位已经告诉我们所以明显的有一个贪心的策略从最高位置开始从最大的数开始遍历是否可以填可以填减去看下一位即可
void solve(){cinnm;for(int i1;in;i){for(int j9;j0;j--){if(mj){coutj;m-j;break;}} }return ;
}
3.小蓝的金牌梦 我们有一个错误的想法就是找出最大的质数x然后直接求长度x的即可为什么是错误的呢因为题目中的元素带有负数所以我们要求出所有满足的来比较最大值我们可以考虑使用线性筛来求出所有的质数然后前缀和来求解即可
vectorint primes;
int cnt;void solve(){cinn;vectorLL a(n5);for(int i1;in;i) cina[i],a[i]a[i-1];auto get [](){vectorbool st(n5);for(int i2;in;i){if(!st[i]){primes.push_back(i);cnt;}for(int j0;primes[j]n/i;j){st[i*primes[j]]true;if(i%primes[j]0) break;}}};get();LL ans-1e18;// 注意初始化防止过小for(int i1;in;i){for(autov:primes){if(iv) break;ansmax(ans,a[i]-a[i-v]);}}coutansendl;return ;
}
4.合并石子加强版 首先我们不要直接先入为主认为是区间dp区间dp的时间复杂度一般是也不现实我们接着找是不是具有什么性质找最简模型
a b c -
1: 先左后右 a*b(ab)*c a*ba*cb*c
2: 先右后左 b*c(bc)*a a*ba*cb*c
我们可以发现无论左右结果不会变的那么也就是我们这个结果是不受操作所影响的所以我们选择最优的操作直接从左到右即可注意数据范围很大所以我们考虑要使用__int128来处理
void solve(){cinn;vectorLL a(n5);__int128 res0;for(int i1;in;i) cina[i];LL prea[1];for(int i2;in;i){resa[i]*pre;prea[i];}functionvoid(__int128) print [](__int128 res){if(res9) print(res/10);putchar(res%100);};print(res);return ;
}
5.简单的LIS问题 题目意思很简单修改一个数然后为然后求最长上升子序列我们可以发现数据范围是
3e3可以使用的接着就是找一个数修改 我们明显的可以划分为前面和后面来区别所以
我们求一个前面的最长上升子序列倒着求一个最长下降子序列拼接接着考虑单独的最长子序列操作对于上升子序列把后面的一个数改成比自己大即可对于改前面的数就需要注意是不是0(题目特殊限制)
void solve(){cinn;vectorint a(n5),dp1(n5,1),dp2(n5,1);for(int i1;in;i) cina[i];for(int i1;in;i)for(int j1;ji;j)if(a[j]a[i]) dp1[i]max(dp1[i],dp1[j]1);for(int in;i1;i--)for(int jn;ji;j--)if(a[i]a[j]) dp2[i]max(dp2[i],dp2[j]1);int ansdp1[n];for(int i1;in;i){for(int ji2;jn;j){if(a[i]a[j]-2){ansmax(ans,dp1[i]dp2[j]1);}}if(i!n) ansmax(ans,dp1[i]1);if(i!1 a[i]!0) ansmax(ans,dp2[i]1);}coutansendl;return ;
}
考虑提升数据范围就使用nlogn同时需要存在来这个时候的最大或者最小值以及数量
void solve(){cinn;vectorint a(n),A(n),B(n),cp(n),cl(n);for(autov:a) cinv;vectorint pre,last;for(int i0;in;i){int va[i];if(pre.empty()||vpre.back()) pre.push_back(v);else pre[lower_bound(pre.begin(),pre.end(),v)-pre.begin()]v;A[i]pre.back();// 表示到这个点的时候的最大值是多少cp[i]pre.size();// 表示到这个点的时候最长上升子序列的长度都是多少}reverse(a.begin(),a.end());int anspre.size();for(int i0;in;i){int va[i];if(last.empty()||vlast.back()) last.push_back(v);else last[lower_bound(last.begin(),last.end(),v,greaterint())-last.begin()]v;B[n-i-1]last.back();//表示到这个点的最小值是多少cl[n-i-1]last.size();// 表示这个点的长度是多少}for(int i0;in-1;i){if(i A[i-1]B[i1]-2){ansmax(ans,cp[i-1]cl[i1]1);}ansmax(ans,cp[i]1);if(i B[i]!0) ansmax(ans,cl[i]1);}coutansendl;return ;
}
6.期望次数
我们可以知道和是一个概率dp依照题目意思我们定义状态为当前 为x是期望为dp[x](xi)
1.当im 时 dp[i]0;
2.当im时
进行变形之后得到答案
其中sum是之和接着就可以按照公式倒着递推即可(注意逆元之类的操作)
LL qmi(LL a,LL b,LL p){LL res1;while(b){if(b1) resres*a%p;b1;aa*a%p;}return res;
}LL inv(LL x){return qmi(x,mod-2,mod);
}void solve(){cinnm;vectorLL dp(m);vectorint a(n);LL sum0;for(int i1;in;i) cina[i],suma[i];for(int im-1;i1;i--){for(int j2;jni*jm;j){dp[i]a[j]*dp[i*j];dp[i]%mod;}(dp[i]sum)%mod;dp[i]dp[i]*inv(sum-a[1])%mod;} coutdp[1]endl;return ;
}
