`

FOJ月赛-2011.12

阅读更多

福州大学月赛总结(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;
}

 

 

  • 大小: 19.7 KB
  • 大小: 2.4 KB
0
1
分享到:
评论

相关推荐

    FOJ.1207.zip_26.2_了然foj

    给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下。 (1)n∈set(n); (2)在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半; (3)按此规则进行处理,直到不能再添加自然数为止。...

    foj.rar_On the Line_meet62l_pick8xd_界面编程

    Source code example for shortcuts to create arbitrary files on the command line

    FOj部分水题AC答案

    代Un的还没被Ac,其余不保证算法够好,只是随便传传

    FOJ 1150 Peter's smokes

    第一次上传东西... 本人是个初学者,希望大家多多指教

    FOJ(大部分标程) ACM

    FOJ(大部分标程) ACMFOJ(大部分标程) ACMFOJ(大部分标程) ACMFOJ(大部分标程) ACMFOJ(大部分标程) ACMFOJ(大部分标程) ACM

Global site tag (gtag.js) - Google Analytics