TIOJ 1726 Dice Wars

  老實說 我這題真的AC得很莫名其妙
本來一點想法也沒有 然後用一些詭異的優化答案就出來了?!

先不管複雜度 說說中心思想

先開n個vector
然後若是第i個位置是k
那麼在第 k 個vector丟入i

若詢問為a,b

那麼就是將所有a所在的位置
都詢問離該點最近的 b 的位置(在b的vector做lower_bound)

所以這樣每步就會是 O( SZ(vec[a]) lg( SZ(vec[b]) ) )
很明顯若是 SZ(vec[a])>SZ(vec[b])
我們可以交換a,b 達到較好的複雜度

最後
有兩個小小技巧
1.
把所有已經回答的詢問存起來
要是以前已經問過 就可以直接回答
2.
如果有連續三個以上一樣的數字
中間的可以全部都不要存

然後我就不會算複雜度了
但是有一種構造方法可以弄成O(n*sqrt(n)*lg(n) )
就是共sqrt(n)個數字 每個數字有sqrt(n)個
詢問種類最多約 sqrt(n)*sqrt(n)/2
每個次詢問是sqrt(n) lg(n)
所以是O(sqrt(n)*sqrt(n)/2*sqrt(n)*lg(n))=O(n*sqrt(n)*lg(n) )

如果有神人會證複雜度務必告訴我

2018/3/8 補證明
我們已經知道每次詢問複雜度是O( SZ(vec[a]) lg( SZ(vec[b]) ) )
假設SZ(vec[a])<=SZ(vec[b])
考量下列兩種情形

1 . SZ(vec[a])<=sqrt(n)
　這時每次詢問都是O( sqrt(n) lg( n ) )
　總詢問q次　所以此部分詢問複雜度是O( q sqrt(n) lg( n ) )

2 . sqrt(n)<=SZ(vec[a])<=SZ(vec[b])
　我們知道大小大於sqrt(n)的vec，最多只有sqrt(n)個
　也就是說，要在此情形詢問vec[a]，最多只會問sqrt(n)次
　也就是說，對於vec[a]裡面每一個元素，最多只會問sqrt(n)次
　而總元素數量是n，所以總複雜度就是O( n sqrt(n) lg( n ) )

所以此題的複雜度就是O( (n+q) sqrt(n) lg( n ) )

#include <bits/stdc++.h>
using namespace std;
//type
typedef long long ll;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef priority_queue<pll,vector<pll>,greater<pll> > heap;
typedef vector<int>::iterator iter;
//macro
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REP1(i,a,b) for(ll i=(a);i<=(b);i++)
#define mkp make_pair
#define pb push_back
const int INF=1e9;
const ll MA=1e6+5;
const ll MOD=1e9+7;
//}}}
int n,m;
vector<int> v[60010];
map<pii,int> mp;
int arr[60010];
int main(){
 ios_base::sync_with_stdio(0); cin.tie(0);
 cin>>n>>m;
 int k;
 for(int i=1;i<=n;i++)
  cin>>arr[i];
 for(int i=1;i<=n;i++){
  if(arr[i-1]!=arr[i]||arr[i+1]!=arr[i])
   v[arr[i]].emplace_back(i);
 }
 int a,b;
 while(m--){
  cin>>a>>b;
  if(!SZ(v[a])||!SZ(v[b])){
   cout<<"-1\n";
   continue;
  }
  if(a==b){
   cout<<"0\n";
   continue;
  }
  if(a>b) swap(a,b);
  if(mp.find({a,b})!=mp.end()){
   cout<<mp.find({a,b})->second<< '\n';
   continue;
  }
  if(SZ(v[a])>SZ(v[b])) swap(a,b);
  int mi=INF;
  for(int i=0,si=SZ(v[a]);i<si;i++){
   int x=lower_bound(ALL(v[b]),v[a][i])-v[b].begin();
   if(x!=SZ(v[b])) mi=min(mi,v[b][x]-v[a][i]);
   if(x){
    x--;
    mi=min(mi,v[a][i]-v[b][x]);
   }
  }
  cout<<mi<< '\n';
  if(a>b) swap(a,b);
  mp[{a,b}]=mi;
 }
 return 0;
}

ZJ d374 X^2 ≡ 1 (mod M)

這是一個數學題

吧

總之模運算什麼的不提了

直接說兩個性質

一：

設F為M的一個因數

若X^2 ≡ 1 (mod M)

則X^2 ≡ 1 (mod F)

二：

若M為質數

X^2 ≡ 1 (mod M)

的X值

只有 1 和 M-1

根據性質二

若M是質數就可以直接回答

若不是質數

可以用一點點有技巧的枚舉

先找出M的因數中

大於等於sqrt(m)的最小的因數

設此數為F

可知

F>=sqrt(m)

先以F為基準

找出所有X^2 ≡ 1 (mod F) 的X  (X<F)

然後將所有找出來的數

枚舉加上kF (最多加M/F次)

看看是否符合 X^2 ≡ 1 (mod M)

若是就加到答案裡

至於複雜度我不會算XD

跪求神人解答

以下附code ：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,p,sq;
vector<ll> ans;
inline bool che(ll k){
 return k*k%m==1;
}
bool is_prime(){
 for(ll i=2;i<=sq;i++)
  if(m%i==0)
   return 0;
 return 1;
}
void solve(){
 ll fac=-1;
 for(ll i=sq;i>=2;i--)
  if(m%i==0){
   fac=i;
   break;
  }
 fac=m/fac;
 vector<ll> mia;
 mia.clear();
 for(ll i=1;i<fac;i++)
  if(i*i%fac==1)
   mia.push_back(i);
 for(ll i=0;i<m;i+=fac)
  for(ll j=0;j<mia.size();j++)
   if(che(i+mia[j]))
    ans.push_back(i+mia[j]);
}
void output(){
 cout<<ans.size()<<'\n';
 for(int i=0;i<ans.size();i++)
  cout<<ans[i]<<'\n';
}
int main(){
 cin>>m;
 // 先將一和二例外判掉
 if(m==1){
  cout<<"0\n";
  return 0;
 }
 else if(m==2){
  cout<<"1\n1\n";
  return 0;
 }
 sq=sqrt(m);
 if(is_prime()){ 
  cout<<"2\n";
  cout<<1<<'\n';
  cout<<m-1<<'\n';
  return 0;
 }
 solve();
 output();
}

四邊形優化 / TIOJ 1283 超大畫框設置

　　本題為四邊形優化。
　　在這之前我花了很多時間讀四邊形優化，然後都看不懂QQ。直到今天我才真正看懂1D/1D凹性以及1D/1D凸性優化。我認為四邊形優化真的很難，我在網路上有看到很多關於四邊形優化的說明，像是建中講義以及吳仲昇的chino，但是在下才疏學淺、數學不好、不懂繁雜的符號，最後看到了2014資訊之芽的講義才完全理解。因此在此我要說明一下我對於四邊形優化的理解，希望能幫到普羅大眾，至於嚴謹的說明以及證明我就不解釋了，這部分可以參閱吳仲昇的chino，直接google "四邊形優化" 第一個應該就是他吧。

1D/1D的優化簡單來說：
就是有一個二維的DP表格，這個表格符合某種單調性（以下會解釋）。
而我們想要求的是，整個表格的極值。

(圖片取自建中講義)

這是一個DP表格
(左下角的狀態不存在 所以圖中把它省略了)

在這個表格中，所有的狀態都可以在前面的狀態已經做好的情況下O(1)求得，所以很當然的有O(N^2)的作法。

一般做法是一次做一行(在此直排稱為行)，每行先各自找出最優解，然後再比較每行的最優解即可。

而「優化」也是一行一行做，每當有一個列能夠插入時，就將之插入，並維護當前最優解，這種東西的複雜度可以均攤到O(1)+O(lgN)=O(lgN) 所以總共是O(NlgN)。

以下將說的更詳細一點。

首先，我們要知道甚麼是單調性，
在此不贅述四邊形不等式(可以參閱吳仲昇的chino)
簡而言之，單調性在這裡的呈現就是
每行最優解的位置會遞增(或遞減)(圖片右上角)

利用這個特性，我們就可以做出這樣的算法：
下列步驟執行n次(假設有n列)

1.插入新的一列
2.維護每一行的＂目前＂最優解

诶诶诶 ＂目前＂是甚麼東西
舉個例子好了

左邊第一張圖：
就是做好第一＂列＂的時候的樣子。

你可能會表示：
我只看到一列而已啊！

是的，這表示 當前的最優解的列範圍，只有包含第一列。


第二張圖：
我們要執行第二次了
所以我們來插入第二列

第三張圖：
是第二列插入完成的時候的樣子

而當前的最優解的列範圍，有包含第一列還有剛剛插入的第二列，總共兩列，也就是說當前每行的最優解不是在第一列就是在第二列。

因此以上的＂目前＂就是指，當下已經有存在的列。


那麼是說 在做同一行時，有沒有可能一次要插入多列、或不用插入？
這是有可能的。
像是以下的表格，只要它符合四邊形不等式的性質，也適用四邊形優化。

因此表格的形狀是無關緊要的，並不是說每做一行 就要插入一列。










接下來終於要說實作的部分了

首先要說明
存區間的容器是deque
存區間的方法是存左右界

看看同一張圖
很明顯的
我們正在做第i列
由於解答會有往右上的趨勢
所以說
可能變以下左圖，也可能變以下右圖。

所以我們的步驟是
1.看看能不能把C全部都殺掉

方法就是跟C的最後一行那格比比看
要是可以 ，就代表贏了整個C（就像右上那張圖）
就可以一次pop掉整個C
然後繼續對B做一樣的事
直到最後贏不了

2.贏不了之後
代表兩列最優解的斷層
就在最後沒有被pop掉的區間內
所以可以對這個區間做二分搜

然後就可以把原本的區間的左界改一下
然後再push新的最優解列即可

在這兩個步驟中
步驟1均攤是O(1)
因為每次都push一個區間而已
所以總共最多pop n個

步驟2則是二分搜
即為O(lgn)

所以總共O(NlgN)
------------------------------------------------------------------------------
最後
我們回到題目

它的狀態是
以i作為頂邊
以j作為底邊
的面積

面積很好求
左右界的交集*上下界的差距就是了( O(1) )
所以原本是O(n^2)
然後我們會發現它的單調性
枚舉底邊
使用的頂邊具有單調性(就是只會一直往右下使用 不會往回)
變成O(NlgN)

補充一些實作上的細節
由於我們主要是想要求每行的最大值
所以在插入列時
就是以行為主體
看看能插到哪列
就一次插完
所以實作上就會變得像是枚舉行
因此每次做完一些列
就可以得到該行的最大值

以下是我的AC code作為參考。

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	int n, m;
	ll tl[100010], th[100010], bh[100010], bl[100010], ans;
	inline ll cnt(ll a,ll b){
	return max( (tl[b] - bl[a-1]) * (bh[a] - th[b]) , 0LL);
	}
	struct qd{
	int l, r, h;
	};
	int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	n >>= 1;
	for(int i = 1; i <= n; ++i)
	cin >> tl[i] >> th[i + 1];
	for(int i = 2; i <= n; ++i){
	tl[i] += tl[i - 1];
	th[i + 1] += th[i];
	}
	cin >> m;
	m >>= 1;
	for(int i = 1; i <= m; ++i)
	cin >> bh[i] >> bl[i];
	for(int i = 2; i <= m; ++i){
	bh[i] += bh[i - 1];
	bl[i] += bl[i - 1];
	}
	deque<qd> sk;
	sk.push_back({1, m, 1});
	int p = 2;
	for(int i = 1; i <= m; ++i){
	if(sk.front().r < i)
	sk.pop_front();
	sk.front().l = max(sk.front().l, i);
	while(p <= n && bh[i] > th[p]){
	while( sk.size() && cnt(sk.back().l, sk.back().h) < cnt(sk.back().l, p) )
	sk.pop_back();
	if(sk.empty())
	sk.push_back({i, m, p});
	else{
	int hi = sk.back().r + 1;
	int de = sk.back().l;
	while(de < hi - 1){
	int mid = de + hi >> 1;
	if(cnt(mid, p) > cnt(mid, sk.back().h))
	hi = mid;
	else
	de = mid;
	}
	sk.back().r = de;
	if(hi <= m) sk.push_back({hi, m, p});
	}
	++p;
	}
	ans = max(ans, cnt(i, sk.front().h));
	}
	cout << ans << '\n';
	}

view raw weed.cpp hosted with ❤ by GitHub

TIOJ 1205 直角三角形

    第一次寫極角排序,用了一些不是很尋常的方法,然後就變成topcoder了
先講講這題的做法吧,首先很明顯枚舉可以做到n^3,
但是這個複雜度我們不是很滿意(其實寫得好,n^3可以過,因為時間限制7秒),
所以想到了一個方法,枚舉是直角的那個點,每次枚舉都做極角排序,
然後用爬行法找出所有以該點為直角的所有三角形,
這樣就可以很健康的1秒內通過

以下有很多其他細節
1.內積外積的等等操作,就不多贅述
2.我的極角排序方法是,先偵測它是否>=π,若是其中一個>=π,而另一個沒有
   就可以直接判斷它的大小,而若是都有或都沒有,就可以保證兩角相差<π,
   這時再用外積比較即可
3.爬行的部分是最容易寫錯的,我就de了好久的bug
   首先我們用p1和p2指向兩個點,比較 p2的角度 和 p1的角度+π/2
   若是前者大(相差超過π/2),那就 p1++
   若是後者大(相差小於π/2),那就 p2++
   而若是相同,那麼答案就可以++,並繼續找下一個p2
   不過有兩點要注意:
   就是p2不能繞一圈之後超過p1 否則會重複計算 所以才有以下 if(p2>=p1+si)break;
   再來是判斷 p2的角度 大於 p1的角度+π/2 的方法 是內積和外積都要>=0
   不是只有內積喔(否則若是差距超過 3/2π 的也會被判定成在π/2內)
   而剩下判斷相差是否在π/2內就只要內積<0即可
   相差剛好是π/2就是內積為0 這不用多說

   以下就是我的code

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> vec;
vec operator+(vec k,vec l){
return {k.X+l.X,k.Y+l.Y};
}
vec operator-(vec k,vec l){
return {k.X-l.X,k.Y-l.Y};
}
ll operator*(vec k,vec l){
return k.X*l.X+k.Y*l.Y;
}
ll operator^(vec k,vec l){
return k.X*l.Y-k.Y*l.X;
}
ll n,x,y;
vec po[1510];
bool cmp(vec a,vec b){
if((a.Y>0||(a.Y==0&&a.X>0))&&(b.Y<0||(b.Y==0&&b.X<0)))
return 1;
if((b.Y>0||(b.Y==0&&b.X>0))&&(a.Y<0||(a.Y==0&&a.X<0)))
return 0;
return (a^b)>0;
}
int dec(int now){
x=po[now].X; y=po[now].Y;
vec *arr=new vec[3010];
int p=0;
int si=n-1;
for(int i=0;i<n;i++){
if(i==now)
continue;
arr[p++]=po[i]-po[now];
}
sort(arr,arr+si,cmp);
for(int i=0;i<si;i++)
arr[i+si]=arr[i];

int p1=0,p2=1;
int ans=0;
while(p1<si){

if(((arr[p1])*(arr[p2]))<0||((arr[p1])^(arr[p2]))<0){
p1++;
continue;
}
if(((arr[p1])*(arr[p2]))>0){
p2++; if(p2>=p1+si) break;
continue;
}
int nu=0;
while(((arr[p1])*(arr[p2]))==0&&((arr[p1])^(arr[p2]))>=0){
nu++;
p2++;
if(p2>=p1+si)
break;
}
ans+=nu;
p2-=nu;
p1++;
}
delete arr;
return ans;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
while(cin>>n){
if(!n)
return 0;
int ans=0;
for(int i=0;i<n;i++)
cin>>po[i].X>>po[i].Y;
for(int i=0;i<n;i++)
ans+=dec(i);
cout<<ans<<'\n';
}
}

TIOJ 1628 組合布丁

    又是個DP呵呵(本人超愛DP)
首先,我們把所有的口味排序,然後找出每種口味有幾個
假設共a種口味 而每種有xi個(Σxi=k)

然後就來定義狀態:
dp[i][j]表示前i種口味取j個的取法數

而第i種口味有xi個 所以它的數量是

轉移方程:dp[i][j]=dp[i-1][j-0]+dp[i-1][j-1]+dp[i-1][j-2]......dp[i-1][j-xi];
(第i種口味有 0個的數量 + 1個的 + 2個的......)
而邊界條件很簡單dp[0][0]=1;

這樣大致上就完成了
然後再把二維陣列壓成一維就好,使用滾動數組
以下是我的code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll n,k,m;
ll dp[2][5010];
ll pud[5010];
vector<pll> typ;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
while(cin>>n>>k>>m){
for(int i=0;i<n;i++)
cin>>pud[i];
sort(pud,pud+n);
typ.clear();
//判斷每種有幾個
typ.push_back({pud[0],1});
int si=0; //vector的大小
for(int i=1;i<n;i++){
if(pud[i]==typ[si].first)
typ[si].second++;
else{
typ.push_back({pud[i],1});
si++;
}
}
si++;
//重複利用 pud 只存每種有幾個
for(int i=0;i<si;i++)
pud[i]=typ[i].second;

memset(dp,0,sizeof dp);
//第0列表示計算至前一種布丁的狀態
//第1列表示當下要計算的第l種布丁

dp[0][0]=1; //第前0種取0個的方法數是1
for(int l=0;l<si;l++){
for(int i=1;i<=k;i++){
for(int j=0;j<=pud[l];j++){
if(i-j<0)
break;
dp[1][i]+=dp[0][i-j];
dp[1][i]%=m;
}
}
//存回去上一列
for(int i=1;i<=k;i++){
dp[0][i]=dp[1][i];
dp[1][i]=0;
}
}
cout<<dp[0][k]<<'\n';
}
}

TIOJ 1058 兩個數字

        由於某位大神的需要,半夜又重新打開電腦打了這篇,這是一個非常麻煩的判斷題

但是如果某些東西運用得當,可以省下不少功夫,在此,我就說說我的簡易作法給各位參考

        首先,題目的麻煩之處,在於小數點以下可能會超出double範圍,所以就得用類似大數的處理方法,而我的方法是先當作c++型字串的string 輸入再處理,以下是我的處理方法

1.利用stringstream轉成浮點數先來大略判定大小

2.要是無法分出大小,可知double可儲存的範圍內,必定相同,所以整數部分必相同,整數位數亦然

    所以從頭開始比較大小即可,而題目說兩數不會相同,所以無須判定相同情況

因此,就有以下的code
p.s. stringstream的清除 一定要ss.clear();和ss.str(""); 缺一不可

#include <bits/stdc++.h>
using namespace std;
string s1,s2;
stringstream ss;
int main(){
 while(cin>>s1>>s2){
  int d1,d2;
  ss<<s1;
  ss>>d1;
  ss.clear();
  ss.str("");
  ss<<s2;
  ss>>d2;
  if(d1>d2)
   cout<<s1<<'\n';
  else if(d2>d1)
   cout<<s2<<'\n';
  else{
   for(int j=0;;j++){
    if(s1[j]>s2[j]){
     cout<<s1<<'\n';
     break;
    }
    else if(s2[j]>s1[j]){
     cout<<s2<<'\n';
     break;
    }
   }
  }
 }
}

TIOJ 1007 燈泡問題

　　這題幾天前就ＡＣ了,但是今天回去看了我的code,發現我根本不知道我在寫什麼ＱＱ

所以我以後打算稍微記下來,不然忘記很痛苦欸,還讓我去看日劇放鬆一下

　　這題很明顯就是ＤＰ,由於數字範圍不大,開個二維陣列不是問題,所以直接開始想狀態和轉移方程

我的想法就很簡單,如果當前要求時間長度為k的答案（最長持續亮時間仍是n),

可以分開討論

1,最後一格是暗的＝＞條件為＂時間長度為k-1"（最長持續亮時間是n)

2,最後一格是亮的＝＞條件為＂時間長度為k-1　且　末端的最長持續亮時間是n-1＂

那麼來定義狀態

dp[x][y]是指　時間長度為x ,而末端的最長持續亮時間是y

轉移方程就會變成

dp[x][y]=dp[x-1][n]+dp[x-1][y-1];

而dp[x][0]就是dp[x-1][n];

而邊界條件呢？

dp[1][0]=1 由於末端不能亮（最長持續亮時間是0) 所以只能是暗的

dp[1][y]=2 for 1<=y<=n 亮或不亮皆可

這樣就解決了這題　時間複雜度是Ｏ(mn) 空間複雜度也是Ｏ(mn) 

可是是說空間好像可以壓縮欸,每次轉移都只有用到上一列的狀態

所以可以把列數省略掉　dp[m][n]變成　dp[n] 而空間變成Ｏ(n)

這樣　就有以下的code

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll n,m;
ll dp[16];
int main(){
cin>>n>>m;
dp[0]=1;
for(int i=1;i<=n;i++){
dp[i]=2;
}
for(int i=2;i<=m;i++){
ll x=dp[n];
for(int j=n;j>0;j--){
dp[j]=x+dp[j-1];
}
dp[0]=x;
}
cout<<dp[n]<<'\n';
}