Chengrui's Blog

0%

发表于 分类于 ， Disqus：

输入一个含有偶数个串的集合，求一个字符串s0，使集合中一半的串大于s0，另一半小于等于s0，多解输出字典序最小的解。只需将s与中间两个串比较即可。

新串s0从空串开始，每次循环加上一个s1中对应位置的字符。只要满足条件就跳出循环，输出。

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
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int main(){
    int n;
    while(cin>>n&&n){
        int k=n/2;
        string s0,s1,s2,temp;
        vector<string>words;
        while(n--){
            cin>>s1;
            words.push_back(s1);
        }
        sort(words.begin(),words.end());
        s1=words[k-1],s2=words[k];//找到中间串。
        int cur=0;
        while(1){
            for(int i=0;i<26;i++){
                temp=s0;
                temp+=i+'A';
                if(temp>=s1&&temp<s2)
                    goto END;
            }
            s0+=s1[cur++];
        }
    END:
        cout<<temp<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

简单的贪心问题。输入n个物品的重量，背包的容量m，每个背包最多装两个物品，问需要多少个背包。

思路很简单，最小的和最大的匹配，装不下就改找比那个小一点的。

匹配要用二分查找，遍历会超时。

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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int find(vector<int> a,const int x,int bott,int top){//二分查找。
    int mid;
    while(bott<top){
        if(x>=a[top]) return top;
        mid=(bott+top)/2;
        if(x==a[mid]) return mid;
        if(x<a[mid+1]&&x>a[mid])
            return mid;
        else{
            if(x<a[mid]) top=mid-1;
            else bott=mid+1;
        }
    }
    if(top==bott&&x>=a[top]) return top;
    return  -1;
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        vector<int>goods;
        int n,bagmax,temp,num=0;
        cin>>n>>bagmax;
        while(n--){
            cin>>temp;
            goods.push_back(temp);
        }
        sort(goods.begin(),goods.end());
        while(1){
            num++;
            int now=goods[goods.size()-1];
            goods.erase(goods.end()-1);
            if(!goods.size()) break;
            if(now+goods[0]>bagmax) continue;
            int k=find(goods,bagmax-now,0,(int)goods.size()-1);//匹配能装下的最大的。
            if(k!=-1) goods.erase(goods.begin()+k);
            if(!goods.size()) break;
        }
        cout<<num<<endl;
        if(t) cout<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 Disqus：

刷题50天了，数据结构差不多看完了，马上就要进入暴力求解了，暴力求解里的回溯法貌似很难的样子。

感觉离百题不远了，但是准备从十七周开始不再长时间刷UVa题，每天至多1h，直至期末考试结束。。所以14年内百题希望不大。。

不多说了，上图：

PS：之前攀哥说看完第六章还觉得简单，那学校就有希望了。感觉现在，至少专业是有希望了。

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

介绍了一个游戏规则，输入牌堆，要求输出胜负或者平。

用vector进行模拟，set储存状态，出现重复状态就是平。

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
78
79
80
81
82
83
84
#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
int t;
vector<vector<int> >piles;
set<vector<vector<int> > >past;
bool read(){
    int k;
    cin>>k;
    if(!k) return false;
    vector<int>temp;
    for(int i=0;i<8;i++) piles.push_back(temp);
    piles[7].push_back(k);
    for(int i=0;i<51;i++){
        cin>>k;
        piles[7].push_back(k);
    }
    return true;
}
void start(){
    t=7;
    for(int i=0;i<7;i++){
        piles[i].push_back(piles[7][0]);
        piles[7].erase(piles[7].begin());
    }
    past.insert(piles);
    return;
}
bool sum(int a,int b,int c,int i){
    int k=piles[i][a]+piles[i][b]+piles[i][c];
    if(k==10||k==20||k==30){
        piles[piles.size()-1].push_back(piles[i][a]);
        piles[piles.size()-1].push_back(piles[i][b]);
        piles[piles.size()-1].push_back(piles[i][c]);
        piles[i].erase(piles[i].begin()+c);
        piles[i].erase(piles[i].begin()+b);
        piles[i].erase(piles[i].begin()+a);
        return true;
    }
    return false;
}
bool pickup(int i){
    if(piles[i].size()<3) return false;
    if(sum(0,1,(int)piles[i].size()-1,i)) return true;
    if(sum(0,(int)piles[i].size()-2,(int)piles[i].size()-1,i)) return true;
    if(sum((int)piles[i].size()-3,(int)piles[i].size()-2,(int)piles[i].size()-1,i)) return true;
    return false;
}
void play(){
    int i=0;
    while(piles[piles.size()-1].size()&&piles.size()!=1){
        piles[i].insert(piles[i].end(),piles[piles.size()-1][0]);
        piles[piles.size()-1].erase(piles[piles.size()-1].begin());
        while(pickup(i));
        if(!piles[i].size()){
            piles.erase(piles.begin()+i);
            i--;
        }
        i++,t++;
        if(i==piles.size()-1) i=0;
        if(past.find(piles)!=past.end()) break;
        past.insert(piles);
    }
    return;
}
void print(){
    if(piles.size()==1) cout<<"Win : "<<t<<endl;
    else if(!piles[piles.size()-1].size()) cout<<"Loss: "<<t<<endl;
    else cout<<"Draw: "<<t<<endl;
    piles.clear();
    past.clear();
    return;
}
int main(){
    ios::sync_with_stdio(false);
    while(read()){
        start();
        play();
        print();
    }
    return 0;
}
1
ios::sync_with_stdio(false);

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出扑克牌堆，当堆顶的扑克与它左边或者左边第三堆的堆顶的扑克match（suit或rank相同），这张牌就移过去，优先移动三格，优先移动最左边牌堆顶的牌。

一开始用的string，stack，vector模拟的，在UVa上2.899s过了，后来学校有这个题，时间限制1s，进行了优化，VJ上测试0.999过的。

优化后代码：

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
#include<cstdio>
#include<cstdlib>
#include<string>
#include<vector>
#include<stack>
using namespace std;
stack<char *>pile;
vector<stack<char *> > piles,emp(52);
bool read(){
    piles=emp;
    char *s=(char *)malloc(3);
    scanf("%s",s);
    if(s[0]=='#') return false;
    piles[0].push(s);
    for(int i=1;i<52;++i){
        s=(char *)malloc(3);
        scanf("%s",s);
        piles[i].push(s);
    }
    return true;
}
bool match(char *a,char *b){
    return (a[0]==b[0]||a[1]==b[1]);
}
int move(int i){
    if(i>2&&match(piles[i].top(),piles[i-3].top())){
        piles[i-3].push(piles[i].top());
        piles[i].pop();
        if(piles[i].empty()) piles.erase(piles.begin()+i);
        return 4;
    }
    if(i>0&&match(piles[i].top(),piles[i-1].top())){
        piles[i-1].push(piles[i].top());
        piles[i].pop();
        if(piles[i].empty()) piles.erase(piles.begin()+i);
        return 2;
    }
    return 0;
}
void solve(){
    int k;
    for(int i=1;i<piles.size();i++){
        k=move(i);
        if(k) i-=k;
    }
    return;
}
void print(){
    printf("%d%s",piles.size(),piles.size()==1?" pile remaining: ":" piles remaining: ");
    for(int i=0;i<piles.size();++i){
        if(i) printf(" ");
        printf("%d",piles[i].size());
    }
    printf("\n");
    return;
}
int main(){
    while(read()){
        solve();
        print();
    }
    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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<string>
#include<vector>
#include<stack>
using namespace std;
stack<string>pile;
vector<stack<string> >piles;
bool read(){
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    if(s=="#") return false;
    piles.push_back(pile);
    piles[0].push(s);
    for(int i=1;i<52;i++){
        cin>>s;
        piles.push_back(pile);
        piles[i].push(s);
    }
    return true;
}
bool match(string a,string b){
    return (a[0]==b[0]||a[1]==b[1]);
}
int move(int i){
    if(i>2&&match(piles[i].top(),piles[i-3].top())){
        piles[i-3].push(piles[i].top());
        piles[i].pop();
        if(piles[i].empty()) piles.erase(piles.begin()+i);
        return 4;
    }
    if(i>0&&match(piles[i].top(),piles[i-1].top())){
        piles[i-1].push(piles[i].top());
        piles[i].pop();
        if(piles[i].empty()) piles.erase(piles.begin()+i);
        return 2;
    }
    return 0;
}
void solve(){
    int k;
    for(int i=0;i<piles.size();i++){
        k=move(i);
        if(k) i-=k;
    }
    return;
}
void print(){
    ios::sync_with_stdio(false);
    cout<<piles.size();
    cout<<(piles.size()==1?" pile remaining: ":" piles remaining: ");
    for(int i=0;i<piles.size();i++){
        if(i) cout<<" ";
        cout<<piles[i].size();
    }
    cout<<endl;
    piles.clear();
    return;
}
int main(){
    while(read()){
        solve();
        print();
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出n个单词，问能否将这n个单词连成串，使得每个单词最后一个字母和下个单词第一个字母相同。

首先对单词预处理，变为从首字母到最后一个字母的有向边，将单词集合变为有向图。

然后统计每个点的入度和出度，至多有两个点出度和入度不相等，且一点出度比入度大1，另一点入度比出度大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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int maxn=30;
int n,inp[maxn],outp[maxn];
bool k,vis[maxn],g[maxn][maxn];
void dfs(int u){//判连通。
    vis[u]=false;
    for (int v=0;v<26;v++)
        if (vis[v]&&g[u][v]) dfs(v);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        memset(inp,0,sizeof(inp));
        memset(outp,0,sizeof(outp));
        memset(vis,0,sizeof(vis));
        memset(g,0,sizeof(g));
        k=true;
        string s;
        for(int i=0;i<n;i++){
            cin>>s;
            inp[s[0]-'a']++;
            outp[s[s.size()-1]-'a']++;
            vis[s[0]-'a']=vis[s[s.size()-1]-'a']=true;//预处理。
            g[s[0]-'a'][s[s.size()-1]-'a']=true;
        }
        int cnt1=0,cnt2=0,sta=s[0]-'a';
        for(int i=0;i<26;i++){//统计每个点的出度和入度。
            if(!k) break;
            inp[i]-=outp[i];
            if(inp[i]!=0){
                if(inp[i]==1){
                    cnt1++;
                    sta=i;
                }
                else if(inp[i]==-1) cnt2++;
                else k=false;
            }
        }
        if(cnt1>1||cnt2>1) k=false;
        dfs(sta);
        for(int i=0;i<26;i++){
            if(!k) break;
            if(vis[i]) k=false;
        }
        if(k) cout<<"Ordering is possible."<<endl;
        else cout<<"The door cannot be opened."<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

输入n表示有n个变量，然后输入m个数对(u,v)，表示变量u<v。要求排列所有变量，输出任意可行解。

变量当作点，大小关系当作边，形成有向图，然后进行拓扑排序就好了。

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
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=105;
int c[maxn];
int topo[maxn],t,n,m;
bool G[maxn][maxn];
bool dfs(int u){
    c[u]=-1;
    for(int v=0;v<n;v++)
        if(G[u][v]){
            if(c[v]<0) return false;
            if(!c[v]&&!dfs(v)) return false;
        }
    c[u]=1;
    topo[--t]=u+1;
    return true;
}
bool toposort(){
    t=n;
    memset(c,0,sizeof(c));
    for(int u=0;u<n;u++)
        if(!c[u])
            if(!dfs(u)) return false;
    return true;
}
int main(){
    while(cin>>n>>m&&n){
        memset(G,0,sizeof(G));
        while(m--){
            int i,j;
            cin>>i>>j;
            G[i-1][j-1]=true;
        }
        memset(topo,0,sizeof(topo));
        if(toposort()){
            for(int i=0;i<n;i++){
                if(i) cout<<" ";
                cout<<topo[i];
            }
            cout<<endl;
        }
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

给出迷宫的结点，和迷宫结点处朝向与行走方向的限制关系，求从入口走到出口的最短路径。

最短路问题BFS，用三位数组d[maxn][maxn][4]记录是否经过，结构体数组p[maxn][maxn][4]记录上一步的位置，达到出口就打印解。

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int maxn=12;
const char* dirs="NESW";
const char* turns="FLR";
const int dr[]={-1,0,1,0};
const int dc[]={0,1,0,-1};
int r0,c0,r1,c1,r2,c2,rx,cx,dir,dirx,turnx,d[maxn][maxn][4];
bool has_edge[maxn][maxn][4][4];
string s,s0;
struct Node{
    int r,c,dir;
    Node(int r=0,int c=0,int dir=0):r(r),c(c),dir(dir){}
};
Node p[maxn][maxn][4];
int dir_id(char c){
    return (int)(strchr(dirs,c)-dirs);
}
int trun_id(char c){
    return (int)(strchr(turns,c)-turns);
}
Node walk(const Node& u,int turn){
    int dir=u.dir;
    if(turn==1) dir=(dir+3)%4;
    if(turn==2) dir=(dir+1)%4;
    return Node(u.r+dr[dir],u.c+dc[dir],dir);
}
bool inside(int x,int y){
    return (x>0&&x<10&&y>0&&y<10);
}
void print_ans(Node u){
    vector<Node>nodes;
    while(1){
        nodes.push_back(u);
        if(!d[u.r][u.c][u.dir]) break;
        u=p[u.r][u.c][u.dir];
    }
    nodes.push_back(Node(r0,c0,dir));
    int cnt=0;
    for(int i=(int)nodes.size()-1;i>=0;i--){
        if(cnt%10==0) printf(" ");
        printf(" (%d,%d)",nodes[i].r,nodes[i].c);
        if(++cnt%10==0) printf("\n");
    }
    if(nodes.size()%10) printf("\n");
}
void solve(){
    queue<Node>q;
    memset(d,-1,sizeof(d));
    Node u(r1,c1,dir);
    d[u.r][u.c][u.dir]=0;
    q.push(u);
    while(!q.empty()){
        Node u=q.front();
        q.pop();
        if(u.r==r2&&u.c==c2){
            print_ans(u);
            return;
        }
        for(int i=0;i<3;i++){
            Node v=walk(u,i);
            if(has_edge[u.r][u.c][u.dir][i]&&inside(v.r,v.c)&&d[v.r][v.c][v.dir]<0){
                d[v.r][v.c][v.dir]=d[u.r][u.c][u.dir]+1;
                p[v.r][v.c][v.dir]=u;
                q.push(v);
            }
        }
    }
    printf("  No Solution Possible\n");
    return;
}
bool read(){
    cin>>s0;
    if(s0=="END") return false;
    cout<<s0<<endl;
    memset(has_edge,0,sizeof(has_edge));
    memset(p,0,sizeof(p));
    cin>>r0>>c0>>s>>r2>>c2;
    for(int i=0;i<4;i++)
        if(s[0]==dirs[i]){
            dir=i;
            break;
        }
    r1=r0+dr[dir];
    c1=c0+dc[dir];
    while(cin>>rx&&rx){
        cin>>cx;
        while(cin>>s){
            if(s=="*") break;
            for(int i=0;i<4;i++)
                if(s[0]==dirs[i]){
                    dirx=i;
                    break;
                }
            for(int i=1;i<s.size();i++){
                for(int j=0;j<3;j++)
                    if(s[i]==turns[j]){
                        turnx=j;
                        break;
                    }
                has_edge[rx][cx][dirx][turnx]=true;
            }
        }
    }
    return true;
}
int main(){
    while(read()){
        solve();
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

输入一个斐波那契数的前缀，求开头与所给前缀相同的最小斐波那契数的编号。

容易超时的一道题，计算前十万个斐波那契数要用高精度算法，还要注意只保留前50位就够了，不然会超时。

然后就是查询，原本保存在string数组中，单次查找复杂度为O(n*s.length())。发现查找会超时，后来使用了字典树，单次查找仅为O(s.lengt h())，效率提高很多，就过了。

建树使用了指针，调用之前一定要判断不为空。

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
78
#include<iostream>
#include<vector>
#include<string>
using namespace std;
vector<int>a[3];
struct Node{
    int num;
    bool have_value;
    Node* p[10];
    Node(int num=0):num(num),have_value(false){}
};
Node* root;
Node* newnode(){
    Node* temp;
    temp=new Node();
    for(int i=0;i<10;temp->p[i++]=NULL);
    return temp;
}
string Sum(int x){//求前十万个斐波那契数。
    string s0;
    a[x%3]=a[(x-1)%3];
    if(a[(x-1)%3].size()!=a[(x-2)%3].size())
        for(int i=1;i<(int)a[(x-1)%3].size();i++)
            a[x%3][i]+=a[(x-2)%3][i-1];
    else for(int i=0;i<(int)a[(x-1)%3].size();i++)
        a[x%3][i]+=a[(x-2)%3][i];
    for(int i=(int)a[x%3].size()-1;i>0;i--){
        a[x%3][i-1]+=a[x%3][i]/10;
        a[x%3][i]%=10;
    }
    while(a[x%3][0]>9){
        a[x%3].insert(a[x%3].begin(),a[x%3][0]/10);
        a[x%3][1]%=10;
    }
    for(int i=0;i<a[x%3].size();s0+=a[x%3][i++]+'0');
    while(a[x%3].size()>50&&a[(x-1)%3].size()>50){
        a[x%3].erase(a[x%3].end()-1);
        a[(x-1)%3].erase(a[(x-1)%3].end()-1);
    }
    return s0;
}
void build(Node* u,string s,int k){//建树。
    for(int i=0;i<s.length();i++){
        int t=s[i]-'0';
        if(u->p[t]==NULL) u->p[t]=newnode();
        if(!u->p[t]->have_value){
            u->p[t]->have_value=true;
            u->p[t]->num=k;
        }
        u=u->p[t];
    }
    return;
}
int search(string s,Node* b){//字典树查找。
    for(int i=0;i<s.length();i++){
        if(b->p[s[i]-'0']==NULL) return -1;
        b=b->p[s[i]-'0'];
    }
    if(!b->have_value) return -1;//指针未赋值，返回-1。
    return b->num;
}
int main(){
    a[0].push_back(1);
    a[1].push_back(1);
    root=newnode();
    root->p[1]=newnode();
    root->p[1]->have_value=true;
    for(int i=2;i<100000;i++)
        build(root,Sum(i),i);
    int n,t=0;
    cin>>n;
    while(n--){
        string s0;
        cin>>s0;
        cout<<"Case #"<<++t<<": "<<search(s0,root)<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

第七章开头水题好多啊。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int main(){
    int k;
    while(cin>>k&&k){
        vector<int>a[2];
        for(int i=k+1;i<=2*k;i++)
            if(k*i%(i-k)==0){
                a[0].push_back(k*i/(i-k));
                a[1].push_back(i);
            }
        cout<<a[0].size()<<endl;
        for(int i=0;i<a[0].size();i++)
        printf("1/%d = 1/%d + 1/%d\n",k,a[0][i],a[1][i]);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **