over 3 years ago

T_T 和timemachin&bakser组队 0.0 另一队豪华全明星阵容:faebdc gty zky 【全是大腿诶有木有】
然后在d题上默默卡死0.0卡了一个多小时……真是对不起
论手残啊啊啊啊
写一下当时做的题&后来出的题的题解吧……
附bakser的F G E I 的sol

C

题意:给一棵树,每个节点有几个属性及属性值,查询一个点和一个属性,问从这个点出发到父亲的链上,第一次出现该属性的属性值是什么。 数据范围:3*10^5
sol: 本来想的是链剖+300000颗动态线段树0.0……被吐槽too young了。于是有了倍增加主席树
建一颗树上主席树。用倍增处理出来查询区间。确定最近的点

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<map>
#include<cmath>
#include<queue>
#define maxn 300001
#define maxm 6000001 
#define l(x) lson[x]
#define r(x) rson[x]
using namespace std;
int lca[maxn][20];
map<string,int>q;
map<int,string> sx[maxn];
int vn=0,widen=0;
int next[maxn],point[maxn],v[maxn];
int lson[maxm],rson[maxm],sum[maxm],root[maxn];
int fn=0,n,border,m;
int l[maxn],maxlength;
string st,s1;
queue<int>que;
void addedge(int x,int y)
{
    widen++;next[widen]=point[x];point[x]=widen;v[widen]=y;
}
void add(int pre,int &now,int left,int right,int pos)
{
    now=++fn;
    sum[now]=sum[pre]+1;
    if (left==right) return;
    int mid=(left+right)>>1;
    if (pos<=mid) {r(now)=r(pre);add(l(pre),l(now),left,mid,pos);}
    else {l(now)=l(pre);add(r(pre),r(now),mid+1,right,pos);}
}
void prepare()
{
    border=(int)ceil(log(maxlength)/log(2));
    for (int i=1;i<=border;i++)
        for (int j=1;j<=n;j++)
            lca[j][i]=lca[lca[j][i-1]][i-1];
}
int exist(int now,int pre,int left,int right,int pos)
{
    if (left==right) return sum[now]-sum[pre];
    int mid=(left+right)>>1;
    if (pos<=mid) return exist(l(now),l(pre),left,mid,pos);
    else return exist(r(now),r(pre),mid+1,right,pos);
}
int query(int x,int y)
{
    for (int i=border;i>=0;i--)
        if (exist(root[x],root[lca[x][i]],1,vn,y)==0)
            x=lca[x][i];
    return x;
}
int main() 
{
    int i,j,k,x,y,pos;map<int,string>::iterator it;
    cin>>n;
    for (i=1;i<=n;i++) 
    {
        cin>>lca[i][0]>>k;
        if (i!=1)addedge(lca[i][0],i);
        for (j=1;j<=k;j++)
        {
            cin>>st;
            pos=st.find('=');
            s1=st.substr(0,pos);
            if (q.find(s1)!=q.end()) x=q[s1];
            else {q[s1]=++vn;x=vn;}
            sx[i][x]=st.substr(pos+1,st.length()-pos-1);
        }
    }
    que.push(1);l[1]=maxlength=1;
    while (!que.empty())
    {
        x=que.front();que.pop();
        root[x]=root[lca[x][0]];
        maxlength=max(maxlength,l[x]);
        for (it=sx[x].begin();it!=sx[x].end();it++)
            add(root[x],root[x],1,vn,it->first); 
        for (k=point[x];k!=0;k=next[k])  que.push(v[k]);l[v[k]]=l[x]+1;
    }
    prepare();
    cin>>m;
    for (i=1;i<=m;i++)
    {
        cin>>x>>st;
        if (q.find(st)==q.end()) {printf("N/A\n");continue;}
        y=q[st];k=query(x,y);
        if (k==0) {printf("N/A\n");continue;}
        cout<<sx[k][y]<<endl;
    } 
}

D

题意:给定n,m a[n] b[n] 选出一些数,使Σa[i]>=n 且选出的数最少,在满足这个的前提下,∑b[i]最大。b[i]为0或1
sol: 想啊想啊捉了好久……最后发现其实就是贪心
按a[n]从大到小排序,可以确定出应选择多少个数,然后不断枚举调整∑b[i]即可
代码丑到不忍直视

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define maxn 200001
#define LL long long 
using namespace std;
struct node{LL x;int y,xh;}a[maxn],zero[maxn];
int n,k,zn=0,rn=0;LL m;
LL s[maxn];
int e[maxn],r[maxn];
bool cmp(const node p,const node q)
{
    return p.x>q.x;
}
int main()
{
    int i,j;LL sum=0;
    scanf("%d%I64d",&n,&m);
    for (i=1;i<=n;i++){scanf("%I64d%d",&a[i].x,&a[i].y);a[i].xh=i;}
    sort(a+1,a+n+1,cmp);
    for (i=1;i<=n;i++)
    {
        sum=sum+(LL)a[i].x;
        if(sum>=m) break; 
    }
    k=i;
    if (i>n) k=n;
    s[0]=0; e[0]=0;
    for (i=1;i<=n;i++) {s[i]=s[i-1]+a[i].x;e[i]=e[i-1]+a[i].y;}
    for (i=1;i<=k;i++)
    {
        if (a[i].y==0)   zero[++zn]=a[i];
        else r[++rn]=a[i].xh;
    }
    if (zn) 
    for (i=k+1;i<=n;i++)
        if (a[i].y==1)
            if (sum-zero[zn].x+a[i].x>=m)
            {
                sum=sum-zero[zn].x+a[i].x;
                r[++rn]=a[i].xh;
                zn--;
                if (zn==0) break;
            }

    for (i=1;i<=zn;i++)r[++rn]=zero[i].xh;
    printf("%d %d\n",k,k-zn);
    for (i=1;i<=rn;i++)printf("%d ",r[i]);
}

K

题意:给出n,以及矩阵a[n][n].a[i][j]代表离i点第j远的点。求满足矩阵a的一棵树
sol:orz zky
首先可以确定a[i][1],a[i][2]必定有边
那么怎么判断后面的点呢?从后面的点的远近距离里找。【真是好厉害】

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 2001
using namespace std;
int a[maxn][maxn],fa[maxn],u[maxn],v[maxn];
int widen=0;
bool f[maxn];
int read()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return result*bj;
}
int find(int x)
{
    int k=x,o;
    while (fa[k]!=k) k=fa[k];
    while (fa[x]!=k) o=fa[x],fa[x]=k,x=o;
    return k;
}
void addedge(int x,int y)
{
    u[++widen]=x;v[widen]=y;
}
int main()
{
    int i,j,k,t,n,x,y;
    t=read();
    while (t--)
    {
        widen=0;
        n=read();
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
                a[i][j]=read();
        for (i=1;i<=n;i++) fa[i]=i;
        for (i=1;i<=n;i++)
        if (find(i)!=find(a[i][2]))
        {
            x=find(i);y=find(a[i][2]);
            fa[x]=y;
            addedge(i,a[i][2]);
        }
        memset(f,false,sizeof(f));
        f[1]=true;f[a[1][2]]=true;
        for (i=3;i<=n;i++)
        {
            f[a[1][i]]=true;
            if (find(a[1][i])!=find(1))
            {
            k=a[1][i];
            for (j=3;j<=n;j++)
                if (f[a[k][j]]==1) break;
            addedge(k,a[k][j]);
            x=find(k);
            fa[x]=find(1);
             }       
        }
        for (i=1;i<=widen;i++)   printf("%d %d\n",u[i],v[i]);
        printf("\n");
    }
}
← 【bzoj1951】【数论集合】古代猪文 线段树维护连通性【bzoj1018堵塞的交通&&hdu5068hp&math teacher】 →
 
comments powered by Disqus