| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 42026 人关注过本帖, 47 人收藏
标题:C论坛算法团队 首战 西安电子科技大学OJ
只看楼主 加入收藏
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
结帖率:100%
收藏(47)
已结贴  问题点数:100 回复次数:178 
C论坛算法团队 首战 西安电子科技大学OJ
闻名遐迩的西电,以信息科学见长。但OJ的规模却与其名气不太相称,不足两百个题目。这也是首战选择西电的主要原因。

但少并不代表简单,我也不敢保证能搞定它所有的题目,所以这次应该会玩的比较尽兴。

学校简介

西安电子科技大学,简称西电。是以信息与电子学科为主,工、理、管、文多学科协调发展的全国重点大学,直属教育部,是国家“优势学科创新平台”项目和“211工程”项目重点建设高校之一,是全国56所设有研究生院的高校之一、首批35所示范性软件学院的高校之一和首批9所获批设立集成电路人才培养基地的高校之一。
 
学校前身是1931年诞生于江西瑞金的中央军委无线电学校,是毛泽东等老一辈革命家亲手创建的第一所工程技术学校。1958年学校迁址西安,1966年转为地方建制,1988年定为现名。
 
建校80余年来,学校始终得到了党和国家的高度重视,是我国“一五”重点建设的项目之一,也是1959年中央批准的全国20所重点大学之一。20世纪60年代,学校就以“西军电”之称蜚声海内外。毛泽东同志曾先后两次为学校题词:“全心全意为人民服务”、“艰苦朴素”。
 
学校现建设有南北两个校区,总占地面积约270公顷,校舍建筑面积130多万平方米,图书馆馆藏文献575万册。学校现有各类在校生3万余人,其中博士研究生近1700人,硕士研究生8600余人,设有通信工程学院、电子工程学院、计算机学院、机电工程学院、技术物理学院、经济管理学院、理学院、人文学院、示范性软件学院、微电子学院、国际教育学院、生命科学技术学院、网络与继续教育学院以及长安学院等14个学院。
 
学校是国内最早建立信息论、信息系统工程、雷达、微波天线、电子机械、电子对抗等专业的高校之一,开辟了我国IT学科的先河,形成了鲜明的电子与信息学科特色与优势。现有2个国家一级重点学科(覆盖6个二级学科)、1个国家二级重点学科,28个省部级重点学科, 12个博士学位授权一级学科,涵盖50个二级学科,20个硕士学位授权一级学科,涵盖101个二级学科。7个博士后科研流动站,52个本科专业。2006年教育部公布全国第二轮一级学科评估结果中,“信息与通信工程”学科全国排名第二,“电子科学与技术”学科全国排名第六。

活动规则

尽情的挑你喜欢的题目去做,AC后总结一下题目的算法分析心得,连同AC代码一起跟贴在这里。

当然在发贴前看一下前面是否已经有人解过这个题目,如果已经被解过,且别人的算法更优秀,那就没必要再发贴了。

如果你觉得自己的算法更优秀,那就不要犹豫,发上来吧。

我会定期整理跟贴,以保证大家的精华言论不被聊天贴掩盖。

OJ地址:http://acm.xidian.

还在等什么? 快去注册个账号开始吧!
搜索更多相关主题的帖子: 高校 重点大学 西安电子 直属教育部 
2012-10-01 16:53
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1001 - A+B Problem
关于发贴格式,这里简单规范一下。以下三部分是必须要有的:

1.题目精确描述

2.算法分析过程

3.实现代码(必须是AC的)

完整包含上述三部分的帖子我将视其为正式解题贴,整理时将完整保留。其他帖子根据内容可能会被定期删除。

下面作个示范,不必完全按这个格式,但条理一定要清晰。

题目描述
Problem 1001 - A+B Problem

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 4242  Accepted: 1116  Special Judge: No

Description

Calculate a + b

Input

Two integer a, b (0<=a, b<=10)

Output

Output a + b

Sample Input

1 2

Sample Output

3

Hint

Source
分析
A+B Problem 几乎是所有OJ的第一个题目。主要是为让大家熟悉ACM的编程方式。

ACM对输入输出格式的要求非常严格,阅读题目时一定要注意。另外建议大家去一个学校的OJ时先看看它的FAQ,了解一下编译器。

题目描述分成以下几部分:

1.题号及标题

2.Description:题目的具体描述,经常会给一个有趣的故事背景

3.Input:问题输入格式的具体描述,即你要接收的数据格式,你要根据它来安排你的数据读取方式

4.Output:问题输出格式的具体描述,即你要print给OJ系统的数据格式,你要根据它来输出你的结果

5.Sample Input:输入示例,一个具体的例子,但不一定是OJ判定时用的数据

6.Sample Output:输出示例,你可以用输入示例测试你的代码,结果如果和输出示例不同,呵呵别急着提交,考虑一下为什么不同

7.Hint:有些题目会在这里给出一些重要提示,有的话一定要看看

8.Source:题目来源

对于这一题,就是接收两个数,然后输出它们的和即可。

提交结果有以下几种:

1.Accepted. ---通过!(AC)

2.Wrong Anwser. ---答案错。(WA)

3.RunTime Error. ---程序运行出错,意外终止等。(RTE)

4.Time Limit Exceeded. ---超时。程序没在规定时间内出答案。(TLE)

5.Presentation Error. ---格式错。程序没按规定的格式输出答案。(PE)

6.Memory Limit Exceeded. ---超内存。程序没在规定空间内出答案。(MLE)

Error. ---编译错。程序编译不过。(CE)

我们的目标是AC。如果得到的是其它结果,请根据结果重新检查代码。
AC代码
程序代码:
#include<stdio.h>
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

重剑无锋,大巧不工
2012-10-01 17:41
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1002 - another a+b
Problem 1002 - another a+b

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 1241  Accepted: 856  Special Judge: No

Description

Just for add problem test, but notice it, this time you got multiple inputs(may contain more than 3 data cases,notice it!)

Input

1 2
2 3
3 4

Output

3
5
7

Sample Input

1 2

Sample Output

3

Hint

如何处理多组数据的输入?
 
在C和C++里,我们可以使用 scanf 的返回值,如果返回值为EOF,则说明已无下一组数据,也可以使用cin的返回值,如果cin返回0,则说明无更多数据。
 
在java中,可以使用Scanner的 hasNext() 函数判断是否还有数据,hasNext() 返回 true,说明还有后续数据,若返回false,说明无更多数据。
 
Here is a sample solution for problem 1002 using C++:
 
#include <iostream>
 
using namespace std;
 
int main()
 
{
 
    int a,b;
 
    while(cin >> a >> b)
 
          cout << a+b << endl;
 
}
 
Here is a sample solution for problem 1002 using C:
 
#include <stdio.h>
 
int main()
 
{
 
      int a,b;
 
      while(scanf("%d %d",&a, &b) != EOF)
 
             printf("%d\n",a+b);
 
             return 0;
 
}
 
Here is a sample solution for problem 1002 using PASCAL:
 
program p1002(Input,Output);
 
var
 
    a,b:Integer;
 
begin
 
    while not eof(Input) do
 
       begin
 
           Readln(a,b);
 
           Writeln(a+b);
 
       end;
 
end.
 
Here is a sample solution for problem 1002 using Java:
 
import java.util.Scanner;
 
public class Main {
 
          public static void main(String[] args) {
 
          Scanner in = new Scanner(System.in);
 
           while (in.hasNextInt()) {
 
                      int a = in.nextInt();
 
                      int b = in.nextInt();
 
                      System.out.println(a + b);
 
           }
 
     }
 
}
 
Source
分析
另一个练习问题。仍然是计算两个数的和,不过这次是有多组数据输入,要求也要有多组数据输出。

Input中有三组数据,Output中是对应在三组输出结果。

很多初学者有这样的疑问,是该计算出所有的结果一起输出,还是该计算出一组结果输出一组呢?

答案是都可以,但建议使用后者的方式。因为前者需要缓存已计算好的结果,浪费有限的内存。

原因,参看数据“流”的概念,并了解C语言的三个标准流(stdin, stdout, stderr)。

为了文档的完整性,虽然题目的Hint中已经有了正确代码,这里再贴一遍吧。
程序代码:
#include<stdio.h>
int main()
{
    int a, b;
    for(; scanf("%d%d", &a, &b) != EOF; printf("%d\n", a + b));
    return 0;
}

重剑无锋,大巧不工
2012-10-02 09:35
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1003 - 最喜欢的数字
前面两题属于熟悉OJ平台用法的试验题,主要是熟悉数据的接收和输出操作,也谈不上用什么算法。

而ACM的乐趣,现在才真正开始。

Problem 1003 - 最喜欢的数字

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 2164  Accepted: 208  Special Judge: No


Description


         zyf最喜欢的数字是1!所以他经常会使用一些手段,把一些非1的数字变 成1,并为此得意不已。他会且仅会的两种手段是:
1.把某个数m除以某个质数p——当然p必须能整除这个数,即m=m/p
2.把某个数m减1,即m=m-1
有一天他突发奇想,想把[a,b]区间中所有的数一个一个地变成1,这是一个巨大的无聊的工程,所以他想知道他最少得花多少操作才能达到目 的。

Input

  输入包含多组数据(1000组数据),EOF结束。
  每组数据以两个整数开头:a,b(0<a<=b<=100000),意义如题意描述。

Output

  每组数据输出一行,最少操作数。

Sample Input

2 3
3 5
11 12

Sample Output

2
4
3

Hint


Source

2010.04内部测试赛(Author: Qinz)
分析
要完成题目的要求,我们需要知道将一个数A按规则变换成1需要多少步。

一般看到这题的第一个想法会是实际地变换一下,尝试所有可能的变换方式,然后记下其中最少的操作数。

ACM是一种极限编程,它是有时间限制的,这道题目要求的时限是1秒。超过时限没有给出结果OJ会终止你的程序进程。给你一个TLE的判定结果。比赛中,除了AC外,其它结果均不得分。

如果用上面的方法计算100000这个数的最少操作步骤,别说是1秒,我在想1个小时能不能出结果。

表面上看这题目该算是道数论相关的题目。

实际上,真正解决这个问题的理论基础和手段来源于图论(至少我是这样解决的)。

将一个数除以一个质数或减1变换成1的过程,倒过来即是将1乘以一个质数或加1而得到这个数的过程。其它的步骤数相同。

建立这样一个图模型,以1到A的所有整数值为结点,如果数a通过加一次1或乘一次质数得到b,那么建立a到b之间的边,设边的权为1。

由此,A的最少操作数等同于图中由1到A的最短路径长度。

尤其本题要求的是一个范围内的数的最少操作数之和,所以可以应用最短路径算法求出1到其它所有值的最短路径长度。

以上既是算法分析的主要部分。

至于图论,它是一种数学分析手段,实际应用中视情况使用合适的数据结构,不一定一提到图就非得出现个邻接矩阵或是若干结构体结点。

初学的朋友不妨仔细体会一下上述图论算法在我的代码中是如何表达的。
程序代码:
#include<stdio.h>
#define N    100000
int main()
{
    int e[N + 1] = {0}, p[N], pn = 0, an, m, i, j, t;

    for(i = 2; i <= N; e[i++] = 1);

    for(i = 2; i <= N; i++)
    if(e[i]) for(p[pn++] = i, j = i + i; j <= N; j += i) e[j] = 0;

    for(an = pn, i = 0; an < N - 1; i++)
    {
        if((t = p[i] + 1) <= N && !e[t]) e[p[an++] = t] = e[p[i]] + 1;

        for(j = 0, m = N / p[i]; j < pn && p[j] <= m; j++)
        if(!e[t = p[i] * p[j]]) e[p[an++] = t] = e[p[i]] + 1;
    }

    for(i = 3; i <= N; i++) e[i] += e[i - 1];

    while(scanf("%d%d", &i, &j) != EOF) printf("%d\n", e[j] - e[i - 1]);

    return 0;
}

重剑无锋,大巧不工
2012-10-02 10:23
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1004 - 亚特兰提斯
Problem 1004 - 亚特兰提斯

Time Limit: 5000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 161  Accepted: 28  Special Judge: No


Description


  为了找寻沉睡的亚特兰提斯大陆,wm来到了大西洋上进行探险,找了半个月仍一无所获。然而在一次突袭而来的暴风雨后,wm
的船莫名地驶入了一片未知的区域,发现了一个地图上未标记的岛屿,这让他感到相当惊讶,强烈的好奇心驱使他上岸看看究竟。
船在岛屿靠岸后岛上的国王举行庆典热情地款待了他,整个岛一片喜庆。国王自称是亚特兰提斯人,而这个岛屿曾经是亚特兰提斯
大陆的最高地。现在岛屿上还有N个城市,由于岛上的资源相当有限且岛上没人知道怎么合理利用资源故一直以来在城市之间都没
有铺设道路,现在国王想请wm规划下道路并进行建设,国王对规划的要求如下:
  1.所有城市必须连通,即任意两个城市都可以互相来往
  2.国王是个娇气的人,所以他希望从任意城市走到任意另一个城市时的“舒适度”越高越好,其中两个城市间的“舒适度”定
义为:两个城市间路径的每一段道路的“舒适度”的最小者,例如从A到B需要经过C城市,A->C段“舒适度”为10,C->B段“舒适
度”为100,则A->B的“舒适度”为10(当然如果两个城市间有很多路径的话国王会走“舒适度”最大的路径)。现在定义K为所有
两个城市间“舒适度”的最小者,而国王希望K越大越好。
  现在岛上的资源只有R单位,国王希望wm帮他规划道路满足他的要求,在岛上资源条件的允许下输出最大的K。如果岛上的资源
不够满足第1个要求,则输出-1。
wm沉迷于岛上的玩乐,懒得去想这问题了,所以他远程求助你,帮他解决这个烦人的问题。

Input

  输入包含多组数据,EOF结束。
  每组数据以三个整数开头,N,M,R。N(2<=N<=1000)是城市数,M(0<=M<=100000)是允许建造的道路数,R(0<=R<=100000
)是岛上仅有的资源数。EOF结束。
  接下来有M行数据,每行包括a,b(0<=a,b<N),v(0<v<=100000),c(0<=c<=100000)四个整数,表示ab城市间允许建一条
双向道路,花费v单位资源,“舒适度”为c。

Output

  每组数据输出一行,岛上资源条件的允许下最大的K或-1。

Sample Input

3 3 1000
0 1 20 8
1 2 10 7
2 0 10 6
3 3 20
0 1 20 8
1 2 10 7
2 0 10 6
2 1 10
0 1 20 8

Sample Output

7
6
-1

Hint


  第一组样例资源允许建设全部三条路(当然也可以只建0-1和1-2这两条道路),其中0-1之间的“舒适度”为8,1-2之间的“
舒适度”为7,0-2之间的“舒适度”为7(可以从城市1中转,不直接走0-2这条“舒适度”为6的道路),故K值为min(8,7,7)=7,
由于找不到更好的方案使K值更大,故输出7。

Source

2010.04内部测试赛(Author: Qinz)
分析
这个题目的难度该算是hard吧。至少我用了很长时间来分析。

问题的目标是在资源允许的情况下建设成能连通所有城市的路网并尽量舒适。

先对这些条件的优先级排一个序。

首先,允许建设的道路必须能连通所有城市。如果判定不能连通,就不必再计算其它条件了。

第二,建设的道路网的费用不能超支。

第三,在有路的条件下国王要求尽量舒适。

这题应该不止一种方案,下面的代码虽然AC,但耗时1秒多,比起排名第一的代码(耗104毫秒)差一个数量级。很想知道他的算法是什么样的。

不管怎样,先解释一下我的方案吧。

第一步,在允许建设的道路范围内尝试建立费用最小的能连通所有城市的路网,即以费用为条件建立最优生成树(因为费用最省,必然不会出现回路)。

第二步,计算最优树的舒适度。

第三步,在允许建设的道路集中删除舒适度小于等于最优树舒适度的路。重新执行第一步,直至不能建立连通图。

那么,最后一次可以建立的最优树的舒适度就是结果所要求的最大舒适度。

最优生成树的建立属于prim算法,不过对边的划入判定我是通过对顶点的染色来完成的。

整个算法的最坏复杂度为 O(N * N * M)。

提交前我一直在怀疑这样的算法能否在时限内完成,看起来,实际边集的收敛速度比我预想的要好,或者没遇到极限数据?

真诚期待更好的算法出现。
程序代码:
#include<stdio.h>
#include<stdlib.h>
#define MAX_N    1000
#define MAX_M    100000
struct{ int a, b, v, c; }E[MAX_M];
int N, M, R;
int cvf(const void * a, const void * b){ return E[*(int *)a].v - E[*(int *)b].v;}
int gv(int *ei, int en)
{
    int v[MAX_N], c = MAX_M, r = R, i, j, t, va, vb, vc;
    if(en < N - 1) return -1;
    for(i = 0; i < N; v[i] = i++);
    for(j = 1, i = 0; i < en && j < N && r > 0; i++)
    {
        if((va = v[E[ei[i]].a]) == (vb = v[E[ei[i]].b])) continue;
        if(c > (vc = E[ei[i]].c)) c = vc;
        for(j++, r -= E[ei[i]].v, t = 0; t < N; t++)
            if(v[t] == vb) v[t] = va;
    }
    if(j < N || r < 0) return -1;
    return c;
}
int cal()
{
    int ei[MAX_M], en = M, i, j, k, t;
    if(M < N - 1) return -1;
    for(i = 0; i < en; ei[i] = i++);
    qsort(ei, M, sizeof(int), cvf);
    for(k = -1; (t = gv(ei, en)) >= 0; en = j)
    {
        if(k < t) k = t;
        for(j = i = 0; i < en; i++)
            if(E[ei[i]].c > t) ei[j++] = ei[i];
    }
    return k;
}
int main()
{
    int i;
    for(; scanf("%d%d%d", &N, &M, &R) != EOF; printf("%d\n", cal()))
    for(i = 0; i < M; i++) scanf("%d%d%d%d", &E[i].a, &E[i].b, &E[i].v, &E[i].c);
    return 0;
}

重剑无锋,大巧不工
2012-10-02 11:13
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1005 - 跳舞毯
Problem 1005 - 跳舞毯

Time Limit: 2000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 193  Accepted: 62  Special Judge: No


Description


  zyf不小心得了一种怪病,为了维持一天的精力他必须不停跳动。于是他买了一条跳舞毯,每天跳上几小时。众所周知,跳舞毯是给定一个序列,让你在指定时间踏指定的按钮,但zyf似乎不怎么擅长,为此他写了个外挂,以修改它的输入序列,得到满分!
  这个外挂的厉害之处在于它能等到zyf跳完、输入序列后再进行修改,修改的方式有三种,在任意位置插入、删除或替换一个指令,每次插入需要a时间,删除需要b时间,替换需要c时间,现在zyf想用最短时间去修改他输入的序列得到满分(即与给定序列一样),但这显然已经超过了当前外挂的能力范围,于是只好求助于你,给这外挂写个补丁。

Input

  输入包含多组数据,EOF结束。
  每组数据包括三行,第一行包含三个整数a,b,c(0<a,b,c<=100),如上文描述,第二行是跳舞毯给定的序列,第三行是zyf跳完、输入的序列,两者的长度都不大于1000,只包含大小写字母。

Output

  每组数据输出一行,最少修改时间。

Sample Input

1 2 3
LDDD
DDDR
7 1 3
LDDR
LZRZDD

Sample Output

3
8


Hint


Source

2010.04内部测试赛(Author: Qinz)
分析
问题类似最长公共子序列问题。最长公共子序列及最长公共子串,是每个程序员都应该掌握的基础算法之一。

其实回头看看常用的基础算法不过区区数十个,学会这些算法并不难。难的是能够把这些算法融会贯通地应用到实际问题当中。

这需要长期的、反复的、坚持不懈的,练习钻研。

这个过程并不好受,所以我也不责怪那些一提算法就牢骚满腹朋友。

其实不光是算法。大多数事情,没有兴趣和信念的支撑,没几个人能做出什么成就。

这里没提天赋的事,天赋即龙睛,要想成事必不可少。

每个人都有天赋,但不一定相同。那如何确定自己的天赋在哪儿呢?

其实很简单,你的兴趣在哪儿,你的天赋就在哪儿。


多说了几句题外话,书归正传,说说本题的解题思路。

这题适合用动态规划的思想来解决。



A为跳舞毯给定序列,A(i)表示序列A的前i个元素构成的子序列

B为输入的序列,B(j)表示序列B的前j个元素构成的子序列

f(i, j)为将B(j)转化为A(i)所需要的最少时间。(大家要尽量学会这样的思维方式)

那么

f(0, 0) = 0             两个空序列之间转换,需要的时间为零

f(i, 0) = i * a         将一个空序列转换成A(i)当然是将A(i)的元素全插入其中了

f(0, j) = j * b         将B(j)转换成一个空序列当然是将B(j)的元素全删除掉

以上是边界条件,现在讨论f(i, j)的情况

如果A[i] == B[j],(表示A的第i个元素和B的第j个元素)

那么转换时不必操作这个元素,它不消耗时间,即

f(i, j) = f(i - 1, j - 1)

如果A[i] != B[j],那么

f(i, j) = min( f(i - 1, j) + a, f(i, j - 1) + b, f(i - 1, j - 1) + c)


算法的时间复杂度是O(M * N),M、N即A、B的序列长度。如果用一个状态阵来存储f的值,那空间复杂度也是O(M * N)。

但注意观察f(i, j)的计算过程,只与本行即上一行的元素有关,所以利用这一点可以将空间复杂度优化到O(M),也可以是O(N)。
程序代码:
#include<stdio.h>
#include<string.h>
int cal(char * s1, char * s2, int a, int b, int c)
{
    int m[2048], *p1 = m, *p2 = &m[1024], *pt;
    int s1n, s2n, sn, i, j, t;
    s1n = strlen(s1);
    s2n = strlen(s2);
    for(p1[0] = i = 0; i < s1n; i++) p1[i + 1] = p1[i] + b;
    for(i = 0; i < s1n; pt = p1, p1 = p2, p2 = pt, i++)
    for(p2[0] = p1[0] + a, j = 0; j < s2n; j++)
        if(s1[i] == s2[j]) p2[j + 1] = p1[j];
        else{
            t = p1[j + 1] + a;
            t = t > p1[j] + c ? p1[j] + c : t;
            t = t > p2[j] + b ? p2[j] + b : t;
            p2[j + 1] = t;
        }
    return p1[s2n];
}

int main()
{
    char s1[1024], s2[1024];
    int a, b, c;
    while(scanf("%d%d%d%s%s", &a, &b, &c, s1, s2) != EOF)
        printf("%d\n", cal(s1, s2, a, b, c));
    return 0;
}

重剑无锋,大巧不工
2012-10-03 09:32
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1006 - 转盘游戏
Problem 1006 - 转盘游戏

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 14  Accepted: 11  Special Judge: No


Description


  wm最近喜欢上一种无聊的转盘解锁游戏,他每天都会为这游戏消磨上三个小时的时间。这游戏由三个正六边形拼成,拼成后一共有13个点,其中有4个黑点和9个白点,如下图。每一步可以顺时针或逆时针转动三个六边形的任意一个60度,转动时六边形的顶点也会相应转动,而这游戏的目的是把四个黑点都转到中间(图中最后一个状态)。这是一个很简单的游戏,想达到游戏目的并不难,但wm觉得这样没挑战性,他决定对于任意一个初始状态,用最少的步数去玩这个游戏。   

Input

  输入包含多组数据(500组),EOF结束。
  每组数据都只有一行13个字符的01串,以从上到下,从左到右的点的顺序表示初始状态(这个由三个正六边形拼成图形最上面一排两个点编号为1 2,第二排三个点编号为3 4 5,依此类推,最后一个点编号为13。第一组样例为上图的初始状态),其中1表示黑点0表示白点。

Output

  每组数据输出一行,解出游戏需要的最小步数。

Sample Input

0000000101011
1011000001000

Sample Output

3
2

Hint


Source

2010.04内部测试赛
分析
这个问题仍然是状态搜索,图的最短路径问题,与1003题没有本质的区别。

原文中的图片也显示不出来,估计被删了。三个六边形的位置大概如下。

   /\    /\
  /  \  /  \
 /    \/    \
|     |     |
|     |     |
 \    /\    /
  \  /  \  /
   \/    \/
   |     |
   |     |
    \    /
     \  /
      \/

代码中的turn函数完成将一个代表一个转盘状态的数值s转变成旋转d一次后的相应数值。

d表示旋转方式一共三个转盘,每个可以顺时针或逆时针旋转,所以共6种旋转方式。
程序代码:
#include<stdio.h>
int turn(int s, int d)
{
    const int c[6][6] = {
        {0, 2, 5, 8, 6, 3}, {0, 3, 6, 8, 5, 2},
        {1, 3, 6, 9, 7, 4},    {1, 4, 7, 9, 6, 3},
        {6, 8, 10, 12, 11, 9}, {6, 9, 11, 12, 10, 8}
    };
    int b[13] = {}, i, t;
    for(i = 0; s; s >>= 1) b[i++] = s & 1;
    for(t = b[c[d][i = 0]]; i < 5; i++) b[c[d][i]] = b[c[d][i + 1]];
    b[c[d][5]] = t;
    for(i = 0; i < 13; i++) s |= b[i] << i;
    return s;
}
int main()
{
    int t[8192] = {}, s[8192] = {0x348}, sn = 1, i, j, ts;
    char str[16];
    for(i = 0; i < sn; i++)
    for(j = 0; j < 6; j++)
    {
        ts = turn(s[i], j);
        if(!t[ts]) t[ts] = t[s[i]] + 1, s[sn++] = ts;
    }
    for(; scanf("%s", str) != EOF; printf("%d\n", t[i]))
    for(i = j = 0; j < 13; j++) i += str[j] - '0' << j;
    return 0;
}

重剑无锋,大巧不工
2012-10-03 14:41
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1007 - 做一名正气的西电人
Problem 1007 - 做一名正气的西电人

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 970  Accepted: 189  Special Judge: No


Description


  一天,wm和zyf想比比谁比较正气,但正气这种东西无法量化难以比较,为此,他们想出了一个方法,两人各写一个数字,然后转化为二进制,谁的数字中二进制1多谁就比较正气!

Input

  输入包含多组数据,EOF结束。
  每组数据包含两行,代表两个非负整数a,b(0<=a,b<10^100,不含前导0),a为wm写的数字,b为zyf写的数字。

Output

  每组数据输出一行,输出正气的西电人名字"wm"或"zyf",如果两人的数字中二进制1一样多就输出"neither"。
 


Sample Input

15
16
17
18
20
19

Sample Output

wm
neither
zyf

Hint


Source

2010.04内部测试赛(Author: Qinz)
分析
呵呵,这个背景故事让我说什么好呢。题目该归到什么类里呢?算是大数运算吧。

没什么可细说的,有兴趣不如细看一下我的代码结构,也许会给你一些语言方面启示。

如果C语言功底不够扎实,请勿模仿。
程序代码:
#include<stdio.h>
int cal(char * s)
{
    int n, c, f, i, j;
    for(n = 0; s[n]; s[n] = s[n++] - '0');
    for(c = i = 0; i < n; c += f, i += !s[i])
    for(f = 0, j = i; j < n; s[j] += f * 10, f = s[j] & 1, s[j++] >>= 1);
    return c;
}
int main()
{
    char a[128], b[128];
    int c;
    for(; scanf("%s%s", a, b) != EOF; puts((c = cal(a) - cal(b)) > 0 ? "wm" : c ? "zyf" : "neither"));
    return 0;
}

重剑无锋,大巧不工
2012-10-03 16:02
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1008 - 数星星
Problem 1008 - 数星星

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 586  Accepted: 50  Special Judge: No


Description


    “不要问我太阳有多高
    我会告诉你我有多真
    不要问我星星有几颗
    我会告诉你很多很多”

  一天Qinz和wudired在天上数星星,由于星星可以排列成一条直线,他们比赛看谁能找到一条直线使得这条直线上的星星最多。假设夜空是一个二维平面坐标系,坐标轴为x,y。星星的坐标(x,y)为整数,且同一位置至多有一颗星星。他们需要你的帮助,一条直线最多可以穿过多少颗星星(直线不必平行于坐标轴)?

Input

  多组数据,EOF结束。
  第一行N(0<=N<=1000)为天上星星的数量。
  接下来N行每行两个数字 X,Y(0<=X,Y<10^9),表示星星的位置。以空格分开。

Output

  输出一行,表示一条直线最多穿过多少颗星星。

Sample Input

3
1 1
2 2
3 3

Sample Output

3

Hint


Source

2010.04内部测试赛(Author: wm)
分析
两点确定一条直线,那么N个点共可以确定N * (N - 1) / 2 条直线,计算这些直线中有多少条是相同的。

各位可以回想一下直线方程都有哪些表示方式。这里最适合使用的是点斜式。y - y1 = k(x - x1)

判断直线相同的方法是其直线方程的参数相同。

我们可以选一个点A,那么过点A与其它点的直线方程中的(x1,y1)即可都使用点A的坐标,由此,这一簇方程的差别就剩斜率k了。

这样我们可以计算出所有其它点与A构成的直线的斜率。斜率相同,那它们一定是共线的。

数斜率可以通过排序来完成,其时间复杂度是O(Nlog(N))

要寻找共点最多的直线需要对每个点做一次上述计算,所以总的时间复杂度是O(N^2 * log(N))
程序代码:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define MAX_NUM    1000

int cmp(const void * a, const void * b)
{
    if(*(double *)a > *(double *)b) return 1;
    if(*(double *)a < *(double *)b) return -1;
    return 0;
}
   
double fun(int x1, int y1, int x2, int y2)
{
    if(x1 == x2) return 1E10;
    return (double)(y2 - y1) / (x2 - x1);
}

int cal(int s[][2], int n)
{
    int x, y, c, i, j, k;
    double line[MAX_NUM];
    if(!n) return 0;
    for(c = i = 0; i < n; i++)
    {
        x = s[i][0];
        y = s[i][1];
        for(j = i + 1; j < n; j++) line[j] = fun(x, y, s[j][0], s[j][1]);
        qsort(line + i + 1, n - i - 1, sizeof(double), cmp);
        for(j = i + 1; j < n; (c = (k - j > c) ? (k - j) : c), j = k)
        for(k = j + 1; k < n && fabs(line[k] - line [j]) < 1E-10; k++);
    }
    return c + 1;
}

int main()
{
    int s[MAX_NUM][2], n, i;
    for(; scanf("%d", &n) != EOF; printf("%d\n", cal(s, n)))
    for(i = 0; i < n; i++) scanf("%d%d", &s[i][0], &s[i][1]);
    return 0;
}

重剑无锋,大巧不工
2012-10-05 19:13
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
Problem 1009 - 小红帽
Problem 1009 - 小红帽

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 670  Accepted: 180  Special Judge: No


Description


  有一群喜欢带小红帽的家伙举行了一场别开生面的聚会,然而某些人被邪恶的WM讲帽子上涂了大灰狼的图标,可是每个人看不到自己头上的帽子有没有被涂,他们只能看到其他人头上的帽子是不是大灰狼的图案,现在告诉你每个人看到的别人头上大灰狼帽子的数量,聪明的你啊,能不能判断出来一共有多少个人头上被汪淼涂了可恶的大灰狼呢,当然如果你发现有些人撒谎的话,就直接输出-1吧

Input

包含多组测试数据,每组数组有两行
第一行读入一个n,代表聚会的人数 (n<=100)
第二行一次读入n个数,a[i]代表第i个人看到的其他人头上的大灰狼的个数

Output

每组数据输出一个数,多少人被涂了大灰狼

Sample Input

3
1 2 1
4
1 1 1 2

Sample Output

2
-1

Hint


Source

Wudired
分析
看到题目的第一直觉是解一个线性方程组。事实上这也是可行的。就以上面的两个例子来说

3
1 2 1

可以建立方程

 0 1 1   1
 1 0 1 = 2
 1 1 0   1

4
1 1 1 2

可以建立方程

 0 1 1 1   1
 1 0 1 1   1
 1 1 0 1 = 1
 1 1 1 0   2

但对于这个题目来说,这么做有点奢侈,其算法复杂度是O(N^2)

由于每个人头上要么没有大灰狼,要么被涂一只大灰狼(不会有两只或以上)。也就是说上面方程每个未知量的取值只有0或1。

设所以大灰狼标记的数量为Y, 第i个人头上的大灰狼标记数量为Xi,他看到的标记数量为Ai,那么

Y - Xi = Ai

Y = Xi + Ai

由于Xi的取值只有两种(0或1)

所以Y的取值也最多只有两种 Y = Ai 或 Y = Ai + 1

当Y确定之后我们就可以很简单地求出其他的X(其他人头上大灰狼标记的数量),再之后就是验证解是否合理了。时间复杂度O(N)

讲到这里,不知各位有没有发现

Y = Xi + Ai

这样的方程我们可以列出N个(i = 1 ~ N),但事实上我们有N + 1个未知量,忘了算Y?所以方程会不会有多个解?

不会。我们还有一个等式没用,那就是

Y = X1 + X2 + X3 + ... + Xn

这样就完整了,详见下面代码。

代码中的x对应上面讲解方程中的Y,t对应Xi
程序代码:
#include<stdio.h>
int cal(int * a, int n)
{
    int c, x, i, t;
    for(c = 0, x = a[0], i = 1; i < n && !((t = x - a[i]) & 0xFFFFFFFE); c += t, i++);
    if(c == x) return x;
    for(c = 1, x = a[0] + 1, i = 1; i < n && !((t = x - a[i]) & 0xFFFFFFFE); c += t, i++);
    if(c == x) return x;
    return -1;
}
int main()
{
    int a[128], n, i;
    for(; scanf("%d", &n) != EOF; printf("%d\n", cal(a, n)))
    for(i = 0; i < n; scanf("%d", &a[i++]));
    return 0;
}


[ 本帖最后由 beyondyf 于 2012-10-6 08:14 编辑 ]

重剑无锋,大巧不工
2012-10-06 08:12
快速回复:C论坛算法团队 首战 西安电子科技大学OJ
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.022164 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved