[TIOJ] 1001. Hello World!

題目連結:http://tioj.infor.org/problems/1001
經典水題一題，不管用cout,puts,printf,write都可，這裡我用我習慣的printf寫 
#include <stdio.h>
int main(){
        printf("Hello Tmt World XD!");
        return 0;
}

留言

張貼留言

這個網誌中的熱門文章

[NTUJ] 2789. Graduate Record Examinations

題目連結: http://acm.csie.org/ntujudge/problem.php?id=2789 原本想要用離散化在定義一堆其怪的狀態來做這題，不過越寫越寫不出來。被雷了才知道，原來其實把那堆bit看成一堆線段就好了，那其實退位就是讓目前最低位消失，並在低他一位的地方長出一堆一直到現在這位置，而進位就更不用說了，畢竟原本進位就是均攤$O(1)$了。 #include <bits/stdc++.h> using namespace std; #define ALL(x) (x).begin(), (x).end() #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second template<typename T> using minHeap = priority_queue<T,vector<T>,greater<T>>; vector<PII> work, ans; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while(t--){ work.clear(); ans.clear(); minHeap<int> pq1, pq2; int n; cin>>n; for(int i=0;i<n;i++){ char c;int k; cin>>c>>k; if(c=='+') pq1.push(k); else if(c=='-') pq2.push(k); } while(pq1.size()>1){ auto a=pq1.top();pq1.pop(); auto b=pq1.top();pq1.pop(); if(a==b) pq1.push(a+1); else{ work.PB({a,1}); pq1.push(b); } } if(!pq1.em
閱讀完整內容

[TIOJ] 1902. 「殿仁．王，不認識，誰啊？」，然後他就死了……

題目連結: https://tioj.infor.org/problems/1902 直接回滾莫隊後套個 trie 來查區間 xor 最大值，複雜度 $O((N^2/K + QK) \log C)$ 之類的(沒仔細算)，$K$好好挑一下就會過。 p.s. 好像好多古代人的解都是 $O(N^2 + Q)$ 😥 #include <algorithm> #include <functional> #include <iostream> #include <iterator> #include <numeric> #include <utility> #include <vector> int main() { std::cin.tie(nullptr)->sync_with_stdio(false); auto maxi = [](auto &a, auto b) { a = std::max(a, b); }; int n, q; std::cin >> n >> q; std::vector<uint32_t> a(1); std::copy_n(std::istream_iterator<int>(std::cin), n, std::back_inserter(a)); std::partial_sum(a.begin(), a.end(), a.begin(), std::bit_xor()); struct Q { int l, r, id; Q(int l_, int r_, int id_) : l(l_), r(r_), id(id_) {} }; static constexpr int K = 128; std::vector<std::vector<Q>> qs((n + K - 1) / K); for (int i = 0; i < q; ++i) { int l, r; std::cin >> l >> r; --l; qs[l / K
閱讀完整內容

[AtCoder] [經典競程 90 題] 023 - Avoid War（★7）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_w 題目大意: 給定一個 $H \times W$ 的棋盤，其中被標記為 # 的格子代表不能擺棋子。問有多少種方式可以在棋盤上擺一堆西洋棋的國王而不會造成至少一組國王可以立即攻擊到對方。 看完馬上想到 大根蘿蔔 ，這種題明顯要狀態壓縮 DP，狀態大概可以是 $dp[x][y][\text{mask}]$ 代表在 $(x, y)$ 的時候 $\text{mask}$ 裡面那些位置是可以擺的，然後轉移就真的看這格要不要擺之類的。 但如果真的無腦這樣做的話，複雜度會是 $O(H \times W \times 2^W)$ ，明顯會跑太久，不過仔細想了想就可以感受到合法狀態數絕對沒有這麼多，因為放一個就會蓋掉周遭之類的。 所以對於這種情況一個好方法就是我們可以先花 $W \times 2^W$ 的時間預處理真正合法的狀態，接著就可以 $O(H \times W \times X)$ (其中 $X$ 是真正可能的合法的狀態數) DP 掉了。 不過因為我很爛，從以前就一直不知道該怎麼好好寫這種預處理 DP，只知道這樣是可行的，所以這題最後跑去看 官解程式碼 才終於學會寫程式。 官解 同時也有稍微說明我上面的那個 $X$ 其實就是費式數列的某項，因為把蓋掉之後能再放的拿出來估一估差不多就會跟費式數列遞迴式一樣。 #include <bits/stdc++.h> using namespace std; static constexpr int C = 167761; static constexpr int N = 24; static constexpr int N2 = 1 << N; static constexpr int MOD = 1'000'000'007; inline int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; } string a[N]; unordered_map<int, pair<int, int>> mp[N]; int cnt[N], stat
閱讀完整內容