赛后——2.22 寒假模拟12
\(\text{T1 Letters}\)
题意
对于给出的 \(n\) 个单词，求有多少个（这 \(n\) 个单词的）子集 \(s\) 使得 \(26\) 个英文字符中的每个字符都在 \(s\) 中的某个单词中出现过了。
数据范围：\(n\le 25\)
思路
\(n\) 很小可以暴搜，预处理出来每个单词的字符包含情况，状态压成一位存储，接着我们只需要判断最终的状态是否为 \(2^{26}-1\) 的即可。
考虑优化，因为存在一些单词是必选的，它们拥有独一无二的字符，于是可以将它们在输入时找出，于是搜索时就不考虑单词的选取情况了。
代码
点击查看代码
int n;
char s[30][105];
vector G[30];
int sit[105],vis[105];
int S,ans;
#define cr (1<<26)-1
inline void dfs(int x,int st){
if(x>n){
if(st==cr) ans++;
return;
}
int tmp=x+1;
while(vis[tmp]&&tmp<=n) tmp++;
if(!x) dfs(tmp,S);
else{
dfs(tmp,st);
dfs(tmp,st|sit[x]);
}
}
int main(){
n=read();
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
}
for(int i=1;i<=n;i++){
int len=strlen(s[i]+1);
for(int j=1;j<=len;j++){
G[s[i][j]-'a'+1].push_back(i);
sit[i]|=(1<<(s[i][j]-'a'));
}
}
for(int i=1;i<=26;i++){
if(G[i].size()==0){
printf("0\n");
return 0;
}
if(G[i].size()==1){
S|=sit[G[i][0]];
vis[G[i][0]]=1;
}
}
dfs(0,0);
printf("%d\n",ans);
return 0;
}
\(\text{T2 Circle}\)
题意
平面上有一些圆，第 \(i\) 个圆的坐标为 \((x_i,0)\)，半径为 \(r_i\)。求这些圆把平面化分成了多少块区域（最外面的也算）。
保证任意两圆不相交，但可以相切。
思路
不难发现，每个圆把包含它的大圆分成了内外两部分（最外面可以视作一个无穷大的圆），于是如果没有相切情况，答案为 \(n+1\)。
接着，对于若干个小圆相接拦断一个大圆（即相切）的情况，答案为 \(+1\)，我们需要统计这种情况的个数。
首先对所有圆进行排序，令每个圆的右端点，即 \(x_i+r_i\) 为第一关键字升序排序，令每个圆的半径 \(r_i\) 为第二关键字升序排序，这样我们会发现，右端点在小圆右侧或半径大于小圆的圆都排在了小圆的后面，换句话说，就是枚举到小圆之前，已经枚举了小圆内部所有的圆，发现当计算完这个小圆后，其内部的圆就已经对后续的答案没有影响了，可以统一合并成这个小圆了。
用单调栈来维护，每次把所有小圆内部的圆都弹栈并累计半径和，如果半径和等于小圆半径，说明出现了“拦腰截断”的情况，答案 \(+1\)。
代码
点击查看代码
int n;
struct node{
int x,r,lpos,rpos;
bool operator <(const node &rhs)const{
if(rpos==rhs.rpos) return r s;
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i].x=read(),a[i].r=read();
a[i].lpos=a[i].x-a[i].r;
a[i].rpos=a[i].x+a[i].r;
}
ans=n+1;
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
int sum=0;
while(!s.empty()&&a[s.top()].lpos>=a[i].lpos&&a[s.top()].rpos<=a[i].rpos){
sum+=a[s.top()].r;
s.pop();
}
s.push(i);
if(sum==a[i].r){
ans++;
}
}
printf("%d\n",ans);
return 0;
}
\(\text{T3 Bag}\)
题意
有 \(n\) 个物品，第 \(i\) 个物品的价值为 \(w_i\)，重量为 \(c_i\)，有 \(k\) 个背包，第 \(i\) 个背包里的容量为 \(v_i\)，每个背包只能装一件物品，求能装走的最大价值。
思路
因为每个背包只能有装一件物品，于是贪心，弄一个 \(\text{multiset}\) 来维护背包接着二分一下就可以了。
代码
点击查看代码
int n,k;
struct node{
ll c,w;
bool operator <(const node &rhs)const{
if(w==rhs.w) return crhs.w;
}
}a[maxn];
multiset s;
ll ans,cnt;
int main(){
n=read(),k=read();
for(int i=1;i<=n;i++){
a[i].c=read(),a[i].w=read();
}
for(int i=1;i<=k;i++){
ll v=read();
s.insert(v);
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
multiset::iterator it=s.lower_bound(a[i].c);
if(it!=s.end()){
s.erase(it);
ans+=a[i].w;
cnt++;
}
if(cnt==k){
printf("%lld\n",ans);
return 0;
}
}
printf("%lld\n",ans);
return 0;
}
\(\text{T4 Forest}\)
题意
有一只猴在树林间蹦跶。
森林里有 \(n\) 棵树，第 \(i\) 棵树的高度是 \(E_i\)有 \(m\) 条蹦跶的路径，从第 \(A_i\) 棵树蹦跶到第 \(B_i\) 棵树花费 \(T_i\) 的时间。
当它从高度为 \(s\) 的位置蹦跶到另一棵树上且花费了 \(t\) 的时间后，他会梦到到目标树上高度为 \(s-t\) 的位置，\(s-t\) 不能为负，也不能超过目标树的高度。
它可以花一单位时间爬上一单位高度或者爬下一单位高度。
它初始在第 \(1\) 棵树，高度为 \(X\)，问它到达第 \(n\) 棵树的顶部所需的最少时间。
思路
首先是 \(40%\) 的部分分直接跑最短路，结果乘上 \(2\) 再加上 \(E_n\) 即可。
接着我们发现，走过一条消耗 \(t\) 的路径时，就会下降 \(t\) 个单位高度，不妨把所有消耗都变成纵向的高度，于是我们每次跳跃有两种选择，选择直接跳过去或者是需要向下一点直到能跳到下一棵树的树顶，当然需要特判出来树高小于路径长的情况。
于是我们维护出的，实际上是全部转移成纵向高度后下降到的位置，用最短路算法可以得出这个 \(dis_n\)，发现这时题目就变成了从 \(x\) 走到 \(dis_n\) 的高度（其实是走到了第 \(n\) 棵树的底下），接着向上走到树顶。
于是答案为：\(X-dis_n+E_n-dis_n\)。
我们再用图解释一下，正常路线是红色路线，平移一下可以得到蓝色路线，因为这条蓝色路线中斜方向的长度是等于任意一条绿色路线的，而绿色路线是 \(X-dis_n\)，蓝色路线竖直方向的长是 \(E_n-dis_n\)，于是答案：\(X-dis_n+E_n-dis_n\)。
代码
点击查看代码
int n,m;
ll x,e[maxn];
vector E[maxn];
struct node{
int u,d;
bool operator<(const node &rhs)const{
return d q;
tmp.u=1,tmp.d=x;
q.push(tmp);
while(!q.empty()){
tmp=q.top();
q.pop();
int u=tmp.u,d=tmp.d;
if(dis[u]!=-llinf) continue;
dis[u]=d;
for(int i=0;ie[u]) continue;
tmp.u=v,tmp.d=min(d-w,e[v]);
q.push(tmp);
}
}
}
int main(){
n=read(),m=read(),x=read();
for(int i=1;i<=n;i++){
e[i]=read();
}
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
E[u].push_back(make_pair(v,w));
E[v].push_back(make_pair(u,w));
}
Dijkstra();
if(dis[n]==-llinf){
printf("-1\n");
}
else{
printf("%lld\n",x-dis[n]+e[n]-dis[n]);
}
return 0;
}