526互联

2018 ICPC Asia Qingdao (The 1st Universal Cup, Stage 9)

发布时间 2023-05-22 18:37:55作者: sz[sz]

image

E

看完题想到二分答案直接一步步贪心，没多想直接和队友说了下，感觉贪心会有点问题，放了一会后冷静分析了一下，发现返回造成的浪费是不可避免的，就很对了！

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
ll m;
ll a[N],b[N];
bool chk(ll ans){
    for(int i=1;i<=n;i++) b[i]=(ans-1)/a[i]+1;
    b[n+1]=0;
    ll res=m;
    for(int i=1;i<=n;i++){
        if(b[i]<=0){
            if(i<n) res--;
            if(res<0) return 0;
            continue;
        }
        res-=b[i]*2-1;
        b[i+1]-=b[i]-1;
        if(res<0) return 0;
    }
    return 1;
}
void work(){
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    ll l=0,r=1e18;
    while(l<r){
        ll mid=(l+r+1)>>1;
        if(chk(mid)) l=mid;
        else r=mid-1;
    }
    printf("%lld\n",l);
}
int main() {
    int T; cin>>T; while(T--) work();
    return 0;
}

G

考虑容斥没覆盖到的2，可以得到一个\(O(n^4)\)的dp，然后自闭一会觉得不可优化；但发现跑不满，用均值不等式和平方前缀和粗略地分析一下常数，发现上界会除掉48，然后就随便过了！

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
const int N=105,P=1e9+7;
void inc(int& x,int y){
    x+=y;
    if(x>=P) x-=P;
}
int prd(int x,int y){
    x=1ll*x*y%P;
    return x;
}
int fpw(int a,int x){
    int s=1;
    for(;x;x>>=1,a=prd(a,a)) if(x&1) s=prd(s,a);
    return s;
}
int n,m,a[N];
int tot,pos[N];
int su[N],c[N][N],f[N][2][N*N];
void work(){
    cin>>n>>m;
    tot=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]==2) pos[++tot]=i;
    }
    pos[0]=0; pos[tot+1]=n+1;
    for(int i=1;i<=n;i++) su[i]=i*(i+1)/2;
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++){
        int last=i-1,sum=0;
        for(int j=i;j<=n;j++){
            if(a[j]==1){
                sum+=su[j-last-1];
                last=j;
            }
            c[i][j]=sum+su[j-last];
            //cout<<"last="<<last<<endl;
            //cout<<i<<" "<<j<<" "<<c[i][j]<<endl;
        }
    }
    //memset(f,0,sizeof(f));
    for(int i=1;i<=tot+1;i++) for(int p=0;p<2;p++) for(int x=0;x<=c[1][n];x++) f[i][p][x]=0;
    f[0][0][0]=1;
    for(int i=1;i<=tot+1;i++){
        for(int j=0;j<i;j++){
            for(int p=0;p<2;p++){
                int t=c[pos[j]+1][pos[i]-1];
                //cout<<i<<" "<<j<<" "<<t<<endl;
                for(int x=t;x<=c[1][pos[i]-1];x++)
                    inc(f[i][p][x],f[j][!p][x-t]);
               // printf("i=%d ")
            }
        }
    }
    int ans=0;
    for(int x=1;x<=c[1][n];x++) {
        int sum=f[tot + 1][1][x];
       // cout<<"x="<<x<<" sum="<<sum<<endl;
        inc(sum,P-f[tot+1][0][x]);
        inc(ans,prd(sum,fpw(x,m)));
    }
    cout<<ans<<endl;
}
int main() {
    int T; cin>>T; while(T--) work();
    return 0;
}

I

过完G看了下感觉没什么思路，最后队友在写一个比较麻烦的做法，可惜来不及了。
最大最小很难同时考虑，先考虑最大：在最小值确定时，如何求出最大值的最小值？直接扫一遍dp即可。
考虑最小值固定为某个值\(v\)的条件（因为是求最值的问题，所以可以看做最小值不小于该值，大于的部分以更劣的方式计算，并且在之后会枚举计算到）：发现其实就是所有小于\(v\)的长度为1或2的段无效，放到dp上就是一些转移无效。
于是考虑从小到大枚举v，就是一个每次禁止掉一些新的转移的过程；而上述的dp是没有方向性的（即方便区间合并），那么是个很经典的问题，直接用线段树维护dp即可（即用区间分治代替线性dp）。

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const ll F=1e10;
int n,a[N],b[N];
void Min(ll& x,ll y){
    if(y<x) x=y;
}
struct SGT{
    ll mnmx[N<<2][2][2];
#define mid ((l+r)>>1)
#define lc (u<<1)
#define rc ((u<<1)|1)
    void mrg(int u){
        for(int p=0;p<2;p++) for(int q=0;q<2;q++){
            mnmx[u][p][q]=F;
            for(int k=0;k<2;k++) Min(mnmx[u][p][q],max(mnmx[lc][p][k],mnmx[rc][k][q]));
        }
    }
    void bld(int u,int l,int r){
        if(l==r){
            mnmx[u][0][0]=a[l];
            if(l<n) mnmx[u][0][1]=b[l];
            else mnmx[u][0][1]=F;
            if(l>1) mnmx[u][1][0]=-F;
            else mnmx[u][1][0]=F;
            mnmx[u][1][1]=F;
            return;
        }
        bld(lc,l,mid);
        bld(rc,mid+1,r);
        mrg(u);
    }
    void upd(int u,int l,int r,int d,int x,int y){
        if(l==r){
            mnmx[u][x][y]=F;
            return;
        }
        if(d<=mid) upd(lc,l,mid,d,x,y);
        else upd(rc,mid+1,r,d,x,y);
        mrg(u);
    }
}T;
struct node{
    int v,d,x,y;
};
bool cmp(node u,node v){
    return u.v<v.v;
}
void work(){
    scanf("%d",&n);
    vector<node>h;
    h.clear();
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        h.push_back((node){a[i],i,0,0});
        if(i>1) {
            b[i - 1] = a[i - 1] + a[i];
            h.push_back((node) {b[i - 1], i - 1, 0, 1});
        }
    }
    std::sort(h.begin(), h.end(),cmp);
    T.bld(1,1,n);
    ll ans=F;
    for(auto u:h){
        ans=min(ans,T.mnmx[1][0][0]-u.v);
        //cout<<T.mnmx[1][0][0]<<" "<<u.v<<endl;
        T.upd(1,1,n,u.d,u.x,u.y);
    }
    printf("%lld\n",ans);
}
int main() {
    int T; cin>>T; while(T--) work();
    return 0;
}

J

看到是签到题，直接认为是取前m+1个-1，再列出一些细节判一下就行，然后喜提一发罚时；然后队友提出会在m个之后取最小的，把第m+1个改成后缀最小值才对。（有点急没考虑清楚，造成拖累了几分钟的进度和签到+1，算是比较小的失误吧）

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,a[N];
ll s[N],mn[N];
void work(){
    int cnt=0,t=0;
    scanf("%d%d",&n,&m);
    for(int x,i=1;i<=n;i++){
        scanf("%d",&x);
        if(!x){
            cnt++;
            continue;
        }
        a[++t]=x;
        s[t]=s[t-1]+a[t];
    }
    mn[t]=a[t];
    for(int i=t-1;i>=1;i--) mn[i]=min(mn[i+1],1ll*a[i]);
    if(m==n) puts("Richman");
    else if(cnt>m) puts("Impossible");
    else {
        m-=cnt;
        printf("%lld\n",s[m]+mn[m+1]-1);
    }
}
int main() {
    int T; cin>>T; while(T--) work();
    return 0;
}