ICPC Premade Contest 4

wuhao2005 · 2023-07-25 14:43:58 · 个人记录

赛后补题

D

类似求 \max(\frac{\sum a_ix_i}{\sum b_ix_i}) ，01分数规划板题

#include<bits/stdc++.h>
using namespace std;
#define db double
const db inf = 1e9; 
const db eps = 1e-10;
const int N = 3009;
int n,kk,head[N],tot,siz[N];
struct pp{int nxt,to;}g[N<<1];
db s[N],p[N],a[N];
void add(int u,int v){g[++tot].nxt=head[u],g[tot].to=v,head[u]=tot;}
db f[N][N];int flag;
void dfs(int u){
    if(u) siz[u]=1,f[u][1]=a[u];
    if(u==0) f[u][0]=0,siz[u]=0;
    for(int i=head[u];i!=-1;i=g[i].nxt){
        int v=g[i].to;dfs(v);
        for(int j=siz[u];j>=0;j--){
            for(int k=siz[v];k>=1;k--)
                if(f[u][j]>-1e8&&f[v][k]>-1e8) f[u][j+k]=max(f[u][j+k],f[u][j]+f[v][k]);
        }
        siz[u]+=siz[v];
    }
    f[u][0]=0;
    return ;
}
bool check(){
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++) f[i][j]=-inf;
    dfs(0);
    return f[0][kk]>-eps;
}

int main(){
    memset(head,-1,sizeof(head));tot=0;
    scanf("%d%d",&kk,&n);
    for(int i=1;i<=n;i++){
        int u;scanf("%lf%lf%d",&p[i],&s[i],&u);add(u,i);
    }
    db l=0,r=1e5,ans;
    while(r>=l+eps){
        db mid=(l+r)/2;
        for(int i=1;i<=n;i++) a[i]=s[i]-mid*p[i];
        if(check()) l=mid,ans=mid;
        else r=mid;
    }
    for(int i=1;i<=n;i++) a[i]=s[i]-ans*p[i];
    check();
    if(abs(f[0][kk])>0.1) throw;
    printf("%.3lf\n",round(ans*1000)/1000);
    return 0;
}
//若干组数对各自和之商=0,1分数规划=二分答案=ai-L*bi权值定，求符合条件下的和的max,看最大>0否

E

对任意 k 求\sum_{i-j=k}A_iB_j

显然，对每个 k 都求，卷积板题，差变和，把其中一个数组反过来就好了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define db double 
const db Pi = acos(-1);
const int N = 3e6+9;
int n,m,tr[N];
char s[N];
struct CP{
    db x,y;
    CP(db x=0,db y=0):x(x),y(y){}
    CP operator+(const CP &a){return CP(x+a.x,y+a.y);}
    CP operator-(const CP &a){return CP(x-a.x,y-a.y);}
    CP operator*(const CP &a){return CP(x*a.x-y*a.y,x*a.y+y*a.x);}
}f[N],p[N];

void fft(CP *F,int nn,int flag){
    for(int i=0;i<nn;i++) if(i<tr[i]) swap(F[i],F[tr[i]]);
    for(int p=2;p<=nn;p<<=1){
        CP tG(cos(2*Pi/p),sin(2*Pi/p));
        if(!flag) tG.y*=-1;
        int len=p>>1;
        for(int j=0;j<nn;j+=p){
            CP buf(1,0);
            for(int k=j;k<j+len;k++){
                CP tt=buf*F[k+len];
                F[k+len]=F[k]-tt;
                F[k]=F[k]+tt;
                buf=buf*tG;
            }
        }
    }
    return ;
}
ll ans[N];

int main(){
    scanf("%s",s);n=strlen(s);
    for(int i=0;i<n;i++)
        if(s[i]=='A') f[i].x=1;
        else p[n-i-1].x=1;
    m=1;while(m<n*2) m*=2;
    for(int i=0;i<m;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?(m>>1):0);
    fft(f,m,1);fft(p,m,1);
    for(int i=0;i<m;i++) f[i]=f[i]*p[i];
    fft(f,m,0);
    for(int i=0;i<m;i++) ans[i]=(ll)(f[i].x/(db)m+0.49);
    for(int i=0;i<n-1;i++) printf("%lld\n",ans[n+i]);
    return 0;
}
/*
你 TM ，我知道为啥是n+i了，
因为你k是负时才是 B ... A啊！！！ 
f[i-j]=\sum B[i]*A[j]
f[k]=\sum B[k+j]*A[j]
B'[n-k-j]=B[k+j]
f'[n-k]=f[k]
f'[n-k]=\sum B'[n-k-j]*A[j]
f[k]=\sum B'[n-k-j]*A[j]

//看到你要求0~n的所有值，差不多卷积了，特别是答案的项数有和/差的关系 
*/

H

背包，n,\sum V 在 1e6 ，权值在 1e9 ，只保证单个体积为 300 以内。

背包能有什么好做法啊，按性价比贪心不太科学（真要能贪还要背包做啥），只能在常规 dp 上发现性质优化。

显然是按每个体积分类做背包，同体积按权值从大到小排序，先选大的一定更优，所以同体积下一定是凸的。

dp 有这个贪心策略就说明在决策上是可以优化的，想想可否决策单调性。（或者是对下标模某个数同余下有单调性）

若决策有单调性，可以试试分治转移，或者斜率优化。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 1e6+9;
const int M = 309;
int n,k;
vector<int >v[M];
vector<ll >sum[M];
ll f[N],g[N];
bool cmp(int x,int y){return x>y;}

void solve(int q,int p,int l,int r,int a,int b){
    if(r<l) return ;
    int mid=(l+r)>>1,id=a;//f[q+p*mid]
    ll t=-1;
    for(int i=a;i<=min(mid-1,b);i++)
        if(mid-i<=v[p].size()&&t<f[q+p*i]+sum[p][mid-i]){
            t=f[q+p*i]+sum[p][mid-i];
            id=i;
        }
    if(f[q+p*mid]>t){t=max(t,f[q+p*mid]);id=mid;}
    solve(q,p,l,mid-1,a,id);
    solve(q,p,mid+1,r,id,b);
    g[q+p*mid]=t;
    return ;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        int s,val;scanf("%d%d",&s,&val);
        v[s].push_back(val);
    }
    for(int i=1;i<=300;i++) sort(v[i].begin(),v[i].end(),cmp);
    for(int i=1;i<=300;i++){
        sum[i].push_back(0);
        ll x=0;
        for(int j=1;j<=v[i].size();j++){
            x+=v[i][j-1];
            sum[i].push_back(x);
        }
    }
    memset(f,-0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=300;i++){
        for(int j=0;j<i;j++){
            solve(j,i,0,(k-j)/i,0,(k-j)/i);
            for(int t=j;t<=k;t+=i) f[t]=g[t];
        }
    }
    ll ans=0;
    for(int i=1;i<=k;i++){
        ans=max(ans,f[i]);
        printf("%lld ",ans);
    }
    puts("");
    return 0;
}

/*
f[i]=f[j]+w_{i-j}
证明 若 j >k ,f[i+1]=f[j]+w_{i+1-j}>f[i+1]=f[k]+w_{i+1-k}
对比 f[i+1]=f[j+1]+w_{i-j} 这是跟 f[i]=f[j]+...同样的选择的 
f[i+1]=f[j]+w_{i+1-j}  
f[i+1]=f[j-1]+w_{i+2-j} 如果3式大于2式，那么意味着在 f[i] 处时应该多选择 w 中比 i-j 更小的那一项
而不是保留之前的项（感受到包含劣于相交就使，实在不行打表决策点！！感受到凸等性质直接决策单调性） 
故决策单调性成立，使用分治
同时这是对于同一模下同余项

决策单调性与直接单调队列区别，
就是决策点虽然是单增的，但你怎么找到这个决策点，每个点转移过来的 dp 值可不一定单峰
所以还是分治加决策单调。 
*/

A

据说是 meet in the middle ，线索是 m<=40 ，这很重要，分成前 \frac{m}{2} 和后 \frac{m}{2} 个，再用下二进制状态试试看

B

据说是先建括号树，从后往前做

J

扫描线

K

点分+李超树/凸包

G

好像是个 n^3 计算几何。