0%

基本的因數性質

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;

int main(){
ios::sync_with_stdio(false);

int dt[1000];
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>dt[i];

}
stable_sort(dt,dt+n,[](int a,int b){
int ctA=0,ctB=0;

while(a>=1){
if(a%2==1){
ctA++;
}
a/=2;
}
while(b>=1){
if(b%2==1){
ctB++;
}
b/=2;
}
return ctA<ctB;
});

for(int i=0;i<n;i++){
cout<<dt[i]<<" ";
}
return 0;
}
閱讀全文 »

用 priority_queue 與 unordered_map 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;

int main(){
ios::sync_with_stdio(false);cin.tie(0);

priority_queue<int> mx;
priority_queue<int,vector<int>,greater<int>> mn;
unordered_map<int,int> s;

int t;
while(cin>>t){
if(t==0) break;

if(t==-1){
while(!mn.empty() && !s[mn.top()]){
mn.pop();
}
if(!mn.empty()){
cout<<mn.top()<<' ';
s[mn.top()]--;
mn.pop();
}
}else if(t==-2){
while(!mx.empty() && !s[mx.top()]){
mx.pop();
}
if(!mx.empty()){
cout<<mx.top()<<' ';
s[mx.top()]--;
mx.pop();
}
}else{
s[t]++;
mx.push(t);
mn.push(t);
}
}
return 0;
}
閱讀全文 »

單調對列模板,因為題目的關係所以用 1 開始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;

int idx[5000100],nm[5000100];

int main(){
ios::sync_with_stdio(false);cin.tie(0);
stack<int> st;
int n;
cin>>n;

for(int i=1;i<=n;i++){
cin>>nm[i];
while(!st.empty() && nm[st.top()]<nm[i]){
idx[st.top()]=i;
st.pop();
}

st.push(i);
}

while(!st.empty()){
idx[st.top()]=0;
st.pop();
}

for(int i=1;i<=n;i++){
cout<<idx[i]<<" ";
}
return 0;
}
閱讀全文 »

關於 stack 的應用 ( 經典題 )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>

using namespace std;

int main(){
string c;
while(getline(cin,c)){
stack<int> st;
for(int i=0;i<c.size();i++){
if(isdigit(c[i])){
st.push(c[i]-'0');
}else{
int a=st.top();
st.pop();
int b=st.top();
st.pop();
if(c[i]=='+'){
st.push(b+a);
}else if(c[i]=='-'){
st.push(b-a);
}else if(c[i]=='*'){
st.push(b*a);
}else if(c[i]=='/'){
st.push(b/a);
}else if(c[i]=='%'){
st.push(b%a);
}
}
}
cout<<st.top()<<"\n";
}
return 0;
}
閱讀全文 »

  1. 先安裝 iBus。
    1
    2
    sudo apt-get update
    sudo apt-get install ibus ibus-table
  2. 解壓縮行易官網上的圖像檔與表格檔,並且放到它們該去的位置。
    1
    2
    3
    4
    5
    tar xvf boshiamy-ibus-1-8-x.tar.gz
    cd boshiamy-ibus-1-8-x
    sudo mv *.png /usr/share/ibus-table/icons/
    sudo mv *.db /usr/share/ibus-table/tables/
    ibus restart
  3. 我是在 en-us 的環境下,先跑一趟 Preferences → Language Support 去確認 Keyboard Input method system 設定為 iBus。
  4. 再從 iBus Preferences 裡面的 Input Method 頁籤新增輸入法:Chinese - boshiamy-t。
  5. 順利的話,就可服用嘸蝦米。

用到了 Bellman-Ford Shortist Path Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
using namespace std;
#define INF 1e9

struct edge{
int from,to,cost;
};

int d[505],c[505],n,m;
edge a[10050];

void shortistPath(){
while(1){
bool update=false;
for(int i=0;i<2*m;i++){
if(d[a[i].from]!=INF &&
d[a[i].to]>d[a[i].from]+a[i].cost+c[a[i].to]){
d[a[i].to]=d[a[i].from]+a[i].cost+c[a[i].to];
update=true;
}
}
if(!update) break;
}
}

int main(){
ios::sync_with_stdio(false);cin.tie(0);

cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
d[i]=INF;
}
cin>>m;
for(int i=0;i<m;i++){
cin>>a[i].from>>a[i].to>>a[i].cost;
a[m+i].from=a[i].to;
a[m+i].to=a[i].from;
a[m+i].cost=a[i].cost;
}
d[1]=0;
shortistPath();
if(d[n]!=INF){
cout<<d[n];
}else{
cout<<"-1";
}
return 0;
}
閱讀全文 »

關於樹狀圖的應用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;

int w[2000010]={0},st[10010],child[2000010][2],n,m;

int dfs(int a){
if(a>=n) return w[a];
w[a]=dfs(child[a][0])+dfs(child[a][1]);
return w[a];
}

int findBox(int stw,int a){
if(a>=n){
return a;
}
if(w[child[a][0]]<=w[child[a][1]]){
w[child[a][0]]+=stw;
return findBox(stw,child[a][0]);
}
w[child[a][1]]+=stw;
return findBox(stw,child[a][1]);
}

int main(){
ios::sync_with_stdio(false);cin.tie(0);

cin>>n>>m;
for(int i=0;i<n;i++) cin>>w[n+i];

for(int i=0;i<m;i++) cin>>st[i];

for(int i=1;i<n;i++){
int p,s,t;cin>>p>>s>>t;
child[p][0]=s;child[p][1]=t;
}
int root=1;
w[1]=dfs(root);
for(int i=0;i<m;i++){
cout<<findBox(st[i],root)<<" ";
}

return 0;
}
閱讀全文 »

樹狀圖的結構以及 DFS ( 深度優先搜索 ) ,另外用了 height[] 來儲存高度以降低複雜度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<(b);i++)

long long n;
vector<long long> child[100010];
long long p[100010],height[100010];

void dfs(long long a){
height[a]=0;
for(long long v:child[a]){
dfs(v);
height[a]=max(height[a],height[v]+1);
}
return;
}

int main(){
cin>>n;
For(i,1,n+1){
long long chN;cin>>chN;
For(j,0,chN){
long long ch;cin>>ch;
child[i].push_back(ch);
p[ch]=i;
}
}
int root;
for(root=1;root<=n;root++){
if(p[root]==0) break;
}
dfs(root);
long long total=0;
for(int i=1;i<=n;i++) total+=height[i];
cout<<root<<"\n";
cout<<total<<"\n";
return 0;
}
閱讀全文 »

直接附上範例

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;

int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
for(int i=0;i<1e6;i++){
cout<<i;
}
}
閱讀全文 »