hgoi#20191031

muronglin
muronglin 2019年10月31日
  • 在其它设备中阅读本文章

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 $ 的因数,对于所有 $ 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("%dn",n-cnt);
    for(int i=1;i<=m;i++)printf("%dn",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("%dn",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],STM;
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++)STi=oula[i];
    for(int j=1;j<=lg[cnt];j++)for(int i=1;i+p[j]-1<=cnt;i++)
        if(depST[i]<dep[ST[i+p[j-1]][j-1]])
            STi=STi;
        else STi=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(depST[x]]<dep[ST[y-p[lg[y-x]]+1][lg[y-x]]])
        return STx];
    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("%dn",ans[a]);
    return 0;
}