Bragging Dice

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

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

AC Code：

#include <bits/stdc++.h>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 <bits/stdc++.h>#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<a.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<PII,std::vector<PII>,std::greater<PII>>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<<ans<<'\n';}return 0;
}

 os：线段树yyds！！！

Slipper

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

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

AC Code;

#include <bits/stdc++.h>typedef long long ll;
typedef std::pair<ll,int>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<PII,std::vector<PII>,std::greater<PII>>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<n;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<<dis[T]<<'\n';}return 0;
}

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

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