英语课

题目背景

声明：本题目中出现的人物与现实中人物无任何联系。

题目描述

你的英语老师 CHY 采用一种独特的课堂提问方式。每次英语课时，她将先指定一名同学开始提问，此后的每个提问对象都由上一名被提问的同学指定。

由于被提问是令人不高兴的事情，当一名同学被提问时（被老师提问除外），他会对选择他提问的同学产生一定的仇恨度，同时选择提问他的同学对他会减少相同的仇恨度。具体来说，同学编号为从 $1$ 到 $n$ ，当同学 $a$ 选择下一个提问同学 $b$ 时， $b$ 对 $a$ 将增加 $a \oplus b$ 的仇恨度，同时 $a$ 对 $b$ 将减少 $a \oplus b$ 的仇恨度，其中 $“\oplus”$ 表示按位异或运算。

英语老师也考虑到了仇恨的问题，因此她规定从第二个被提问的同学开始，每个同学都不能提问上一个被提问的同学，但并不阻止经过一系列提问后再回到某个提问过的同学。

经过了不知道多少次的提问与被提问，几乎所有同学之间都有着不同程度的仇恨。你班级里的每个同学都绝对理智，每个人都会在尽可能避免自己被再次提问（或尽可能延长到下次被提问的时间）的前提下，优先提问自己最仇恨的同学。

身为英语课代表的 BabyFalse 非常好奇，如果下一节英语课英语老师第 $1$ 次提问每个同学都分别会发生什么。他线下调查了每个同学之间的仇恨关系，希望你来完成预测工作。不过，他没有直接把调查结果给你，而是一条一条地将仇恨关系告诉你，并且随时可能询问你在当前状态下如果第 $1$ 个提问某位同学，那么第 $k$ 个被提问的同学将会是谁，仇恨关系未知时默认双方的仇恨度均为 $0$ ，给出的仇恨度可能是负数。

输入格式

输入的第一行包含两个正整数 $n,m$ ，分别表示班上的同学数和仇恨关系的条数。

接下来 $m$ 行，每行格式为以下两种之一：

四个整数 $1,a,b,c$ ，表示同学 $a$ 对同学 $b$ 有着 $c$ 的仇恨度。

三个整数 $2,x,k$ ，表示询问只考虑目前给出的仇恨关系时，若第一个提问同学 $x$ ，第 $k$ 个被提问的同学的编号。

输出格式

对于每个询问，输出一行一个整数，表示答案。

样例 #1

样例输入 #1

样例输出 #1

0 1 2 3

提示

对于"尽可能避免自己被再次提问（或尽可能延长到下次被提问的时间）"，计算到第 $k$ 个被提问的同学截止。

【数据范围】

对于所有测试数据，保证不会给出两条仇恨者与被仇恨者都相同的仇恨关系。

示例代码

并没有想出什么比较好的解法，就写了个暴力。欢迎大家提供更好的解法！

#include<bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    // freopen("xiao_xiao_yu.in","r",stdin);

    LL n,m,q;
    cin>>n>>m;
    vector<vector<LL>>stu(n,vector<LL>(n,0));//仇恨度
    while(m--){
        LL opt;
        cin>>opt;
        if(opt==1){
            LL a,b,c;
            cin>>a>>b>>c;
            stu[a][b]=c;
        }else if(opt==2){
            LL x,k;
            cin>>x>>k;
            function<pair<LL,vector<LL>>(LL,LL,LL)>dfs=
                [&](LL node/*当前节点*/,LL now/*搜索深度*/,LL father/*上一个节点*/)->pair<LL,vector<LL>>{ 
                //pair<LL,vector<LL>>:ans,time
                if(now>=k){ //当到达最后一层(即搜到答案)
                    return {node,vector<LL>(n,LONG_LONG_MAX/2)/*从这个节点到任何节点的时间都是INF*/};
                }
                LL minest=-1;//下一个最佳抽问人
                LL minestnum=0;//最后一个被抽问的(即ans)
                vector<LL> minesttime;//如果选择下一个抽问人到达每一个节点的时间
                LL minestcnm=LONG_LONG_MIN;//仇恨度
                for(LL i=0;i<n;i++){
                    if(i==father||node==i){//抽问上一位和自己无效
                        continue;
                    }
                    //加上仇恨度
                    stu[node][i]-=node^i;
                    stu[i][node]+=node^i;
                    pair<LL,vector<LL>>p=dfs(i,now+1,node);
                    //还原仇恨度
                    stu[node][i]+=node^i;
                    stu[i][node]-=node^i;
                    if(minest==-1||p.second[node]>minesttime[node]){//当接下来抽到自己的时间要小于"最佳抽问人"时，换人
                        minest=i;
                        minestnum=p.first;
                        minesttime=p.second;
                        minestcnm=stu[node][i];
                    }
                    else if(p.second[node]==minesttime[node]){//如果相等
                        if(stu[node][i]>minestcnm){//比较仇恨度
                            minest=i;
                            minestnum=p.first;
                            minesttime=p.second;
                            minestcnm=stu[node][i];
                        }
                    }
                }
                minesttime[minest]=min(minesttime[minest],now);//更新到达自己的时间
                return {minestnum,minesttime};
            };
            cout<<dfs(x,1,-1).first<<endl;
        }
    }
    return 0;
}

本文作者：tsxc

本文链接：https://tsxc-github.github.io/posts/5bcef9d8/

版权声明：本博客中所有文章除特别声明外，均不允许转载。此外的的转载文章，请按原作者要求转载。

最后更新：2023-11-26, 10:48

By tsxc.

随机文章回味旧文

edge居然给localhost开HSTS！！！

博客信息

文章数目

6