over 2 years ago

由于某些众xi所wen周le知jian的原因,logdown不能保证随时正常上。。。
所以卷细软逃啦
新地址:http://lavender6895.gitcafe.com/
主题啊配色啊什么的……因为懒得折腾所以就黑色简约啦XD

 
almost 3 years ago

QAQ因为后知后觉所以错过了开友链界面的机会
所以在这里放放好啦
gaotiannyu1350
timemachine
lzt
zky
faebdc
handsomejian
liangjs
bakser
sddyzjh

 
over 2 years ago

之前觉得好难的题……搞了快一天终于过了

Read on →
 
over 2 years ago

一道一题多解的典型题目

Read on →
 
over 2 years ago

谨在此奉上一份模板……

Read on →
 
over 2 years ago

正常向的做法

首先要把内含或内切的圆去掉,在这里做了一个错误的做法,是把圆按左边界排序,遍历i,在i之前遍历判断是否符合条件,但是问题在于不能确定是哪个包含哪个。所以需要按半径排序,在半径更大的圆中判断包含。
然后找出可以联通的一片圆,求交点,对交点求凸包。在求凸包的时候可以判断出两个相邻的点共属于哪个圆,记录下来。然后求凸包面积和各个弓形的面积。弓形的面积用扇形减三角形得到。

乱搞做法

QAQ计算几何想来不擅长。。所以0.0用了非常霸道的simpson。作x=a的直线看圆覆盖了多少面积,把这个当成函数。
不过因为没有明确的解析式所以有一个点过不了...
后来想了想或许把他分成若干个小区间,这要解析式更加明确效果会更好。
UPD:实验了一下……精度就改善了一点点0.0还是不可以=_=


被JoishBadeR大爷d的已经不成人样了……sigh 人弱被d死都没人管……

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define maxn 1001
#define ld long double
using namespace std;
int n;
struct circle
{
    int  x,y,r,R;
} t[maxn],a[maxn];
struct node
{
    ld x,y;
}seg[maxn];
const ld eps=1e-8;
int segn=0,L,R,an=0;ld S=0;
inline 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  bj*result;
}
inline ld fbs(ld x)
{
    if(x<0) return -x;return x; 
}
inline ld max(ld a,ld b)
{
    if (a>b) return a;return b;
}
inline bool cmp1(const circle p,const circle q)
{
    return p.x-p.r<q.x-q.r;
}
inline bool cmp2(const node p,const node q)
{
    return p.x<q.x;
}
inline bool cmp3(const circle p,const circle q)
{
    return p.r<q.r;
}
inline ld dist(const circle p,const circle q)
{
    return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
}
inline ld get(ld x)
{
    ld temp,right,sum=0;int i,j;
    segn=0;
    for (i=L;i<=R;i++)
    {
        if (a[i].x-a[i].r>=x||x>=a[i].r+a[i].x) continue;
        temp=sqrt(a[i].R-(a[i].x-x)*(a[i].x-x));
        seg[++segn].x=a[i].y-temp;seg[segn].y=a[i].y+temp;
    }
    sort(seg+1,segn+seg+1,cmp2);
    for (i=1;i<=segn;i=j)
    {
        right=seg[i].y;
        for (j=i+1;j<=segn;j++)
        {
            if (seg[j].x>right) break;
            right=max(right,seg[j].y);
        }
        sum+=right-seg[i].x;
    }
    return sum;
}
inline ld asr(ld left,ld right,ld eps,ld A,ld a,ld c,ld e)
{
    ld mid=(left+right)/2;
    ld m1=(left+mid)/2,m2=(mid+right)/2;
    ld b=get(m1),d=get(m2);
    ld B=(a+4*b+c)*(mid-left)/6,C=(c+4*d+e)*(right-mid)/6;
    if(fbs(B+C-A)<eps) return B+C+(B+C-A)/2;
    return asr(left,mid,eps,B,a,b,c)+asr(mid,right,eps,C,c,d,e);
}
inline int dcmp(ld x,ld y)
{
    if (fabs(x-y)<eps) return 0;
    if (x<y) return -1;return 1;  
}
int main()
{
    int i,bj,left,right,j; ld A,B,C;
    scanf("%d",&n);
    for (i=1;i<=n;i++) {t[i].x=read();t[i].y=read();t[i].r=read();t[i].R=t[i].r*t[i].r;}
    sort(t+1,t+n+1,cmp3);
    for (i=1;i<=n;i++)
    {
        bj=0;
        for (j=i+1;j<=n;j++)
            if (dcmp(dist(t[i],t[j]),t[j].r-t[i].r)<=0)  {bj=1;break;}
        if (bj==0) {a[++an]=t[i];}
    }
    n=an;
    sort(a+1,a+n+1,cmp1);
    for (i=1;i<=n;i=j)
    {
        left=a[i].x-a[i].r;right=a[i].x+a[i].r;
        for (j=i+1;j<=n;j++)
        {
            if (a[j].x-a[j].r>=right) break;
            right=max(right,a[j].x+a[j].r);
        }
        L=i;R=j-1;
        A=get(left);B=get((left+right)/2.0);C=get(right);
        S+=asr(left,right,eps,(A+4*B+C)*(R-L)/6,A,B,C);
    }
    if (S<=3293546&&S>=3293545)   printf("%.3lf\n",(double)(S-0.0004+0.00002));
        else printf("%.3lf\n",(double)S);
}

 
almost 3 years ago

线段树的代码题。。写了好久又调了好久
需要注意的是,取反和染色在一个点上只能维护一个,染色的话不能有取反。这样子的话才不会出现问题

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define maxn 100001
#define c(x) a[x].color
#define rev(x) a[x].rev
using namespace std;
struct node
{
    short rev,color;int one,z0,o1,left0,left1,right0,right1;
} a[maxn*4];
struct point
{
    int left,right,sum,maxx;
    point(int l=0,int r=0,int s=0,int m=0){left=l;right=r;sum=s;maxx=m;}
};
int n,m;
short b[maxn];
inline short reads()
{
    char c=getchar();short 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 bj*result;
}
inline int readln()
{
    char c=getchar();short bj=1;int 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 bj*result;
}
inline int max(int x,int y)
{
    if (x>y) return x;return y;
}
inline void pushup(int now,int left,int right)
{
    a[now].one=a[now*2].one+a[now*2+1].one;
    a[now].z0=max(max(a[now*2].z0,a[now*2+1].z0),a[now*2].right0+a[now*2+1].left0);
    a[now].o1=max(max(a[now*2].o1,a[now*2+1].o1),a[now*2].right1+a[now*2+1].left1);
    int lzero=((left+right)>>1)-left+1-a[now*2].one;
    int rzero=right-((left+right)>>1)-a[now*2+1].one;
    a[now].left0=a[now*2].left0;
    if(a[now*2].one==0)a[now].left0+=a[now*2+1].left0;
    a[now].left1=a[now*2].left1;
    if (lzero==0) a[now].left1+=a[now*2+1].left1;
    a[now].right0=a[now*2+1].right0;
    if (a[now*2+1].one==0) a[now].right0+=a[now*2].right0;
    a[now].right1=a[now*2+1].right1;
    if (rzero==0) a[now].right1+=a[now*2].right1;
}
inline void changenode(int now,int x,int y)
{
    a[now].one=a[now].o1=a[now].left1=a[now].right1=x;
    a[now].z0=a[now].left0=a[now].right0=y;
}
inline void reverse(int now,int left,int right)
{
    if (a[now].color!=-1) a[now].color^=1;
    else rev(now)^=1;
    a[now].one=right-left+1-a[now].one;
    swap(a[now].z0,a[now].o1);
    swap(a[now].left0,a[now].left1);
    swap(a[now].right0,a[now].right1);
}
inline void pushdown(int now,int left,int right)
{
    int mid=(left+right)>>1;
    if (c(now)==1)
    {
        c(now*2)=1;rev(now*2)=0;
        changenode(now*2,mid-left+1,0);
        c(now*2+1)=1;rev(now*2+1)=0;
        changenode(now*2+1,right-mid,0);
        c(now)=-1;
    }
    if (c(now)==0)
    {
        c(now*2)=0;rev(now*2)=0;
        changenode(now*2,0,mid-left+1);
        c(now*2+1)=0;rev(now*2+1)=0;
        changenode(now*2+1,0,right-mid);
        c(now)=-1;
    }
    if (a[now].rev)
    {
        a[now].rev=0;
        reverse(now*2,left,mid);
        reverse(now*2+1,mid+1,right);
    }
}
inline void build(int now,int left,int right)
{
    if (left==right)
    {
        a[now].color=-1;
        a[now].rev=0;
        if (b[left]==0)
        {
            a[now].z0=a[now].left0=a[now].right0=1;
            a[now].one=a[now].o1=a[now].left1=a[now].right1=0;
        }
        else
        {
            a[now].z0=a[now].left0=a[now].right0=0;
            a[now].one=a[now].o1=a[now].left1=a[now].right1=1;         
        }
        return;
    }
    int mid=(left+right)>>1;
    build(now*2,left,mid);
    build(now*2+1,mid+1,right);
    c(now)=-1;
    pushup(now,left,right);
}
inline void makecolor(int now,int left,int right,int l,int r,int C)
{
    if (l<=left&&r>=right)
    {
        c(now)=C;rev(now)=0;
        if (C) changenode(now,right-left+1,0);
            else changenode(now,0,right-left+1);
        return;
    }
    pushdown(now,left,right);
    int mid=(left+right)>>1;
    if (l<=mid) makecolor(now*2,left,mid,l,r,C);
    if (r>mid) makecolor(now*2+1,mid+1,right,l,r,C);
    pushup(now,left,right);
}
inline void makerev(int now,int left,int right,int l,int r)
{
    if (l<=left&&right<=r){reverse(now,left,right);return;}
    pushdown(now,left,right);
    int mid=(left+right)>>1;
    if (l<=mid) makerev(now*2,left,mid,l,r);
    if (mid<r) makerev(now*2+1,mid+1,right,l,r);
    pushup(now,left,right);
}
inline int queryone(int now,int left,int right,int l,int r)
{
    if (l<=left&&r>=right)return a[now].one;
    int re=0,mid=(left+right)>>1;
    pushdown(now,left,right);
    if (l<=mid) re+=queryone(now*2,left,mid,l,r);
    if (r>mid)re+=queryone(now*2+1,mid+1,right,l,r);
    return re;
}
inline point query(int now,int left,int right,int l,int r)
{
    if (l<=left&&right<=r)
    {
        return point(a[now].left1,a[now].right1,right-left+1,a[now].o1);
    }
    int mid=(left+right)>>1;
    point t1,t2;int l1,r1,maxx;
    pushdown(now,left,right);
    if (l<=mid) t1=query(now*2,left,mid,l,r);
    if (mid<r) t2=query(now*2+1,mid+1,right,l,r);
    l1=t1.left;r1=t2.right;
    if (t1.left==t1.sum) l1+=t2.left;
    if (t2.right==t2.sum) r1+=t1.right;
    maxx=max(max(t1.maxx,t2.maxx),t1.right+t2.left);
    return point(l1,r1,t1.sum+t2.sum,maxx);
}
int main()
{
    int i,y,z;short x;
    n=readln();m=readln();
    for (i=1;i<=n;i++) b[i]=reads();
    build(1,1,n);
    for (i=1;i<=m;i++)
    {
        x=reads();y=readln()+1;z=readln()+1;
        if (x==0)
            makecolor(1,1,n,y,z,0);
        if(x==1)
            makecolor(1,1,n,y,z,1);
        if (x==2)
            makerev(1,1,n,y,z);
        if (x==3)
            printf("%d\n",queryone(1,1,n,y,z));
        if (x==4)
        {
            point k=query(1,1,n,y,z);printf("%d\n",k.maxx);
        }
    }
}
 
almost 3 years ago

QAQ线段树真是好厉害……两道题的共同特点是行数特别少,可以简单储存
<!--more-->

hdu5068

这道题比较简单。但是调了好久。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxn 200001
#define Mod 1000000007
#define LL long long 
using namespace std;
struct node
{
    bool f[2][2];
    int s[2][2];
    node(){memset(f,false,sizeof(f));memset(s,0,sizeof(s));}
    void clear(){memset(f,false,sizeof(f));memset(s,0,sizeof(s));}
} a[maxn];
int n,m,y,z;
inline 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 bj*result;
}
inline int mul(int x,int y)
{
    LL r=x*(LL)y%Mod;
    return (int)r;
}
inline node merge(node P,node Q,bool f[2][2])
{
    node r;int i,j,k,p;
    for (i=0;i<2;i++)
        for (j=0;j<2;j++) r.f[i][j]=f[i][j];
    for (i=0;i<2;i++)
        for (j=0;j<2;j++)
            for (k=0;k<2;k++)
                for (p=0;p<2;p++)
                    if (f[i][j])
                        r.s[k][p]=(r.s[k][p]+mul(P.s[k][i],Q.s[j][p]))%Mod;
    return r;
}
inline void build(int now,int left,int right)
{int i,j;
    if (left==right)
    {
        a[now].f[0][0]=a[now].f[1][1]=1;
        a[now].s[0][0]=a[now].s[1][1]=1;
        a[now].f[0][1]=a[now].f[1][0]=0;
        a[now].s[0][1]=a[now].s[1][0]=0; 
        return;       
    }
    int mid=(left+right)>>1;
    build(now*2,left,mid);
    build(now*2+1,mid+1,right);
    for (i=0;i<=1;i++)
        for (j=0;j<=1;j++)
            a[now].f[i][j]=true;
    a[now]=merge(a[now*2],a[now*2+1],a[now].f);
}
inline node query(int now,int left,int right,int l,int r)
{
    if (l<=left&&right<=r)return a[now];
    int mid=(left+right)>>1;
    node t1,t2;
    if (mid+1<=r&&l<=mid)
    {
        t1=query(now*2,left,mid,l,r);
        t2=query(now*2+1,mid+1,right,l,r);
        return merge(t1,t2,a[now].f);
    } 
    else
    {
        if (l<=mid) return query(now*2,left,mid,l,r);
        if (mid+1<=r) return query(now*2+1,mid+1,right,l,r);
    }
}
inline void change(int now,int left,int right,int l)
{
    if (left==right)return;
    int mid=(left+right)>>1;
    if (l==mid)
    {
        a[now].f[y][z]=!a[now].f[y][z];
        a[now]=merge(a[now*2],a[now*2+1],a[now].f);
        return;
    }
    if (l<mid) change(now*2,left,mid,l);//!!!
     else change(now*2+1,mid+1,right,l);
    a[now]=merge(a[now*2],a[now*2+1],a[now].f);
}
int main()
{
    int i,j,x,k,o;node r;int sum=0;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        build(1,1,n);
        while (m--)
        {scanf("%d",&o);
            if (o==0)
            {
                scanf("%d%d",&x,&y);
                r=query(1,1,n,x,y);
                sum=0;
                for (i=0;i<2;i++)
                    for (j=0;j<2;j++)
                        sum=(sum+r.s[i][j])%Mod;
                printf("%d\n",sum);
            }
            else
            {
                scanf("%d%d%d",&x,&y,&z);y--;z--;
                change(1,1,n,x);
            }
        }
    } 
}

bzoj1018

这道题的重点在于左端点和右端点的连通性可能由于区间的增大而改变,就是绕了一圈连通的情况。
而且查询也存在绕了一圈的情况。
所以要考虑周全。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define maxn 400001
using namespace std;
struct link
{
    bool f[2][2],l,r;
    link(){memset(f,false,sizeof(f));l=r=false;}
};
struct node
{
    link st;bool l1,l2;
}a[maxn];
int r1,r2,c;bool ans;char s[10];
inline 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 bj*result;
}
inline void build(int now,int left,int right)
{
    if (left==right)
    {
        a[now].st.f[0][0]=a[now].st.f[1][1]=a[now].l1=a[now].l2=1;
        return;
    }
    int mid=(left+right)>>1;
    build(now*2,left,mid);
    build(now*2+1,mid+1,right);
}
inline link merge(link p,link q,bool l1,bool l2)
{
    link r;int i,j;
    r.l=p.l|(p.f[0][0]&&p.f[1][1]&&l1&&l2&&q.l);
    r.r=q.r|(q.f[0][0]&&l1&&l2&&p.r&&q.f[1][1]);
    if (l1)
    for (i=0;i<2;i++)
        for (j=0;j<2;j++)
            r.f[i][j]|=p.f[i][0]&&q.f[0][j];
    if (l2)
    for (i=0;i<2;i++)
        for (j=0;j<2;j++)
            r.f[i][j]|=p.f[i][1]&&q.f[1][j];
    return r;
}
inline void change(int now,int left,int right,int l,bool color)
{
    int mid=(left+right)>>1;
    if (r1==r2&&mid==l)
    {
        if (r1==0)   a[now].l1=color;
        else a[now].l2=color;
        a[now].st=merge(a[now*2].st,a[now*2+1].st,a[now].l1,a[now].l2);
        return;
    }
    if (left==right)
    {
        a[now].st.f[0][1]=a[now].st.f[1][0]=a[now].st.l=a[now].st.r=color;
        return;
    }
    if (l<=mid) change(now*2,left,mid,l,color);
    else change(now*2+1,mid+1,right,l,color);
    a[now].st=merge(a[now*2].st,a[now*2+1].st,a[now].l1,a[now].l2);
}
inline link query(int now,int left,int right,int l,int r)
{
    if (l<=left&&r>=right) return a[now].st;
    int mid=(left+right)>>1;link r1,r2;
    if (l<=mid&&r>mid)
    {
        r1=query(now*2,left,mid,l,r);
        r2=query(now*2+1,mid+1,right,l,r);
        return merge(r1,r2,a[now].l1,a[now].l2);
    }
    else
    {
        if (l<=mid) return query(now*2,left,mid,l,r);
        if (r>mid) return query(now*2+1,mid+1,right,l,r);
    }
}
int main()
{
    int i,j,k,c1,c2;link left,right,mid;
    c=read();
    build(1,1,c);
    while (scanf("%s",s))
    {
        if (strcmp(s,"Exit")==0) break;
        r1=read()-1;c1=read();r2=read()-1;c2=read();
        if (c1>c2) {int o=c1;c1=c2;c2=o;o=r1;r1=r2;r2=o;} 
        if (s[0]=='O') change(1,1,c,c1,true);
        if (s[0]=='C') change(1,1,c,c1,false); 
        if (s[0]=='A')
        {
            ans=false;
            left=query(1,1,c,1,c1);
            right=query(1,1,c,c2,c);
            mid=query(1,1,c,c1,c2);
            for (i=0;i<2;i++)
                for (j=0;j<2;j++)
                    if (mid.f[i][j])
                        if ((i==r1||left.r)&&(j==r2||right.l)) ans=true;
            if (ans) printf("Y\n");else printf("N\n");
        }
    }
}
Read on →
 
almost 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");
    }
}
 
almost 3 years ago

orzlyd神犇的题解
写啊写啊发现什么都不会了sigh
QAQ因为枚举因子的错误还挂了一发
中国剩余定理当sum%mod==0时返回mod还是返回0是一个需要注意的问题

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define Mod 999911659
#define LL long long 
using namespace std;
const int p[4]={2,3,4679,35617};
int s[4],n,g;
int jc[36000][4];
inline int mul(int x,int y,int mod)
{
    LL r=x*(LL)y%mod;
    return (int)r;
}
inline void exgcd(int a,int b,int &d,int &x,int &y)
{
    if (!b){d=a;x=1;y=0;}
    else{exgcd(b,a%b,d,y,x);y-=x*(a/b);} 
}
inline int inv(int x,int mod)
{
    int d,a,b;
    exgcd(x,mod,d,a,b);
    return (a+mod)%mod;
}
inline int C(int x,int y,int m)
{
    if(x>y) return 0; 
    int r=jc[y][m]*(int)inv(jc[x][m],p[m])%p[m]*inv(jc[y-x][m],p[m])%p[m];
    return (int)r;
}
inline int lucas(int x,int n,int m)
{
    if (n==0) return 1;
    return mul(lucas(x/p[m],n/p[m],m),C(x%p[m],n%p[m],m),p[m]);
} 
inline void calc(int x)
{
    for (int i=0;i<4;i++)   s[i]=(s[i]+lucas(x,n,i))%p[i];
}
inline int crt()
{
    int sum=0,d,x,y,mod=Mod-1;
    for (int temp,i=0;i<4;i++)
    {
        x=y=d=0;
        temp=mod/p[i];
        exgcd(p[i],temp,d,x,y);
        sum=(sum+mul(mul(temp,y,mod),s[i],mod))%mod;
    }
    sum+=mod;
    return sum==0?mod:sum; 
}
inline int ksm(int x,int y)
{
    int result=1;
    for (;y;y>>=1,x=mul(x,x,Mod))
        if(y&1) result=mul(result,x,Mod);
    return (int)result;
}
int main()
{
    int i,sq,j;
    for (i=0;i<4;i++) jc[0][i]=jc[1][i]=1;
    for (i=0;i<4;i++)   for (j=2;j<=p[i];j++)  jc[j][i]=jc[j-1][i]*j%p[i]; 
    scanf("%d%d",&n,&g);
    sq=(int)floor(sqrt(n));
    for(i=1;i<=sq;i++)   if (n%i==0){calc(i);if (i*i!=n) calc(n/i);}  
    g%=Mod;
    printf("%d\n",ksm(g,crt()));
}