oToToT的code收藏區

題目連結: http://poj.org/problem?id=1769 一開始用cin有把連結斷開還是吃了個TLE QQ。 回到正題，本題我個人的一開始的想法其實是看看某個線段插到線段樹後可以幹嘛，後來想一想後發現有點DP的fu，狀態大概就是$dp[i]$為最遠轉移到i時的最小值，那新增一條線段的時候其實就是查$[l,r]$之間的最小值，然後把$r$那個點設成先前查到的最小值+1，因為$\displaystyle dp[i] = \min_{l \leq j \leq r}dp[j]+1 $，不過實際在寫的時候要再跟原值取個min，因為有可能r被覆蓋很多次之類的。 #include <cstdio> #include <algorithm> using std::min; const int N = 50000 + 10; const int INF = 1<<30; class SegTree{ private: int nodes[N<<2], size; inline int lc(int x){return (x<<1)+1;} inline int rc(int x){return (x<<1)+2;} void build(int l, int r, int id){ nodes[id] = INF; if(r-l>1){ int mid=(l+r)>>1; build(l, mid, lc(id)); build(mid, r, rc(id)); } } void modify(int ql, int qr, int v, int l, int r, int id){ if(qr <= l o...

題目連結: 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://poj.org/problem?id=3468 裸的線段樹，區間加值、區間查和，不過也可以用BIT做掉，不過我不太會QQ #include <iostream> #include <utility> using namespace std; typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int N = 100000 + 5; class SegTree{ private: PLL nodes[N<<2]; int size; inline int lc(int x){return (x<<1)+1;} inline int rc(int x){return (x<<1)+2;} inline void push(int l, int r, int id){ if(r-l>1){ nodes[lc(id)].FF += nodes[id].FF; nodes[rc(id)].FF += nodes[id].FF; } nodes[id].SS += nodes[id].FF * (r-l); nodes[id].FF=0; } inline void pull(int l, int r,int id){ int mid=(l+r)>>1; lld ll = nodes[lc(id)].SS+nodes[lc(id)].FF*(mid-l); lld rr =...

題目連結: http://tioj.infor.org/problems/1316 一開始想錯方向，以為是有一堆開頭跟結尾，然後要選一些之類的...。卡了超久做不出來後，才發現其實它就是一堆線段，然後要選一堆線段，使得同一個位置只能最多被覆蓋到兩次。那其實就直接greedy選右界最靠近左邊的就好了(因為越短，表示你越可以選到後面的)。 這裡寫了個線段樹，來判斷可不可以插入，不過應該可以不用，然後也可以直接$O(N)$的做這個操作XD #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define FF first #define SS second const int N = 4000 + 5; class SegTre{ private: struct node{ int flag=0, val=0; } nodes[N<<3]; int size; inline int lc(int x){return 2*x+1;} inline int rc(int x){return 2*x+2;} inline void push(int l, int r, int id){ if(r-l > 1){ nodes[lc(id)].flag+=nodes[id].flag; nodes[rc(id)].flag+=nodes[id].flag; } nodes[id].val += nodes[id].flag; nodes[id].flag=0; } inline void pull(int id){ ...

題目連結: http://tioj.infor.org/problems/1361 卡了超久....寫了支暴搜對答案也看不出個所以然，最後才發現原來沒保證$a \leq b$，所以要判一下... 回到正題，觀察一下後會發現對於$[1, x]$中出現的0的個數，考慮個位時就是看$\lfloor \frac{x}{10^1} \rfloor$，但考慮十位時則是$\lfloor \frac{x}{10^2} \rfloor \times 10$，稍微想一下就可以推出考慮第$i$位時就是看$\lfloor \frac{x}{10^i} \rfloor \times 10^{i-1}$，不過要稍微注意一下邊界，若是不足$10^{i-1}$時要修正回來。 所以對於$[l, r]$做法就是用算$[0, r]-[0, l-1]$ #include <bits/stdc++.h> using namespace std; typedef long long lld; inline int getSum(int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int l, r; while(cin>>l>>r){ if(l>r) swap(l, r); cout<<getSum(r)-getSum(l-1)<<'\n'; } return 0; } inline int getSum(int x){ if(x<0) return 0; int r=1; for(lld i=10;i<=x;i*=10){ r += (x/i) * (i/10); if((x%i)<(i/10)) r -= (i/10)-(x%i)-1; } return r; }

題目連結: http://tioj.infor.org/problems/1046 一開始看到的時候不知所措，後來瀚瀚(?講了我才知道。其實只要枚舉最上面那排要怎麼按，下面的所有按鈕就可以知道要怎麼按了，因為一定要把上面的按掉這樣，複雜度$O(2^N)$。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define X first #define Y second const int INF = 1000000; char game[10][10]; int n, m; int dfs1(int); int dfs2(); inline bool check(); inline void click(int,int); int main(){ while(true){ char c; for(n=0;;n++){ c=getchar(); for(m=0;c!='\n';m++){ if(c=='#')break; game[n][m]=c; c=getchar(); } if(c=='#')break; game[n][m]='\0'; if(game[n][0]=='\0') break; } if(c=='#')break; m=strlen(game[0]); int ans = dfs1(0); if(ans >= INF) puts("Another Skeleton in the Ancient Tom...

題目連結: http://tioj.infor.org/problems/1331 看一眼大概就可以發現這就是一個經典的矩陣優化DP的題目，稍微算一下後得到轉移矩陣$ \begin{bmatrix} 0 & x \\ 1 & y \\ \end{bmatrix} $，所以要求$a_n$其實就是算$ \begin{bmatrix} a_0 & a_1 \\ \end{bmatrix} \times \begin{bmatrix} 0 & x \\ 1 & y \\ \end{bmatrix}^n = \begin{bmatrix} a_n & a_{n+1} \\ \end{bmatrix}$ ，然後冪次的部分用快速冪解決。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef unsigned long long llu; const llu mod = 1LL<<32; auto A = new llu[2][2]; auto B = new llu[2][2]; auto C = new llu[2][2]; auto F = new llu[2][2]; void mTimes(llu[2][2],llu[2][2],llu[2][2],int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); lld n, a, b, x, y; while(cin>>n, n>=0){ cin>>a>>b>>x>>y; F[0][0]=a; F[0][1]=b; A[0][0]=0; A[0][1]=x; A[1][0]=1; A[1][1]=y; B[0][0]=...