目录

1010 Bragging Dice

题目

​ 两个人玩明牌的 “吹牛骰子” 游戏，求先手和后手谁赢。 一个人投出的点数全部不同时，视为没有点数。

分析

​ 只有当一个塞子都没有的情况下后手必胜，否则先手必胜

代码

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

int n;
int a[10],b[10];

int main(){
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		int x;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		bool flag1,flag2;
		flag1=flag2=1;
		for(int i=1;i<=n;i++) {
            scanf("%d",&x);
            if(a[x]) flag1=0;
            a[x]++;
		}
		for(int i=1;i<=n;i++) {
            scanf("%d",&x);
            if(b[x]) flag2=0;
            b[x]++;
		}
		if(flag1&&flag2) printf("Just a game of chance.\n");
		else printf("Win!\n");
	}
    return 0;
}

1012 Buy Figurines

题目

​ n个人m个窗口买手办，每个人有对应到的时间和花费的时间，问最后一个人离开的时间。

分析

​ 模拟题。利用两个优先队列，一个维护队列第一个人离开时间，一个维护每个队列的人数。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e3+7;
const int N=2e5+10,M=5e5+5;

int n,m;
struct node {
    ll t; int id;
    bool operator<(const node &b) const {
        if(t==b.t) return id>b.id;
        return t>b.t;
    }
};

struct person {
    int x,y;
    bool operator<(const person &b) const {
        return x<b.x;
    }
}p[N];

struct seg{
    int x,id;
    bool operator<(const seg &b) const {
        if(x==b.x) return id>b.id;
        return x>b.x;
    }
};

long long te[N]; //每个队第一个离开时间
queue<int> q[N];

int main(){
    // freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;
    scanf("%d",&T);
    while(T--) {
        memset(te,0,sizeof(te));
        priority_queue<node> heapa;
        priority_queue<seg> heapb;
        scanf("%d%d",&n,&m);
        int x,y;
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&x,&y);
            p[i]={x,y};
        }
        sort(p+1,p+n+1);
        for(int i=1;i<=m;i++) {
            heapb.push({0,i});
        }
        for(int i=1;i<=n;i++) {
            while(heapa.size()) {  // 出队
                int id=heapa.top().id;
                if(te[id]<=p[i].x) {
                    q[id].pop();
                    while(q[id].size()) {
                        if(te[id]+q[id].front()<=p[i].x) {
                            te[id]+=q[id].front();
                            q[id].pop();
                        } else {
                            te[id]+=q[id].front();
                            break;
                        }
                    }
                    heapa.pop();
                    if(q[id].size()) {
                        heapa.push({te[id],id});
                    }
                    heapb.push({q[id].size(),id});
                } else break;
            }

            // 入队
            seg que=heapb.top(); heapb.pop();
            while(q[que.id].size()!=que.x) { // 过时信息
                 que=heapb.top(); heapb.pop();
            }
            int id=que.id;
            //printf("i=%d id=%d\n",i,id);
            if(q[id].size()==0) { // 队伍为空
                te[id]=p[i].x+p[i].y;
                heapa.push({te[id],id});
            }
            q[id].push(p[i].y);
            heapb.push({q[id].size(),id});
        }

        ll ans=0;
        for(int i=1;i<=m;i++) {
            if(q[i].size()) q[i].pop();
            while(q[i].size()) {
                te[i]+=q[i].front();
                q[i].pop();
            }
            ans=max(ans,te[i]);
        }
       printf("%lld\n",ans);
    }
    return 0;
}

1003 Slipper

题目

​ 给定一棵树和树上边权，每次可以走树上的边，也可以花费 p 的代价向上或向下跳 k层。求点 s到点 t 的最短路。

分析

​ 在建立树的基础上，对于相差k层的节点建立权值为p的边，可以给同一层建立公共的节点，减少边的数量。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e3+7;
const int N=4e6+10,M=5e5+5;

int n,k,p,s,t;
int h[N],ver[N],ne[N],e[N],tot=0;
int dep[N],st[N],maxDep=0;
ll dis[N];

void add(int x,int y,int z) {
    ver[++tot]=y; ne[tot]=h[x];
    e[tot]=z; h[x]=tot;
}

void dfs(int x,int fa) {
    dep[x]=dep[fa]+1;
    maxDep=max(maxDep,dep[x]);
    for(int i=h[x];~i;i=ne[i]) {
        int y=ver[i];
        if(y==fa) continue;
        dfs(y,x);
    }
}

void dijkstra() {
    memset(dis,0x3f,sizeof(dis));
    memset(st,0,sizeof(st));
    priority_queue<PII> q;
    dis[s]=0; q.push({0,s});
    while(q.size()) {
        int x=q.top().second; q.pop();
        if(st[x]) continue;
        st[x]=true;
        for(int i=h[x];~i;i=ne[i]) {
            int y=ver[i],z=e[i];
            if(dis[y]>dis[x]+z) {
                dis[y]=dis[x]+z;
                q.push({-dis[y],y});
            }
        }
    }
}

int main() {
    freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;
    scanf("%d",&T);
    while(T--) {
        tot=0; memset(h,-1,sizeof(h));
        scanf("%d",&n);
        int u,v,w;
        for(int i=2;i<=n;i++) {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w); add(v,u,w);
        }
        scanf("%d%d",&k,&p);
        scanf("%d%d",&s,&t);
        dep[0]=-1;
        dfs(1,0);
        for (int i = 1; i <= n; ++i) {
            //printf("dep=%d\n",dep[i]);
            if (dep[i] != 0)
                add(n + 2 * dep[i] - 1, i, p);
            if (dep[i] != maxDep)
                add(n + 2 * (dep[i] + 1), i, p);
            if (dep[i] + k <= maxDep)
                add(i, n + 2 * (dep[i] + k) - 1, 0);
            if (dep[i] - k >= 0)
                add(i, n + 2 * (dep[i] - k + 1), 0);
        }
        dijkstra();
        printf("%lld\n",dis[t]);
    }
    return 0;
}