公司让做网站违法,天津市城乡建设网,重庆自有网站推广,新乡公司做网站找哪家公司好A - Excange
题意
用这些零钱能否不找零地买这些物品
思路
因为 500 5 100 10 50 50 10 500 1 5005\times 10010\times 5050\times 10500\times 1 5005100105050105001。
所以说#xff0c;我们这道题可以采用贪心算法#xff0c;优先取大的减去目前零钱最大的…A - Excange
题意
用这些零钱能否不找零地买这些物品
思路
因为 500 5 × 100 10 × 50 50 × 10 500 × 1 5005\times 10010\times 5050\times 10500\times 1 5005×10010×5050×10500×1。
所以说我们这道题可以采用贪心算法优先取大的减去目前零钱最大的即可。
#include iostream
#include cstdio
#include queue
#define N 15
using namespace std;
int money[N],n,X[N],sum,p[10]{0,1,5,10,50,100,500};
priority_queueint q;
signed main(){cin money[1] money[2] money[3] money[4] money[5] money[6] n;for (int i 1;i n;i ) cin X[i],sum X[i],q.push(X[i]);if (sum money[1] * 1 money[2] * 5 money[3] * 10 money[4] * 50 money[5] * 100 money[6] * 500) return cout No,0;for (int i 6;i;i --) while (!q.empty() money[i] q.top() p[i]) {int t q.top();q.pop();t - p[i];money[i] --;
// cout i t t p[i] money[i] endl;if (t)q.push(t);}if (!q.empty()) cout No;else cout Yes;return 0;
}B - Puzzle of Lamps
关灯
有两个选择
A把排最左边的 0 变成 1B把排最左边的 1 变成 0。
思路
很容易想到先把 A 选择到最右边的位置然后用 B 把最右边 1 的位置的左边第一个没有 0 的位置一直重复操作即可。
#include iostream
#include cstdio
#include cstring
#include algorithm
#define N 50
using namespace std;
int n;
string s;
int ans 0;
string ans_st ;
signed main(){cin n s;int k n - 1;while (k 0) {while (k 0 s[k] ! 1) k --;ans k 1;for (int i 0;i k;i ) ans_st A;while (k 0 s[k] ! 0) k --;ans k 1;for (int i 0;i k;i ) ans_st B;}cout ans endl ans_st;return 0;
}C - Routing
题意
有一个 N × N N\times N N×N 的地图每个格子上标有红色或者蓝色R 或者 B现在我们有若干次操作把当前格子变成紫色P代表既是 R 的路又是 B 的路使得
从 ( 1 , 1 ) → ( N , N ) (1,1)\rightarrow(N,N) (1,1)→(N,N) 只走 R 的路能够到达从 ( 1 , N ) → ( N , 1 ) (1,N)\rightarrow(N,1) (1,N)→(N,1) 只走 B 的路能够到达。
求操作的最小次数。
思路
观察特性发现这里走的两条路径必定会有一个交点。但是这个交点只会被算一次。
我们可以想到用 BFS 搜索 ( 1 , 1 ) → ( N , N ) (1,1)\rightarrow(N,N) (1,1)→(N,N) 以及 ( 1 , N ) → ( N , 1 ) (1,N)\rightarrow(N,1) (1,N)→(N,1) 的路径的最少走不合法的格子的数量最后相加即可。
#include iostream
#include cstdio
#include algorithm
#include queue
#include vector
#define N 505using namespace std;
const int INF 1e9;
int n,vis1[N][N],vis2[N][N],fxy[4][2] {{1,0},{-1,0},{0,-1},{0,1}};
bool a[N][N];
struct pos{int x,y,sp;
};
queuepos q;
signed main(){cin n;for (int i 1;i n;i )for (int j 1;j n;j ) {char x;cin x;a[i][j] (x R);}for (int i 0;i n 1;i )for (int j 0;j n 1;j )vis1[i][j] vis2[i][j] INF;vis1[1][1] 0;q.push({1,1,0});while(!q.empty()) {pos t q.front();q.pop();for (int i 0;i 4;i ) {int xx t.x fxy[i][0],yy t.y fxy[i][1];if (xx 1 || yy 1 || xx n || yy n) continue;int nt t.sp;if (!a[xx][yy]) nt ;if (vis1[xx][yy] nt) continue;q.push({xx,yy,nt});vis1[xx][yy] nt;}}q.push({1,n,0});while(!q.empty()) {pos t q.front();q.pop();for (int i 0;i 4;i ) {int xx t.x fxy[i][0],yy t.y fxy[i][1];if (xx 1 || yy 1 || xx n || yy n) continue;int nt t.sp;if (a[xx][yy]) nt ;if (vis2[xx][yy] nt) continue;q.push({xx,yy,nt});vis2[xx][yy] nt;}}cout vis1[n][n] vis2[n][1] endl;return 0;
}D - Earthquakes以后更
题意
有 n n n 个建筑高度都为 j j j。 有 n n n 次地震第 i i i 次地震的两级中的一级会倒下向左和向右倒的概率为 50 % 50\% 50%而且当前第 i i i 个建筑的位置为 a i a_i ai如果说 ∣ a i − a i ± 1 ∣ ≤ h |a_i-a_{i\pm1}|\le h ∣ai−ai±1∣≤h那么那个建筑也会随着他倒下的方向倒下。 那么第 i i i 次地震时建筑全都倒下的概率是多少请将它乘上 2 n 2^n 2n 后输出可以证明输出的是整数。
思路
略
