csp-201609

2020-08-29

20160901（最大波动）

代码1

//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005

int n;
int prices[MAXN];

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    for(int i=0;i<n;i++) cin>>prices[i];
    int diff = INT_MIN;
    for(int i=0;i<n-1;i++){
        diff = max(diff,abs(prices[i+1]-prices[i]));
    }
    cout<<diff;
}

20160902（火车购票）

代码1

用bool seats[20][6] 来描述每个座位号是否被占，seats[][0] 表示每一排被占了几个座位。对于购票请求，先看有没有一排的空座位数大于等于购票数（空座位数一定连续），否则，就从最小的座位号开始分配。

//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int seats[20][6];
int n;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    memset(seats,0,120);

    while(n--){
        int num;
        cin>>num;
        bool flag = false;
        for(int i=0;i<20;i++){
            if(5-seats[i][0]>=num){
                flag = true;
                for(int j=seats[i][0]+1;j<seats[i][0]+1+num;j++){
                    seats[i][j] = 1;
                    if(j == seats[i][0]+1) cout<<i*5+j;
                    else cout<<" "<<i*5+j;
                }
                cout<<endl;
                seats[i][0] += num;
                break;
            }
        }
        int cnt = 0;
        if(!flag){
            for(int i=0;i<20&&cnt<num;i++){
                for(int j=1;j<=5&&cnt<num;j++){
                    if(seats[i][j] == 0){
                        seats[i][j] = 1;
                        if(cnt==0) cout<<i*5+j;
                        else cout<<" "<<i*5+j;
                        cnt++;
                        seats[i][0]++;
                    }
                }
            }
            cout<<endl;
        }
    }
}

20160903（炉石传说）

代码1

设计一个结构体表示每一方的战斗力，包括英雄和随从的情况，以及是否输掉；

struct Player{
    int health; //30
    int attacks[8]; //[1,7]使用
    int healths[8]; //[1,7]使用
};

有Player players[2] 表示两个玩家，players[0] 表示先手玩家。int playerId=0 表示当前的玩家id，一旦遇到end命令，就将playerId变为对手的。

//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

struct Player{
    int health; //30
    int attacks[8]; //[1,7]使用
    int healths[8]; //[1,7]使用
    Player(){
        health = 30;
        memset(attacks,-1,sizeof(attacks));
        memset(healths,-1,sizeof(healths));
    }
};
int n;
Player players[2];
int playerId=0;

//当playerId的arg1号随从被攻击后，检查是否需要移动
void postAttack(int playerId, int arg1){
    if(players[playerId].healths[arg1]<=0){
        int j = arg1 + 1;
        while(j<8){
            players[playerId].healths[j-1] = players[playerId].healths[j];
            players[playerId].attacks[j-1] = players[playerId].attacks[j];
            j++;
        }
        players[playerId].healths[j-1] = -1;
        players[playerId].attacks[j-1] = -1;
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    //init
    players[0] = players[1] = Player();

    cin>>n;
    string op;
    int arg1,arg2,arg3;
    for(int i=0;i<n;i++){
        cin>>op;
        if(op == "summon"){
            cin>>arg1>>arg2>>arg3;
            int attack1=arg2,attack2,health1=arg3,health2;
            int j = arg1;
            do{
                attack2 = players[playerId].attacks[j];
                health2 = players[playerId].healths[j];
                players[playerId].attacks[j] = attack1;
                players[playerId].healths[j] = health1;
                attack1 = attack2;
                health1 = health2;
                j++;
            }while(j<8);
        }else if(op == "attack"){
            cin>>arg1>>arg2;
            if(arg2 != 0){
                players[playerId].healths[arg1] -= players[playerId^1].attacks[arg2];
            }
            if(arg2 == 0){
                players[playerId^1].health -= players[playerId].attacks[arg1];
                postAttack(playerId,arg1);
                if(players[playerId^1].health<=0) break;
            }else{
                players[playerId^1].healths[arg2] -= players[playerId].attacks[arg1];
                postAttack(playerId,arg1);
                postAttack(playerId^1,arg2);
            }
        }else{
            playerId = playerId^1;
        }
    }
    //output
    if(players[0].health <= 0){
        cout<<"-1"<<endl;
    }else if(players[1].health<=0){
        cout<<"1"<<endl;
    }else{
        cout<<"0"<<endl;
    }
    for(int i=0;i<2;i++){
        cout<<players[i].health<<endl;
        int num = 0;
        for(int j=1;j<=7;j++){
            if(players[i].healths[j]!=-1){
                num++;
            }
        }
        cout<<num;
        for(int j=1;j<=7;j++){
            if(players[i].healths[j]!=-1){
                cout<<" "<<players[i].healths[j];
            }
        }
        cout<<endl;
    }
}

这题我做的有很大问题，可能会出现巨大错误。原因是56行到69行的对postAttack函数放在哪个位置进行处理这个问题变得很糊涂，也犯了很多逻辑错误。正常的做法是，我要将双方的角色生命值都减去后再进行双发角色的postAttack操作（也就是对随从的位置移动操作），还要注意，当攻击对方的英雄时，也就是，arg2=0时，不要对对方进行postAttack操作，因为，我会把[1,7] 位置的数据全部移动到[0,6]位置，这是个很严重的错误。

20160904（交通规划）

代码1

这题是使用dijkstra算法，但是不同的是，每次在选出一个u点时，都要从它的所有最短路径前驱路径点a中，选出使得<a,u> 最小的那个a。因此有set<int> pre[] 来存储最短的<a,u> 的距离。然后将<a,u>累加到结果ans中。

//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10005
#define INF 1e9

struct Node{
    int v,w;
};
int n,m;
vector<Node> graph[MAXN];
long long ans = 0;

int pre[MAXN];
int vis[MAXN];
long long dist[MAXN];
void Dijkstra(){
    //init
    memset(vis,0,sizeof(vis));
    for(int i=0;i<MAXN;i++){
        dist[i]=1e18;
        pre[i] = INF;
    }
    dist[1] = 0;
    pre[1] = 0;

    for(int i=0;i<n;i++){
        int u=-1;
        long long minDist = 1e18;
        for(int j=1;j<=n;j++){
            //cout<<dist[j]<<endl;//////
            if(!vis[j] && dist[j]<minDist){
                minDist = dist[j];
                u = j;
            }
        }
        if(u==-1) break;
        vis[u] = 1;
        ans += pre[u];
        for(int j=0;j<graph[u].size();j++){
            int v=graph[u][j].v, w=graph[u][j].w;
            if(!vis[v]){
                if(dist[u]+w < dist[v]){
                    dist[v] = dist[u]+w; //error: dist[j]
                    pre[v] = w;
                }else if(dist[u]+w == dist[v]){
                    pre[v] = min(pre[v],w);
                }
            }
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    int a,b,c;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }
    Dijkstra();
    cout<<ans;
}

最近总是犯小错误，像45行的错误：把v错当成j，真的太低级了；第5行，我想写10005的，结果写成了1005，报了运行错误。