LJH-coding

Zerojudge c364 我鄙視你 題目 https://zerojudge.tw/ShowProblem?problemid=c364 給你一個序列，問你第iii個值往右看和往左看直到碰到≥\ge≥他的值就停下來，然後計算這些數字的總和 Solution 做兩次單調Stack，分別是從右到左跟從左到右 由於第iii個值碰到≥\ge≥他的值就會停下來，我們假設這個值叫做aja_jaj​，則ai,aj,...a_i,a_j,...ai​,aj​,...可以觀察出一個遞增或遞減的單調性，而區間(i,j)(i,j)(i,j)之間的值就是被aia_iai​或aja_jaj​所鄙視的值(根據是右到左做單調Stack還是左到右做來決定區間內的值要被誰鄙視) 用ans1,ans2ans1,ans2ans1,ans2分別儲存每個值往左鄙視跟往右鄙視的總和，最後輸出再把他們加總起來就好了。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455 ...

APIO 2017 Travelling Merchant 題目敘述 有nnn個工作站、kkk個商品，每個工作站上會告訴你每個商品的賣出與買入的價格，如果不賣或不買的話價格會標示−1-1−1，現在給你一張有向圖，圖的節點是工作站，邊權為從工作站uuu走到工作站vvv的時間，問你這張圖中的一個環的最大收益時間比值，也就是這張圖中環上的總收益時間\frac{總收益}{時間}時間總收益​最大是多少。 題解 先把時間用adjacency_matrix存起來，對這個矩陣做floyd warshall，即可得知每個點對的最短時間，然後再枚舉每個點對(u,v)(u,v)(u,v)，去計算u→vu \to vu→v的最大收益是多少，一樣用adjacency_matrix儲存。 最後可以發現答案會介於[0,109][0,10^9][0,109]之間，且答案具有單調性，也就是假設目前答案為xxx，我們就可以發現[0,x][0,x][0,x]這個區間內都有辦法構成一個收益時間比值，所以我們可以用二分搜找xxx的最大值。 假設目前收益時間比值∑(S)∑(T)≥x\displaystyle\frac{\sum( ...

CSES 1673 High Score 題目 https://cses.fi/problemset/task/1673 Solution 用Bellman Ford找出111到每個點的最長路徑(邊權改成負的後的最短路徑)，然後用dfs檢查路徑上是否有存在負環的點，如果有的話就直接輸出−1-1−1，如果沒有就輸出1→n1\to n1→n的最短距離。 dfs檢查的部分，如果在Bellman Ford的第nnn次還有被修改到的話，那這個點就是負環上的點。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include <bits/stdc++.h>#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")#pragma GCC target("abm,bmi,bmi2,mmx,s ...

前言 用deque模擬貪食蛇身體，剩下的就是一些實作 程式碼 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145#include <bits/stdc++.h>#include <windows.h>#include <conio.h>const int width = 60,height = 28;using namespace std;char inpu ...

前言 在差不多三月的時候接了一個Python程式設計的case，但其實我的專長不是Py，可是因為沒錢所以就硬著頭皮接下去了，過程也是邊做邊學這樣。 學生年齡很小，只有小六，不過已經學了幾年程式了，對電腦操作非常熟悉，也都了解過Py的基礎語法，甚至自學了JS還有自己私底下幫班上寫班級網站，放到github page上的那種，是個很厲害的弟弟。 過程 這段期間其實教了蠻多東西的，像是pygame、dc bot、tkinter等等的，雖然很明顯地能看出我對python的生疏，可是至少都還算順利，Super(學生的暱稱)在過程中都學得很開心，表定上課時間是從晚上7:30~9:30，可是我們有時候都會延後到十點多才下課，大部分都是因為寫程式寫得太入迷，有時候Super也會和我分享他的小作品，生活趣事等等的，我們還互追哀居，發現他的生活真的很多采多姿，回想起我小六的時候，大概只有戰鬥陀螺跟全民槍戰吧哈哈。 結論 雖然過程都很順利，教學也非常開心，可是，這終究不是我的專長，所以我就在前幾天做出了終止合作的決定，把Super轉手交給我的學弟了，我學弟他python比我厲害許多，也擅長實務開發，相信能教 ...