Chengrui's Blog

0%

发表于 分类于 ， Disqus：

简单的栈应用。一开始忽略了判断栈是否为空。

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<iostream>
#include<string>
#include<stack>
#include<map>
using namespace std;
int n;
string s;
map<char,char>a;
int main(){
    a[')']='(';
    a[']']='[';
    cin>>n;
    cin.get();
    while(n--){
        stack<char>c;
        getline(cin,s);
        int i;
        for(i=0;i<s.length();i++){
            if(s[i]=='('||s[i]=='[') c.push(s[i]);
            else if(s[i]==')'||s[i]==']'){
                if(c.empty()) break;
                if(c.top()==a[s[i]]) c.pop();
                else break;
            }
            else continue;
        }
        if(i==(int)s.length()&&c.empty()) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

是道例题，没错就是道例题。书上有代码，就是有代码。有代码的题应该不写博客的，可是代码不对，不对！！！！

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<iostream>
#include<stack>
using namespace std;
const int maxn=1000+10;
int n,target[maxn];
int main(){
    while(cin>>n&&n){
        while(cin>>target[1]&&target[1]){
            stack<int>s;
            int A=1,B=1;
            for(int i=2;i<=n;i++)
                cin>>target[i];
            int ok=1;
            while(B<=n){
                if(A==target[B]){
                    A++;
                    B++;
                }
                else if(!s.empty()&&s.top()==target[B]){
                    s.pop();
                    B++;
                }
                else if(A<=n) s.push(A++);
                else{
                    ok=0;
                    break;
                }
            }
            if(ok) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        
        cout<<endl;
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

昨天ACM培训时开始写的，一看就有思路，建了两个结构体表示topics和员工。循环中间多加了个else一直没检查出来，错了好多次。

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<algorithm>
#include<vector>
using namespace std;
struct topic{
    int tid,num,t0,t,dt,q_num,finished;
};
struct member{
    int pid,k,work_left,last;
    vector<int>pidk;
    bool operator <(const member&a) const{
        if(a.last==last) return a.pid>pid;
        else return a.last>last;
    }
};
vector<topic>topics;
vector<member>staff;
int main(){
    int m,n,kase=0;
    while(cin>>m&&m){
        int time=0,need=0;
        while(m--){
            topic a;
            cin>>a.tid>>a.num>>a.t0>>a.t>>a.dt;
            a.q_num=a.finished=0;
            topics.push_back(a);
        }
        cin>>n;
        int z=0;
        while(n--){
            z++;
            member a;
            int x;
            a.work_left=a.last=0;
            cin>>a.pid>>a.k;
            a.pid=z;
            for(int i=0;i<a.k;i++){
                cin>>x;
                a.pidk.push_back(x);
            }
            staff.push_back(a);
        }
        while(1){
            for(int i=0;i<topics.size();i++)
                if(time>=topics[i].t0&&topics[i].finished+topics[i].q_num<topics[i].num){
                    topics[i].t0+=topics[i].dt;
                    topics[i].q_num=min(++topics[i].q_num,topics[i].num-topics[i].finished);
                }
            sort(staff.begin(),staff.end());
            for(int i=0;i<staff.size();i++){
                if(!staff[i].work_left)
                    for(int j=0;j<staff[i].pidk.size();j++)
                        for(int k=0;k<topics.size();k++)
                            if(staff[i].pidk[j]==topics[k].tid&&topics[k].q_num){
                                staff[i].last=time;
                                staff[i].work_left=topics[k].t;
                                topics[k].q_num--;
                                need=max(need,topics[k].t);
                                
                                if(++topics[k].finished==topics[k].num){
                                    topics.erase(topics.begin()+k);
                                    if(!topics.size()){
                                        time+=need;
                                        goto END;
                                    }
                                }
                                goto NEXT_P;
                            }
            NEXT_P:
                continue;
            }
            time++;
            need=max(--need,0);
            for(int i=0;i<staff.size();i++)
                staff[i].work_left=max(--staff[i].work_left,0);
        }
    END:
        kase++;
        cout<<"Scenario "<<kase<<": All requests are serviced within "<<time<<" minutes."<<endl;
        staff.clear();
        topics.clear();
    }
    return 0;
}

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

发表于 分类于 Disqus：

本来想Ac掉UVa-12333的但后来发现目前的知识做有些困难，准备以后再做了，又Ac了个第五章的例题，有效题数50了。

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

发表于 分类于 ， Disqus：

给出一个表格，问有没有r1、r2、c1、c2满足着两行与两列相交的单元格内部分别相同。

首先进行预处理，给每一种数据分配ID，将string转化为int。

然后使用pair，把两个int组成二元组，存在另一个map里，之后单次遍历储存查找。

PS:这是UVa上Ac的第50道题。

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<iostream>
#include<cstring>
#include<string>
#include<map>
using namespace std;
int a[10010][15];
typedef pair<int,int>two_data;
map<string,int>data_id;
map<two_data,int>data_r;//二元组映射。
string s0;
int main(){
    int m,n;
    while(cin>>m>>n){
        int t=1;
        getchar();
        string s;
        for(int i=0;i<m;i++){
            int k=0;
            getline(cin,s);
            string x;
            for(int j=0;j<s.length();j++){//预处理分配ID。
                if(s[j]!=',') x+=s[j];
                if(s[j]==','||j==s.length()-1){
                    if(!data_id.count(x)){
                        data_id[x]=t;
                        t++;
                    }
                    a[i][k]=data_id[x];
                    x=s0;
                    k++;
                }
            }
        }
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                for(int k=0;k<m;k++){
                    int x=a[k][i],y=a[k][j];
                    if(data_r.count(make_pair(x,y))){//遍历数据库查找相同组。
                        cout<<"NO"<<endl;
                        cout<<data_r[make_pair(x,y)]+1<<" "<<k+1<<endl;
                        cout<<i+1<<" "<<j+1<<endl;
                        goto END;
                    }
                    data_r[make_pair(x,y)]=k;
                }
                data_r.clear();
            }
        }
        cout<<"YES"<<endl;
    END:
        data_id.clear();
        data_r.clear();
        memset(a,0,sizeof(a));
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出旧字典和新字典，输出字典的变化增加+、减少-、更改*。

保存字典之后对比就好，但是注意在没有那项变动时不要多输出符号。

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
using namespace std;
struct key_value{
    string key,value;
};
set<string>key;
vector<string>change[3];
map<string,string>dict[2];
int main(){
    int t,flag=1;
    key_value x,y;
    cin>>t;
    getchar();
    while(t--){
        dict[0].clear();
        dict[1].clear();
        for(int i=0;i<3;i++) change[i].clear();
        change[0].push_back("+");
        change[1].push_back("-");
        change[2].push_back("*");
        key.clear();
        char c;
        for(int i=0;i<2;){
            c=getchar();
            if(c=='{'){
                flag=1;
                x=y;
                continue;
            }
            if(c=='}'){
                if(x.key!=""&&x.value!=""){
                    dict[i][x.key]=x.value;
                    key.insert(x.key);
                }
                i++;
                getchar();
                continue;
            }
            if(c==','||c==':'){
                flag=!flag;
                if(c==','){
                    dict[i][x.key]=x.value;
                    key.insert(x.key);
                    x=y;
                }
                continue;
            }
            if(flag) x.key+=c;
            else x.value+=c;
        }
        for(set<string>::iterator it=key.begin();it!=key.end();it++){
            if(!dict[0].count(*it)) change[0].push_back(*it);
            else if(!dict[1].count(*it)) change[1].push_back(*it);
            else if(dict[0][*it]!=dict[1][*it]) change[2].push_back(*it);
        }
        int k=0;
        for(int i=0;i<3;i++){
            int first=2;
            if(change[i].size()-1){
                for(int j=0;j<change[i].size();j++){
                    if(first) first--;
                    else cout<<",";
                    cout<<change[i][j];
                }
                cout<<endl;
                k++;
            }
        }
        if(!k) cout<<"No changes"<<endl;
        cout<<endl;
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出平面上的n个点，求一条竖直直线使平面上所有点对称，注意是竖直直线。

给所有的点排序，排序后取第一个点作为标准，找其他的点进行匹配，确定一条轴，判断其他点是否关于这个轴对称。

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<algorithm>
#include<vector>
using namespace std;
struct point{
    double x,y;
    bool operator < (const point &a)const{
        if(a.y==y) return a.x>x;
        else return a.y>y;
    }
};
vector<point>a;
vector<point>b;
int main(){
    int t;
    double mid=0;
    cin>>t;
    while(t--){
        int n,k=1;
        point p;
        cin>>n;
        while(n--){
            cin>>p.x>>p.y;
            a.push_back(p);
            b.push_back(p);
        }
        if(n==1){
            cout<<"YES"<<endl;
            a.clear();
            b.clear();
            continue;
        }
        sort(a.begin(),a.end());
        for(int i=1;i<a.size();i++){
            if(a[0].y!=a[i].y){
                mid=(a[0].x+a[i-1].x)/2;
                break;
            }
        }
        for(int i=0;i<b.size();i++) b[i].x=2*mid-b[i].x;
        sort(b.begin(),b.end());
        for(int i=0;i<a.size();i++){
            if(a[i].x!=b[i].x||a[i].y!=a[i].y){
                k=0;
                break;
            }
        }
        if(k) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        a.clear();
        b.clear();
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

输入一段程序代码，要你找出bug，有两种bug，一是引用未赋值变量，二是下标越界。

主要考察的就是细节，思路并不难，找程序的bug，首先自己写的程序细节上不能出bug。

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<string>
#include<sstream>
#include<map>
using namespace std;
string s0,s,s1,s2,left_value,right_value;
int bug;
map<string,unsigned int>a;
map<string,string>value;
string get_value(string x,string arr){
    unsigned int t=0;
    string y,z;
    if(x.find("[")==string::npos){
        stringstream ss(x);
        ss>>t;
        if(arr!=s0&&t>=a[arr]) bug=1;
        return x;
    }
    y=x.substr(0,x.find("["));
    z=x.substr(x.find("[")+1,x.find_last_of("]")-2);
    z=get_value(z,y);
    if(bug) return s0;
    x=y+"["+z+"]";
    if(!value.count(x)) bug=1;
    return value[x];
}
void get_arr(){
    string x,y;
    unsigned int z;
    x=s.substr(0,s.find("["));
    y=s.substr(s.find("[")+1,s.find_last_of("]")-2);
    y=get_value(y,s0);
    stringstream ss(y);
    ss>>z;
    a[x]=z;
    return;
}
int main(){
    int flag=0,cnt=1;
    a[s0]=0;
    string arr,indx;
    while(cin>>s){
        if(s!=".") flag=1;
        else if(!flag) break;
        else{
            if(!bug) cout<<"0"<<endl;
            a.clear();
            value.clear();
            left_value=right_value=s0;
            cnt=1;
            bug=flag=0;
            continue;
        }
        if(bug) continue;
        if(s.find("=")==string::npos) get_arr();
        else{
            s1=s.substr(0,s.find("="));
            s2=s.substr(s.find("=")+1);
            arr=s1.substr(0,s1.find("["));
            indx=s1.substr(s1.find("[")+1,s1.find_last_of("]")-2);
            indx=get_value(indx,arr);
            stringstream ss(indx);
            unsigned int t;
            ss>>t;
            if(t>=a[arr]) bug=1;
            left_value=arr+"["+indx+"]";
            right_value=get_value(s2,s0);
            if(bug){
                cout<<cnt<<endl;
                continue;
            }
            value[left_value]=right_value;
            left_value=right_value=s0;
        }
        cnt++;
    }
    return 0;
}

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

发表于 分类于 Disqus：

做UVa的第三十天。。本来准备明天Ac道题再写总结的，但是，昨天晚上9点半，出现了很好玩的东西。

昨完题之后十一点多，目测十二点之前也睡不着了，所以就直接写总结了。。

这十天刷的题挺多的，学到的也很多。感觉第五章前面好多水题。

从7号到现在一直没刷题。。周六做了协会题，周日比赛，昨天写了道没写完。。

这十天主要学了STL，感觉没想象中的那么难，之前的UVa-101现在看也很简单了。

比赛时发现，其实主要还是要学后面几章，尽快结束第五章。

以后继续努力吧。

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

发表于 分类于 Disqus：

和学长一起参加了青理工的比赛，从开始到断电，做了3h40min，Ac了5道题，感觉现场做题确实是容易有点小激动。。很多低级的错误都出现了。。

5道题中，我参与了其中四道。

C题英文题学长看着感觉水，就先做了。

G题是判断谁能在游戏中获胜的题，很快找到了思路，由于印刷的题目错了，第一次提交WA了。。想了好久发现109是印刷错误应该为10^9。修改代码之后一次Ac。

J题是计算多边形面积的，其实挺水的，但我们在第一次交对""的处理不到位WA了，修改过后Ac。

H是素数间隙判断，看着像水题，学长在看别的题时，我先写了部分代码。。居然连素数表都打错了。。后来经学长重新打表修改Ac了。。

B题求幸运数问题，一开始我用set做的但是TLE了，后来学长找到了幸运数公式。修改简化循环后Ac。

剩下几道题都没什么思路。。三角形面积的那个可能是需要什么公式吧，感觉其他的都需要学习紫书后面的知识。还是要继续往下学啊。

总的来说这次比赛挺让人满意的，体验了竞赛的感觉，也学到了一些做题的技巧。

至于下一步的打算，当然是继续做题、学习。准备最晚明年三月做完UVa的百题，加入集训队。现在尽量多看紫书上的知识点、和C++Primer上关于C++的函数的讲 解。

以后的路还长，这只是个开始。

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