oToToT的code收藏區

題目連結: http://poj.org/problem?id=1067 我通靈不出來，盯了他一個晚上只發現對於每個$i$都有一個$j$使他慘掉(?，而且似乎有個1.6左右的比例，但我就不會了QAQ 正解是這個： 威佐夫遊戲 結論就是只要看符不符合$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/problemset/problem/839/D 超級無敵久沒寫blog了，記錄一下這題好了，我過然數學還是不太好QQ 首先我們可能會想要對每個gcd都計算答案，那這時候我們可能會想知道有可能對這個gcd有貢獻的人會有誰，所以不妨先計算好有多少個數字含有因數$i$。那接著我們就直接計算總長度，對於每個因數$i$計算$\sum_{j=0}^{cnt[i]} j\cdot \binom{cnt[i]}{j}$但是這樣會重複計算到太多人，所以要扣掉他的2倍、3倍....的答案，而要算答案的時候則再乘上$i$即可。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 200000 + 5; const int C = 1000000 + 5; const int MOD = 1000000007; int arr[N], cnt[C]; lld ans[C], two[N]; int main(int argc, char* argv[]){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; two[0] = 1; for(int i=1;i<n;i++) two[i] = two[i-1]*2 % MOD; for(int i=0;i<n;i++){ cin>>arr[i]; cnt[arr[i]]++; } for(int i=1;i<=C;i++) for(int j=2;j*i<=C;j++){ cnt[i] += cnt[i*j]; } lld ret = 0; for(int i=C;i>=2;i--){ if(cnt[i]==0)...

題目連結: http://codeforces.com/problemset/problem/798/D 很久以前比賽的時候沒寫出來，最近又再想還是想不到，只好去看題解QQ 大致的想法是，會發現對於$a$我們其實只要在$a$的任意排列的裡面選$a_{2i}$跟$a_{2i+1}$中比較大的人的index，那加起來就一定會夠。但是如果只是無腦的這樣挑很有可能$b$不會符合，所以不妨想想我們把$a$排序一下，並且一定選第一個，接著看相對映的$b$哪個index比較大，就挑他，這樣的話因為$b$一定是好的(跟前面講的一樣)，而$a$若是每次都挑到比較小的那個也不會爛，因為我們已經挑了最大的那個(可以想像成$a$是從$0$開始挑比較大的，$b$是從$1$開始挑比較大的之類的)。 #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; int a[N], b[N], p[N], ans[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; for(int i=0;i<n;i++) p[i]=i; sort(p, p+n, [](int x, int y){ return a[x] > a[y]; }); cout<<n/2+1<<'\n'; ans[0] = p[0]; for(int i=1;i<n;i+=2){ if(b[p[i]] > b[p[i+1]]) ans[(i+1)/2] = p[i]; else ans[(i+1)/2] = p[i+1]; } ...

題目連結: http://codeforces.com/problemset/problem/735/C 我覺得這其實滿有趣的(?，我自己是半猜出跟費式數列有關，感覺好像是要找到最大的$i$使得$\sum_{j=0}^{i}F_j \leq n$，但一直不知道為什麼。看了題解才知道原來其實就是我們想想看如果要贏$n$場比賽，那勢必自己要贏$n-1$場，並且找一個贏過$n-2$場的人來打會最好，所以就得到$F_n = F_{n-1}+F_{n-2}$的費式數列公式了XDD。 #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); long long n; cin>>n; long long prepre = 0, pre=1, cnt = 0; int ans; for(ans=0;cnt<n;ans++){ long long cur = prepre+pre; prepre=pre; pre=cur; cnt+=prepre; cerr<<cnt<<'\n'; } cout<<ans-1<<'\n'; return 0; }

題目連結: http://codeforces.com/contest/842/problem/C 一直以為因數個數會太多，所以只打算枚舉質因數.... 但其實直接枚舉因數，然後看看哪個因數個數有超過n-1個之類的就好，枚舉完後把他插進去，讓下面的人來看。(頭痛，有點不知所云OAO #include <bits/stdc++.h> using namespace std; #define PB push_back const int C = 200000 + 5; const int N = 200000 + 5; vector<int> frac[C], G[N]; int arr[N], ans[N], cnt[C]; void sieve(int); void dfs(int,int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); sieve(C); int n; cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; for(int i=1;i<n;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } dfs(1, 1, 0, 0); for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n]; return 0; } void sieve(int n){ for(int i=2;i<n;i++) for(int j=i;j<n;j+=i){ frac[j].PB(i); } } void dfs(int...

題目連結: http://codeforces.com/problemset/problem/735/D IOICamp的時候有提到這題，不過我其實已經忘了結論了www 去翻了一下才知道原來是跟哥德巴赫猜想有關，其猜想簡而言之就是說對於任意一個大於二的偶數，都可以拆成兩個質數相加。所以我們這題的做法就是先看看給定的數是不是質數，如果是當然就輸出1，接下來看他是不是偶數，是的話那根據歌德巴赫猜想，答案應該會是2，而對於一個奇數，我們要先看看他減二是不是質數，是的話輸出2，不是的話輸出3，因為對於一個奇數他一定是拆成一個質數加一個偶數，然後偶數拆成兩個質數，但要是拆出來的偶數是二，那答案就變成2了。 p.s. 附個維基上哥德巴赫猜想的條目 https://zh.wikipedia.org/wiki/哥德巴赫猜想 #include <bits/stdc++.h> using namespace std; bool isprime(int n){ for(int i=2;i*i<=n;i++){ if(n%i==0) return false; } return 1; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; if(isprime(n)) cout<<1<<'\n'; else if(n%2==0 or isprime(n-2)) cout<<2<<"\n"; else cout<<3<<'\n'; return 0; }

題目連結: http://codeforces.com/problemset/problem/731/F 惹...原來可以暴力做。直接枚舉每個人$i$當作leader時的情況，而計算時就是要算$[ik, i(k+1))$的數字數有幾個，因為在這區間的數字$a$再扣完之後一定都變成$ik$。此外枚舉倍數是$nlogn$的(某種調和級數的想法)，所以就照著做囉(? #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 200000 + 5; lld sum[N]; bool isok[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ int x; cin>>x; sum[x]++; isok[x]=1; } for(int i=1;i<N;i++) sum[i]+=sum[i-1]; lld ans = 0; for(int i=1;i<N;i++){ if(!isok[i]) continue; lld cur = 0; for(int j=i;j<N;j+=i) cur += j*(sum[min(j+i,N)-1]-sum[j-1]); ans = max(ans, cur); } cout<<ans<<'\n'; return 0; }

題目連結: http://codeforces.com/problemset/problem/463/E 某種DP感的東東，我的作法大概就是先篩好質因數表，接著DFS下去的時候就把每個數的質因數塞到某個set之類的裡面，而在塞之前可以看一下是不是有前面的人有這個質因數了，然後紀錄一下就好了XD #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const int C = 2000000 + 5; const int N = 100000 + 5; bool notprime[C]; vector<int> frac[C], G[N]; int arr[N], ans[N], dep[N], mp[C]; inline void sieve(int); void dfs(int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); sieve(C); memset(mp, -1, sizeof(mp)); int n, q; cin>>n>>q; for(int i=1;i<=n;i++) cin>>arr[i]; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } dep[1]=1; dfs(1, 1); while(q--){ int tp; cin>>tp; if(tp==1){ ...

題目連結: http://tioj.infor.org/problems/1409 我被雷了才知道原來多邊形也有任$n-1$邊之和大於第$n$邊的事，所以就掃過去紀錄最大值是誰，然後看$sum-max > max$有沒有成立就好了XD #include <bits/stdc++.h> using namespace std; const int N = 1000000 + 5; int main(int argc, char* argv[]){ int n; while(~scanf("%d",&n)){ int mx = -1; long long cnt = 0; for(int i=0;i<n;i++){ int x; scanf("%d",&x); mx = max(mx, x); cnt+=x; } puts((cnt>(mx<<1))?"YES":"NO"); } return 0; }

題目連結: http://codeforces.com/problemset/problem/832/C 煩躁的一題...還因為沒注意到一定要放在整數點卡了一段時間QQ。 作法大概就是對答案二分搜，而驗證的時候，則會發現若是考慮要讓某個人往右的人達到終點，如果直接放在他身上可以，那往他左邊一點可能也可以，所以可以求出一個區間 ；同理往左的也是。這樣就轉化成為先將一堆區間填在數線上，接著詢問一堆區間是否與先前的區間們有碰在一起的地方。而找出對於往右區間的方法這裡是列了$$\frac{x-x^\prime}{s-v}+\frac{10^6-\frac{x-x^\prime}{s-v}\cdot v-x}{s+v} \leq t\\x^\prime \geq 10^6-\frac{v(10^6-x-vt)}{s}-st$$往左的則是$$\frac{x^\prime-x}{s-v}+\frac{x-\frac{x^\prime-x}{s-v}\cdot v}{s+v} \leq t\\x^\prime \leq \frac{v(x-vt)}{s}+st$$ #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second typedef long double llf; typedef long long lld; const int N = 1e6 + 5; int n, s; vector<PII> L, R; lld arr[N]; inline bool isOK(llf); int main(){ cin>>n>>s; for(int i=0;i<n;i++){ PII tp; cin>>tp.FF>>tp.SS; int x; cin>>x; ...

題目連結: http://tioj.infor.org/problems/1846 想了一段時間才想出來，我的數學一定是太爛了QQ。做法就是先用圓心距跟兩個半徑套餘弦定理求出兩個扇形的夾角，那答案就是兩個扇形的面積扣掉兩組半徑所構成的箏形面積，此外記得多判一下兩園沒交點的情況。 #include <bits/stdc++.h> using namespace std; const double PI = acos(-1); inline double dis(double,double,double,double); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while(t--){ int x1, y1, r1; cin>>x1>>y1>>r1; int x2, y2, r2; cin>>x2>>y2>>r2; double dd = dis(x1, y1, x2, y2); if(dd >= r1+r2) cout<<"0.00\n"; else if(dd+min(r1, r2) <= max(r1, r2)) cout<<fixed<<setprecision(2)<<min(r1, r2)*min(r1, r2)*PI<<'\n'; else{ double deg1 = acos((dd*dd+r1*r1-r2*r2)/(2*dd*r1)); double deg2 = acos((dd*dd+r2*r2-r1*r1)/(2*dd*r2)); double ans = r1*r1*deg1+r2*r2*deg2 - ...

題目連結: http://codeforces.com/problemset/problem/785/D 應該稍微簡單想兩下就會發現本題可以大致列出一個式子 $$ \sum_{\forall str[i]=(}{\sum_{j=1}^{\min(L_i, R_i)}{\binom{L_i-1}{j-1} \cdot \binom{R_i}{R_i-j}}} $$ 其中$L_i$代表前$i$個字元中左括號的個數，$R_i$則代表第$i$個字元後右括號的個數，這寫法的想法其實是我從左掃到右，然後計算第$i$個字元為最後一個佐括號時有幾種方法數，但是很明顯如果單單的照這樣做複雜度可能會到$O(n^2)$甚至應該會到$O(n^3)$，所以就需要用數學來把他優化，有個易證的組合恆等式 $$ \sum_{i=0}^{n}{\binom{n}{i} \cdot \binom{m}{i}} = \sum_{i=0}^{n}{\binom{n}{i} \cdot \binom{m}{m-i}} = \binom{n+m}{m} = \binom{n+m}{n}$$ (想像你要挑從$n+m$個東西裡挑$m$個，他不是出現在$n$個的那堆就是出現在$m$個的那堆) 於是乎我們就可以把一開始的式子稍微改寫幾下 $$ \sum_{\forall str[i]=(}{\sum_{j=1}^{\min(L_i, R_i)}{\binom{L_i-1}{j-1} \cdot \binom{R_i}{j}}} \\ = \sum_{\forall str[i]=(}{\sum_{j=1}^{\min(L_i, R_i)}{\binom{L_i-1}{j-1} \cdot \binom{R_i}{R_i-j}}} \\= \sum_{\forall str[i]=(}{ \binom{L_i+R_i-1}{R-1} } $$ 這樣就有了可能還是$O(n^2)$的做法，因為算組合需要$O(n)$，用二項式定理DP也還是$O(n^2)$，所以又要再觀察一點小事。發現你每次往右移動時$L$或$R$都頂多動一而已(即$L_i-L_{i-1}+R_i-R_{i-1} \leq 1 $)，所以算組合的時候也可以用一點基本的乘除運算來達到$O(1)$的轉移!!!，這樣我們就有了$O(n)/O(nlogn)$的...

題目連結: http://arc079.contest.atcoder.jp/tasks/arc079_b 構造題，我的構造方法是假定有$n$個數且要湊出$k$次，讓最後的結果為$n-2, n-2, n-2, \cdots , n-2, n-1$，則稍微算一下後就會發現原始的數字必為$n \lfloor \frac{k}{n} \rfloor - (k - \lfloor \frac{k}{n} \rfloor) + n-2, \cdots , n \lfloor \frac{k}{n} \rfloor - (k - \lfloor \frac{k}{n} \rfloor) + n-2,n \lfloor \frac{k}{n} \rfloor - (k - \lfloor \frac{k}{n} \rfloor) + n-1 $，因為其實對於每個數他其實就只會扣掉$n$ $\lfloor \frac{k}{n} \rfloor$次，並且加上總次數減掉$\lfloor \frac{k}{n} \rfloor$的$1$，所以全部家負號後就變成這樣了，不過餘數的地方要好好處理一下(平均分給別人)，以免有地方不小心太大。 為了怕有數字超過$10^{16}+1000$這裡$N$直接取50即可。 #include <bits/stdc++.h> using namespace std; typedef long long lld; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); lld k;cin>>k; int n=50; cout<<n<<'\n'; for(int i=0;i<n-1;i++){ lld kn = k/n; if(i<k%n) kn++; cout<<n*kn-(k-kn)+n-2<<' '; } lld kn = k/n; cout<<n*kn-(k-kn)+n-1...

題目連結: http://tioj.infor.org/problems/1351 $\sqrt{n}$把數字分解掉，再記錄一下就好了 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t;cin>>t; while(t--){ int x;cin>>x; int sx = ceil(sqrt(x)); vector<int> fac; for(int i=1;i<sx;i++){ if(x%i==0){ fac.PB(i); fac.PB(x/i); } } if(sx*sx==x) fac.PB(sx); lld sm=0; for(auto i:fac) sm+=i; cout<<sm*fac.size()<<'\n'; } return 0; }

題目連結: http://arc077.contest.atcoder.jp/tasks/arc077_b 我賽中的時候蠢蠢的，一直想說要$\binom{n+1}{k}-\sum^{n+1}_{i=1}{\binom{p-1}{i} \times \binom{n+1-q}{n+1-i}}$，後來才發現其實那就等價於$\binom{n+1}{k}-\binom{n-q+p}{k-1}$，其中$p,q$為重複的那兩個數的位置。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 100000 + 5; const int mod = 1000000007; int arr[N], pos[N]; lld moni[N], cmb[2][N]; lld qPow(lld,lld); lld C(int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, p, q;cin>>n; for(int i=1;i<=n+5;i++) moni[i]=qPow(i, mod-2); for(int i=0;i<=n;i++) cin>>arr[i]; fill(pos, pos+1+n, -1); for(int i=0;i<=n;i++){ if(pos[arr[i]]==-1) pos[arr[i]]=i; else{ p=pos[arr[i]]; q=i; break; } } cmb[0][0]=1; cmb[1][0]=1; for(int i=1;i<=n+1;i++){ ...

題目連結: http://tioj.infor.org/problems/1107 裸卡特蘭數題，而卡特蘭數可由$C_0=1$及$C_{n+1}=\frac{2(2n+1)}{n+2} \times C_{n}$的遞迴關係式算出，不過本題要輸出成科學記號有點麻煩，記得處理一下ww #include <bits/stdc++.h> using namespace std; #define N 1000000 struct sciF{ double _a; int _n; inline sciF operator=(int x){ _a=x; _n=0; while(_a>10){ _n++; _a/=10.; } return *this; } inline sciF operator*(int x){ _a*=x; while(_a>10){ _n++; _a/=10.; } return *this; } inline sciF operator/(int x){ _a/=x; while(_a<1){ _n--; _a*=10.; } return *this; } }; bitset<N+5> isset; sciF cc[N+...