2011 Multi-University Training Contest 6

打了4hours，做出一道题。。。太菜了。rank:45/107

开场看B，题目看不懂。。。3hours半才发现i<=N-1,不是i<=x-1.然而还是不会。

看到J有人过了，发现是个简单的树形DP，先处理出根节点的贡献，再O(1)向下转移。。于是49min A了J。

然后就没有任何题会了。。。

A？坐标范围这么大？离散化后好像还是无法搞。。。

B？差分？怎么差都差不出。。。

C？不会数论。。。

D？刚开始写了一个自认为正确的DP+矩阵快速幂，然而发现好像无法处理颜色的排列不允许的情况。。。然后推了个公式，发现要用容斥。。弃疗。。。

E？什么玩意。。。

FGHI....没看。。。

A.Apparent Magnitude(离散化+树状数组)

类似于poj数星星的加强版。但是这道题的坐标范围巨大。离散化后还有60000*60000个点。导致考试时没想清楚。。。

先把点的纵坐标和询问的纵坐标离散化。

考虑求矩形(lx,ly,rx,ry)的点的总数和亮度总和，只需要求出矩形(0,ly,lx-1,ry)和(0,ly,rx,ry)的即可。

考虑离线，把询问的lx和rx排序，然后依次求出每个询问的子询问的ans即可。实际上只需要树状数组的更新和求和即可。复杂度O(nlogn).

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct Node{int x, y; double val;}node[N];

struct Q{int x, ly, ry, id, flag;}q[N];

VI v;

int tree1[N<<], ans1[N][], siz;

double tree2[N<<], ans2[N][];

bool comp1(Node a, Node b){return a.x<b.x;}

bool comp2(Q a, Q b){

    if (a.x==b.x) return a.flag<b.flag;

    return a.x<b.x;

}

void init(){

    mem(tree1,); v.clear();

    FO(i,,N<<) tree2[i]=;

}

void add1(int x, int val){while (x<=siz) tree1[x]+=val, x+=lowbit(x);}

void add2(int x, double val){while (x<=siz) tree2[x]+=val, x+=lowbit(x);}

int query1(int x){

    int res=;

    while (x) res+=tree1[x], x-=lowbit(x);

    return res;

}

double query2(int x){

    double res=;

    while (x) res+=tree2[x], x-=lowbit(x);

    return res;

}

int main ()

{

    int n, m;

    while (~scanf("%d%d",&n,&m)) {

        init();

        FOR(i,,n) scanf("%d%d%lf",&node[i].x,&node[i].y,&node[i].val), v.pb(node[i].y);

        sort(node+,node+n+,comp1);

        FOR(i,,m) {

            scanf("%d%d%d%d",&q[i].x,&q[i].ly,&q[i+m].x,&q[i].ry);

            v.pb(q[i].ly); v.pb(q[i].ry);

            q[i].id=q[i+m].id=i; q[i+m].ly=q[i].ly; q[i+m].ry=q[i].ry;

            q[i].flag=; q[i+m].flag=;

        }

        sort(v.begin(),v.end());

        siz=unique(v.begin(),v.end())-v.begin();

        FOR(i,,n) node[i].y=lower_bound(v.begin(),v.begin()+siz,node[i].y)-v.begin()+;

        FOR(i,,*m) {

            q[i].ly=lower_bound(v.begin(),v.begin()+siz,q[i].ly)-v.begin()+;

            q[i].ry=lower_bound(v.begin(),v.begin()+siz,q[i].ry)-v.begin()+;

        }

        sort(q+,q+*m+,comp2);

        int now=;

        FOR(i,,*m) {

            if (q[i].flag==) {

                while (now<=n&&node[now].x<q[i].x) add1(node[now].y,), add2(node[now].y,node[now].val), ++now;

            }

            else {

                while (now<=n&&node[now].x<=q[i].x) add1(node[now].y,), add2(node[now].y,node[now].val), ++now;

            }

            ans1[q[i].id][q[i].flag]=query1(q[i].ry)-query1(q[i].ly-);

            ans2[q[i].id][q[i].flag]=query2(q[i].ry)-query2(q[i].ly-);

        }

        FOR(i,,m) printf("%.2lf/%d\n",ans2[i][]-ans2[i][]+eps,ans1[i][]-ans1[i][]);

    }

    return ;

}

D.Drawing Pictures(矩阵快速幂)

考试时构造不出矩阵啊，发现自己还是太蠢了。。。

首先可以发现偶数是不可能满足对称且相邻的颜色不同的。所以只可能奇数。

奇数由于要满足对称性，于是考虑折半后就可以消除对称性的要求了，有一点，题目要求不能出现123456这样的颜色序列。由于对称性也不能出现654321的序列。

我们定义10个状态。(0)表示合法序列。 (1)表示以1结尾的合法序列。 (12)表示以2结尾的合法序列。 (123), (1234),(12345),(6),(65),(654),(6543),(65432)同理。

于是有i(0)=(i-1)(0)*5-(i-1)(12345)-(i-1)(65432).

i(1)=(i-1)(0)-(i-1)(1)-(i-1)(65432). 其他可以很轻松的推出来。

然后矩阵快速幂加速这个转移就行了。

还有一个地方需要注意，因为转移矩阵有-1且过程会取模，导致结果可能是负数。需要再+mod%mod.

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct Matrix{LL matrix[N][N];}a, sa, unit, kk;

Matrix Mul(Matrix a, Matrix b) //矩阵乘法(%MOD)

{

    Matrix c;

    FOR(i,,) FOR(j,,) {

          c.matrix[i][j]=;

          FOR(l,,) c.matrix[i][j]+=a.matrix[i][l]*b.matrix[l][j];

          c.matrix[i][j]%=MOD;

    }

    return c;

}

Matrix Cal(int exp)  //矩阵快速幂

{

    Matrix p=a, q=unit;

    if (exp==) return q;

    while (exp!=) {

        if (exp&) exp--, q=Mul(p,q);

        else exp>>=, p=Mul(p,p);

    }

    return Mul(p,q);

}

void init(){

    FO(i,,) unit.matrix[i][i]=;

    kk.matrix[][]=; kk.matrix[][]=kk.matrix[][]=;

    a.matrix[][]=; a.matrix[][]=a.matrix[][]=-;

    a.matrix[][]=; a.matrix[][]=a.matrix[][]=-;

    FOR(i,,) a.matrix[i-][i]=;

    a.matrix[][]=; a.matrix[][]=a.matrix[][]=-;

    FOR(i,,) a.matrix[i-][i]=;

}

int main ()

{

    int n;

    init();

    while (~scanf("%d",&n)) {

        if (n%==) {puts(""); continue;}

        n=(n+)/;

        sa=Cal(n-); sa=Mul(kk,sa);

        printf("%lld\n",(sa.matrix[][]+MOD)%MOD);

    }

    return ;

}

E.East and West(贪心+树形DP)

如果着眼于一条边每次只能通过一条火车的限制的话，是感觉很繁杂的。

注意到题目说一定存在一条边使得这两个点集分割开。也就是说这条边是必经之路。从这条边出去的火车一定会满足时间不同。那么经过这条边之后是一定不能产生冲突了。

那么我们只需要求出k个火车到这条边的某个点的最小时间就行了。比如 3 3 3 5，由于这条边存在冲突，所以实际上的时间是 3 4 5 6.

然后求出这个点到东部的点的最短距离。贪心一下即可。因为显然通过这条边时间最少的火车去的点距离远。

我们可以通过一次BFS+排序完成。

关键是如何找到这条割边。

可以通过一次树形DP来完成，记size1[x]是x的子树内属于东部的点的个数。size2[x]是x的子树内属于西部的点的个数。如果满足size1[x]=e&&size2[x]=0或者size1[x]=0&&size2[x]=w.就代表这个点一定出现在割边上。

因此总的时间复杂度是O(nlogn).

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct Edge{int p, next;}edge[N<<];

int head[N], cnt=, n, m, e, w;

int dis[N], node[N], siz[][N];

bool vis[N];

queue<int>Q;

int belong(int x){

    if (x<=e) return ;

    if (x>=n-w+) return ;

    return ;

}

void add_edge(int u, int v){edge[cnt].p=v; edge[cnt].next=head[u]; head[u]=cnt++;}

void dfs(int x, int fa){

    for (int i=head[x]; i; i=edge[i].next) {

        int v=edge[i].p;

        if (v==fa) continue;

        dfs(v,x);

        siz[][x]+=siz[][v]; siz[][x]+=siz[][v];

    }

    if (belong(x)!=) siz[belong(x)][x]+=;

}

void init(){mem(head,); cnt=; mem(vis,); mem(siz,);}

void BFS(int x){

    int u, v;

    dis[x]=; Q.push(x); vis[x]=true;

    while (!Q.empty()) {

        u=Q.front(); Q.pop();

        for (int i=head[u]; i; i=edge[i].next) {

            v=edge[i].p;

            if (vis[v]) continue;

            dis[v]=dis[u]+; Q.push(v); vis[v]=true;

        }

    }

}

int main ()

{

    int u, v, p, K;

    while (~scanf("%d%d%d%d",&n,&m,&e,&w)) {

        init();

        FOR(i,,m) scanf("%d%d",&u,&v), add_edge(u,v), add_edge(v,u);

        dfs(,);

        FOR(i,,n) if ((siz[][i]==e&&siz[][i]==)||(siz[][i]==&&siz[][i]==w)) {p=i; break;}

        BFS(p);

        scanf("%d",&K);

        FOR(i,,K) scanf("%d",&u), node[i]=dis[u];

        sort(node+,node+K+); sort(dis+n-w+,dis+n+);

        int now=node[];

        FOR(i,,K) {

            if (node[i]<now) node[i]=now;

            else now=node[i];

            ++now;

        }

        int ans=;

        FOR(i,,K) ans=max(node[i]+dis[n-w+K-i+], ans);

        printf("%d\n",ans);

    }

    return ;

}

F.Find the Circle(解方程)

这题很强。。。可以推出一个三元二次方程组，然后随便乱减再代一下，得到一个异常麻烦的公式。。。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

inline int Scan() {

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

inline double sqr(double a)

{

    return a*a;

}

double ax, x2, x3, ay, y2, y3, r1, r2, r3;

int m1, m2, m3;

bool check(double x, double y, double r)

{

    if(fabs(sqr(x-ax)+sqr(y-ay)-sqr(r+m1*r1))>eps)return false;

    if(fabs(sqr(x-x2)+sqr(y-y2)-sqr(r+m2*r2))>eps)return false;

    if(fabs(sqr(x-x3)+sqr(y-y3)-sqr(r+m3*r3))>eps)return false;

    return true;

}

int main()

{

    int t;

    scanf("%d", &t);

    while(t-->)

    {

        scanf("%lf%lf%lf%d%lf%lf%lf%d%lf%lf%lf%d", &ax, &ay, &r1, &m1, &x2, &y2, &r2, &m2, &x3, &y3, &r3, &m3);

        if(m1==)m1=-;

        if(m2==)m2=-;

        if(m3==)m3=-;

        double a, b, c, d, aa, bb, cc, dd;

        //ax+by=cr+d

        a=*(ax-x2);

        b=*(ay-y2);

        c=*(r2*m2-r1*m1);

        d=m2*m2*r2*r2-m1*m1*r1*r1-x2*x2+ax*ax-y2*y2+ay*ay;

        aa=*(ax-x3);

        bb=*(ay-y3);

        cc=*(r3*m3-r1*m1);

        dd=m3*m3*r3*r3-m1*m1*r1*r1-x3*x3+ax*ax-y3*y3+ay*ay;

        double a1, b1, a2, b2;

        if(fabs(bb*a-aa*b)<eps){printf("NO SOLUTION!\n");continue;}

        a1=(a*cc-c*aa)/(bb*a-aa*b);//y=a1*r+b1;

        b1=(dd*a-d*aa)/(bb*a-aa*b);

        if(fabs(b*aa-bb*a)<eps){printf("NO SOLUTION!\n");continue;}

        a2=(cc*b-c*bb)/(b*aa-bb*a);//x=a2*r+b2;

        b2=(b*dd-bb*d)/(b*aa-bb*a);

        double A, B, C;//A*r^2+B*r+C=0;

        A=a2*a2+a1*a1-;

        B=*a2*b2-*ax*a2+*a1*b1-*ay*a1-*m1*r1;

        C=b2*b2-*ax*b2+ax*ax+b1*b1-*ay*b1+ay*ay-r1*r1;

        double rr;

        if(B*B-*A*C<){printf("NO SOLUTION!\n");continue;}

        if(fabs(A)<eps){printf("NO SOLUTION!\n");continue;}

        rr=(sqrt(B*B-*A*C)-B)//A;

        double rx=a2*rr+b2;

        double ry=a1*rr+b1;

        if(rr>=-eps&&check(rx, ry, rr))

        {

            printf("%.4lf %.4lf", rx, ry);

            if(fabs(rr)>=eps)printf(" %.4lf", rr);

            printf("\n");

            continue;

        }

        rr=(-B-sqrt(B*B-*A*C))//A;

        rx=a2*rr+b2;

        ry=a1*rr+b1;

        if(rr>=-eps&&check(rx, ry, rr))

        {

            printf("%.4lf %.4lf", rx, ry);

            if(fabs(rr)>=eps)printf(" %.4lf", rr);

            printf("\n");

            continue;

        }

        printf("NO SOLUTION!\n");

    }

    return ;

}

J.JLUCPC(树形DP)

可以一次dfs算出根节点的答案，然后再dfs一次向下转移后每个节点的答案。复杂度O(n).

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct Edge{int p, next, w;}edge[N<<];

int node[N], head[N], cnt=, dep[N];

LL val[N], siz[N], sum;

void init(){mem(head,); cnt=; mem(siz,); mem(val,); mem(dep,);}

void add_edge(int u, int v, int w){

    edge[cnt].p=v; edge[cnt].next=head[u]; edge[cnt].w=w; head[u]=cnt++;

}

void dfs(int x, int fa){

    siz[x]+=node[x];

    for (int i=head[x]; i; i=edge[i].next) {

        int v=edge[i].p;

        if (v==fa) continue;

        dep[v]=dep[x]+edge[i].w;

        dfs(v,x);

        siz[x]+=siz[v];

    }

}

void dfs1(int x, int fa){

    for (int i=head[x]; i; i=edge[i].next) {

        int v=edge[i].p;

        if (v==fa) continue;

        val[v]=val[x]-siz[v]*edge[i].w+(sum-siz[v])*edge[i].w;

        dfs1(v,x);

    }

}

int main ()

{

    int n, u, v, w;

    while (~scanf("%d",&n)) {

        sum=;

        init();

        FOR(i,,n) scanf("%d",node+i), sum+=node[i];

        FO(i,,n) scanf("%d%d%d",&u,&v,&w), add_edge(u,v,w), add_edge(v,u,w);

        dfs(,);

        FOR(i,,n) val[]+=(LL)node[i]*dep[i];

        dfs1(,);

        LL ans=(LL)<<;

        FOR(i,,n) ans=min(ans,val[i]);

        printf("%lld\n",ans);

    }

    return ;

}

巴特西

2011 Multi-University Training Contest 6 - Host by JLU

最新文章

热门文章