2022“杭电杯”中国大学生算法设计超级联赛（5）

Bragging Dice

 两个人掷骰子，两人都知道对方手中和自己手中的牌数，现在有两种操作，一种是挑战，即打开盖子，看是否是前一人说的那样；另一种是声称，即给出判断，类似有x个y点的骰子这样的说法。给出两人手中的牌，判断谁会赢。

思路：很坑人的签到题。因为声称是有要求的每次要么x大于上一个x，y是任意的；要么x等于前一个x，y大于上一个y。这样其实先手有策略控制claim的次数，即先手最大化x和y，这样使得后手无法接着claim，先手必赢。

AC Code：

#include 
 
typedef long long ll;
const int N=15;
int t,n,x;
int a[N],b[N];
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		for(int i=1;i<=n;i++){
			std::cin>>x;
			a[x]++;
		}
		for(int i=1;i<=n;i++){
			std::cin>>x;
			b[x]++;
		}
		bool flag=false;
		for(int i=1;i<=6;i++){
			if(a[i]>1||b[i]>1){
				flag=true;
				break;
			}
		}
		std::cout<<(flag?"Win!":"Just a game of chance.")<<'\n';
	}
	return 0;
}

Buy Figurines

 有n个人买东西，给出n个人来的时间和需要的时间，一共有m个窗口，每个人会优先选择编号最小且人最少的窗口，问从第一个人来到最后一个人走需要多长时间。

思路：比较麻烦的模拟题。我们不仅要维护每一个队列，还要对每个人的开始时间结束时间和在哪买全都包括。如果简单的用m个队列的话会T，这里有种线段树维护的方式，线段树维护的是最适合把人放在哪个位置，用优先队列维护每个人的信息，细节见代码。

 AC Code：

#include 
 
#define int long long
typedef std::pair<int,int>PII;
const int N=2e5+5;
int t,n,m;
int leave[N];
 
struct SegmentTree{
	struct Tree{
		int l,r;
		int pos,min;
	}tr[N<<2];
	struct node{
		int sta,len;
		bool operator <(const node &a) const{
			return sta
		}
	}e[N];
	void pushup(int u){
		tr[u].min=std::min(tr[u<<1].min,tr[u<<1|1].min);
		if(tr[u<<1].min==tr[u].min) tr[u].pos=tr[u<<1].pos;
		else tr[u].pos=tr[u<<1|1].pos;
	}
	void build(int u,int l,int r){
		tr[u]={l,r,l,0};
		if(l==r) return;
		else{
			int mid=l+r>>1;
			build(u<<1,l,mid);
			build(u<<1|1,mid+1,r);
			pushup(u);
		}
	}
	void modify(int u,int x,int v){
		if(x==tr[u].l&&x==tr[u].r) tr[u].min+=v;
		else{
			int mid=tr[u].l+tr[u].r>>1;
			if(x<=mid) modify(u<<1,x,v);
			if(x>mid) modify(u<<1|1,x,v);
			pushup(u);
		}
	}
}ST;
 
signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n>>m;
		for(int i=1;i<=n;i++){
			int a,b;
			std::cin>>a>>b;
			ST.e[i]={a,b};
		}
		for(int i=1;i<=m;i++){
			leave[i]=0;
		}
		ST.build(1,1,m);
		std::priority_queue,std::greater>pq;
		std::sort(ST.e+1,ST.e+1+n);
		int ans=0;
		for(int i=1;i<=n;i++){
			while(!pq.empty()&&pq.top().first<=ST.e[i].sta){
				ST.modify(1,pq.top().second,-1);
				pq.pop();
			}
			int pos=ST.tr[1].pos;
			ST.modify(1,pos,1);
			leave[pos]=std::max(ST.e[i].sta,leave[pos])+ST.e[i].len;
			pq.push({leave[pos],pos});
			ans=std::max(leave[pos],ans);
		}
		std::cout<'\n';
	}
	return 0;
}

 os：线段树yyds！！！

Slipper

 给出一棵树，每一条边之间有权值，也可以花费p传送到距离k层的位置，求最短路。

思路：主要问题是如何建图和如何解决数据范围较大的问题。如果在每一个相距k层的点之间建边，n^2肯定不可行，考虑两层之间新建一层，入度边权为0，出度为p，解决了建边问题之后直接跑Dijkstra求最短路即可。

AC Code;

#include 
 
typedef long long ll;
typedef std::pairint>PII;
#define INF 0x3f3f3f3f
const int N=4e6+5;
int t,n,k,p,S,T,cnt;
int e[N<<1],next[N<<1],w[N<<1],deep[N],head[N];
ll dis[N];
std::vector<int>v[N];
bool vis[N];
 
void add_edge(int u,int v,int x){
	e[cnt]=v;
	w[cnt]=x;
	next[cnt]=head[u];
	head[u]=cnt++;
}
 
void DFS(int u,int fa){
	deep[u]=deep[fa]+1;
	v[deep[u]].push_back(u);
	for(int i=head[u];~i;i=next[i]){
		int j=e[i];
		if(j==fa) continue;
		DFS(j,u);
	}
}
 
void Dijkstra(){
	std::priority_queue,std::greater>pq;
	memset(dis,INF,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[S]=0;
	pq.push({dis[S],S});
	while(!pq.empty()){
		auto tt=pq.top();
		pq.pop();
		int now=tt.second;
		if(vis[now]) continue;
		vis[now]=true;
		for(int i=head[now];~i;i=next[i]){
			int u=e[i];
			if(dis[u]>dis[now]+w[i]){
				dis[u]=dis[now]+w[i];
				pq.push({dis[u],u});
			}
		}
	}
}
 
signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		memset(head,-1,sizeof(head));
		cnt=0;
		std::cin>>n;
		for(int i=1;i<=n;i++){
			v[i].clear();
		}
		for(int i=1;i
			int a,b,c;
			std::cin>>a>>b>>c;
			add_edge(a,b,c);
			add_edge(b,a,c);
		}
		std::cin>>k>>p>>S>>T;
		DFS(1,0);
		for(int i=1;i<=n;i++){
			for(auto u:v[i]){
				add_edge(u,i+n*2,0);
				add_edge(i+n,u,0);
			}
			if(i-k>0) add_edge(i+n*2,i-k+n,p);
			if(i+k<=n) add_edge(i+n*2,i+k+n,p);
		}
		Dijkstra();
		std::cout<'\n';
	}
	return 0;
}

os：感觉这个题和之前在kuangbin专题做的最短路难度挺相似的，，好像还有一个题和这个idea解题的差不多，只不过弱队签到都要搞好久，，

下一个NTT啊，没学，跑路！