layout: post
title: 南昌邀请赛网络赛
- author: "luowentaoaa"
- catalog: true
- tags:
- mathjax: true
- - codeforces
- - DP
传送门
今天我的问题:
1: 没有看 D, 一眼认为 D 是大模拟题, 就不做了,(其实 D 只是个 DP 而且我是可以切掉的)
2: 不去做 I 题, 其实 I 题我有基本思路但是我的想法代码量太大.(太懒)
3: 梦游太久, 没有及时去开新题. 坐等翻译
4:C 题没想清楚就上了, 后面发现自己没有大数快速幂板子, 浪费时间
D. Match Stick Game
D 这题是真特么可以做得出来, 学弟让我做 我第一眼看到图, 以为是个大模拟, 我操 结果赛后一发 AC fuck
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn=1e5+50;
- #define bug cout<<"hello"<<endl;
- int num[maxn];
- /// 0 1 2 3 4 5 6 7 8 9
- int a[50]={6,2,5,5,4,5,6,3,7,6};
- ll mx[20][150],mi[150][20];/// 几位用了几根;
- ll dp[200][1000];/// 前几个数字用了多少根
- void init(){
- for(int i=1;i<20;i++)
- for(int j=0;j<150;j++){
- mx[i][j]=-1e18,mi[i][j]=1e18;
- }
- mx[0][0]=mi[0][0]=0;
- for(int i=0;i<20;i++){
- for(int j=0;j<150;j++){
- for(int k=0;k<=9;k++){
- int ned=a[k];
- if(i==0&&k==0)continue;
- if(mx[i][j]!=-1e18){
- mx[i+1][j+ned]=max(mx[i+1][j+ned],mx[i][j]*10+k);
- }
- if(mi[i][j]!=1e18){
- mi[i+1][j+ned]=min(mi[i+1][j+ned],mi[i][j]*10+k);
- }
- }
- }
- }
- // cout<<mx[1][2]<<endl;
- // cout<<mx[1][7]<<endl;
- }
- int main()
- {
- init();
- int t;
- cin>>t;
- while(t--){
- int n;
- cin>>n;
- string s;
- cin>>s;
- int cnt=0;
- int k=1;
- memset(num,0,sizeof(num));
- for(int i=0;i<n;i++){
- if(s[i]=='-'){
- cnt++;
- ++k;
- }
- else if(s[i]=='+'){
- cnt+=2;
- ++k;
- }
- else{
- cnt+=a[s[i]-'0'];
- num[k]++;
- }
- }
- for(int i=0;i<=n+10;i++){
- for(int j=0;j<1000;j++){
- dp[i][j]=-1e18;
- }
- }
- // cout<<"cnt="<<cnt<<endl;
- dp[0][0]=0;
- for(int i=1;i<=k;i++){
- if(i==1){
- for(int j=1;j<=cnt;j++){
- for(int len=1;len<100&&len<=j;len++){
- if(dp[i-1][j-len]!=-1e18&&mx[num[i]][len]!=-1e18){
- dp[i][j]=max(dp[i][j],dp[i-1][j-len]+mx[num[i]][len]);
- // cout<<"a[i]="<<num[i]<<"len="<<len<<endl;
- // cout<<"mx[a[i][len]="<<mx[num[i]][len]<<endl;
- // cout<<"a[i]="<<num[i]<<endl;
- }
- }
- }
- }
- else{
- for(int j=1;j<=cnt;j++){
- for(int len=1;len<100;len++){
- if(len+2<=j&&dp[i-1][j-len-2]!=-1e18&&mx[num[i]][len]!=-1e18){
- dp[i][j]=max(dp[i][j],dp[i-1][j-len-2]+mx[num[i]][len]);
- }
- if(len+1<=j&&dp[i-1][j-len-1]!=-1e18&&mi[num[i]][len]!=1e18){
- dp[i][j]=max(dp[i][j],dp[i-1][j-len-1]-mi[num[i]][len]);
- }
- }
- }
- }
- }
- cout<<dp[k][cnt]<<endl;
- }
- return 0;
- }
- I. Max answer
单调栈处理出 左边界和右边界, 然后贪心选取前缀和差分一下.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn=5e5+50;
- #define bug cout<<"hello"<<endl;
- int ls[maxn],rs[maxn];
- ll sum[maxn];
- int a[maxn];
- stack<int>st;
- ll mx[maxn<<2],mi[maxn<<2];
- void build(int o,int l,int r){
- if(l==r){
- mx[o]=sum[l];
- mi[o]=sum[r];
- return;
- }
- int mid=(l+r)/2;
- build(o<<1,l,mid);
- build(o<<1|1,mid+1,r);
- mx[o]=max(mx[o<<1],mx[o<<1|1]);
- mi[o]=min(mi[o<<1],mi[o<<1|1]);
- }
- ll querymi(int o,int l,int r,int ql,int qr){
- // cout<<"o="<<o<<endl;
- if(ql<=l&&qr>=r){
- return mi[o];
- }
- int mid=(l+r)/2;
- ll ans=1e18;
- if(ql<=mid)ans=min(ans,querymi(o<<1,l,mid,ql,qr));
- if(qr>mid)ans=min(ans,querymi(o<<1|1,mid+1,r,ql,qr));
- return ans;
- }
- ll querymx(int o,int l,int r,int ql,int qr){
- if(ql<=l&&qr>=r){
- return mx[o];
- }
- int mid=(l+r)/2;
- ll ans=-1e18;
- if(ql<=mid)ans=max(ans,querymx(o<<1,l,mid,ql,qr));
- if(qr>mid)ans=max(ans,querymx(o<<1|1,mid+1,r,ql,qr));
- return ans;
- }
- int main()
- {
- int n;
- cin>>n;
- for(int i=1;i<=n;i++){
- cin>>a[i];
- sum[i]=sum[i-1]+a[i];
- }
- build(1,0,n);
- a[0]=a[n+1]=-1e9;
- st.push(0);
- for(int i=1;i<=n;i++){
- while(!st.empty()&&a[st.top()]>=a[i])st.pop();
- ls[i]=st.top();
- st.push(i);
- }
- while(!st.empty())st.pop();
- st.push(n+1);
- for(int i=n;i;i--){
- while(!st.empty()&&a[st.top()]>=a[i])st.pop();
- rs[i]=st.top();
- st.push(i);
- }
- ll ans=0;
- for(int i=1;i<=n;i++){
- int l1=ls[i],r1=i-1;
- int l2=i,r2=rs[i]-1;
- if(a[i]<0){
- ans=max(ans,a[i]*(querymi(1,0,n,l2,r2)-querymx(1,0,n,l1,r1)));
- }
- else{
- ans=max(ans,a[i]*(querymx(1,0,n,l2,r2)-querymi(1,0,n,l1,r1)));
- }
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3030875.html