推薦文章(持續更新)

I/O優化https://horikitacoding.blogspot.com/2019/07/how-to-optimize-your-code-in-c.html

離散數學-同餘https://ithelp.ithome.com.tw/articles/10205727

留言

張貼留言

這個網誌中的熱門文章

TIOJ 1080 . A.逆序數對 (BIT解法)

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1080 先做一波離散化 把所需的BIT長度壓到10⁵以內 而後就記錄目前放了幾個數字進BIT 用放了幾個數字減去有幾個數字比當前輸入的數字小(BIT存的) 就是當前的逆序數對 以下為code #include < bits/stdc++.h > #include < bits/extc++.h > using namespace std; using namespace __gnu_cxx; using namespace __gnu_pbds; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); #define lowbit ( x ) x &- x ll n; struct BIT { vector < ll > v; void modify ( ll x , ll val ) { for (;x < v. size ();x += lowbit (x)) v[x] += val; } ll query ( ll x ) { ll t = 0 ; for (;x;x -= lowbit (x)) t += v[x]; return t; } }; int main () { AC ll num = 1 ; while (cin >> n && n) { cout << " Case # " << num ++<< " : " ; ll cnt = 0 ,r = 0 ,rnk = 1 ; BIT sum; vector < ll > v (n); set < ll > s; ...
閱讀完整內容

AtCoder Educational DP Contest E - Knapsack 2

題目鏈接: https://atcoder.jp/contests/dp/tasks/dp_e 這題還蠻有趣的 他的重量開到10⁹導致不能用上一題(常規0/1背包)的做法去做 要把價值當做dp轉移,去找當前價值所需的最小重量 最後找到的最大的小於重量限制的價值就是答案 以下為code #include < bits/stdc++.h > using namespace std ; using ll = long long ; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC int n,w,r = 0 ; cin >> n >> w; vector < ll > dp ( 100001 , 1 e 10 ); dp[ 0 ] = 0 ; for ( int i = 0 ;i < n;i ++ ) { int wei,val; cin >> wei >> val; for ( int j = 100000 ;j >= val;j -- ) dp[j] = min (dp[j],dp[j - val] + wei); } for ( int i = 1 ;i < dp. size ();i ++ ) if (dp[i] <= w) r = i; cout << r << ' \n ' ; }
閱讀完整內容

TIOJ 1072 . A.誰先晚餐

呃... 沒有證明隨便亂寫就AC了 題目鏈接: https://tioj.ck.tp.edu.tw/problems/1072 總之就是用Greedy跑下去就對啦 從吃最久的人先開始跑 把每道菜所需做的時間都存下來 (因為就算每個人都吃零分鐘也需要消耗做菜時間) 也就是說所需最小時間≥做菜時間 每次做完一道新菜後,再比較當前所用做菜時間加上吃飯時間(R)和之前所用最大的R 取其中大者 (也就是吃飯時間有沒有超過做下一道菜的時間) 以下為code #include < bits/stdc++.h > using namespace std; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll n; while (cin >> n && n) { ll c,e,r = 0 ,t = 0 ; priority_queue < pair < ll,ll >> pq; for (ll i = 0 ;i < n;i ++ ) { cin >> c >> e; pq. push ( make_pair (e,c)); } for (;pq. size ();pq. pop ()) { t += pq. top ().second; r = max (r,t + pq. top ().first); } cout << r << ' \n ' ; } }
閱讀完整內容