2016年10月20日 星期四

TIOJ 1733 - 最大二維子矩陣

http://tioj.infor.org/problems/1733

跟1277很像
不過因為不能不拿 所以最大值的預設值隨便給個-INF就好了

 

 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
#include<bits/stdc++.h>
using namespace std;

int rn,cn;
int m[55][55];
int add[55][55];

int main(){
    while(cin>>rn>>cn){
        memset(m,0,sizeof(m));
        memset(add,0,sizeof(add));
        for(int i=1;i<=rn;i++){
            for(int j=1;j<=cn;j++){
                cin>>m[i][j];
                for(int k=1;k<=i;k++){
                    add[k][j]+=m[i][j];
                }
            }
        }
        int mx=-(1<<28);
        for(int i=1;i<=rn;i++){
            for(int j=i;j<=rn;j++){
                int cur=0,prv=0;;
                for(int k=1;k<=cn;k++){
                    cur+=(add[j][k]-add[i-1][k]);
                    mx=max(mx,cur);
                    if(cur<add[j][k]-add[i-1][k])cur=add[j][k]-add[i-1][k];
                    mx=max(mx,cur);
                }
            }
        }
        cout<<mx<<endl;
    }
}
張貼者： 於 沒有留言:

TIOJ 1277 - 俄羅斯娃娃－續

http://tioj.infor.org/problems/1277

枚舉上下界 $O(n^2)$
壓縮起來變成一維 然後再 $O(n)$ 跑過去求max就好了



 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
50
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define ld long double
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
#define pii pair<int,int>
#define vint vector<int>
#define rz(x) resize(x)
#define X first
#define Y second
// #define m (l+r)/2
// #define xm (x1+x2)/2
// #define ym (y1+y2)/2
#define DE cout<<"de"<<endl;
#define PQ priority_queue

int n,i,j,k,l;
ll a[502][502],ans,now,mx,rr[502][502];

inline void t(int &x,int &y){
    now=0,mx=0;
    for(l=1;l<=n;l++){
        now+=(rr[y][l]-rr[x-1][l]);
        if(now<0)now=0;
        mx=max(mx,now);
    }
    ans=max(mx,ans);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            cin>>a[i][j];
            for(k=1;k<=i;k++){
                rr[i][j]+=a[k][j];
            }
        }
    }
    for(i=1;i<=n;i++){
        for(j=i;j<=n;j++){
            t(i,j);
        }
    }
    cout<<ans<<endl;
}
張貼者： 於 沒有留言:

TIOJ 1211 - 圖論 之 最小生成樹

http://tioj.infor.org/problems/1211

校隊培訓裡面的某題
因為一開始做kruskal
然後大家都在寫prim覺得也來寫寫看 
然後覺得好慢又用priority_queue優化

 所以這次code有三種寫法喔OwO

 跑這題的時間大概分別是 640ms, 7000ms, 500ms

 kruskal : 

 
 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;

struct edge{
    int l,r,c;
    friend bool operator > (const edge &l,const edge &r){
        return l.c>r.c;
    }
};

int m,n,i,j,c,lo,s[10005],ans,sz[10005],apped[10005],appcnt;
priority_queue<edge,vector<edge>,greater<edge> > pq;
void C();
void Init();

int F(int a){
    if(a==s[a])return a;
    return s[a] = F(s[a]);
}
inline bool U(int a,int b){
    a=F(a),b=F(b);
    if(a==b)return 0;
    if(sz[b]<sz[a])swap(a,b);
    s[a]=b;
    sz[b]+=sz[a];
    return 1;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    while(cin>>n>>m && m && n){
        C();

        for(lo=0;lo<m;lo++){
            cin>>i>>j>>c;
            pq.push({i,j,c});
        }

        Init();

        while(pq.size()){
            edge e=pq.top();
            pq.pop();
            if(U(e.l,e.r)){
                ans+=e.c;
            }
        }
        if(sz[F(1)]!=n){
            cout<<"-1\n";
        }
        else{
            cout<<ans<<endl;
        }
    }
}

inline void C(){
    memset(s,0,sizeof(s));
    memset(sz,0,sizeof(sz));
    ans=0;
    while(pq.size())pq.pop();
}
inline void Init(){
    for(lo=0;lo<=n;lo++){
        s[lo]=lo;
        sz[lo]=1;
    }
}

prim : 

 
 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
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#define pii pair<int,int>
#define X first
#define Y second
using namespace std;
int n,m;
vector<pii> G[10003];
bitset<10003> ined;
int dist[10003];
int ans;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while(cin>>n>>m && n){
        for(int i=0;i<10003;i++)G[i].clear();
        ined.reset();
        memset(dist,0,sizeof(dist));
        ans=0;
        for(int i=0;i<m;i++){
            int z,x,c;
            cin>>z>>x>>c;
            G[z].push_back({x,c});
            G[x].push_back({z,c});
        }
        memset(dist,0x7f,sizeof(dist));
        dist[1]=0;
        for(int ppp=0;ppp<n;ppp++){
            int nowc=-1,noww=0x7f7f7f7f;
            for(int i=1;i<=n;i++){
                if(!ined[i] && dist[i]<noww){
                    nowc=i;
                    noww=dist[i];
                }
            }
            if(nowc==-1){
                break;
            }
            // cout<<"join:nowc:"<<nowc<<endl;
            ined[nowc]=1;
            ans+=noww;
            for(int i=0;i<(int)G[nowc].size();i++){
                if(!ined[G[nowc][i].X] && G[nowc][i].Y < dist[G[nowc][i].X]){
                    dist[G[nowc][i].X]=G[nowc][i].Y;
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(!ined[i]){
                cout<<"-1\n";
                goto jizz;
            }
        }
        cout<<ans<<endl;
        jizz:;
    }
}

prim + priority_queue : 


 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
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int n,m;
struct node{int pt,val;};
vector<node> G[10003];
bitset<10003> ined;
int dist[10003];
int ans;
int ppp,i;
priority_queue<node,vector<node>,greater<node>> pq;
bool operator>(const node &a,const node &b){
    return a.val>b.val;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while(cin>>n>>m && n){
        for(i=1;i<=n;i++)G[i].clear();
        ined.reset();
        memset(dist,0,sizeof(dist));
        ans=0;
        while(pq.size())pq.pop();
        for(int i=0;i<m;i++){
            int z,x,c;
            cin>>z>>x>>c;
            G[z].push_back({x,c});
            G[x].push_back({z,c});
        }
        memset(dist,0x7f,sizeof(dist));
        dist[1]=0;
        pq.push({1,0});
        for(ppp=0;ppp<n;ppp++){
            int nowc=-1;
            while(pq.size() && ined[pq.top().pt]){
                pq.pop();
            }
            if(!pq.size()){
                break;
            }
            nowc=pq.top().pt;
            ined[nowc]=1;
            // cout<<"join:nowc:"<<nowc<<endl;
            ans+=pq.top().val;
            for(i=0;i<(int)G[nowc].size();i++){
                if(!ined[G[nowc][i].pt] && G[nowc][i].val < dist[G[nowc][i].pt]){
                    dist[G[nowc][i].pt]=G[nowc][i].val;
                    pq.push({G[nowc][i].pt,dist[G[nowc][i].pt]});
                }
            }
        }
        for(i=1;i<=n;i++){
            if(!ined[i]){
                cout<<"-1\n";
                goto jizz;
            }
        }
        cout<<ans<<"\n";
        jizz:;
    }
}
張貼者： 於 沒有留言:

TIOJ 1125 - 組合電路的模擬

http://tioj.infor.org/problems/1125

每次跑太麻煩了
反正狀態不多 所以直接先建表然後直接查就好

那時候不知道stringstream可以直接.clear() 然後就宣告了一堆= =


 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
#include<bits/stdc++.h>
using namespace std;

map<string,bitset<3> > ina;
map<string,int> inf;

int main(){
    for(int i=0;i<32;i++){
        bitset<5> bs(i);
        bitset<4> o;
        bitset<3> f;
        o[3]=!(bs[4]&bs[3]);
        o[2]=!(bs[3]&bs[2]);
        o[1]=!(bs[2]&bs[1]);
        o[0]=!(bs[1]&bs[0]);
        f[2]=!(o[3]&o[2]);
        f[1]=!(o[2]&o[1]);
        f[0]=!(o[1]&o[0]);
        stringstream ss;
        ss<<bs;
        string s;
        ss>>s;
        ina[s]=f;
        stringstream sss;
        sss<<f;
        string ssss;
        sss>>ssss;
        inf[ssss]++;
    }
    string s;
    while(cin>>s){
        if(s.length()==5){
            cout<<ina[s]<<endl;
        }
        else{
            cout<<inf[s]<<endl;
        }
    }
}
張貼者： 於 沒有留言:

TIOJ 1113 - [入門] Evanesco

http://tioj.infor.org/problems/1113

還是勇敢的dfs下去
不過因為要照字典序 然後把全排列弄出來之後再sort會很慢
所以就直接先對原本的字串sort然後照順序拿就好了

 

 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;
string s;
bool took[8];
vector<string> ans;
void t(string now){
    if(now.length()==s.length()){
        ans.push_back(now);
        return;
    }
    for(int i=0;i<s.length();i++){
        if(!took[i]){
            took[i]=1;
            t(now+s[i]);
            took[i]=0;
        }
    }
    return;
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    while(cin>>s){
        sort(s.begin(),s.end());
        memset(took,0,sizeof(took));
        ans.clear();
        t("");
        for(auto i:ans)cout<<i<<endl;
        cout<<endl;
    }
}
張貼者： 於 沒有留言:

TIOJ 1109 - [入門] Anapneo

http://tioj.infor.org/problems/1109

直接輸出 什麼都不用管(?

沒有版的code還是好可愛

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int n,k,i;
string s;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    while(cin>>n>>k){
        for(i=0;i<n;i++){
            cin>>s;
            if(i==n-k){
                cout<<s<<'\n';
            }
        }
    }
}
張貼者： 於 沒有留言:

TIOJ 1108 - 樹的三兄弟

http://tioj.infor.org/problems/1108

 有點煩的一題 遞迴處理
因為可以想到 在前序中的第一個字會是樹根
然後中序中 樹根會剛好把左右邊兩顆子樹分開
所以遞迴找根就好了

覺得沒有板的code好短好可愛(?

 

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

string _(string pre,string in){
    // cout<<"pre="<<pre<<", in="<<in<<endl;
    assert(pre.length()==in.length());
    if(pre.length()<=1)return pre;
    int in_pos=in.find(pre[0]);
    string left_pre = pre.substr(1,in_pos);
    string right_pre = pre.substr(in_pos+1,pre.length()-in_pos-1);
    string left_in = in.substr(0,in_pos);
    string right_in = in.substr(in_pos+1,pre.length()-in_pos-1);

    // cout<<left_in<<" "<<right_in<<endl;
    return _(left_pre,left_in)+_(right_pre,right_in)+pre[0];
}

int main(){
    string pre,in;
    while(cin>>pre>>in){
        string ans = _(pre,in);
        cout<<ans<<endl;
    }
}
張貼者： 於 沒有留言:

toj 259 - 竹園崗

http://toj.tfcis.org/oj/pro/259/

 正的做一次LIS 逆的再做一次LIS
然後兩邊交起來取max就過惹


 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define ld long double
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
#define pii pair<int,int>
#define vint vector<int>
#define rz(x) resize(x)
#define X first
#define Y second
// #define m (l+r)/2
// #define xm (x1+x2)/2
// #define ym (y1+y2)/2
#define DE cout<<"de"<<endl;
#define PQ priority_queue

inline int rit(){
    int t=0,k=1;
    char c;
    do{
        c=getchar();
        if(c=='-')k=-1;
    }while(c<'0'||c>'9');
    do{
        t=t*10+c-'0';
        c=getchar();
    }while(c>='0'&&c<='9');
    return t*k;
};

int n;
int a[10005],l[10005],r[10005];
int pos[10005],len;
int mx;

int main(){
    while(cin>>n){
        memset(a,0,sizeof(a));
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        memset(pos,-1,sizeof(pos));
        len=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(a[i]>pos[len-1]){
                pos[len++]=a[i];
            }
            else{
                *lower_bound(pos,pos+len,a[i])=a[i];
            }
            l[i]=len;
        }
        len=0;
        memset(pos,-1,sizeof(pos));
        for(int i=n-1;i>=0;i--){
            if(a[i]>pos[len-1]){
                pos[len++]=a[i];
            }
            else{
                *lower_bound(pos,pos+len,a[i])=a[i];
            }
            r[i]=len;
        }
        mx=0;
        for(int i=0;i<n;i++){
            mx=max(min(l[i],r[i])*2-1,mx);
        }
        // cout<<"l:";for(int i=0;i<n;i++)cout<<l[i]<<" ";cout<<endl;
        // cout<<"r:";for(int i=0;i<n;i++)cout<<r[i]<<" ";cout<<endl;
        cout<<mx<<endl;
    }
}
張貼者： 於 沒有留言:

TIOJ 1025 - 數獨問題

http://tioj.infor.org/problems/1025

 就判斷還有哪些可以填 然後勇敢的dfs下去吧(?



 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define ld long double
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
#define pii pair<int,int>
#define vint vector<int>
#define rz(x) resize(x)
#define X first
#define Y second
// #define m (l+r)/2
// #define xm (x1+x2)/2
// #define ym (y1+y2)/2
#define DE cout<<"de"<<endl;
#define PQ priority_queue

int s[10][10];
bool posi[10];
int ans;

void put(int x,int y){
    bool bye=0;
    for(int i=x;i<=9;i++){
        for(int j=y;j<=9;j++){
            if(s[i][j]==0){
                memset(posi,1,sizeof(posi));
                for(int ii=(i-1)/3*3+1,c=0;c<3;c++,ii++){
                    for(int jj=(j-1)/3*3+1,d=0;d<3;d++,jj++){
                        posi[s[ii][jj]]=0;
                    }
                }
                for(int k=1;k<=9;k++){
                    posi[s[i][k]]=0;
                    posi[s[k][j]]=0;
                }
                for(int k=1;k<=9;k++){
                    if(posi[k]){
                        s[i][j]=k;
                        put(i,j);
                    }
                }
                s[i][j]=0;
                bye=1;break;
            }
            if(x==9 && y==9){
                ans++;
                for(int ii=1;ii<=9;ii++){
                    for(int jj=1;jj<=9;jj++){
                        if(jj-1)cout<<" ";
                        cout<<s[ii][jj];
                    }
                    cout<<endl;
                }
                cout<<endl;
            }
        }
        if(bye)break;
    }
}

int main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            cin>>s[i][j];
        }
    }
    put(1,1);
    cout<<"there are a total of "<<ans<<" solution(s).";
}

然後我發現我結尾居然沒有換行還是AC了OAO(?
張貼者： 於 沒有留言:

2016年10月18日 星期二

zj d242 / UVa 00481 - What Goes Up


最基本的LIS
不過因為要輸出LIS的內容 所以要記錄一下那個位置的值就好

 

 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define ld long double
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
#define pii pair<int,int>
#define vint vector<int>
#define rz(x) resize(x)
#define X first
#define Y second
// #define m (l+r)/2
// #define xm (x1+x2)/2
// #define ym (y1+y2)/2
#define DE cout<<"de"<<endl;
#define PQ priority_queue

inline int rit(){
    int t=0,k=1;
    char c;
    do{
        c=getchar();
        if(c=='-')k=-1;
    }while(c<'0'||c>'9');
    do{
        t=t*10+c-'0';
        c=getchar();
    }while(c>='0'&&c<='9');
    return t*k;
};

int n,i,a[1005],j;
string s;
stack<int> st;

int main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    bool fst=0;
    while(cin>>n && n){
        getline(cin,s);
        if(fst)cout<<endl;
        fst++;
        while(getline(cin,s) && s[0]!='0'){
            stringstream ss;
            ss<<s;
            i=1;
            while(ss>>a[i]){
                i++;
            }
            int head=1;
            while(st.size())st.pop();
            bool no=0;
            for(i=1;i<=n;i++){
                again:
                if(a[i]==head){
                    head++;
                    continue;
                }
                else if(st.size() && st.top()==a[i]){
                    st.pop();
                    continue;
                }
                else if(a[i]<head){
                    no=1;
                    break;
                }
                st.push(head);
                head++;
                goto again;
            }
            if(no)cout<<"No\n";
            else cout<<"Yes\n";
        }
    }
}
張貼者： 於 沒有留言:
訂閱： 文章 (Atom)