[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;
}

留言

張貼留言

這個網誌中的熱門文章

[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
閱讀完整內容

[AtCoder] [經典競程 90 題] 022 - Cubic Cake（★2）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_v 題目大意: 給定一個 $A \times B \times C$ 的蛋糕，問最少要幾刀才能把蛋糕切成一堆等大的正方體。切的方法只能平行面且不能亂移蛋糕。 照著算 (?) 反正盡量大塊就是好的，所以切出來的就是邊長的最大公因數。 #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); uint64_t a, b, c; cin >> a >> b >> c; uint64_t r = gcd(a, gcd(b, c)); cout << (a / r) + (b / r) + (c / r) - 3 << '\n'; return 0; }
閱讀完整內容