# 拿來整理一些基礎題目的地方

## P1 (stdio)
[題目](https://zerojudge.tw/ShowProblem?problemid=a001)
**解題思路:**
很基礎的輸入輸出，沒啥好講的
**Code:**
>c
>```c=
> #include <stdio.h>
> int main()
> {
> char i[255];
> scanf("%s",i);
> printf("hello, %s",i);
> }
>```
>c++
> ```cpp=
> #include<bits/stdc++.h>
> using namespace std;
> #define 幫我撐五秒 \
> ios::sync_with_stdio(false); \
> cin.tie(0); \
> cout.tie(0);
> int main ()
> {
> 幫我撐五秒 //優化用的不用管他
> string i;
> cin >> i;
> cout << "hello, " << i;
> }
> ```
> python
> ```python=
> i = input()
>print("hello, "+i)
>```
>Rust
>```rust=
> fn main() {
> let mut i = String::new();
> std::io::stdin().read_line(&mut i);
> println!("hello, {}", i);
> }
> ```

## P2 (stdio、數學)
[題目](https://zerojudge.tw/ShowProblem?problemid=a002)
**解題思路:**
很基礎的stdio和運算，沒啥好講的
**Code:**
> c
> ```C=
> #include<stdio.h>
> int main()
> {
> long int a,b;
> scanf("%ld %ld",&a,&b);
> printf("%ld",a+b);
> }
> ```
> c++
> ```cpp=
> #include<bits/stdc++.h>
> using namespace std;
> #define 幫我撐五秒 \
> ios::sync_with_stdio(false); \
> cin.tie(0); \
> cout.tie(0);
> int main()
> {
> 幫我撐五秒
> long int a,b; //根據題目a, b絕對值的大小可能int會產生溢位
> cin>>a>>b;
> cout<<a+b;
> }
> ```
> python
> ```python=
> i=input()
> a,b=i.split()
> print(int(a)+int(b))
> ```
> Rust
> ```rust=
> fn main() {
> let mut i = String::new();
> std::io::stdin().read_line(&mut i);
> let mut iter = i.split_whitespace();
> let a: i64 = iter.next().unwrap().parse().unwrap();
> let b: i64 = iter.next().unwrap().parse().unwrap();
> println!("{}", a + b);
> }
> ```

## P3 (多元判斷)
[題目](https://zerojudge.tw/ShowProblem?problemid=a003)
**解題思路:**
就運算、取模$mod$加判斷，也沒啥好講的
**Code:**
> c
> ```c=
> #include<stdio.h>
> int main()
> {
> int m,d;
> scanf("%d %d",&m,&d);
> switch((m*2+d)%3){
> case 0:{
> printf("普通");
> break;
> }
> case 1:{
> printf("吉");
> break;
> }
> case 2:{
> printf("大吉");
> break;
> }
> }
> }
> ```
> c++
> ```cpp=
> #include<bits/stdc++.h>
> using namespace std;
> #define 幫我撐五秒 \
> ios::sync_with_stdio(false); \
> cin.tie(0); \
> cout.tie(0);
> int main ()
> {
> 幫我撐五秒
> int m,d;
> cin>>m>>d;
> /*
> 使用switch函數進行多元判斷，避免使用if時產生的混亂
> 至於所謂的混亂於linux內核風格指南中提出，
> "當一程式超過三行的縮排就代表程式發生了混亂，應立即修正"
> 當然用if、else if確實也能實現同樣的目的
> */
>
> switch((m*2+d)%3){
> case 0:{
> cout<<"普通";
> break;
> }
> case 1:{
> cout<<"吉";
> break;
> }
> case 2:{
> cout<<"大吉";
> break;
> }
> }
> }
> ```
> python
> ```python=
> i = input()
> m, d = i.split()
> a = (int(m) * 2 + int(d)) % 3
> match a:
> case "1":
> print("吉")
> case "2":
> print("大吉")
> case _:
> print("普通")
> ```
> Rust
> ```rust=
> fn main() {
> let mut i = String::new();
> std::io::stdin().read_line(&mut i);
> let mut iter = i.split_whitespace();
> let m: i64 = iter.next().unwrap().parse().unwrap();
> let d: i64 = iter.next().unwrap().parse().unwrap();
> match (m*2+d)%3{
> 0=>println!("普通"),
> 1=>println!("吉"),
> _=>println!("大吉")
> }
> }
> ```

## P4 (二元判斷)
[題目](https://zerojudge.tw/ShowProblem?problemid=a004)
**解題思路:**
根據定義閏年為被4整除且不被100整除，或被400整除的數
**Code:**
> c
> ```c=
> #include<stdio.h>
> int main()
> {
> int i;
> while(scanf("%d",&i)!=EOF)
> {
> if((i%4==0 && i%100!=0)||(i%400==0)){
> printf("閏年\n");
> }
> else{
> printf("平年\n");
> }
> }
> }
> ```
> c++
> ```cpp=
> #include<bits/stdc++.h>
> using namespace std;
> #define 幫我撐五秒 \
> ios::sync_with_stdio(false); \
> cin.tie(0); \
> cout.tie(0);
> int main ()
> {
> 幫我撐五秒
> int y;
> /*
> 題目中所謂的EOF簡單來說就是檔案執行結束
> 使用的空間名是std也就是標準輸入輸出
> 因此讀入檔案的來源為標準輸入介面
> 故在這EOF代表輸入結束
> 而當輸入結束時，cin的回傳質為0，將使while不成立
> */
>
> while (cin>>y)
> {
> if((y%4==0 && y%100!=0)||(y%400==0)){
> cout<<"閏年"<<endl;
> }
> else{
> cout<<"平年"<<endl;
> }
> }
>
> }
> ```
> python
> ```python=
> while True:
> try:
> i = int(input())
> if((i%4==0 and i%100!=0)or(i%400==0)):
> print("閏年\n");
>
> else:
> print("平年\n");
>
> except ValueError:
> break
> ```
> Rust
> ```rust=
> use std::io::{self, BufRead};
> fn main() {
> let stdin = io::stdin();
> for line in stdin.lock().lines() {
> let y: i32 = line.unwrap().trim().parse().unwrap();
> if (y % 4 == 0 && y % 100 != 0) || y % 400 == 0 {
> println!("閏年");
> } else {
> println!("平年");
> }
> }
> }
> ```

## P5 (迴圈)
[題目](https://zerojudge.tw/ShowProblem?problemid=a038)
**解題思路:**
最直覺的方法就是把最後一位移動到第一位，重覆到全部都被處理過
若輸入數字為**i**並有一空白整數變數***temp***透過取除10的***mod***可以獲得最後一位的數字，加入***temp***後將**i**除等於10並把***temp***乘10便可實現移位的功能。
**Code:**
> c
> ```c=
> #include <stdio.h>
> int main()
> {
> int temp , rem , re ;
> scanf("%d",&temp) ;
> re = 0 ;
> while ( temp != 0 ) {
> rem = temp % 10 ;
> re = re * 10 + rem ;
> temp /= 10 ;
> }
>
> printf("%d",re);
> }
> ```
> c++
> ```cpp=
> #include <bits/stdc++.h>
> using namespace std;
> int main ( ) {
> ios_base::sync_with_stdio(false);
> cin.tie(0);
> cout.tie(0);
> int temp , rem , i ;
>
> cin >> i ;
> temp = 0 ;
> while ( i != 0 ) {
> rem = temp % 10 ;
> temp = temp * 10 + rem ;
> i /= 10 ;
> }
>
> cout << temp ;
> }
> ```
> python
> ```python=
> temp = int(input())
> re = 0
> while temp != 0:
> rem = temp % 10
> re = re * 10 + rem
> temp //= 10
>
> print(re)
> ```
> Rust
> ```rust=
> fn main() {
> let mut temp = String::new();
> std::io::stdin().read_line(&mut temp).expect("Failed to read input.");
> let temp: i32 = temp.trim().parse().expect("Invalid input. Please enter an integer.");
>
> let mut re = 0;
> let mut num = temp;
> while num != 0 {
> let rem = num % 10;
> re = re * 10 + rem;
> num /= 10;
> }
>
> println!("{}", re);
> }
> ```
*接下來我懶得寫其他語言了 --by.Chen*
## P6 (數學)
[題目](https://zerojudge.tw/ShowProblem?problemid=a010)
**解題思路:**
關於因式分解的方法詳細可見師大的[這篇](https://web.ntnu.edu.tw/~algo/Divisor.html)接下來就只剩簡單的判斷和輸出了
**Code:**
> c++
> ```cpp=
> #include<bits/stdc++.h>
> using namespace std;
> int main(){
> ios_base::sync_with_stdio(false);
> cin.tie(0);
> cout.tie(0);
> int n;
> cin >> n;
> map<int,int>factor;
> while (n % 2 == 0)
> {
> factor[2]++;
> n /= 2;
> }
> for (int p=3; p*p<=n; p+=2){
> while (n % p == 0)
> {
> factor[p]++;
> n /= p;
> }
> }
> if (n > 1) factor[n]1++;
> for (auto it = factor.begin(); it != factor.end(); it++) {
> if(it != factor.begin()) cout << " * ";
> if((*it).second>1){
> cout << (*it).first << '^' << (*it).second;
> }
> else{
> cout << (*it).first;
> }
> }
> }
> ```
> python
> ```python=
> n = int(input())
> factor = {}
> while n % 2 == 0:
> if 2 in factor:
> factor[2] += 1
> else:
> factor[2] = 1
> n //= 2
> for p in range(3, int(n**0.5) + 1, 2):
> while n % p == 0:
> if p in factor:
> factor[p] += 1
> else:
> factor[p] = 1
> n //= p
> if n > 1:
> if n in factor:
> factor[n] += 1
> else:
> factor[n] = 1
> cut=0
> for key, value in factor.items():
> cut+=1
> if cut<len(factor):
> if value > 1:
> print(key, "^", value,end=" * ")
> else:
> print(key,end=" * ")
> else:
> if value > 1:
> print(key, "^", value)
> else:
> print(key)
> ```
## P7 (字元、字串判斷)
[題目](https://zerojudge.tw/ShowProblem?problemid=d103)
**思路分析:**
除了需注意字元和整數的轉換和識別碼為**10**的狀況以外就只剩基本的數學運算了，真沒什麼好講的。
**Code:**
> c++
> ```cpp=
> #include<bits/stdc++.h>
> using namespace std;
> int main(){
> string i;
> while (cin>>i)
> {
> string temp = i;
> int counter=0;
> vector<int> s;
> for(int n = 0;n<=temp.length();n++){
> if(temp[n]!='-'){
> s.push_back(temp[n]);
> }
> }
> for(int c = 0;c<9;c++){
> counter+=(s[c]-48)*(c+1);
> }
> if(temp[12]==char(counter%11+48)||(temp[12]=='X'&&counter%11==10)){
> cout<<"Right\n";
> }
> else{
> if(counter%11==10){
> temp[12]='X';
> }
> else{
> temp[12]=char(counter%11+48);
> }
> cout<<temp<<endl;
> }
> }
>
> }
> ```

## P8 (字元、字串、數學)
[題目](https://leetcode.com/problems/roman-to-integer)
**解題思路:**
**Code:**
最簡單的方式就是可以先將符號轉換成數字，再透過前後向比較大小決定需要加還是減。
> c++
> ```cpp=
> #include<bits/stdc++.h>
> using namespace std;
> int romanToInt(string s) {
> int counter{0};
> vector<int>temp;
> for(char i : s){
> if(i=='I'){
> temp.push_back(1);
> }
> else if(i=='V'){
> temp.push_back(5);
> }
> else if(i=='X'){
> temp.push_back(10);
> }
> else if(i=='L'){
> temp.push_back(50);
> }
> else if(i=='C'){
> temp.push_back(100);
> }
> else if(i=='D'){
> temp.push_back(500);
> }
> else{
> temp.push_back(1000);
> }
> }
> for(int i = 0;i <= temp.size()-1;i++){
> if(i<temp.size()-1 && temp[i]<temp[i+1]){
> counter+=temp[i+1]-temp[i];
> i++;
> }
> else{
> counter+=temp[i];
> }
> }
> return counter;
> }
> int main(){
> string roman = "MCMXCIV";
> int i= romanToInt(roman);
> cout<<i;
> }
> ```
其實是可以透過**map**的方式把轉換成數字的過程優化掉的，可以減少一半的時間複雜度。
優化後長這樣
> ```cpp=
> #include<bits/stdc++.h>
> using namespace std;
> int romanToInt(string s) {
> unordered_map<char, int> m;
> m['I'] = 1;
> m['V'] = 5;
> m['X'] = 10;
> m['L'] = 50;
> m['C'] = 100;
> m['D'] = 500;
> m['M'] = 1000;
> int ans = 0;
> for(int i = 0; i < s.length(); i++){
> if(m[s[i]] < m[s[i+1]]){
> ans -= m[s[i]];
> }
> else{
> ans += m[s[i]];
> }
> }
> return ans;
> }
> int main(){
> string roman = "MCMXCIV";
> int i= romanToInt(roman);
> cout<<i;
> }
> ```

## P9 (數學)
[題目](https://leetcode.com/problems/power-of-two/)
**解題思路:**
我只能說位元運算是好東西
為二的$n$次方的數在二進制中只會有一位數字為1，稱他為第$M$位
而二的$n$次方-1則剛好相反，第$M$位會被翻轉成0，而第$M$位後的數都會被翻轉成1
透過兩數進行**AND**運算可以得到0，但要記得先排除負數的輸入
**Code:**
> cpp
> ```cpp=
> #include<bits/stdc++.h>
> using namespace std;
> bool isPowerOfTwo(int n) {
> return (n > 0) && ((n & (n - 1)) == 0);
> }
> int main(){
> int n = 16;
> bool ans = isPowerOfTwo(n);
> cout<<ans;
> }
> ```
## P10 (陣列)
[題目](https://leetcode.com/problems/monotonic-array)
**解題思路:**
先判首項及末項的大小判斷應該是遞增還是遞減，
再一項一項慢慢判是不是每一個都符合就好了，
**Code:**
> cpp
> ```cpp=
> #include<bits/stdc++.h>
> using namespace std;
> bool isMonotonic(vector<int>& nums) {
> bool b;
> if(nums[0]>nums[nums.size()-1]){
> b=false;
> }
> else{
> b=true;
> }
> for(int i=0;i<nums.size()-1;i++){
> if(nums[i]<nums[i+1] && !b){
> return false;
> }
> if(nums[i]>nums[i+1]&& b){
> return false;
> }
> }
> return true;
> }
> int main(){
> vector<int> n = {1,2,4,4};
> bool ans = isMonotonic(n);
> cout<< ans ;
> }
> ```