比赛地址

Codeforces Gym

目前还在补题

[A] Rush Hour Puzzle

题意

给出一个6\times 6的棋盘,上面散布着有长度为2或3的一些玩具车.每个车为横向或者纵向放置.游戏规则和华容道比较像,问能否在10步数内将某辆车移出棋盘.

题解

DFS爆搜+玄学剪枝

直接深搜,记录下当前棋盘的状态,和每辆车的车头的坐标,车辆长度,横纵情况.然后根据车辆移动的情况搜就行了.

中间加了一些奇奇怪怪的剪枝,同时用了一个感觉不怎么靠谱的Hash函数来记忆化棋盘,没想到居然过了.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 3000010
#define MOD 32767
#define INF 0x3f3f3f3f
using namespace std;

int i,j,cnt,flag,sum,res,Ans=INF;
int C[10][10],l[15],f[15],s[15];
bool ha[MOD+10];

map <int,int> M;

struct Car{
    int x,y,f,l;
};

struct Data{
    int h;
    short m[7][7];
    Car c[15];
}a[N];

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

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

IL int Hash(int x){
    reg int i=0,j=0,H=0,s=0;
    for (i=1;i<=6;i++)
        for (j=1;j<=6;j++){
            s=(i-1)*6+j;
            H=(H+s*a[x].m[i][j]*15)%MOD;
        }
    return H;
}

IL void Ready(){
    reg int i=0,j=0,x=0;
    for (i=1;i<=6;i++)
        for (j=1;j<=6;j++){
            a[0].m[i][j]=x=C[i][j];
            if (x==C[i][j-1] && x!=C[i][j+1]){
                a[0].c[x].f=1;  a[0].c[x].x=i;  a[0].c[x].y=j;
                a[0].c[x].l=2;
                if (j>2 && x==C[i][j-2])    a[0].c[x].l++;
            }
            if (x==C[i+1][j] && x!=C[i-1][j]){
                a[0].c[x].f=2;  a[0].c[x].x=i;  a[0].c[x].y=j;
                a[0].c[x].l=2;
                if (x==C[i+2][j])   a[0].c[x].l++;
            }
        }
    for (i=1;i<=10;i++)
        if (a[0].c[i].x)    cnt=i,f[i]=a[0].c[i].f,s[i]=a[0].c[i].l;
    for (i=1;i<=cnt;i++)
        if (a[0].c[i].f==2)
            l[a[0].c[i].y]+=a[0].c[i].l;
    for (i=a[0].c[1].y+1;i<=6;i++)
        if (l[i]==6)    {
            puts("-1"); flag=1;
            return;
        }
    if (a[0].c[1].x!=3) {
        puts("-1"); flag=1;
        return;
    }
    if (a[0].c[1].f!=1) {
        puts("-1"); flag=1;
        return;
    }
    a[0].h=Hash(0);
    res=6-a[0].c[1].y;
/*  for (i=1;i<=10;i++)
        if (a[0].c[i].x)
            cout<<i<<" "<<a[0].c[i].x<<" "<<a[0].c[i].y<<" "<<a[0].c[i].l<<endl;
*/
}

IL void Dfs(int p,int step){
    if (step<=res && a[p].m[3][a[p].c[1].y+1]!=0){
        sum--;  return;
    }
    if (a[p].m[3][6]==1){
        sum--;
        Ans=Min(Ans,8-step);    return;
    }
    if (Ans<=8-step){
        sum--;  return;
    }
    if (!step){
        sum--;  return;
    }
    if (ha[a[p].h]>step){
        sum--;  return;
    }
    ha[a[p].h]=step;
    reg int i=0,x=0,y=0,L=0;
    res=6-a[0].c[1].y;
/*  for (x=1;x<=6;x++){
        for (y=1;y<=6;y++){
            printf("%d ",a[p].m[x][y]);
        }
        putchar(10);
    }
    putchar(10);*/
    for (i=1;i<=cnt;i++){
        if (f[i]==1){
            x=a[p].c[i].x;  y=a[p].c[i].y;  L=s[i]-1;
            if (y==6 || a[p].m[x][y+1]!=0)  goto END;
            ++sum;  a[sum]=a[p];
            a[sum].m[x][y-L]=0; a[sum].m[x][y+1]=i;
            a[sum].c[i].y++;
            a[sum].h=Hash(sum);
            Dfs(sum,step-1);
            END:
            if (y<=L+1 || a[p].m[x][y-(L+1)]!=0)    continue;
            if (i==1)   continue;
            ++sum;  a[sum]=a[p];
            a[sum].m[x][y]=0;   a[sum].m[x][y-(L+1)]=i;
            a[sum].c[i].y--;
            a[sum].h=Hash(sum);
            Dfs(sum,step-1);
        }   else {
            x=a[p].c[i].x;  y=a[p].c[i].y;  L=s[i]-1;
            if (x+L==6 || a[p].m[x+L+1][y]!=0)  goto END2;
            ++sum;  a[sum]=a[p];
            a[sum].m[x][y]=0;   a[sum].m[x+L+1][y]=i;
            a[sum].c[i].x++;
            a[sum].h=Hash(sum);
            Dfs(sum,step-1);
            END2:
            if (x==1 || a[p].m[x-1][y]!=0)  continue;
            ++sum;  a[sum]=a[p];
            a[sum].m[x+L][y]=0; a[sum].m[x-1][y]=i;
            a[sum].c[i].x--;
            a[sum].h=Hash(sum);
            Dfs(sum,step-1);            
        }
    }
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    for (i=1;i<=6;i++)
        for (j=1;j<=6;j++)
            C[i][j]=read();
    Ready();
    if (flag)   return 0;
    Dfs(0,8);
    if (Ans==INF) {
        cout<<"-1"<<endl;
        return 0;
    }
    Ans+=2;
    if (Ans>10){
        cout<<"-1"<<endl;
        return 0;
    }
    cout<<Ans<<endl;
    return 0;
}

[C] Are They All Integers?

题意&题解

签到题

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,i,j,k,x,flag=0;
int a[55];

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

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

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%d",&n);
    for (i=1;i<=n;i++)  scanf("%d",&a[i]);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            for (k=1;k<=n;k++){
                if (i==j || j==k || i==k)   continue;
                x=(a[i]-a[j])/a[k];
                if (x*a[k]!=(a[i]-a[j])){
                    flag=1;
                }
            }
    if (flag==1)    puts("no");
    else puts("yes");
    return 0;
}

[D] Tapioka

题意&题解

签到题

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int s;
string a,b,c,d,e;

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

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

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    cin>>a>>b>>c;
    d="bubble"; e="tapioka";
    if (a==d || a==e)   s++;
    if (b==d || b==e)   s++;
    if (c==d || c==e)   s++;
    if (s==3){
        puts("nothing");
        return 0;
    }
    if (a!=d && a!=e)   cout<<a<<" ";
    if (b!=d && b!=e)   cout<<b<<" ";
    if (c!=d && c!=e)   cout<<c<<" ";
    return 0;
}

[E] The League of Sequence Designers

题意

给出一段长度为n的整数序列,1 \leq n <2000.并给出了一段求(r-l+1)\sum_{i=l}^{r}a_{i}的最大值的贪心代码.现在要求构造出一段这样的序列,要求正确的最大值比给出代码求出的最大值恰好大k.输出任意一种方案.

题解

简单构造.

直接构造长度为1999的序列.令序列的第一位为-1,后面全都是非负数.这样贪心找到的子序列长度就是1998,正解找到的子序列长度是1999.设后面这些数的和为x.可以得到如下方程:

1999(x-1)-1998x=k

化简得,x=k+1999

然后把x随便填充到后面的空位中即可.

代码

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

int main() {
    int T; cin >> T; while(T--) {
        long long int k, L;
        cin >> k >> L;
        if (L >= 2000)  {
            printf("-1\n");
            continue;
        }
        printf("1999\n");
        long long int sum = k + 1999;
        int tot = 0;
        printf("-1 ");
        while(sum) {
            if (sum > 1000000) {
                printf("1000000 ");
                sum -= 1000000;
                tot++;
            }
            else {
                printf("%d ", sum);
                sum = 0;
                tot++;
            }
        }
        for (int i = tot+1; i < 1999; i++) printf("0 ");
        printf("\n");
    }
    return 0;
}

[H] Mining a

题意

给出一个数n.求最大的a,使得存在b,满足\frac{1}{n}=\frac{1}{a \oplus b}+\frac{1}{b}.中间的运算符为异或.

题解

有趣的结论题.b=n+1.然后反解出a就行了.

但是并不会证明

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

LL n,i,x,y;

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

IL LL read(){
    LL p=0,f=1; char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();
    for (i=1;i<=n;i++){
        x=read();
        y=x*(x+1);
        y^=(x+1);
        cout<<y<<endl;
    }
    return 0;
}

[J] Automatic Control Machine

题意

给出m个集合,每个集合中有一些正整数.现在求它的一个最小的集合子集,使得这些集合的并集中恰好包含了n个数.

题解

二进制暴力枚举,拿Bitset直接通过或运算来计算并集的情况.实际运行的速度快的飞起.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<bitset>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int T,n,m,i,j,Ans,s;
char c[520];
bitset <500> a[17];

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

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

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        scanf("%d%d",&n,&m);
        a[0].reset();   Ans=INF;
        for (i=1;i<=m;i++){
            scanf("%s",&c);
            a[i].reset();
            for (j=0;j<n;j++){
                if (c[j]=='1')
                    a[i][j+1]=1;
            }
        }
        for (i=1;i<(1<<m);i++){
            a[0].reset();   s=0;
            for (j=0;j<m;j++){
                if (i&(1<<j)){
                    s++;    a[0]|=a[j+1];
                }
            }
            if (a[0].count()==n)    Ans=Min(Ans,s);
        }
        if (Ans==INF)   puts("-1");
        else printf("%d\n",Ans);
    }
    return 0;
}

[K] Length of Bundle Rope

题意&题解

签到题

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
#define N 1010
using namespace std;

int i,j,k,len,T,n,x,y,Ans;
int s[N];
int f[N][N];

priority_queue <int> Q;

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

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

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    T=read();
    while (T--){
        n=read();
        for (i=1;i<=n;i++)  Q.push(-read());
        Ans=0;
        while (Q.size()>1){
            x=Q.top();  Q.pop();
            y=Q.top();  Q.pop();
            Ans-=x+y;
            Q.push((x+y));
        }
        Q.pop();
        printf("%d\n",Ans);
    }
    return 0;
}

[L] Largest Quadrilateral

题意

给出平面上的一堆点,要求从其中找出四个点,使得这四个点围成的多边形的面积最大.(可能有重合的情况)

题解

旋转卡壳+枚举

构造出凸包后,枚举这个四边形的一条直径,然后类似旋转卡壳那样找面积最大的情况.需要卡一下常数.

代码

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

#define _BS 1048576
char _bf[_BS];
char *__p1=_bf,*__p2=_bf;
#define _IO char *_p1=__p1,*_p2=__p2;
#define _OI __p1=_p1,__p2=_p2;

#define GC (_p1==_p2&&(_p2=(_p1=_bf)+fread(_bf,1,_BS,stdin),_p1==_p2)?EOF:*_p1++)
#define PC putchar
#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 _G1(_1) int _1;sc(_1)
#define _G2(_1,_2) int _1,_2;sc(_1)sc(_2)
#define _G3(_1,_2,_3) int _1,_2,_3;sc(_1)sc(_2)sc(_3)
#define _gG(_1,_2,_3,_get, ...) _get
#define get(...) _gG(__VA_ARGS__,_G3,_G2,_G1, ...)(__VA_ARGS__)
#define F(i,l,r) for(int i=(l);i<(r);++i)
#define FD(i,l,r) for(int i=(l);i<=(r);++i)

#define IL inline
#define OP operator
#define CON constexpr

using vint = long long;
vint VINF = 0x3f3f3f3f3f3f3f3fLL;
using namespace std;

IL vint sqr(vint x) { return x * x; };

struct Po
{
    int id;
    vint x, y;
    Po() {}
    Po(vint x, vint y) : x(x), y(y) {}
    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); }
    bool OP < (const Po &o) const { return x < o.x || x == o.x && y < o.y; }
    bool 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)); }
};

CON int MP = 1e4 + 7;
struct Poly
{
    int n;
    Po p[MP];
    int top;
    Po sta[MP];
    Poly() : n(0) {}
    void clear() { p[n] = sta[top] = {0, 0}, n = 0; top = 0; }
    void emplace(const Po &ne) { p[n++] = ne; }
    void convex()
    {
        sort(p, p + n);
        top = 0;
        for (int i = 0; i < n; ++i)
        {
            while (top > 1 && ((sta[top - 1] - sta[top - 2]) ^ (p[i] - sta[top - 2])) <= 0)
                --top;
            sta[top++] = p[i];
        }
        int k = top;
        for (int i = n - 2; i >= 0; --i)
        {
            while (top > k && ((sta[top - 1] - sta[top - 2]) ^ (p[i] - sta[top - 2])) <= 0)
                --top;
            sta[top++] = p[i];
        }
        if (n > 1)
            --top;
    }

    #define MOD(a, b) (a=(a>=b ? a-b:a))
    vint rt_cp()
    {
        this->convex();

        if (top <= 2)
            return 0;

        if (top == 3) // 凹多边形
        {
            vint ans = 0;
            vint min_tri = VINF;
            ans = abs((sta[0] - sta[2]) ^ (sta[1] - sta[2]));
            for (int i = 0; i < n; i++)
            {
                if (sta[0].id == p[i].id || sta[1].id == p[i].id || sta[2].id == p[i].id)
                    continue;
                min_tri = min(min_tri, abs((sta[0] - p[i]) ^ (sta[1] - p[i])));
                min_tri = min(min_tri, abs((sta[1] - p[i]) ^ (sta[2] - p[i])));
                min_tri = min(min_tri, abs((sta[2] - p[i]) ^ (sta[0] - p[i])));
            }
            if (min_tri == VINF)
                return 0;
            return ans - min_tri;
        }

        vint ans = 0;
        for (int i = 0; i < top; i++)
        {
            int ni = i+1, nj = i+2;
            MOD(ni, top), MOD(nj, top);
            for (int j=nj; j!=i; ++j, MOD(j, top))
            {
                while (MOD(ni, top) != j && abs((sta[j]-sta[i]) ^ (sta[ni]-sta[i])) - abs((sta[j]-sta[i]) ^ (sta[ni+1]-sta[i])) < 0 )  ++ni;
                while (MOD(nj, top) != i && abs((sta[j]-sta[i]) ^ (sta[nj]-sta[i])) - abs((sta[j]-sta[i]) ^ (sta[nj+1]-sta[i])) < 0 )  ++nj;
                ans = max(ans, abs((sta[ni] - sta[i]) ^ (sta[j] - sta[i])) + abs((sta[nj] - sta[i]) ^ (sta[j] - sta[i])));
            }
        }

        return ans;
    }
} p;

int main()
{
    _IO

        get(T)
        const char *ss[] = {"%lld\n", "%lld.5\n"};
    Po x;
    while (T--)
    {
        p.clear();
        get(n)
            for (int i=0; i<n; ++i)
            {
                x.id = i;
                sc(x.x)sc(x.y)
                    p.emplace(x);
            }
        vint ans = p.rt_cp();
        printf(ss[ans & 1], ans >> 1);
    }
    return 0;
}

总结

整场比赛发挥还可以,智商基本上持续在线.比如H题直接猜出了结论节省了很多时间.当然中间还是犯了一些错误,M题开场读完后以为是一个广义Lucas定理,甩给队友持续研究了半天.到最后快结束的时候才发现题目中的取模是重新定义过的,并不是板子题.导致前期开题时人手有些不够,切签到题的速度有些慢.中间推E题构造式子的时候也有些慢.A题在RE了一发之后,一直以为是递归崩栈了,改了几次无果之后才发现是数组越界,多吃了很多次罚时.最后的时间全部用来推F题,感觉是一个SPFA实数费用流模型,但是直到最后也没有完成对模型的修正,正好回头找一队问一下做法.

别人的520用来秀恩爱,我的520用来训练,我们都度过了充实的一天

说点什么
支持Markdown语法
好耶,沙发还空着ヾ(≧▽≦*)o
Loading...