今天的题目看完思路以后感觉不是很难，但是我为什么空着三道题呢？没事，我是蒟蒻我有理
1 Jumping on the walls(签到题){
-
题意：有两个长度为n的墙，你可以操控你的忍者朋友在其中穿梭，当你在一堵墙上时，你可以选择上下移动，如果你选择跳到另一堵墙上，那么你将向上跳动k个距离，但前提是不能落在字符为X的下标上，且每隔一秒都会有水涨上一米，你如何保证不淹没水中且能够成功跃出墙
-
思路：看到这样的一道题，我首先想到了双指针，（于是便尝试），但直觉告诉我们要以图论方面的视角来看待这道题。首先我们可以将初始节点x,y入对，也就是所谓的右下角，然后再模拟一个移动数组d[3]={1,-1,cur.t+k}(这里分别对应上移，下移和跳跃)，每次当遇到X时跳过，被水赶上时跳过，只要最后能到达n就输出Yes否则输出No
-
算法：单源BFS
}
核心代码：
for(int i=0;i<3;i++){
int nx=(i==2)?1-cur.x:cur.x;//跳墙
int ny=cur.y+d[i];//上下移动
int nt=cur.t+1;//更新水涨
if(ny>=n){
return true;
}
if(ny<0||ny<nt) continue;
if(vis[nx][ny]) continue;
if(wall[nx][ny]=='X') continue;//不能待跳过
vis[nx][ny]=true;//标记已来过
q.push({nx,ny,nt});
}
}
2 Igor and his way to work{
-
题意：有一张图，其中给定起点和终点，我们需要在这其中找到一条路线，使得到达终点的转向次数不超过2次，且不经过沿途的障碍路段，求是否能找到
-
思路：看到这种题目就是个裸的BFS，但直觉告诉我们不能用正常眼光看待这道题（本人WA就WA在这里）。因为我们不仅要考虑避开其中的障碍，还要兼顾其中的转向次数，因此这里我们在原始bfS的标记数组内添加维度：vis[N][N][4][4]。添加转向次数和方向。初始时，vis[sx][sy][i][0]四个方向都设置为可执行，之后如果遇到了不同的方向，次数加1，如果超过了限定次数直接跳过，如果最终到达了终点则输出答案
3，算法：单源BFS，多维数组
}
核心代码：
while(!q.empty()){
st cur=q.front();
q.pop();
if(cur.turn>2) continue;
for(int i=0;i<4;i++){
int nx=dx[i]+cur.x;
int ny=dy[i]+cur.y;
int nturn=(i==cur.dir?0:1)+cur.turn;
if(f(nx,ny)&&!vis[nx][ny][i][nturn]&&mp[nx][ny]!='*'){//在合法范围内，且可以走
vis[nx][ny][i][nturn]=1;
q.push({nx,ny,i,nturn});
}
}
}
for(int i=0;i<4;i++){
if(vis[t1][t2][i][0]||vis[t1][t2][i][1]||vis[t1][t2][i][2]) return true;
}
3 Rudolf and CodeVid{
-
题意：有一个初始01串，每个1表示患有的病，其中还有n种不同药物，每个药物都有其对应的两个01串，第一个表示可治疗的1，第二个表示会重新患上的1，每种药物都有其对应的天数代价，求最终是否能得到一个全0串，能则输出最小天数代价，不能输出-1
-
思路：看到01串我们想到什么？老朋友位运算。但是这题并不只是位运算这么简单。首先对于每种药物的正作用，我们可以让它和原先初始状态进行取反位与从而达到消除原先的双1位置，然后再和副作用进行位或来添加1的位置，因此我们可以推出状态公式：mask=mask&(~(a[i]))|b[i]。状态我们已经得到了，那最小天数代价怎么办？作为初学者的我自然是没想到，但是经过点播，我们可以将每个药带来的新状态作为图的节点，一种状态到另一种状态的天数代价为边权，这样我们就能得到一张图，而这时针对最小代价的球法就只需要一个裸的dj算法即可解决
}
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int main() {
int t;
cin>>t;
while (t--) {
int n, m;
cin >> n >> m;
string s;
cin >> s;
int start=0;
for (int i=0;i<n;i++) {
if (s[i]=='1') start|=(1<<(n-1-i));//初始值
}
vector<int> day(m), cure(m), side(m);
for (int i=0;i<m;i++) {
cin >> day[i];
string a, b; cin >> a >> b;
for (int j=0;j<n;j++) {
if (a[j]=='1') cure[i]|=(1<<(n-1-j));//初始化每个药的正负作用
if (b[j]=='1') side[i]|=(1<<(n-1-j));
}
}
vector<int> dist(1<<n,INF);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
dist[start]=0; pq.push({0, start});
while (!pq.empty()) {
auto [d,mask]=pq.top(); pq.pop();
if (d!=dist[mask]) continue;
if (mask==0) break;
for (int i=0;i<m;i++) {
int nxt=(mask&(~cure[i]))|side[i];//合并状态
if (dist[nxt]>d+day[i]) {//更新最小代价
dist[nxt]=d+day[i];
pq.push({dist[nxt],nxt});
}
}
}
cout<<(dist[0]==INF?-1:dist[0])<<endl;
}
}
4 Mad City{
-
题意：有一张n条边n个节点的无向图，保证图中没有重边，有两个人在互相进行追捕，一人逃，一人追，求逃跑者是否能永远不被追捕者追上，输出YES,NO
-
思路：因为逃跑者可以预判追捕者的行为，因此我们只需要找出图中的环即可。但这题的关键并不是只找到环那么简单。因为这两人都有各自的初始点，因此我们还需要知道两个人谁最先到达环。所以我们先用拓扑序列找环，再用BFS算出逃跑者和追捕者距离环中第一个点的距离，只要逃跑者的len<追捕者的len，一定输出YES,否则输出NO
-
算法：基环树，拓扑排序
}
两个关键部分：
1算距离：
void bfs(int s, vector<int>& dis) {
dis.assign(n+1,-1);
queue<int> q;
q.push(s);
dis[s]=0;
while (!q.empty()) {
int u=q.front(); q.pop();
for (int v:g[u]) {
if (dis[v]==-1) {
dis[v]=dis[u] + 1;
q.push(v);
}
}
}
}
2 找环：
while (!q.empty()) {
int u=q.front();
q.pop();
for (int v:g[u]){
if (--deg[v]==1) q.push(v);
}
}
5 Colored Portals(没AC,调不动了){
-
题意：有n个城市，他们彼此之间可以通过一些有相同颜色的传送门进行传送， 现在给出每个城市拥有的传送门颜色，并且有q次询问，求两个城市n,m之间互相抵达的最小代价：|i-j|
-
思路：（由于这题还没AC,这里只给部分分思路）这题显然不能直接用字符串去判断两个城市间是否能实现相互抵达，我们可以将颜色字符串进行赋值，然后再判断两个城市间是否有相同的数值。但光有这些还不够，我们需要求最小代价，因此我们需要给城市颜色出现的顺序进行set排序，然后枚举0到5这六种颜色，找到第一个不小于x的颜色顺序，这里分三种情况：
1 it<=x(在x到y的答案区间的左边)：ans=min(ans,(x-*it)+(y-*it))
2 X<=it<=y(在答案区间的中间，最友好):ans=min(ans,y-x)
3 It>=y(在答案区间的右边):ans=min(ans,(*it-x)+(*it-y))
3.算法：二分
}
石山代码：
#include <bits/stdc++.h>
using namespace std;
map<string,int> id={
{"BG",0},{"BR",1},{"BY",2},{"GR",3},{"GY",4},{"RY",5}
};//等效替代
int color[6][2]={
{0,1},{0,2},{0,3},{1,2},{1,3},{2,3}
};
bool share(int x,int y){
return color[x][0]==color[y][0]||color[x][0]==color[y][1]||
color[x][1]==color[y][0]||color[x][1]==color[y][1];
}//判断颜色是否相同
int main(){
int t;
cin>>t;
while(t--){
int n,m;
cin >> n >> m;
vector<int> type(n+1);
vector<set<int>> l(6);
for(int i=1;i<=n;i++){
string s;
cin >> s;
type[i]=id[s];
l[type[i]].insert(i);
}
for(int i=1;i<=m;i++){
int x,y;
cin >> x >> y;
if(x==y){
cout<<0<<endl;
continue;
}
if(x>y) swap(x,y);
int tx=type[x],ty=type[y];
if(share(tx,ty)){//直接匹配
cout<<abs(x-y)<<endl;
continue;
}
int ans=INT_MAX;
for(int tp=0;tp<6;tp++){
if(tp==tx||tp==ty) continue;//重复的没必要再找一遍
auto &st=l[tp];
auto it=st.lower_bound(x);//找到第一个不小于x的位置
if(it!=st.end()&&*it<=y){//恰好在中间
ans=min(ans,y-x);
break;//已达到理论最优，可以退出
}
if(it!=st.begin()){
it--;
ans=min(ans,(x-*it)+(y-*it));//在左端，
}
if(it!=st.end()){
ans=min(ans,(*it-x)+(*it-y));//在右端
}
}
cout<<(ans==INT_MAX?-1:ans)<<endl;
}
}
}
6 Great Graphs{
-
题意：给你一张图中每个点之间的最短编辑距离，求这张图中边权之和的最小值
-
思路：这种题目首先想到的就是建图，但是不要再在写代码的时候建。题目没有要求我们输出每一条边并构造答案，因此我们只需要关心每一条边的最短编辑距离对答案的贡献即可。因此我们可以考虑直接对数组进行排序，然后用pre存储目前为止的数组内的前缀和，再算贡献值。这里要用一个数学公式推导。我们都知道，一条边的最短编辑贡献为：(d[i]-a[1])+(d[i]-a[2])+(d[i]-a[3])+...+(d[i]-a[i])，我们可以归纳为d[i]*i-pre[i]，也就是减去当前的pre,所以我们最后只要输出此时的值与d[n-1]，也就是最大边长的差值即可
}
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<long long> num(n);
long long ans=0,pre=0;
for(int i=0;i<n;i++) cin>>num[i];
sort(num.begin(),num.end());//没让我们建图，所以节点编号并不重要，重要的是最短编辑距离
for(int i=0;i<n;i++){
ans+=1LL*i*num[i]-pre;//与之前所有边构成最短距离时对答案的总贡献
pre+=num[i];//求前缀
}
cout<<num[n-1]-ans<<endl;//用最大边长减去总贡献
}
}
评论
0