2018年湘潭大学程序设计竞赛 个人笔记 题解

链接：https://ac.nowcoder.com/acm/contest/105/F
来源：牛客网
 

题目描述

小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用'#'表示，小明进入陷阱就会死亡，'.'表示没有陷阱。小明所在的位置用'S'表示，目的地用'T'表示。

小明只能向上下左右相邻的格子移动，每移动一次花费1秒。

有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵，将不会发生任何事情，小明可以继续向上下左右四个方向移动。

一个格子可能既有多个入口，又有多个出口，小明可以选择任意一个入口开启传送阵。使用传送阵是非常危险的，因为有的传送阵的出口在陷阱里，如果小明使用这样的传送阵，那他就会死亡。也有一些传送阵的入口在陷阱里，这样的传送阵是没有用的，因为小明不能活着进入。请告诉小明活着到达目的地的最短时间。

输入描述:

有多组数据。对于每组数据：
第一行有三个整数n,m,q(2≤ n,m≤300,0≤ q ≤ 1000)。
接下来是一个n行m列的矩阵，表示迷宫。
最后q行，每行四个整数x1,y1,x2,y2(0≤ x1,x2< n,0≤ y1,y2< m)，表示一个传送阵的入口在x1行y1列，出口在x2行y2列。

输出描述:

如果小明能够活着到达目的地，则输出最短时间，否则输出-1。

示例1

输入

复制

5 5 1
..S..
.....
.###.
.....
..T..
1 2 3 3
5 5 1
..S..
.....
.###.
.....
..T..
3 3 1 2
5 5 1
S.#..
..#..
###..
.....
....T
0 1 0 2
4 4 2
S#.T
.#.#
.#.#
.#.#
0 0 0 3
2 0 2 2

输出

复制

6
8
-1
3

bfs,搜索题毕竟还是搜索题，不是很难，但不知道为什么这题通过率最低qaq,感觉没什么好讲的，要处理的东西比较多，因为传送点可能会有1000个，如果走到每个点在判断它是否可以传送那么复杂度就会很大，所以我们可以预处理，用数组记录每个点可以传送到的点的位置，不能传送就-1,复杂度O(1),同时也很方便的处理了这个传送门的2个出入口是否有陷阱

#include
#include
#include
#include
using namespace std;const int MAX = 305;struct Node{int x,y,t;bool operator < (const Node &e) const{return t > e.t;//小}
};int n,m,q,x1,y1,x2,y2;
char ch[MAX][MAX];
int vis[MAX][MAX];
int s[MAX][MAX][2];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};void bfs(){priority_queue pq;pq.push({x1,y1,0});if(s[x1][y1][0]!=-1)pq.push({s[x1][y1][0],s[x1][y1][1],3});while(!pq.empty()){Node u = pq.top();pq.pop();if(u.x==x2 && u.y==y2){cout<u.t+3){pq.push({sx,sy,u.t+3});//传送vis[sx][sy] = u.t+3;}for(int i=0;i<4;i++){int x = u.x + dx[i];int y = u.y + dy[i];if(x>=0 && x=0 && yu.t+1){vis[x][y] = u.t+1;pq.push({x,y,u.t+1});}}}}cout<<-1<>n>>m>>q){memset(vis,999999,sizeof(vis));memset(s,-1,sizeof(s));for(int i=0;i>ch[i][j];if(ch[i][j]=='S')x1=i,y1=j;else if(ch[i][j]=='T')x2=i,y2=j;}for(int i=0;i>u>>v>>uu>>vv;if(ch[u][v]!='#' && ch[uu][vv]!='#'){s[u][v][0] = uu;s[u][v][1] = vv;}}bfs();}return 0;
}

G.又见斐波那契

链接：https://ac.nowcoder.com/acm/contest/105/G
来源：牛客网
 

题目描述

输入描述:

第一行是一个整数T(1 ≤ T ≤ 1000)，表示样例的个数。
以后每个样例一行，是一个整数n(1 ≤ n ≤ 1018)。

输出描述:

每个样例输出一行，一个整数，表示F(n) mod 1000000007。

示例1

输入

复制

4
1
2
3
100

输出

复制

1
16
57
558616258

看公式。

显然是矩阵快速幂，和2016沈阳一样，不过这里是i^3。

把初始矩阵弄个出来就行了（填数字游戏）

#include
#include
#include
using namespace std;typedef long long ll;
const ll mod = 1e9+7;struct Matrix{ll a[6][6];Matrix(){memset(a,0,sizeof(a));}Matrix operator * (const Matrix & rhs){Matrix res;for(int i=0;i<6;i++)for(int j=0;j<6;j++)for(int k=0;k<6;k++)res.a[i][j] = (res.a[i][j] + a[i][k]*rhs.a[k][j])%mod;return res;}
}res,G;void mpow(ll n){while(n>0){if(n%2==1)res=res*G;G=G*G;n>>=1;}
}int main(){ll T,n;scanf("%lld",&T);ll b[6][6] =  {{1,1,1,1,1,1},{1,0,0,0,0,0},{0,0,1,3,3,1},{0,0,0,1,2,1},{0,0,0,0,1,1},{0,0,0,0,0,1}};while(T--){for(int i=0;i<6;i++)for(int j=0;j<6;j++){G.a[i][j] = b[i][j];if(i==j)res.a[i][j] = 1;elseres.a[i][j] = 0;}scanf("%lld",&n);mpow(n-1);ll ans = (res.a[0][0] + 8*res.a[0][2] + 4*res.a[0][3] + 2*res.a[0][4] + res.a[0][5])%mod;printf("%lld\n",ans);}return 0;
}

H.统计颜色

链接：https://ac.nowcoder.com/acm/contest/105/H
来源：牛客网
 

题目描述

n个桶按顺序排列，我们用1~n给桶标号。有两种操作：
1 l r c 区间[l,r]中的每个桶中都放入一个颜色为c的球 (1≤l,r ≤n,l≤r,0≤c≤60)
2 l r   查询区间[l,r]的桶中有多少种不同颜色的球     (1≤l,r ≤n,l≤r)

输入描述:

有多组数据，对于每组数据：
第一行有两个整数n,m(1≤n,m≤100000)
接下来m行，代表m个操作，格式如题目所示。

输出描述:

对于每个2号操作，输出一个整数，表示查询的结果。

示例1

输入

复制

10 10
1 1 2 0
1 3 4 1
2 1 4
1 5 6 2
2 1 6
1 7 8 1
2 3 8
1 8 10 3
2 1 10
2 3 8

输出

复制

2
3
2
4
3

线段树区间更新，用或运算进行状态压缩（c<=60疯狂暗示压缩）

#include
#include
using namespace std;typedef long long ll;const int MAX = 100005;struct Node{int l,r;ll sum,lazy;
}tree[4*MAX];int n,m,op,x,y;
ll c;void pushup(int u){tree[u].sum = tree[2*u].sum | tree[2*u+1].sum;
}void pushdown(int u){if(tree[u].lazy!=0){tree[2*u].lazy = tree[2*u].lazy | tree[u].lazy;tree[2*u+1].lazy = tree[2*u+1].lazy | tree[u].lazy;tree[2*u].sum = tree[2*u].sum | tree[u].lazy;tree[2*u+1].sum = tree[2*u+1].sum | tree[u].lazy;tree[u].lazy = 0;}
}void buildTree(int u,int l,int r){tree[u].sum=tree[u].lazy=0;tree[u].l = l;tree[u].r = r;if(l==r)return;int mid = l + (r-l)/2;buildTree(2*u,l,mid);buildTree(2*u+1,mid+1,r);
}void update(int u,int l,int r,ll add){if(tree[u].l>=l && tree[u].r<=r){tree[u].lazy = tree[u].lazy | add;tree[u].sum = tree[u].sum | add;return;}pushdown(u);int mid = tree[u].l + (tree[u].r-tree[u].l)/2;if(l<=mid)update(2*u,l,r,add);if(r>mid)update(2*u+1,l,r,add);pushup(u);
}ll query(int u,int l,int r){if(tree[u].l>=l && tree[u].r<=r)return tree[u].sum;pushdown(u);int mid = tree[u].l + (tree[u].r-tree[u].l)/2;ll ans = 0;if(l<=mid)ans = ans | query(2*u,l,r);if(r>mid)ans = ans | query(2*u+1,l,r);return ans;
}ll getAns(ll x){ll ans = 0;while(x>0){ans += x%2;x/=2;}return ans;
}int main(){while(~scanf("%d%d",&n,&m)){buildTree(1,1,n);while(m--){scanf("%d",&op);if(op==1){scanf("%d%d%lld",&x,&y,&c);ll add = (1ll)<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！