A Sagheer and Crossroads
题意：
给你一个双向行驶的十字路口， 每条道路上都以四个灯， l, s, r, p分别表示如图三个方向上和人行道上的红绿灯。如果汽车在绿灯的时候开车撞到了人行道上的人，就会发生交通意外。现在给你每条路上的红绿灯，判断是否会发生交通意外。
思路:
直接暴力写
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> using namespace std; typedef long long LL; //typedef __int64 Int; typedef pair<int, int> PAI; const int INF = 0x3f3f3f3f; const double ESP = 1e-5; const double PI = acos(-1.0); const int MOD = 1e9 + 7; const int MAXN = 1e5 + 10; const int MAX = 3000; int a[5][5]; int judge() { if (a[1][4]&&(a[1][1]||a[1][2]||a[1][3]||a[3][2]||a[4][3]||a[2][1])) return 1; if (a[2][4]&&(a[2][1]||a[2][2]||a[2][3]||a[4][2]||a[1][3]||a[3][1])) return 1; if (a[3][4]&&(a[3][1]||a[3][2]||a[3][3]||a[1][2]||a[2][3]||a[4][1])) return 1; if (a[4][4]&&(a[4][1]||a[4][2]||a[4][3]||a[2][2]||a[3][3]||a[1][1])) return 1; return 0; } int main(int argc, char const *argv[]) { for (int i = 1; i <= 4; i++) { for (int j = 1; j <= 4; j++) { scanf("%d", &a[i][j]); } } int t = judge(); if (t) printf("%s ", "YES"); else printf("%s ", "NO"); return 0; }
B. Sagheer, the Hausmeister
题意：
用矩阵表示一栋大楼，N层M+2行，其中每层的两侧是楼道，其他的是房间。每间房间有两个状态，1——房间的灯是亮的，0——房间的灯是灭的。现在有一个人要从一楼左边的楼梯开始关掉所有的灯，每走一个矩阵的单位花费的时间是1，求从他开始到关掉所有的灯所花费的最下时间。
思路：
我是从最上层有灯的一层开始向下dp，每次这个人在下一层有两个状态，一个是在楼梯的左边，一个是在楼梯的右边。依次dp到左下角。
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <math.h> using namespace std; const int MAXN = 1e5 + 10; char a[20][200]; int dp[20][200]; int main(int argc, char const *argv[]) { int N, M; while (scanf("%d%d", &N, &M) != EOF) { memset(dp, 0, sizeof(dp)); for (int i = 0; i < N; i++) { scanf("%s", a[i]); } int begin = -1; for (int i = 0; i < N; i++) { for (int j = 0; j < M + 2; j++) if (a[i][j] == '1') {begin = i; break;} if (begin != -1) break; } if (begin == -1) {printf("0 "); continue;} int t1 = 0, t2 = 0; for (int j = 0; j <= M + 1; j++) { if (a[begin][j] == '1') t1 = j; } dp[begin][0] = t1; for (int j = M + 1; j >= 1; j--) { if (a[begin][j] == '1') t2 = M + 1 - j; } dp[begin][1] = t2; for (int i = begin + 1; i < N; i++) { t1 = t2 = 0; for (int j = 0; j <= M + 1; j++) { if (a[i][j] == '1') t1 = j; } for (int j = M + 1; j >= 0; j--) { if (a[i][j] == '1') t2 = M + 1 - j; } dp[i][0] = min(2*t1 + dp[i - 1][0], M + 1 + dp[i - 1][1]) + 1; dp[i][1] = min(2*t2 + dp[i - 1][1], M + 1 + dp[i - 1][0]) + 1; } printf("%d ", min(dp[N - 1][0], dp[N - 1][1] + M + 1)); } return 0; }
C. Sagheer and Nubian Market
题意：
商店里有n个纪念品， Sagheer有M单位的钱，第j个的价值是 axj + xj·k，其中k是Sagheer可以买到最大的纪念品的数目，Xj是该纪念品的位置（1……n）。求出k，和此时花掉的钱。
思路：
直接二分k就好。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int MAXN = 1e5 + 10; typedef long long LL; LL a[MAXN]; struct node { LL b, id; } da[MAXN]; LL M, N; int judge(LL x) { memset(a, 0, sizeof(a)); for (int i = 0; i < N; i++) { a[i] = da[i].b + x*da[i].id; } sort(a, a + N); LL s = M; LL t = x; for (int i = 0; i < N; i++) { if (s >= a[i]) { s -= a[i], t--; } else break; } return t <= 0; } int main(int argc, char const *argv[]) { while (scanf("%I64d%I64d", &N, &M) != EOF) { for (int i = 0; i < N; i++) scanf("%I64d", &da[i].b), da[i].id = i + 1; LL lb = 0, ub = N; LL ans = 0; while (ub >= lb) { LL mid = (lb + ub)/2; if (judge(mid)) { ans = mid; lb = mid + 1; } else ub = mid - 1; } judge(ans); LL s = M; for (int i = 0; i < ans; i++) { if (s >= a[i]) s -= a[i];; } printf("%I64d %I64d ", ans, M - s); } return 0; }