HackMD
Else OJ
網站
- LIOJ
難度：⭐
LIOJ
#1014
/*
解題思路：
計算1 ~ n有多少9，再用n減掉
特性為
10有1個、20有2個；
100有19個、200有38個；
...
例如13452，將10000提出計算，累積到counter
接著以3452，將1000提出計算*3，累積到counter
...
最後以n - counter
*/
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int count_nines(int n) {
int count = 0;
for (int i = 1; i <= n; ++i) {
int num = i;
while (num != 0) {
int digit = num % 10;
if (digit == 9) {
++count;
break;
}
num /= 10;
}
}
return count;
}
int main() {
int N, n, counter = 0;
string str;
cin >> N;
n = N;
//N為原始輸入，n為原始值隨計算減少直到 = 0
while (n > 0) {
str = to_string(n);
//抓開頭計算
counter += int(str.front() - '0') * count_nines(pow(10, str.size() - 1));
//去掉第一位數
n -= int(str.front() - '0') * pow(10, str.size() - 1);
}
cout << N - counter << endl;
return 0;
}
#1019
//DFS 二維vector解題
//此題由於不會有岔路跟死路需返回的情況，只有一條路可以走，故可用此解法
#include <iostream>
#include <vector>
using namespace std;
int main() {
int w, h;
cin >> w >> h;
// 宣告一個二維 vector，初始值為 '.'
vector<vector<char>> maze(h, vector<char>(w, '.'));
// 讀入迷宮地圖
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> maze[i][j];
}
}
int x = 0, y = 0, steps = 0;
// 從 (0,0) 走到 (w-1,h-1)
while (x != w - 1 || y != h - 1) { //當還沒走到右下角前就繼續
maze[y][x] = '#'; // 走過的路標記為牆壁，避免重複走
// 優先往右或下走，如果右或下是路就走，否則往左或上走
if (x < w - 1 && maze[y][x + 1] == '.') {
x++;
}
else if (y < h - 1 && maze[y + 1][x] == '.') {
y++;
}
else if (x > 0 && maze[y][x - 1] == '.') {
x--;
}
else if (y > 0 && maze[y - 1][x] == '.') {
y--;
}
steps++;
}
cout << steps << endl;
return 0;
}
#1033
#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;
struct Point {
int x;
int y;
};
int main() {
int N, mP1, mP2;
double now_dist, min_dist = INT_MAX;
cin >> N;
vector<Point> points(N);
for (int i = 0; i < N; i++) {
cin >> points[i].x >> points[i].y;
}
//假設有5號，
//i=0 vs j=1,2,3,4
//i=1 vs j=2,3,4
//i=2 vs j=3,4
//i=3 vs j=4
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
now_dist = sqrt(pow(points[i].x - points[j].x, 2) + pow(points[i].y - points[j].y, 2));
if (now_dist < min_dist) {
min_dist = now_dist;
mP1 = i;
mP2 = j;
}
}
}
if (points[mP1].x < points[mP2].x) {
cout << points[mP1].x << ' ' << points[mP1].y << endl;
cout << points[mP2].x << ' ' << points[mP2].y;
}
else if (points[mP1].x > points[mP2].x) {
cout << points[mP2].x << ' ' << points[mP2].y << endl;
cout << points[mP1].x << ' ' << points[mP1].y;
}
else {
if (points[mP1].y < points[mP2].y) {
cout << points[mP1].x << ' ' << points[mP1].y << endl;
cout << points[mP2].x << ' ' << points[mP2].y;
}
else {
cout << points[mP2].x << ' ' << points[mP2].y << endl;
cout << points[mP1].x << ' ' << points[mP1].y;
}
}
return 0;
}
#1034
#include <iostream>
#include <string>
using namespace std;
int main() {
int n, size, i_tmp;
string S;
cin >> n >> S;
size = S.size();
for (int i = 0; i < size; i++) {
n %= 26;
i_tmp = int(S[i]) + n;
if (i_tmp > 122) {
i_tmp = i_tmp - 122 + 97 - 1;
}
S[i] = char(i_tmp);
}
cout << S << endl;
return 0;
}
#1048
#include <iostream>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
int max_sum = INT_MIN; // 設定一個非常小的初值
int sum = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
sum += x;
max_sum = max(max_sum, sum);
sum = max(sum, 0);
}
cout << max_sum << endl;
return 0;
}
#1052
//使用二維vector建構DP表，解0/1背包問題
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, w, tmp;
vector<int> v_w(1,-1), v_p(1,-1);//在index=0推入無效值，讓資料從index=1開始
cin >> n >> w;
vector<vector<int>> dp(n + 1, vector<int>(w + 1));//讓資料從i=1, j=1開始排列
for (int i = 0; i < n; i++) {
cin >> tmp;
v_w.push_back(tmp);
cin >> tmp;
v_p.push_back(tmp);
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= w; j++) {
if (i == 0 || j == 0) {//將i=0跟j=0填滿0
dp[i][j] = 0;
}
else if (j < v_w[i]) {
dp[i][j] = dp[i - 1][j];
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v_w[i]] + v_p[i]);
}
}
}
cout << dp[n][w] << endl;
return 0;
}
#1053
//使用其他演算法很容易超時
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// 定義無限大
const int INF = climits;
// 定義迷宮結構
struct Maze {
int h; // 高度
int w; // 寬度
vector<vector<char>> grid; // 圖案
vector<vector<int>> dist; // 距離
// 建構函數
Maze(int h, int w) {
this->h = h;
this->w = w;
grid.resize(h, vector<char>(w));
dist.resize(h, vector<int>(w, INF));
}
// 讀取迷宮圖案
void readGrid() {
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> grid[i][j];
}
}
}
// 判斷是否在範圍內
bool inRange(int x, int y) {
return x >= 0 && x < h&& y >= 0 && y < w;
}
// Dijkstra算法
void dijkstra() {
// 定義方向陣列
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
// 建立優先佇列（以距離排序）
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 將起點加入佇列並設定距離為0
pq.push({ 0, 0 });
dist[0][0] = 0;
while (!pq.empty()) {
// 取出佇列頂端元素（距離最小）
auto p = pq.top();
pq.pop();
int x = p.second / w;
int y = p.second % w;
// 如果已經訪問過，則跳過
if (p.first > dist[x][y]) continue;
// 遍歷四個方向
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
// 如果在範圍內且不是牆壁，且有更小的距離，則更新並加入佇列
if (inRange(nx, ny) && grid[nx][ny] == '.' && dist[nx][ny] > dist[x][y] + 1) {
dist[nx][ny] = dist[x][y] + 1;
pq.push({ dist[nx][ny], nx * w + ny });
}
}
}
// 輸出終點的距離（如果沒有路徑則輸出-1）
if (dist[h - 1][w - 1] == INF) {
cout << -1 << endl;
}
else {
cout << dist[h - 1][w - 1] << endl;
}
}
};
// 主函數
int main() {
// 讀取迷宮的高度和寬度
int h, w;
cin >> h >> w;
// 建立迷宮物件
Maze maze(h, w);
// 讀取迷宮圖案
maze.readGrid();
// 執行Dijkstra算法
maze.dijkstra();
return 0;
}
