最後更新日期 2024 / 01 / 01

題解 CSES Weird Algorithm

https://cses.fi/problemset/task/1068

題意

給予一個數字 n
如果他是偶數就把他除 2
否則就把他乘 3 再加 1
重複直到 n 變成 1

想法

沒什麼特別的概念
直接模擬操作就可以了

程式碼

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
	int n;
	cin >> n;
	while(n != 1) {
		cout << n << " ";
		if (n & 1 == 1) {
			 n *= 3;
			 n++;
		} else {
			n /= 2;
		}
	}
	cout << 1 << endl;
}

推薦文章

題解 CSES Repetitions

你有一個由 A、C、G、T 組成的字串 目標是算出同樣的字母最多連續重複幾次把整個字串從左邊往右掃 用一個 curLen 變數維護目前的長度 遇到一個字母時 curLen 加 1 如果跟上個字母不同就把 curLen 歸零 每次掃過一個字母再用 maxLen 維護出現過最大的 curLencppusing namespace std;signed main { char chr, tmp = 'X'; int maxLen = 1, curLen = 1; while cin chr { if tmp = 'X' tmp == chr { curLen++; } else { curLen = 1; } maxLen = maxmaxLen, curLen; tmp = chr; } cout maxLen endl;}

CSES

題解 CSES Restaurant Customers

給你 n 位客人的進入和離開餐廳的時間 輸出最多同時有幾位客人同時在餐廳- n le 2 times 10^5把每個人加入時間和離開的時間分別看成兩個時間點 並把所有時間點加入陣列後一起排序 然後用一個變數來維護目前餐廳人數 每次遇到加入就增加 反之遇到離開就減少 維護中遇到的最大值就是答案了 時間複雜度:Oncpp using namespace std; signed main { int n; cin n; vectorpii v; for int i = 0; i n; i++ { int s, t; cin s t; v.pushback{s, true}; v.pushback{t, false}; } sortv.begin, v.end; int cur = 0; int ans = 0; for auto e : v { if e.ss == true cur++; else cur--; ans = maxcur, ans; } cout ans endl;}

CSES

題解 CSES Common Divisors

找到兩個數字 使得兩數的最大公因數盡量大可以把題目想成 找到最大的 x 使得陣列中出現至少兩個他的倍數 於是我們可以先用 cnt 陣列紀錄每個數字的出現次數 然後枚舉每個可能的因數 假設目前枚舉到 k 從 k、2k、3k dots 計算陣列中存在多少個倍數 根據調和級數.harmonic-series可以算出時間複雜度為 On log ncppconst int maxn = 1e6 + 10;int cntmaxn;signed main { int n; cin n; vectorint vn; for int i = 0; i n; i++ { cin vi; cntvi++; } for int k = maxn; k 0; k-- { int cur = 0; for int j = k; j maxn; j += k { cur += cntj; } if cur = 2 { cout k endl; return 0; } }}

CSES