FOJ月赛-2011.12

gzhu_101majia

浏览: 204953 次
性别:
来自: 广州

最近访客更多访客>>

那个人1

很厉害的jq

leave8426

Tension1900

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

比赛

C++ACM 数据结构算法月赛

福州大学月赛总结（2011.12）

福州大学12月的月赛，平常很少去比赛，这次就说说，总结一下吧。

排名刚刚50：

链接：http://acm.fzu.edu.cn/contest/list.php?cid=118

第一题：

水题啊！竟然没看清是按顺序的，还排序了，WA两次，冲动是魔鬼！

代码：

#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;

int a[105];

int main()
{
    int i, n, q, num, sum, t;
    while(scanf("%d", &n) != EOF)
    {
        for(i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        //sort(a, a+n);
        scanf("%d", &q);
        while(q--)
        {
            scanf("%d", &t);
            num = sum = 0;
            for(i = 0; i < n; i++)
            {
                if(sum + a[i] <= t)
                {
                    sum += a[i];
                    num++;
                }
                else break;
            }
            printf("%d\n", num);
        }
    }

    return 0;
}

第二题：

还是水题，直接暴力就行，数据很小，居然也WA了一次，忘记判断越界!冲动是魔鬼！

代码：

#include <iostream>
#include <stdio.h>
using namespace std;

int a[105][105];

int main()
{
    int i, j, k, t, n, m, w, num;
    bool flag;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d %d", &n, &m, &w);
        for(i = 0; i < n; i++)
            for(j = 0; j < m; j++)
                scanf("%d", &a[i][j]);
        num = 0;
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < m; j++)
            {
                if(j + w > m) break;
                flag = true;
                for(k = j; k < j+w; k++)
                {
                    if(a[i][k] == 1)
                    {
                        flag = false;
                        break;
                    }
                }
                if(flag) num++;
            }
        }
        printf("%d\n", num);
    }

    return 0;
}

第三题：

模拟题，判断是否是数字，很好的模拟题，考你的基本功，我分了5种情况判断是否合法，写得很长，不过最终还是过了！

代码：

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
using namespace std;

char str[15];

bool judge()
{
    int i, len;
    int dot_pos, e_pos, s_pos;
    bool b_dot, l_dot, e_flag, s_flag, num_flag;
    char ch[15];
    strcpy(ch, str);
    len = strlen(ch);
    for(i = 0; i < len; i++)
    {
        if( !(ch[i] >= '0' && ch[i] <= '9'
           || ch[i] == '.'
           || ch[i] == 'e' || ch[i] == 'E'
           || ch[i] == '+' || ch[i] == '-') ) return false;
        /// 有不合法字符
    }
    b_dot = l_dot = false;
    e_flag = s_flag = false;
    num_flag = false;
    if(ch[0] == '.')    /// 有前置'.'
    {
        b_dot = true;
        for(i = 1; i < len; i++)
        {
            ch[i-1] = ch[i];
        }
        ch[len-1] = 0;
    }
    len = strlen(ch);
    if(len == 0) return false;
    for(i = 0; i < len; i++)
    {
        if(ch[i] == '.')
        {
            dot_pos = i;
            l_dot = true;
            break;
        }
    }
    if(b_dot && l_dot) return false;  /// 有两个'.'

    if(l_dot)   /// 有后置的'.'
    {
        for(i = 0; i < dot_pos; i++)
        {
            if( !(ch[i] >= '0' && ch[i] <= '9') ) return false;
        }
        for(i = dot_pos + 1; i < len; i++)
        {
            if(ch[i] == '+' || ch[i] == '-' || ch[i] == '.') return false;
            if(ch[i] == 'e' || ch[i] == 'E')
            {
                e_flag = true;
                e_pos = i;
                break;
            }
        }
    }
    else    /// 没有后置'.'
    {
        for(i = 0; i < len; i++)    /// 则后面 全部是数字 或 有e
        {
            if( !(ch[i] >= '0' && ch[i] <= '9') && !num_flag) return false;
            if(ch[i] >= '0' && ch[i] <= '9') num_flag = true;

            if(ch[i] == '+' || ch[i] == '-') return false;
            if(ch[i] == 'e' || ch[i] == 'E')
            {
                e_flag = true;
                e_pos = i;
                break;
            }
        }
    }

    if(e_flag)  /// 后面有e
    {
        if(e_pos + 1 >= len) return false;      /// 以e/E结束，错误

        /// 判断是否有+符号
        if(ch[e_pos+1] == '+' || ch[e_pos+1] == '-')
        {
            s_flag = true;
            s_pos =  e_pos + 1;
        }
        else s_pos = e_pos;

        if(s_flag)  /// 有+符号
        {
            if(s_pos + 1 >= len) return false;  /// 以符号结束，错误
            for(i = s_pos + 1; i < len; i++)
            {
                /// +符号后面只有数字，若不是则错误
                if( !(ch[i] >= '0' && ch[i] <= '9') ) return false;

            }
        }
        else    /// 没有+符号
        {
            for(i = s_pos + 1; i < len; i++)
            {
                if( !(ch[i] >= '0' && ch[i] <= '9') ) return false;
            }
        }
    }
    return true;
}

int main()
{
    int t;
    scanf("%d", &t);
    getchar();
    while(t--)
    {
        scanf("%s", str);
        if(judge()) printf("%s\n", str);
    }

    return 0;
}

第四题：

当时没做出来，原来是先按x小到大排序，x相同按y从小到大排，然后求y的最长递减序列，数据是10W，要用nlgn的算法，原来一个二分就行！

代码：

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

struct Node
{
	int x, y;
}a[100005];

int que[100005];

bool cmp(Node a, Node b)
{
	if(a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

int half(int x, int len)
{
	int l, r, mid;
	l = 0;
	r = len - 1;
	while(l <= r)
	{
		mid = (l + r) >> 1;
		if(que[mid] > a[x].y) l = mid + 1;
		else r = mid - 1;
	}
	return l;
}

int main()
{
	int i, k, n, m, ans;
	while(scanf("%d %d", &n, &m) != EOF)
	{
		for(i = 0; i < m; i ++)
        {
            scanf("%d %d", &a[i].x, &a[i].y);
        }
		sort(a, a + m, cmp);
		ans = 0;
		for(i = 0; i < m; i++)
		{
			k = half(i, ans);
			que[k] = a[i].y;
			if(k >= ans) ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}

第五~八题：

题目没怎么看，搞其他题目弄了很多时间，很少人做出来，应该很难做出来了，所以就这样。

第九题：

寻找一个lucky数，任意3位的数不能相同，而且不能有递增或者递减的数，如果是两位数，两个数不能相同，一位数就肯定算lucky数。例如：1324就不属于lucky数，因为有1-3-4这样递增的3个数，所以不行，132、5386等就可以。经过研究，发现五位数以上都是不行的，就这样，用暴力解决了。

代码：

#include <iostream>
#include <stdio.h>
using namespace std;

bool lucky[1000005];

bool violent(int len, int a[])
{
    if(len == 2)
    {
        if(a[0] == a[1]) return false;
        return true;
    }
    if(len == 3)
    {
        if(a[0] <= a[1] && a[1] <= a[2]) return false;
        if(a[0] >= a[1] && a[1] >= a[2]) return false;
        if(a[0] == a[1] || a[0] == a[2] || a[1] == a[2]) return false;
        return true;
    }
    if(len == 4)
    {
        if(a[0] <= a[1] && a[1] <= a[2]) return false;
        if(a[0] <= a[1] && a[1] <= a[3]) return false;
        if(a[0] <= a[2] && a[2] <= a[3]) return false;
        if(a[1] <= a[2] && a[2] <= a[3]) return false;
        if(a[0] >= a[1] && a[1] >= a[2]) return false;
        if(a[0] >= a[1] && a[1] >= a[3]) return false;
        if(a[0] >= a[2] && a[2] >= a[3]) return false;
        if(a[1] >= a[2] && a[2] >= a[3]) return false;
        if(a[0] == a[1] || a[0] == a[2] || a[0] == a[3]) return false;
        if(a[1] == a[2] || a[1] == a[3] || a[2] == a[3]) return false;
        return true;
    }
    return true;
}

bool judge(int n)
{
    int i, len, ans, a[10];
    len = 0;
    ans = n;
    while(ans)
    {
        ans /= 10;
        len++;
    }
    ans = n;
    for(i = len-1; i >= 0; i--)
    {
        a[i] = ans%10;
        ans /= 10;
    }
    return violent(len, a);
}

void init()
{
    int i;
    for(i = 0; i < 10000; i++)
    {
        lucky[i] = judge(i);
    }
    for(i = 10000; i <= 1000000; i++)
    {
        lucky[i] = false;
    }
}

int main()
{
    int i, t, li, ri, num;
    init();
    scanf("%d", &t);
    while(t--)
    {
        num = 0;
        scanf("%d %d", &li, &ri);
        for(i = li; i <= ri; i++)
        {
            if(lucky[i]) num++;
        }
        printf("%d\n", num);
    }
    return 0;
}