Chengrui's Blog

0%

发表于 分类于 Disqus：

这次题目不难，就是最后一道题感觉表述不大清楚，对一个名字中数字的处理讲的不是很清楚，所以不做了。。

这次所有题交之前都没进行测试。。错了好多次。。

第一题，水题。

Ac代码：

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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100010;
int a[maxn];
int main(){
    int n,first=1;
    while(cin>>n){
        memset(a,0,sizeof(a));
        int first2=1;
        for(int i=0;i<n;i++) cin>>a[i];
        sort(a,a+n);
        if(first) first=0;
        else cout<<endl;
        for(int i=0;i<n/2;i++){
            if(first2) first2=0;
            else cout<<" ";
            if(i!=n-1-i) cout<<a[i]<<" "<<a[n-1-i];
            else break;
        }
        if(n%2==1){
            if(first2) first2=0;
            else cout<<" ";
            cout<<a[n/2];
        }
        cout<<endl;
    }
    return 0;
}

第二题，还是水题。

Ac代码：

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>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100010;
int a[maxn];
int main(){
    int n,first=1;
    while(cin>>n){
        int cnt1=0,cnt2=0;
        memset(a,0,sizeof(a));
        int first2=1;
        for(int i=0;i<n;i++) cin>>a[i];
        sort(a,a+n);
        if(first) first=0;
        else cout<<endl;
        if(n%2==1){
            for(int i=0;cnt1<n/2+1;i+=2){
                if(first2) first2=0;
                else cout<<" ";
                cout<<a[i];
                cnt1++;
            }
            for(int i=1;cnt2<n/2;i+=2){
                if(first2) first2=0;
                else cout<<" ";
                cout<<a[n-1-i];
                cnt2++;
            }
            cout<<endl;
        }
        else{
            for(int i=0;cnt1<n/2;i+=2){
                if(first2) first2=0;
                else cout<<" ";
                cout<<a[i];
                cnt1++;
            }
            for(int i=1;cnt2<n/2;i+=2){
                if(first2) first2=0;
                else cout<<" ";
                cout<<a[n-i];
                cnt2++;
            }
            cout<<endl;
        }
    }
    return 0;
}

第三题，还是水题。

Ac代码：

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
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
vector<unsigned long long>a;
int main(){
    string s;
    while(cin>>s){
        for(int i=0;i<(int)s.length();i++) if(s[i]=='5') s[i]=' ';
        stringstream ss(s);
        unsigned long long x;
        while(ss>>x)
            a.push_back(x);
        sort(a.begin(),a.end());
        int first=1;
        for(int i=0;i<(int)a.size();i++){
            if(first) first=0;
            else cout<<" ";
            cout<<a[i];
        }
        cout<<endl;
        a.clear();
    }
    return 0;
}

第四题，单元格调整，一开始在A和Z的处理上出现了问题。。卡了挺久的。。

Ac代码：

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<iostream>
#include<string>
#include<sstream>
using namespace std;
void a_to_b(string s){
    string a,b;
    int c=0;
    for(int i=0;i<s.length();i++)
        if(!isdigit(s[i])) a+=s[i];
        else b+=s[i];
    for(int i=0;i<a.length();i++){
        c*=26;
        c+=a[i]-'A'+1;
    }
    cout<<"R"<<b<<"C"<<c<<endl;
}
void b_to_a(string s){
    stringstream ss(s);
    int a,b,k[6],t[6];
    for(int i=0;i<6;i++){
        t[i]=0;
        int j=5-i;
        k[i]=1;
        while(j--) k[i]*=26;
    }
    string c;
    ss.get();
    ss>>a;
    ss.get();
    ss>>b;
    for(int i=0;b>0;i++){
        t[i]=b/k[i];
        b-=t[i]*k[i];
    }
    for(int i=5;i>=0;i--){
        int cnt=0;
        for(int j=i-1;j>=0;j--)
            if(t[j]>0) cnt++;
        if(t[i]<=0&&cnt){
            t[i]+=26;
            t[i-1]--;
        }
    }
    for(int i=0;i<6;i++)
        if(t[i]>0)
            c+='A'-1+t[i];
    cout<<c<<a<<endl;
}
int main(){
    string s;
    int n;
    cin>>n;
    cin.get();
    while(n--){
        getline(cin,s);
        int t=0;
        for(int i=1;i<s.size();i++)
            if(isalpha(s[i-1])&&isdigit(s[i])) t++;
        if(t==1) a_to_b(s);
        else b_to_a(s);
    }
    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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
using namespace std;
struct book{
    string author;
    int status;
};
map<string,book>books;
vector<string>name;
bool compare(string a,string b){
    if(books[a].author==books[b].author) return a<b;
    else return books[a].author<books[b].author;
}
int main(){
    string x,z,m;
    book y;
    while(getline(cin,m)){
        if(m=="END") break;
        x=m.substr(0,m.find_last_of("\"")+1);
        y.author=m.substr(m.find_last_of("\"")+1);
        name.push_back(x);
        books[x]=y;
    }
    sort(name.begin(),name.end(),compare);
    for(int i=0;i<name.size();i++)
        books[name[i]].status=1;
    while(cin>>x){
        if(x=="END") break;
        if(x=="BORROW"){
            getchar();
            getline(cin,z);
            books[z].status=0;
        }
        if(x=="RETURN"){
            getchar();
            getline(cin,z);
            books[z].status=-1;
        }
        if(x=="SHELVE"){
            for(int i=0;i<name.size();i++)
                if(books[name[i]].status==-1){
                    int j;
                    for(j=i;j>=0;--j)
                        if(books[name[j]].status==1) break;
                    if(j>-1) cout<<"Put "<<name[i]<<" after "<<name[j]<<endl;
                    else cout<<"Put "<<name[i]<<" first"<<endl;
                    books[name[i]].status=1;
                }
            cout<<"END"<<endl;
        }
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

跟UVa400差不多的题，要求调整代码格式，照这那道题代码改的，一定要注意空格的输出和对齐问题，并不是很难。

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
#include<iostream>
#include<string>
#include<vector>
#include<sstream>
#include<algorithm>
using namespace std;
const int maxn=1010;
vector<string> word[maxn];
int a[maxn];
void print(const string& s,int len,char extra){
    cout<<s;
    for(int i=0;i<len-s.length()+1;i++) cout<<extra;
}
int main(){
    int maxl=0,cnt=0;
    string s,x;
    while(getline(cin,s)){
        stringstream ss(s);
        while(ss>>x) word[cnt].push_back(x);
        maxl=max(maxl,(int)word[cnt].size());
        cnt++;
    }
    for(int i=0;i<cnt;i++){
        for(int j=0;j<word[i].size();j++)
        a[j]=max(a[j],(int)word[i][j].length());
    }
    for(int i=0;i<cnt;i++){
        for(int j=0;j<word[i].size();j++){
            if(j==(int)word[i].size()-1) cout<<word[i][j];
            else print(word[i][j],a[j],' ');
        }
        cout<<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
37
38
39
#include<iostream>
#include<vector>
using namespace std;
vector<int>queue;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m,x,cnt=0;
        cin>>n>>m;
        
        while(n--){
            cin>>x;
            queue.push_back(x);
        }
        while(1){
            int i;
            for(i=0;i<queue.size();i++)
                if(queue[i]>queue[0]){
                    queue.push_back(queue[0]);
                    queue.erase(queue.begin());
                    if(m) m--;
                    else m=(int)queue.size()-1;
                    i=0;
                }
            if(i==queue.size()){
                queue.erase(queue.begin());
                cnt++;
                if(m) m--;
                else{
                    cout<<cnt<<endl;
                    break;
                }
            }
        }
        queue.clear();
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

输入一个词典，找出其中所有的复合词。单词数量小于120000。

将所有的单词保存在一个set中，单次遍历，对每一个单词判断是否为合成词。

判断时分别判断单词前缀和后缀是否在set中出现，set中排好序了，所以查找时间复杂度为O(logn)，总时间复杂度O(nlogn)，不会超时。

set.find()返回查找元素的迭代器，未找到返回set.end()。s.substr()返回s中的一段连续子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<string>
#include<set>
using namespace std;
set<string>dict;
int main(){
    string s;
    while(cin>>s)
        dict.insert(s);
    s.clear();
    for(set<string>::iterator it=dict.begin();it!=dict.end();it++){
        s=*it;
        for(int i=1;i<s.length();i++){
            if(dict.find(s.substr(0,i))!=dict.end()&&dict.find(s.substr(i,s.length()-i))!=dict.end()){
                cout<<s<<endl;
                break;
            }
        }
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

有n个学生要当交换生，输入每个人的目标地和原始地，学生两两交换，问能否交换成功。

用结构体排序做的，两个vector分别保存交换前和交换后的学生，对比目标地和原始地是否完全相同，相同即可完成交换。

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<vector>
#include<algorithm>
using namespace std;
struct candidate{
    int a;
    int b;
};
vector<candidate>cd;
vector<candidate>excd;
int n;
candidate x;
bool compare(candidate x,candidate y){
    if(x.a!=y.a) return x.a<y.a;
    else return x.b<y.b;
}
int main(){
    while(cin>>n&&n){
        int t=n;
        for(int i=0;i<n;i++){
            cin>>x.a>>x.b;
            cd.push_back(x);
            swap(x.a,x.b);
            excd.push_back(x);
        }
        sort(cd.begin(),cd.end(),compare);
        sort(excd.begin(),excd.end(),compare);
        for(int i=0;i<n;i++)
            if(cd[i].a==excd[i].a&&cd[i].b==excd[i].b) t--;
        if(t) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
        cd.clear();
        excd.clear();
    }
    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
#include<iostream>
#include<vector>
using namespace std;
vector<int>a;
vector<int>b;
int n,x,y;
int main()
{
    while(cin>>n&&n)
    {
        int t=1;
        for(int i=0;i<n;i++)
        {
            cin>>x>>y;
            a.push_back(x);
            b.push_back(y);
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(a[i]==b[j]&&a[j]==b[i]&&i!=j)
                    a[i]=a[j]=b[i]=b[j]=0;
            }
        }
        for(int i=0;i<n;i++)
            if(a[i])
            {
                t=0;
                break;
            }
        if(t)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
        a.clear();
        b.clear();
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出Ducci序列定义，输入一个序列，判断它会变成0还是循环。循环次数仅为1000，序列长度最大为15。

就按照给出条件模拟就好，不需要担心超时，可以用来练习STL的使用。

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<cstdlib>
#include<vector>
using namespace std;
const int maxn=1010;
vector<int>a;
int t,n;
bool is_zero()
{
    int p,q=0;
    for(int i=0;i<maxn;i++)
    {
        q=0;
        p=a[0];
        for(int j=0;j<n-1;j++)
        {
            a[j]=abs(a[j]-a[j+1]);
            if(!a[j])
                q++;
        }
        a[n-1]=abs(a[n-1]-p);
        if(!a[n-1])
            q++;
        if(q==n)
            return true;
    }
    return false;
}
int main()
{
    int x;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>x;
            a.push_back(x);
        }
        if(is_zero())
            cout<<"ZERO"<<endl;
        else
            cout<<"LOOP"<<endl;
        a.clear();
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

给出牌的顺序，输出每次扔掉的牌和最后剩下的牌。挺简单的道题，直接模拟就行。用的vector，一开始输出格式错了。改改就过了。

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
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int>cards;
int main()
{
    while(cin>>n&&n)
    {
        int first=1;
        for(int i=1;i<=n;i++)
            cards.push_back(i);
        cout<<"Discarded cards:";
        while(!cards.empty())
        {
            if(cards.size()==1)
                break;
            if(first)
            {
                first=0;
                cout<<" ";
            }
            else
                cout<<", ";
            cout<<cards[0];
            cards.erase(cards.begin());
            cards.push_back(cards[0]);
            cards.erase(cards.begin());
        }
        cout<<endl;
        cout<<"Remaining card: "<<cards[0]<<endl;
        cards.clear();
    }
    return 0;
}

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

发表于 分类于 ， Disqus：

输入每个学生的睡眠－清醒周期和当前状态，每个学生在睡觉前都会检查班里人的状态，仅当睡眠人数严格大于清醒人数时才会睡觉，否则继续保持清醒状态持续一个周期。求学 生全部清醒的时刻，不存在则输出-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>
#define maxn 15
#define infinite 1e6
using namespace std;
int a[maxn],b[maxn],c[maxn];
int n,cnt;
void next_min()
{
    for(int i=0;i<n;i++)
    {
        c[i]%=a[i]+b[i];
        if(c[i]==a[i]&&cnt>=n-cnt)//睡眠人数严格大于清醒人数才能睡觉。
            c[i]=0;
        c[i]++;
    }
    return;
}
bool all_awake()
{
    cnt=0;
    for(int i=0;i<n;i++)
        if(c[i]<=a[i])
            cnt++;
    if(cnt==n)//判断是否全部清醒。
        return true;
    else
        return false;
}
int main()
{
    int t=1;
    while(cin>>n&&n)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        for(int i=0;i<n;i++)
            cin>>a[i]>>b[i]>>c[i];
        int x;
        for(x=1;x<infinite;x++)
        {
            if(all_awake())
                break;
            next_min();
        }
        if(x<infinite)//到上限就是不存在。
            cout<<"Case "<<t<<": "<<x<<endl;
        else
            cout<<"Case "<<t<<": -1"<<endl;
        t++;
    }
    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
#include<iostream>
#include<iomanip>//当时居然用了这么奇怪的头文件。控制流式输出精度用的。
#include<algorithm>
#define EPS 1e-8
using namespace std;
int m,n,v,flood,cnt2;
double h,x,s,cnt1;
int main()
{
    int t=1;
    while(cin>>m>>n)
    {
        if(!m&&!n)
            break;
        int ld[m*n];
        cnt1=m*n;
        flood=v=0;
        h=x=0;
        for(int i=0;i<m*n;i++)
            cin>>ld[i];
        sort(ld,ld+m*n);//排序。
        cin>>flood;
        v+=flood+ld[0]*100;
        s=100;
        h=v/s+EPS;
        cnt2=1;
        for(int i=1;i<m*n;i++)
            if(h>ld[i])//循环判断能否淹没。
            {
                v+=ld[i]*100;
                s+=100;
                h=v/s+EPS;
                cnt2++;
            }
        cout<<"Region "<<t<<endl;
        cout<<"Water level is "<<setiosflags(ios::fixed)<<setprecision(2)<<h<<" meters."<<endl;//用printf比这个简单多了。
        cout<<setiosflags(ios::fixed)<<setprecision(2)<<100*cnt2/cnt1<<" percent of the region is under water."<<endl;
        cout<<endl;
        t++;
    }
    return 0;
}

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