比赛地址

Vjudge Contest

[A]Alice's Print Service

题意

打印一定的页数的文件会产生一些费用,每页的打印代价是一个分段函数,当总页数达到一定值得时候,每页的费用会发生变化.给出计费策略和需要打印的总页数,求最小花费.

题解

签到题

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;

int T, n, m;
long long int s[100005], p[100005], used[100005], a;

int main(){
    cin >> T;
    while(T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%lld%lld", &s[i], &p[i]);
        }
        for (int i = 1; i <= n; i++) used[i] = s[i] * p[i];
        for (int i = n-1; i >= 1; i--) used[i] = min(used[i], used[i+1]);
        used[n+1] = used[n];
        for (int i = 1; i <= m; i++) {
            scanf("%lld", &a);
            int x = 1, y = n;
            while(y > x) {
                int mid = ((x+y) >> 1) + 1;
                if (a >= s[mid]) x = mid;
                else y = mid - 1;
            }
            if (x == n) cout << a*p[x] << endl; 
            else    cout << min(a*p[x], used[x+1]) << endl;
        }
    }
    return 0;
}

[C]Collision

题意

在桌面的圆形轨道区域内部有一个光滑的圆形障碍,现在在桌面上滑出一枚硬币,给出硬币的速度矢量和半径大小,求硬币的某一部分在轨道内部的总时间.

题解

计算几何

代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cctype>
#include <cfloat>
#include <vector>
#include <algorithm>

#define GC getchar()
#define _Q_(x) {register char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;
#define _H_(x) for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define sc(x) _Q_(x)_H_(x)
#define se(x) _Q_(x)else if(_c==EOF)return 0;_H_(x)

#define sqrt(x) sqrt(ABS(x))       //【极其重要】防止一个绝对值小于EPS的负数进入sqrt！！！！ 类似的还有ac、as，要防止一个值为1+EPS or -1-EPS的数进入！！！！ 
#define IL inline
#define OP operator


typedef double vint;

const vint EPS = 1e-6, INF = 1e22, PI = 3.141592653589793238462643383279502884197169399375105820974944592, RAD = 180 / PI;

enum PSTA
{
    REV_EX = -3, EX = 3,    // 反向延长线上，延长线上 
    IS_S = -2, IS_T = 2,    // 是起点，是终点
    RIGHT = -1, LEFT = 1,   // 在右侧（顺时针侧），在左侧（逆时针侧） 
    INSIDE = 0,             // 严格在内部

    N_SSSTA = 7,
    N_LSSTA = 3,
};

IL vint ABS(vint x) {return x>0 ? (x>EPS ? x:0) : (x<-EPS ? -x:0);}
IL vint MIN(vint a, vint b) {return a<b ? a:b;}
IL vint MAX(vint a, vint b) {return a>b ? a:b;}
IL bool eq(vint a, vint b) {return a>b ? a-b<EPS : b-a<EPS;}
IL bool zero(vint x) {return x>0 ? x<EPS : x>-EPS;}
IL int  sign(vint x) {return x>0 ? (x>EPS ? 1:0) : (x<-EPS ? -1:0);}
IL vint norm(vint x) {return x>0 ? (x>EPS ? x+EPS:0) : (x<-EPS ? x-EPS:0);}
#define PC putchar
void PRT(const char *fmt, vint x)   // 格式字串fmt后面加什么都行，但是务必保证开头第一个字符就是数字的第一位或者负号
{
    static char buf[666];
    sprintf(buf, fmt, norm(x));

    bool all_0 = true;
    for (char *p=buf; *p; ++p)
        if (isdigit(*p) && *p!='0')
        {
            all_0 = false;
            break;
        }
    printf("%s", buf + (all_0 && *buf=='-'));
}

IL vint sqr(vint x) {return x*x;}
IL vint cub(vint x) {return x*x*x;}
IL vint dtoa(vint d) {return d / RAD;}
IL vint atod(vint a) {return a * RAD;}

typedef struct Po
{
    vint x, y;

    Po(void) { }
    Po(vint xx, vint yy) : x(xx), y(yy) { }
    Po(const Po &a, const Po &b) : x(b.x-a.x), y(b.y-a.y) { }

    void println() const {PC('('), PRT("%.3f, ", x), PRT("%.3f)\n", y);}
    vint len() const {return sqrt(sqr(x) + sqr(y));}

    Po OP +(vint d) const {return Po(x+d, y+d);}
    Po OP -(vint d) const {return Po(x-d, y-d);}
    Po OP +=(vint d) {x+=d, y+=d; return *this;}
    Po OP -=(vint d) {x-=d, y-=d; return *this;}
    Po OP *(vint k) const {return Po(x*k, y*k);}
    friend Po OP*(vint k, const Po &o) {return Po(k*o.x, k*o.y);}
    Po OP /(vint k) const {return Po(x/k, y/k);}

    Po OP +(const Po &o) const {return Po(x+o.x, y+o.y);}
    Po OP -(const Po &o) const {return Po(x-o.x, y-o.y);}
    Po OP +=(const Po &o) {x+=o.x, y+=o.y; return *this;}
    Po OP -=(const Po &o) {x-=o.x, y-=o.y; return *this;}

    vint OP *(const Po &o) const {return x*o.x + y*o.y;}
    vint OP ^(const Po &o) const {return x*o.y - y*o.x;}
    vint OP |(const Po &o) const {return sqrt(sqr(x-o.x)+ sqr(y-o.y));}
} Vec;
vint dist(const Po &a, const Po &b)
{
    return sqrt(sqr(a.x-b.x) + sqr(a.y-b.y));
}

struct Li
{
    Po s, t;

    Li(void) { }
    Li(const Po &a, const Po &b) : s(a), t(b) { }
    Li(vint x1, vint y1, vint x2, vint y2) : s(x1, y1), t(x2, y2) { }
    Li(vint k, vint b) : s(0, b), t(1, k+b) { }
    Li(vint a, vint b, vint c)
    {
        if (zero(a))    // y = -c/b
            s = {1, -c/b}, t = {2, -c/b};
        else if (zero(b))   // x = -c/a
            s = {-c/a, 1}, t = {-c/a, 2};
        else
            s = {1, (-c-a)/b}, t = {0, -c/b};   // 不能是{(-c-b)/a, 1}，因为这个可能和 {1, (-c-a)/b} 是同一个点！！！
    }

    void println() const {printf("("), PRT("%.3f, ", s.x), PRT("%.3f) -> (", s.y), PRT("%.3f, ", t.x), PRT("%.3f)\n", t.y);}
    vint len() const {return (t-s).len();}
    vint dist(const Po &p) const
    {
        return ABS((t-s) ^ (p-s) / (s | t));
    }
    int rel(const Po &p) const  // -1: right, 0: inside, 1: left
    {
        return sign((t-s) ^ (p-s));
    }

    Po OP &(const Li &o) const
    {
        const vint p1 = (o.t-o.s) ^ (s-o.s);
        const vint p2 = (o.t-o.s) ^ (t-o.s);
        return Po((s.x*p2 - t.x*p1)/(p2-p1), (s.y*p2 - t.y*p1)/(p2-p1));
    }
    bool OP ==(const Li &o) const {return zero((t-s) ^ (o.s-s)) && zero((t-s) ^ (o.t-s));}  // 共线
    bool OP &&(const Li &o) const {return zero((t-s) * (o.t-o.s));} // 垂直
    bool OP ||(const Li &o) const {return zero((t-s) ^ (o.t-o.s)) && !(*this==o);}  // 平行，不共线
    bool OP / (const Li &o) const {return zero((t-s) ^ (o.t-o.s));} // 平行或共线，不会有唯一交点
};



int main()
{
    vint sr, br, cr, cx, cy, vx, vy;
    Po O(0, 0);
    while (~scanf("%lf %lf %lf %lf %lf %lf %lf", &sr, &br, &cr, &cx, &cy, &vx, &vy))
    {
        Po v(vx, vy), c(0-cx, 0-cy);
        vint vabs = v.len();
        Po vn(vx / vabs, vy / vabs);
        if (sign(v * c) <= 0)
        {
            puts("0");
            continue;
        }
        Li l(c, c+v);
        vint dco = l.dist(O);
        if (sign(dco - (cr+br)) >= 0)
        {
            puts("0");
            continue;
        }

        vint xian = sqrt(sqr(cr+br) - sqr(dco));
        Po vcz(-v.y, v.x);
        Li lv(O+vcz, O);
        Po ct = lv & l;
        Po A = ct - (xian*vn);
        Po B = ct + (xian*vn);

        vint dx, dt;
        if (sign(dco - (cr+sr)) >= 0)   // 穿过
        {
            dx = dist(A, B);
            dt = dx / vabs;
        }
        else    // 碰撞
        {
            xian = sqrt(sqr(cr+sr) - sqr(dco));
            Po D = ct - (xian*vn);
            dx = dist(A, D);
            dt = dx / vabs;
            dt *= 2;
        }
        PRT("%.10f\n", dt);
    }
    return 0;
}

[G]Graph Reconstruction

题意

给出一个简单无向图的点数和每个点的度数,求是否存在这样的图.如果存在且唯一,输出方案;如果不唯一,输出任意两种方案,如果无解,则输出"IMPOSSIBLE".

题解

和CF某场比赛的题目很像.

根据Wikipedia上的某个图论定理(具体名字记不清了),首先将度数从大到小排序,然后取出度数最大的点,向后面的点依次连边,被连边的点的度数减1.之后重复以上步骤,直到所有点的度数全变成0.当某个点在被连边时度数为0,说明无解.如果某时刻最后一个连边的点的后一个点的度数不为0,则说明有多解;否则解唯一.

当有多组解时,在连最后一条边的时候跳过本该连接的点,转而和后一个度数非零的点连边,这样就构造出了第二种方案.但是,根据其他队的实验.原题貌似没写SPJ,构造解的方法必须和样例透露出的方法完全一致才能AC.辣鸡出题人.

代码

非比赛AC版,但是在有SPJ的条件下应该没问题

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define N 257
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,j,flag,cnt;
int v[N];
int l[N][N];
int Ans[8*N*N],ans[8*N*N];

struct Data{
    int x,id;
}d[N],dd[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline bool cmp(Data x,Data y){return x.x>y.x;}

inline void Work(){
    int i=0,p=0,q=0;
    memset(l,0,sizeof(l));
    for (i=1;i<=n;i++){
        sort(d+i,d+i+n,cmp);
        /*for (j=i;j<=n;j++)
            printf("%d ",d[j].x);
        cout<<endl;*/
        p=d[i].id;
        if (!d[i].x)    break;
        for (j=i+1;j<=i+d[i].x;j++){
            l[p][d[j].id]=1;    l[d[j].id][p]=1;
            d[j].x--;
            if (d[j].x<0){
                flag=2; return;
            }
        }
        if (d[j].x>0)   flag=1;
    }
}

inline void Find(){
    int i=0,p=0,q=0;
    memset(l,0,sizeof(l));
    for (i=1;i<=n;i++){
        sort(d+i,d+i+n,cmp);
        /*for (j=i;j<=n;j++)
            printf("%d ",d[j].x);
        cout<<endl;*/
        p=d[i].id;
        if (!d[i].x)    break;
        for (j=i+1;j<=i+d[i].x;j++){
            l[p][d[j].id]=1;    l[d[j].id][p]=1;
            d[j].x--;
        }
        d[i].x=0;
        if (d[j].x==d[j-1].x+1&&d[j].x>0){
            l[p][d[j-1].id]=0;  l[d[j-1].id][p]=0;
            l[p][d[j].id]=1;    l[d[j].id][p]=1;
            d[j-1].x++; d[j].x--;
        }
    }
}

int main(){
    while (~scanf("%d",&n)){
        m=0;
        memset(d,0,sizeof(d));  memset(dd,0,sizeof(dd));
        for (i=1;i<=n;i++){
            scanf("%d",&d[i].x);
            d[i].id=i;  m+=d[i].x;
            dd[i]=d[i];
        }
        if (n==1){
            if (d[1].x==0){
                printf("UNIQUE\n");
                printf("1 0\n");
                cout<<endl;
                cout<<endl;
                continue;
            }   else {
                printf("IMPOSSIBLE\n");
                continue;
            }
        }


        flag=0; cnt=0;  m/=2;
        Work();
        if (flag==2){
                printf("IMPOSSIBLE\n");
                continue;
        }


        if (flag==0)    printf("UNIQUE\n");
        else printf("MULTIPLE\n");
        printf("%d %d\n",n,m);
        cnt=0;
        memset(ans,0,sizeof(ans));
        memset(Ans,0,sizeof(Ans));
        for (i=1;i<=n;i++)
            for (j=i+1;j<=n;j++)
                if (l[i][j])    {
                    ++cnt;
                    ans[cnt]=i; Ans[cnt]=j;
                }
        for (i=1;i<=cnt;i++)    printf("%d ",ans[i]);
        cout<<endl;
        for (i=1;i<=cnt;i++)    printf("%d ",Ans[i]);
        cout<<endl;
        if (flag==0)    continue;
        for (i=1;i<=n;i++)  d[i]=dd[i];
        Find();
        cnt=0;
        memset(ans,0,sizeof(ans));
        memset(Ans,0,sizeof(Ans));
        printf("%d %d\n",n,m);
        for (i=1;i<=n;i++)
            for (j=i+1;j<=n;j++)
                if (l[i][j])    {
                    ++cnt;
                    ans[cnt]=i; Ans[cnt]=j;
                }
        for (i=1;i<=cnt;i++)    printf("%d ",ans[i]);
        cout<<endl;
        for (i=1;i<=cnt;i++)    printf("%d ",Ans[i]);
        cout<<endl;
    }
    return 0;
}

[H]Skycity

题意

给出一个n层建筑,每一层的形状是一个圆柱体.给出建筑的总高度,高度平均分配,现在要求在每一层建筑外面贴一个多边形的瓷砖,要求圆柱体和外面的多边形相切,且外面瓷砖的面积不能小于某个定值.求最小的瓷砖面积是多少.

题解

计算几何,二分每一层的多边形边数,然后计算面积再统计即可.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;

double R, r, H, S;
double eps = 1e-8;
int F;

int main(){
    double pi = acos(-1);
    while(scanf("%lf%lf%lf%d%lf", &R, &r, &H, &F, &S) == 5) {
        double h = H/F;
        double ans = 0;
        for (int i = 0; i < F; i++) {
            double rx = 1.0*i/(F)*(R-r) + r;
            int x = 3, y = 10000000;
            while(y > x) {
                int k = (x+y) >> 1;
                k++;
                double l = 2*rx*tan(pi/k);
                if (l*h >= S) x = k;
                else y = k-1;
            }
            /*
            while(1) {
                int t = x+1;
                double l = 2*rx*tan(pi/t);
                printf("%lf %lf\n", 2*rx*tan(pi/x)*h, l*h);
                if (l*h >= S) x = t;
                else break; 
            }*/
            double l = 2*tan(pi/x);
            ans += rx * x * l * h;
        }
        printf("%.3lf\n", ans);
    }
    return 0;
}

[J]Josephina and RPG

题意

有n支AI队伍进行比赛,给出队伍之间对战的胜率.然后给出敌方的出战顺序,一开始可以选定一支AI队伍开始和敌方对战.每场对战胜利后,可以选择切换成刚刚击败的队伍进行下面的比赛,也可以不切换.求q场比赛后的最高胜率是多少.

题解

设第i场敌方出战的AI是t[i],f[i][j]表示第i场使用j队伍的最高胜率,则有如下转移方程:

f[i+1][j]=Max(f[i+1][j],f[i][j]*win[j][t[i+1]])

f[i+1][t[i]]=Max(f[i+1][t[i]],f[i][j]*win[t[i]][t[i+1]])

表示是否切换队伍,然后取最后一次比赛的最大值即可.

比赛时代码莫名RE,根据赛后测试,输入数据存在越界的情况......辣鸡出题人!

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;

int n,m,i,j,q;
double Ans;
double dp[20010][255];
double a[255][255];
int t[20010];

inline double Max(double a,double b){return (a>b)?a:b;}

int main(){
    while (~scanf("%d",&m)){
        n=m*(m-1)*(m-2)/6;
        memset(a,0,sizeof(a));
        memset(dp,0,sizeof(dp));
        memset(t,0,sizeof(t));
        Ans=0;
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
                scanf("%lf",&a[i][j]);
        scanf("%d",&q);
        for (i=1;i<=q;i++)  scanf("%d",&t[i]),t[i]++;
        if (q==1){
            for (i=1;i<=n;i++)
                Ans=Max(Ans,a[i][t[1]]);
            printf("%.10lf\n",Ans);
            continue;
        }
        for (i=1;i<=n;i++)  dp[1][i]=a[i][t[1]];
        for (i=1;i<q;i++)
            for (j=1;j<=n;j++){
                dp[i+1][j]=Max(dp[i+1][j],dp[i][j]*a[j][t[i+1]]);
                dp[i+1][t[i]]=Max(dp[i+1][t[i]],dp[i][j]*a[t[i]][t[i+1]]);
            }
        for (i=1;i<=n;i++)  Ans=Max(Ans,dp[q][i]);
        printf("%.10lf\n",Ans);
    }
    return 0;
}

[K]Pocket Cube

题意

给出一个二阶魔方各个位置的编号方式以及染色情况,求在至多旋转N步(1步的定义是让某一面旋转90度,方向任意)的情况下至多拼好几个面.

题解

大模拟.

代码

有待补充

总结&吐槽

有史以来做的最辣鸡的一套题,没有之一.J题数据越界导致莫名RE,吃了两次罚时加上不可忽略的Debug和代码重构时间,间接导致K题没有写完.G题莫名WA,赛后交流发现应该是根本就没有SPJ或者SPJ写的和出题人一样辣鸡.这种情况排名也没什么意义了,不想多说什么.GTMD出题人.