Ivan the Fool VS Gorynych the Dragon AC

题解

/*
    http://codeforces.com/problemset/problem/48/E
    Ivan the Fool VS Gorynych the Dragon
*/
#include <bits/stdc++.h>

using namespace std;

int h,t,r,n,m;
int times = 1,max_dis = -1;
int graph[512][512],vis[512][512];
queue <int> task;
queue <int> empty;
struct tasks{
    int head,tail;
}tasks[5120000];
struct head{
    int head,tail;
}head[256];
struct tail{
    int head,tail;
}tail[256];

void dp(){
    int x,y;
    while(!task.empty()){
        x = tasks[task.front()].head;
        y = tasks[task.front()].tail;
        task.pop();
        for(int i = 1;i<=n;i++){
            if(i>x){
                break;
            }
            if(~graph[0][0]){
                return;
            }
            if(graph[x+head[i].head][y+head[i].tail]==-1||graph[x+head[i].head][y+head[i].tail]>graph[x][y]+1){
                graph[x+head[i].head][y+head[i].tail] = graph[x][y]+1;
                if(x+head[i].head+y+head[i].tail<=r){
                    task.push(times);
                    tasks[times].head = x+head[i].head;
                    tasks[times].tail = y+head[i].tail;
                    times++;
                }
                else{
                    max_dis = max(max_dis,graph[x+head[i].head][y+head[i].tail]);
                }
            }
        }
        for(int i = 1;i<=m;i++){
            if(i>y){
                break;
            }
            if(~graph[0][0]){
                return;
            }
            if(graph[x+tail[i].head][y+tail[i].tail]==-1||graph[x+tail[i].head][y+tail[i].tail]>graph[x][y]+1){
                graph[x+tail[i].head][y+tail[i].tail] = graph[x][y]+1;
                if(x+tail[i].head+y+tail[i].tail<=r){
                    task.push(times);
                    tasks[times].head = x+tail[i].head;
                    tasks[times].tail = y+tail[i].tail;
                    times++;
                }
                else{
                    max_dis = max(max_dis,graph[x+tail[i].head][y+tail[i].tail]);
                }
            }
        }
    }
    return;
}

void find_max(){
    memset(graph,-1,sizeof(graph));
    graph[h][t] = 0;
    int x,y;
    while(!task.empty()){
        x = tasks[task.front()].head;
        y = tasks[task.front()].tail;
        task.pop();
        for(int i = 1;i<=n;i++){
            if(i>x){
                break;
            }
            if(graph[x+head[i].head][y+head[i].tail]<graph[x][y]+1){
                graph[x+head[i].head][y+head[i].tail] = graph[x][y]+1;
                if(x+head[i].head+y+head[i].tail<=r){
                    task.push(times);
                    tasks[times].head = x+head[i].head;
                    tasks[times].tail = y+head[i].tail;
                    times++;
                }
                else{
                    max_dis = max(max_dis,graph[x+head[i].head][y+head[i].tail]);
                }
            }
        }
        for(int i = 1;i<=m;i++){
            if(i>y){
                break;
            }
            if(graph[x+tail[i].head][y+tail[i].tail]<graph[x][y]+1){
                graph[x+tail[i].head][y+tail[i].tail] = graph[x][y]+1;
                if(x+tail[i].head+y+tail[i].tail<=r){
                    task.push(times);
                    tasks[times].head = x+tail[i].head;
                    tasks[times].tail = y+tail[i].tail;
                    times++;
                }
                else{
                    max_dis = max(max_dis,graph[x+tail[i].head][y+tail[i].tail]);
                }
            }
        }
    }
    return;
}

bool find_annulus(int x,int y){
    vis[x][y]=2;
    for(int i=1;i<=n&&i<=x;i++){
        int xx=x+head[i].head,yy=y+head[i].tail;
        if(xx+yy>r)continue;
        if(!vis[xx][yy]){
            if(find_annulus(xx,yy))return true;
        }
        else if(vis[xx][yy]==2)return true;
    }
    for(int i=1;i<=m&&i<=y;i++){
        int xx=x+tail[i].head,yy=y+tail[i].tail;
        if(xx+yy>r)continue;
        if(!vis[xx][yy]){
            if(find_annulus(xx,yy))return true;
        }
        else if(vis[xx][yy]==2)return true;
    }
    vis[x][y]=1;
    return false;
}

void is_ivan_die(){
    if(find_annulus(h,t)){
        cout<<"Draw";
    }
    else{
        graph[h][t] = 0;
        task.push(0);
        find_max();
        cout<<"Zmey"<<endl<<max_dis;
    }
    return;
}

int main(){cin>>h>>t>>r;
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>head[i].head>>head[i].tail;
        head[i].head = head[i].head-i;
    }
    cin>>m;
    for(int i = 1;i<=m;i++){
        cin>>tail[i].head>>tail[i].tail;
        tail[i].tail = tail[i].tail-i;
    }
    memset(graph,-1,sizeof(graph));
    graph[h][t] = 0;
    task.push(0);
    tasks[0].head = h;
    tasks[0].tail = t;
    dp();
    if(graph[0][0]!=-1){
        cout<<"Ivan"<<endl<<graph[0][0];
    }
    else{
        is_ivan_die();
    }
    cout<<endl;
    return 0;
}

000001 AC

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

int n;
int a[1024]={0,1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 1, 2, 1, 2, 1, 1, 1, 3, 2, 1, 3, 2, 1, 1, 1, 7, 1, 1, 1, 4, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 5, 2, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 2, 1, 1, 2, 11, 1, 1, 1, 2, 1, 1, 1, 6, 1, 1, 2, 2, 1, 1, 1, 5, 5, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 2, 1, 1, 1, 7, 1, 2, 2, 4, 1, 1, 1, 3, 1, 1, 1};
int b[1024]={0,0, 0, 0, 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 9, 0, 3, 0, 3, 1, 1, 0, 12, 0, 1, 2, 2, 0, 3, 0, 44, 0, 1, 0, 10, 0, 1, 1, 11, 0, 5, 0, 2, 0, 1, 0, 47, 0, 3, 0, 3, 0, 12, 1, 10, 1, 1, 0, 11, 0, 1, 2, 256, 0, 3, 0, 3, 0, 3, 0, 44, 0, 1, 1, 2, 0, 5, 0, 47, 10, 1, 0, 13, 0, 1, 0, 9, 0, 8, 0, 2 };

int main(){
    cin>>n;
    cout<<a[n]+b[n];
}


打赏 赞(0)
微信二维码图片

微信扫描二维码打赏

发表评论

电子邮件地址不会被公开。

Scroll Up