oToToT的code收藏區

題目連結: http://codeforces.com/problemset/problem/909/C 我不會DP QAQ 本題狀態可以訂成$dp[i][j]$代表到第$i$個statement時有$j$個intent的方法數，那轉移想了想後就可以得到，如果前面是for statement，那顯然現在的東西就只能擺在跟他同一個intent，而若前一個是普通的statement，則我們可以擺到intent比較小的任意一個位置。而這樣的話複雜度會變成$O(N^3)$，但是其實我們可以透過預處理前綴和以達到$O(N^2)$的複雜度。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int MOD = 1000000007; const int N = 5000 + 5; bool arr[N]; lld dp[N][N], sum[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ string ss; cin>>ss; if(ss[0]=='s') arr[i] = 1; else arr[i] = 0; } auto psum = [](int l, int r){ // 0-base [l, r] if(l) return sum[r]-sum[l-1]; else return sum[r]; }; dp[0][0] = 1; for(int i=1;i<=n;i++){ if(arr[i-1]){ sum[0] = dp[i-1][0]; for(int j=1;j<=n;j++) sum[j] = (sum[j-1]+dp[i-1][j])%MOD; if(arr[i]) for(int j=0;j<=n;j++) dp[i][j] = (psum(j, n)+MOD)%MOD; else for(int j=1;j<=n;j++) dp[i][j] = (psum

題目連結: http://tioj.infor.org/problems/1134 想了想覺得把1換成-1, 0換成1之後會有好事情，然後似乎可以做類似最大子矩陣的方式，但是我不知道該怎麼用。 被雷了之後才發現其實我只要把兩個問題合在一起就好了，一個是最大子矩陣，一個是某種找有多少大於零的序列的問題。首先我們可以先對一維用前綴和之後枚舉頂跟底，接著就變成一維的問題了，變成一維的問題後就是要問說對於所有大於零的序列中，最長是多少，作法也是考慮枚舉前綴和，每次只要查小於當前前綴和的所有鍵值中最小的值是多少，接著就把當前前綴和當做鍵值，現在的位置當作值插到某種資料結構就好了。 #include <bits/stdc++.h> using namespace std; #define ALL(x) begin(x), end(x) const int N = 200 + 5; const int INF = 1<<30; class LiSan{ private: vector<int> vv; public: inline void init(){vv.clear();} inline void insert(int x){vv.push_back(x);} inline void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } inline int size(){return vv.size();} inline int get(int x){ return distance(vv.begin(), lower_bound(ALL(vv), x)); } inline int inv_get(int x){return vv[x];} } lisan; class BIT{ private: vector<int> arr; int n; inline int lowbit(int x){return x&(-x);} public: void init(int n_){ n = n_; arr.resize(n);

題目連結: http://poj.org/problem?id=1067 我通靈不出來，盯了他一個晚上只發現對於每個$i$都有一個$j$使他慘掉(?，而且似乎有個1.6左右的比例，但我就不會了QAQ 正解是這個： 威佐夫遊戲 結論就是只要看符不符合$i < j \land (j-i)\frac{1+\sqrt{5}}{2} == i$就可以了。 我缺少知識QQ #include <iostream> #include <cmath> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); long double TongLing = (sqrt((long double)5)+1)/2; int n, m; while(cin>>n>>m){ if(n > m) swap(n, m); cout << ((int)((m-n)*TongLing) != n) << '\n'; } return 0; }

題目連結: http://codeforces.com/contest/912/problem/E 記錄一下覺得滿有趣的題目。 首先要知道$10^{18}$以內的只包含包個質因數的數，大約只有$10^6~10^7$種左右，所以我們可以把給定的$n$個質數採用砍半枚舉產生出所有$10^{18}$以內僅包含給定的質因數的數，但是因為如果真的把全部都長出來了會太大，所以我們還可以二分搜第k大會是誰，這樣就只要知道比某個數小的數字有幾個就好了，而計算這個的方法很簡單，就枚舉一邊，再二分搜另外一邊即可。 #include <bits/stdc++.h> using namespace std; typedef uint64_t llu; #define PB push_back #define ALL(x) begin(x), end(x) const llu C = 1000000000000000000LL; llu primes[20], p1[10], p2[10]; vector<llu> num1, num2; inline llu calc(llu); void dfs(int,llu,llu[],int,vector<llu>&); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>primes[i]; sort(primes, primes+n); int n1 = 0, n2 = 0; for(int i=0;i<n;i+=2) p1[n1++] = primes[i]; for(int i=1;i<n;i+=2) p2[n2++] = primes[i]; dfs(0, 1, p1, n1, num1); dfs(0, 1, p2, n2, num2); sort(ALL(num1)); num1.resize(distance(num1.begin(), unique(ALL(num1)))); sort(ALL(num2)); num2.resize(distance(num2.begin(), u