慕容琳的后花园
慕容琳的后花园
hgoi#20191031

T1-Divisors

给出 m 个不同的正整数 a_i ,设数论函数f(k) = \sum\limits_{i = 1}^{n} [(\sum\limits_{j = 1}^{m} [i |a_j] )== k]
其中 a | b 表示 ab 的因数,对于所有 k \in [0,m] ,输出答案。
对于100%的数据满足 n\leq 200 , a_i \leq 10^9

解法

这道题直接暴力算每个数的贡献
因为一个数的因数个数并不多,一定不超过\sqrt n
最劣也是 n \sqrt {a_i} 个数,完全存的下

ac代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
int n,m,cnt,x,k,p[200010],ans[210];
int main()
{
    freopen("div.in","r",stdin);
    freopen("div.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&x),k=sqrt(x);
        for(int i=1;i<=k;i++)if(x%i==0)
        {
            if(mp[i]==0&&i<=n)mp[i]=++cnt;
            if(i<=n)p[mp[i]]++;
            if(mp[x/i]==0&&x/i<=n)mp[x/i]=++cnt;
            if(x/i<=n)p[mp[x/i]]++;
        }
        if(k*k==x&&k<=n)p[mp[k]]--;
    }
    for(int i=1;i<=cnt;i++)ans[p[i]]++;
    printf("%d\n",n-cnt);
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}

T2-Marke

n 个商店,每个商店某一时刻 r_i 及以后会卖 1 种物品且只有 1 个。
每个物品有花费 c_i 和价值 v_i ,处理 m 个询问,表示在 t_i 时刻购买所有物品且有钱数 w_i
输出当前限制的最大价值。
对于100%的数据满足 1 \leq n \leq 300, 1 \leq m \leq 10^5, 1 \leq c_i,w_i \leq 10^9, 1 \leq r_i , t_i \leq 300

解法

dp,设 f_i 表示价值达到i需要的最少花费
暴力更新的复杂度是 n^3
以时间为轴去更新
如果当前时间点有询问
由于f[i]具有单调性,所以二分答案

ac代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define mid (l+r>>1)
#define inf 0x3f3f3f3f
using namespace std;
struct node
{
    int c,v,t;
    void init(){scanf("%d%d%d",&c,&v,&t);}
    bool operator<(const node&a)const{return t<a.t;}
}a[310];
struct Node
{
    int id,t,m;
    void init(int i){id=i,scanf("%d%d",&t,&m);}
    bool operator<(const Node&a)const{return t<a.t;}
}q[100010];
int n,m,maxx,maxm,f[100010],ans[100010];
//f[i]表示i价值最少要多少钱 
void upd(int&x,int y){x=min(x,y);}
int main()
{
//  freopen("market.in","r",stdin);
//  freopen("market.out","w",stdout);
    memset(f,0x3f,sizeof(f)),f[0]=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)a[i].init();
    for(int i=1;i<=m;i++)q[i].init(i),maxm=max(maxm,q[i].m);
    sort(a+1,a+n+1),sort(q+1,q+m+1);
    for(int i=1,x=1,y=1;i<=n;i++)
    {
        while(a[x].t==i)
        {
            for(int j=90000;j>=0;j--)
            {
                if(f[j]+a[x].c>maxm)continue;
                upd(f[j+a[x].v],f[j]+a[x].c);
            }
            for(int j=90000;j>=1;j--)
                upd(f[j-1],f[j]);
            x++;
        }
        while(q[y].t==i)
        {
            int l=0,r=90000,res;
            while(l<=r)
                if(f[mid]<=q[y].m)res=mid,l=mid+1;
                else r=mid-1;
            ans[q[y].id]=res,y++;
        }
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}

T3-Dash Speed

一棵含有 n 个节点的树,每一条无向边都有一个区间 [l_i , r_i]
给出 m 个询问,每次输入一个 x ,设树上一条 k 条边的路径,p_1 , p_2 , … ,p_k
求 $ x \in \cap {i = 1}^{k} [l{p_i}, r_{p_i}] ,最大化 k 的值。
对于100%的数据满足
1 \leq n ,m\leq 7\times 10^4 , 1 \leq l_i \leq r_i \leq n,1 \leq x \leq n $

解法

考虑转化这个问题
就是要维护一个动态树的直径
对于增边操作,新树的直径的端点一定是两棵原树的直径的端点
并查集搞一下就可以做到
对于删边操作,有点难搞

显然要先预处理出所有答案,再在线询问
对询问进行分治(类似整体二分)
如果当前处理的区间为 [l,r]
那么它可以经过所有承受区间包含 [l,r] 的边
把这些边加入并合并,然后继续分治
因为两边都要去分治,所以需要回溯操作
那么并查集就不能路径压缩,而是按秩合并
回溯时撤销之前的操作即可
如果用欧拉序和ST表求LCA
复杂度可以达到 n \log n

ac代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define mid (l+r>>1)
#define ls (nw<<1)
#define rs (nw<<1|1)
#define N 70010
#define M 140010
#define P 280010
#define K 20
using namespace std;
vector<int>e[N];
vector<pair<int,int> >g[P];
struct node{int t,x,y;}u;
stack<node>q;
int n,m,a,b,c,d,t,tmp,cnt;
int p[K],f[N],A[N],B[N],dep[N],depth[N];
int fst[N],ans[N],oula[M],lg[M],ST[M][K];
void ins(int nw,int l,int r,int ql,int qr,int x,int y)
{
    if(ql<=l&&r<=qr){g[nw].pb(mp(x,y));return;}
    if(ql<=mid)ins(ls,l,mid,ql,qr,x,y);
    if(qr>mid)ins(rs,mid+1,r,ql,qr,x,y);
}
void dfs(int u,int fa)
{
    f[u]=A[u]=B[u]=u,oula[++cnt]=u,fst[u]=cnt;
    for(auto v:e[u])if(v!=fa)
        dep[v]=dep[u]+1,dfs(v,u),oula[++cnt]=u;
}
void init()
{
    for(int i=1;i<=cnt;i++)ST[i][0]=oula[i];
    for(int j=1;j<=lg[cnt];j++)for(int i=1;i+p[j]-1<=cnt;i++)
        if(dep[ST[i][j-1]]<dep[ST[i+p[j-1]][j-1]])
            ST[i][j]=ST[i][j-1];
        else ST[i][j]=ST[i+p[j-1]][j-1];
}
int lca(int x,int y)
{
    if(x==y)return x;
    x=fst[x],y=fst[y];
    if(x>y)swap(x,y);
    if(dep[ST[x][lg[y-x]]]<dep[ST[y-p[lg[y-x]]+1][lg[y-x]]])
        return ST[x][lg[y-x]];
    else return ST[y-p[lg[y-x]]+1][lg[y-x]];
}
int find(int x){return x==f[x]?x:find(f[x]);}
int dis(int x,int y){return dep[x]+dep[y]-dep[lca(x,y)]*2;}
void merge(int x,int y,int&res)
{
    x=find(x),y=find(y),t=-1;
    tmp=dis(A[x],B[x]);
    if(tmp>t)t=tmp,a=A[x],b=B[x];
    tmp=dis(A[x],A[y]);
    if(tmp>t)t=tmp,a=A[x],b=A[y];
    tmp=dis(A[x],B[y]);
    if(tmp>t)t=tmp,a=A[x],b=B[y];
    tmp=dis(B[x],A[y]);
    if(tmp>t)t=tmp,a=B[x],b=A[y];
    tmp=dis(B[x],B[y]);
    if(tmp>t)t=tmp,a=B[x],b=B[y];
    tmp=dis(A[y],B[y]);
    if(tmp>t)t=tmp,a=A[y],b=B[y];
    if(res<t)res=t;
    if(depth[x]==depth[y])depth[x]++,q.push({0,x,0});
    if(depth[x]<depth[y])swap(x,y);
    q.push({1,y,0}),q.push({2,x,A[x]}),q.push({3,x,B[x]}),
    f[y]=x,A[x]=a,B[x]=b;
}
void split(int pos)
{
    while(q.size()>pos)
    {
        u=q.top(),q.pop();
        if(u.t==0)depth[u.x]--;
        if(u.t==1)f[u.x]=u.x;
        if(u.t==2)A[u.x]=u.y;
        if(u.t==3)B[u.x]=u.y;
    }
}
void solve(int nw,int l,int r,int res)
{
    int pos=q.size();
    for(auto x:g[nw])merge(x.fir,x.sec,res);
    if(l==r)ans[l]=res;
    else solve(ls,l,mid,res),solve(rs,mid+1,r,res);
    split(pos);
}
int main()
{
    scanf("%d%d",&n,&m),lg[0]=-1;
    for(int i=1;i<M;i++)lg[i]=lg[i>>1]+1;
    for(int i=0;i<K;i++)p[i]=(1<<i);
    for(int i=1;i<n;i++)
        scanf("%d%d%d%d",&a,&b,&c,&d),
        e[a].pb(b),e[b].pb(a),ins(1,1,n,c,d,a,b);
    dfs(1,0),init(),solve(1,1,n,0);
    while(m--)scanf("%d",&a),printf("%d\n",ans[a]);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

hgoi#20191031
T1-Divisors 给出 $ m $ 个不同的正整数 $ a_i $ ,设数论函数$ f(k) = \sum\limits_{i = 1}^{n} [(\sum\limits_{j = 1}^{m} [i |a_j] )== k] $ 其中 $ a | b $ 表示 $ a $ 是 $ b $ 的因…
扫描二维码继续阅读
2019-10-31
功能