npos

npos

关注
发信
关注(28)粉丝(399)

2014哈商大ICPC/ACM校赛解题报告

被debug邀请去參加校赛，哎，被虐。。我对不起工大。。

由于本人不搞ACM，算法处于HelloWorld水准。。

虽然题目除了鸟不拉屎星人之外都非常水，但我能做到这个程度，全然是超水平发挥了。。

数据：点此下载

==============================================================


a：逆序数组+删除特定元素

题目：

代码：
#include <iostream>

#include <vector>

using namespace std;

int main()

{

    int n,tmp,delNum;

    while(cin >> n){

        vector<int> a;

        while(n--){

            cin >> tmp;

            a.push_back(tmp);

        }

        cin >> delNum;

        vector<int>::reverse_iterator a_rIter;

        for(a_rIter = a.rbegin();a_rIter != a.rend(); ++a_rIter){

            if(*a_rIter == delNum)

                continue;

            cout << *a_rIter;

        }

        cout << endl;

    }

    return 0;

}


b：括号匹配


题目：

代码：

#include <iostream>

#include <stack>

using namespace std;

int main()

{

    stack<char> s;

    string str;

    while(cin >> str){

        char tmp;

        bool ans = true;

        for(unsigned int i = 0 ; i < str.size();i++){

            if(str[i] == '(' || str[i] == '[' || str[i] == '{')

                s.push(str[i]);

            else{

                if(s.empty()){ //假设栈为空，并且还遇到这样的字符就直接No了

                    ans = false;

                    break;

                }

                tmp = s.top();

                s.pop();

                if((str[i] == ')' && tmp == '(') ||

                   (str[i] == ']' && tmp == '[') ||

                   (str[i] == '}' && tmp == '{')){

                    continue;

                }else{

                    ans = false;

                    break;

                }

            }

        }

        if(ans)

            cout<<"Yes"<<endl;

        else

            cout<<"No"<<endl;

    }

    return 0;

}

c： 再多一天


题目：

代码：
#include <iostream>

#include <string>

#include <vector>

#include "stdio.h"

using namespace std;

class Time{

public:

    int year;

    int month;

    int day;

    Time(int year,int month,int day)

    {

        this->day = day;

        this->month = month;

        this->year = year;

    }

    bool isRunYear(){

        if((this->year % 4 == 0 && this->year % 100 != 0) || this->year % 400 == 0)

            return true;

        return false;

    }

    void addOneDay(){

        this->day += 1;

        //do with day

        if(this->day == 32){

            this->day = 1;

            this->month += 1;

        }

        else if(this->day == 31 && (this->month == 4 || this->month == 6 || this->month == 9 || this->month == 11)){

            this->day = 1;

            this->month += 1;

        }

        else if(this->day == 30 && this->month == 2 && isRunYear()){

            this->day = 1;

            this->month += 1;

        }

        else if(this->day == 29 && this->month == 2 && !isRunYear()){

            this->day = 1;

            this->month += 1;

        }

        //do with month

        if(month == 13){

            this->month = 1;

            this->year += 1;

        }

    }

};

int main()

{

    int y,m,d;

    while(scanf("%d-%d-%d",&y,&m,&d)==3){

        Time *t = new Time(y,m,d);

        t->addOneDay();

        cout<<t->year<<"-"<<t->month<<"-"<<t->day<<endl;

    }

    return 0;

}

/*改动于2014-4-23:9:23

强子说，推断一个月是不是大月，直接if(this->day == 32) 就好了。。
太有道理了，不然就冗余了。。感谢强子的修正！
*/


一開始傻逼了，我对输入的“2014-1-1”，当成字符串，然后切割。。
附加赠送C++分割字符串，当中vector返回的是year,month,day的int型集合体：
vector<int> split(string str, string patternStr)

{

    vector<int> res;

    for(unsigned int i = 0 ; i < str.size() ; i++){

        int pos = str.find(patternStr,i);

        string s;

        if(pos < str.size() && pos >= 0){

            s = str.substr(i,pos-i);

            i = pos;

        }else{

            s = str.substr(i);

        }

        stringstream ss; //string 转 int

        ss << s;

        int t;

        ss >> t;

        res.push_back(t);

    }

    return res;

}

d：相似字符串

题目：

代码：
#include <iostream>

#include <string>

using namespace std;

int main()

{

    string str1,str2;

    while(cin>>str1>>str2){

        string str3 = str2+str2;

        int length = str1.size();

        if(str3.find(str1)<length)

            cout<<"Yes"<<endl;

        else

            cout<<"No"<<endl;

    }

    return 0;

}

在str2+str2中怎样能找到str1，就是相似。。

string.find() 找不到后会返回一个非常大的值。。不是-1。。

 
/*改动于2014-4-28
C++的find()找不到的时候究竟返回什么，有的说是-1，有的说是无穷大。
str.find("e")返回值是string::size_type。由于 string::size_type (由字符串配置器 allocator 定义) 描写叙述的是 size，故需为无符号整数型别。
由于缺省配置器以型别 size_t 作为 size_type，于是 -1 被转换为无符号整数型别。

找不时,返回值是string::npos。 

npos是这样定义的： static const size_type npos = -1;

但输出是做无符号整数型别输出,即-1的补码4294967295。

所以应该这么用：
当 str.find("哦")==string::npos时则说明字符串str中不存在“哦”这个字符，

反之，str.find("哦")!=string::npos则说明字符串str中存在“哦”这个字符

用string:npos来推断就可以。
*/

e：迷宫


题目：


代码：
#include <iostream>

#include "stdio.h"

using namespace std;

char m[100][100];

int r = 0; //row

int c = 0; //column

void dfs(int x,int y)

{

    if(m[x][y] != '0')

        cout<<m[x][y]<<endl;

    m[x][y] = '1';//标记訪问过

    //down

    if(x+1 < r && m[x+1][y] != '1'){

        dfs(x+1,y);

    }

    //up

    if(x-1 >= 0 && m[x-1][y] != '1'){

        dfs(x-1,y);

    }

    //right

    if(y+1 < c && m[x][y+1] != '1'){

        dfs(x,y+1);

    }

    //left

    if(y-1 >= 0 && m[x][y-1] != '1'){

        dfs(x,y-1);

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    string t;

    int index = 0 ;

    while(cin>>t){

        for(unsigned int i=0;i<t.size();i++)

            m[index][i] = t[i];

        c = t.size();

        index ++;

    }

    r = index;

    //入口在左边，找入口

    for(int i = 0;i<r;i++){

        if(m[i][0] == '0')

            dfs(i,0);

    }

    return 0;

}


f：小胖子厨师


题目：

代码： 
#include <iostream>

using namespace std;

int main()

{

    int n;

    while(cin>>n){

        int ans = (1+n)*n/2 + 1;

        cout<<ans<<endl;

    }

    return 0;

}

这道题不得不停下来吐槽下，平面切割问题。。。


当有n-1条直线时，平面最多被分成了f（n-1）个区域。

则第n条直线要是切成的区域数最多，就必须与每条直线相交且不能有同一交点。

这样就会得到n-1个交点。

这些交点将第n条直线分为2条射线和n-2条线断。

而每条射线和线断将以有的区域一分为二。

这样就多出了2+（n-2）个区域。

故：
f(n)=f(n-1)+n

      =f(n-2)+(n-1)+n

       ……

      =f(1)+1+2+……+n

      =n(n+1)/2+1


g：小气的自来水公司


题目：

代码：
#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include "stdio.h"

using namespace std;

#define MAXN 1000

#define INF 1<<30

int closest[MAXN],lowcost[MAXN],m;// m为节点的个数

int G[MAXN][MAXN];//邻接矩阵

int prim(int m)

{

    for(int i=0;i<m;i++)

    {

        lowcost[i]=INF;

    }

    for(int i=0;i<m;i++)

    {

        closest[i]=0;

    }

    closest[0]=-1;//增加第一个点，-1表示该点在集合U中，否则在集合V中

    int num=0,ans=0,e=0;//e为最新增加集合的点

    while(num<m-1)//增加m-1条边

    {

        int micost=INF,miedge=-1;

        bool flag = false;

        for(int i=0;i<m;i++){ //找出最小边

            if(closest[i]!=-1)

            {

                int temp=G[e][i];

                if(temp<lowcost[i])

                {

                    lowcost[i]=temp;

                    closest[i]=e;

                }

                if(lowcost[i]<micost){

                    micost=lowcost[i];

                    miedge = i;

                    flag = true;

                }

            }

        }

        if(!flag){

            return -1;

        }

        ans+=micost;

        closest[miedge]=-1;

        e = miedge;

        num++;

    }

    return ans;

}

int main()

{

    int m,n;

    while(scanf("%d %d",&m,&n) == 2){

        for(int i=0;i<m;i++) //清空数组

            for(int j=0;j<m;j++)

                G[i][j] = INF;

        char a,b;

        int w;

        for(int i = 0 ; i < n;i++){

            cin>>a>>b>>w;

            G[a-'A'][b-'A'] = w;

            G[b-'A'][a-'A'] = w;

        }

        int ans = prim(m);

        if(ans == -1)

            cout<<"Can't do it"<<endl;

        else

            cout<<"Total:"<<ans<<endl;

    }

    return 0;

}




h：吐槽星人大战鸟不拉屎大王


题目：

/*改动于2014-4-28

这道题用到了：偏序集的Dilworth定理!

样例例如以下：

求一个序列的最长上升子序列。其最大值即等于不上升子序列的最小划分数。

这就涉及到组合数学中偏序集的 Dilworth定理，代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int a[100],f[100],g[100];

int main(){

    freopen("lmis.in","r",stdin);

    freopen("lmis.out","w",stdout);

    int n,i;

    scanf("%d",&n);

    memset(g,0x7f,sizeof(g));

    memset(f,0,sizeof(f));

    for(i=0;i<n;i++)

      scanf("%d",&a[i++]);

    for(i=0;i<n;i++){

            int k=lower_bound(g+1,g+n,a[i])-g;

            f[i]=k+1;

            g[k+1]=a[i];

    }

    printf("%d\n",*max_element(f,f+n));

    return 0;

}

*/

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=250*250+10;

const int INF=9999999;

int b[MAXN],n,p,q;

int g[MAXN],id[MAXN],x[MAXN];//g[i]:ICS为i时候的最小下标，x[i]：lis值

int main()

{

    //freopen("1.txt","r",stdin);

    int T,kase=1;

    while(scanf("%d",&T)==1){

        kase=1;

        while(T--)

        {

            int temp,len=0;

            scanf("%d%d%d",&n,&p,&q);

            memset(id,0,sizeof(id));

            for(int i=1;i<=p+1;i++)

            {

                scanf("%d",&temp);

                id[temp]=i;

            }

            for(int i=0;i<q+1;i++)

            {

                scanf("%d",&temp);

                if(id[temp])

                    b[len++]=id[temp];

            }

            for(int i=0;i<=len;i++)

                g[i]=INF;

            int ans=0;

            for(int i=0;i<len;i++)

            {

                int k=lower_bound(g+1,g+len+1,b[i])-g;

                x[i]=k;

                g[k]=b[i];

                ans=max(ans,x[i]);

            }

            printf("Case %d: %d\n",kase++,ans);

        }

    }

    return 0;

}

05-01 02:05
Powered by LMLPHP ©2024 npos 0.059117