KeyFansClub

首页 » - 特色讨论区 - » 键社茶餐厅 » NOIP竞赛结束大家感觉如何
凌波然 - 2005/11/20 13:42:00
信息学奥赛复赛结束!庆祝一下.
我参加的是普及组,这次的题目好简单,比前几届简单多了,提高组好像也是这样。我做出三道题目,第四道题目虽然有思路,程序也打出来了,不过就是不对,希望这次成绩能好一点。

题目大致如下:求一个正整数n的正整数次幂的后k位是否会发生循环?如果
是,最短循环长度是多少?(1<k<=100)输出循环长度,若不存在,输出-1

同祝大家成绩优秀。
[IMG=upload/KFCFile7164_edo2.jpg]上传文件7164[/IMG]
神奈备命 - 2005/11/20 13:49:00
祝愿楼主取得好成绩啊~~~~
某也只能说这个了...关于"信息学奥赛".....连名字都米听过....


←---某小白飘过...
Miliardo - 2005/11/20 13:52:00
某素提高组……
RP爆发爆发了220分……
不过省队就断念了……
碇 - 2005/11/20 14:00:00
楼主好强= =
也不知道“信息学奥赛”
而且发现……我不会算……zro
K<100的,而且只要最短循环长度……似乎可以来穷举的?
好奇= =
问下,用什么语言?循环是指从末位算么,如123123算是循环而1231237不算什么的?
千叶奈奈 - 2005/11/20 14:33:00
然姐姐参加的复赛结束了?那么先祝贺一下...
实话说奈奈数学烂烂的||||所以那道谜题看了半天貌似也做不出来 = = 也没法给姐姐什么帮助 面壁...

总之希望姐姐能进决赛 也不要太辛苦了哟^^
幻蓝飘羽 - 2005/11/20 14:35:00
信息学奥赛复赛????信息学????楼主来阐释一下吧~~~~
粘土火星 - 2005/11/20 14:50:00
以下引用Miliardo在2005-11-20 13:52:36的发言:
某素提高组……
RP爆发爆发了220分……
不过省队就断念了……


话说去年230分来着-___________-b


提高组如果比去年还简单我可以去死了……

PS:楼主的题N有范围么?
碇 - 2005/11/20 15:13:00
以下引用神奈の无奈在2005-11-20 14:33:48的发言:
实话说奈奈数学烂烂的||||所以那道谜题看了半天貌似也做不出来 = =

这是正常的,我看着不太像是能用数学解决的= = 或者我实在太废了
唔,因为不知道K位内有循环的具体定义(算压缩算法?还是纯粹严格的循环?)7123123123这样算是有循环不?1231231237这样呢?
我是废人,试着用C写严格循环(123123123)的吧……zro
Miliardo - 2005/11/20 15:15:00
以下引用粘土火星在2005-11-20 14:50:46的发言:


话说去年230分来着-___________-b


提高组如果比去年还简单我可以去死了……

PS:楼主的题N有范围么?


去年提高组的题目……简单到渣……
可惜某去年初赛挂掉了……T_T……

今年貌似难到出题人被诅咒……详情请见OIBH……Orz……
粘土火星 - 2005/11/20 15:18:00
循环的样例……楼主没提供= =b

话说这题,时间大概耗在维护高精度上……
碇 - 2005/11/20 15:25:00
以下引用粘土火星在2005-11-20 15:18:53的发言:
话说这题,时间大概耗在维护高精度上……


“正整数n的正整数次幂”
突然想到,我为什么会觉得是C呢……难道被虐待习惯了(一般考算法什么都会跑到C上考……)数字向字符串转换都要自己来……zro
粘土火星 - 2005/11/20 15:27:00
以下引用Miliardo在2005-11-20 15:15:54的发言:


去年提高组的题目……简单到渣……
可惜某去年初赛挂掉了……T_T……

今年貌似难到出题人被诅咒……详情请见OIBH……Orz……


那么先恭喜阁下=v=???去年的渣题咱的分数也没阁下多哼哼哼,大概一辈子会和低级错误沾边了

PS:综上所述和OI有关的WEB SITE和某已经无缘=v=b,也算是种解脱咯

PS:不要再出现比前年还低的分数吧-_-b 80太寒了
LOVEHINA-AVC - 2005/11/20 15:53:00
题目都没有看懂orz
LOVEHINA-AVC - 2005/11/20 19:04:00
吃完饭后试了一下,不知道对题意有没理解错误-_-d
[strike]由于偶不熟悉C和PASCAL(爆),以下源码各位请54……[/strike]

.386
.model flat,stdcall
option casemap:none

include \masm32\include\kernel32.inc
includelib \masm32\lib\kernel32.lib
include \masm32\include\user32.inc
includelib \masm32\lib\user32.lib


.DATA
szSignedFormat    db    "%d",0
szUnsignedFormat    db    "%u",0

.CODE

start:

    push    4        ;Power
    push    100        ;Base
    call    GetCycle
    mov    ebp,esp
    push    eax
    push    OFFSET szSignedFormat
    push    ebp
    call    wsprintf
    add    esp,12
    mov    ebp,esp
    push    0
    push    ebp
    push    ebp
    push    0
    call    MessageBox
    push    0
    call    ExitProcess

GetCycle    proc    stdcall

    mov    eax,[esp + 4]
    mov    ebx,eax
    mov    ecx,[esp + 8]
    dec    ecx
    sub    esp,104
    mov    ebp,esp
    and    DWORD PTR[ebp + 100],0

@@:

    xor    edx,edx
    mul    ebx
    jo    Overflow
    dec    ecx
    jnz    @b
   
@@:
   
    push    eax
    push    eax
    push    OFFSET szUnsignedFormat
    push    ebp
    call    wsprintf
    add    esp,12
    pop    eax
    xor    ecx,ecx

@@:

    inc    ecx
    mov    bl,[esp + ecx]
    test    bl,bl
    jz    @f
    mov    [esp + ecx - 1],bl
    jmp    @b

@@:

    dec    ecx
    cmp    ecx,100
    ja    NotFound
    xor    esi,esi
    inc    esi

CompareStringStart:

    mov    edi,esi

CompareStringLoop:

    xor    ebp,ebp

@@:

    mov    bl,[esp + ebp]
    add    edi,ebp
    cmp    edi,ecx
    je    NotMatch
    mov    dl,[esp + edi]
    sub    edi,ebp
    cmp    bl,dl
    jne    NotMatch
    inc    ebp
    cmp    ebp,esi
    jne    @b
    add    edi,esi
    cmp    edi,ecx
    jb    CompareStringLoop
   
FullyMatched:

    mov    [esp + 100],esi

NotMatch:

    inc    esi
    mov    edx,ecx
    shr    edx,1
    cmp    esi,edx
    jbe    CompareStringStart
    cmp    DWORD PTR[esp + 100],0
    je    NotFound
    xor    edx,edx
    mov    eax,ecx
    mov    ecx,[esp + 100]
    div    ecx

EndOfProc:

    add    esp,104
    ret    8
   
Overflow:
NotFound:

    xor    eax,eax
    dec    eax
    jmp    EndOfProc
   
GetCycle    endp
   
end start

编译选项:
ml /c /coff /nologo GetCycle.asm
link /subsystem:windows /libpath:\masm32\lib /nologo GetCycle.obj

很懒就没有做参数录入了,不知道比赛的话这样会不会扣分?
另外精度是个问题……完整的应该要采用浮点寄存器Orz
碇 - 2005/11/20 19:14:00
#include "string.h"

int cycle(int n,int s,int k){
char x[101],q[101],w[101];
int i=0,j,l,m=0,r,o,p=0;
unsigned long a=1;

for(j=0;j<s;j++)
a*=(unsigned long)n;
printf("%ld\n",a);

while(a)
{
x=a-a/10*10+48;
a=a/10;
i++;
}
x=0;

if(i>k) i=k;

for(j=0;j<i/2;j++)
{r=i/(j+1);
if (i%(j+1)) continue;

for(l=0;l<=j;l++)
{
q[l]=x[m];
m++;
}
q[l]=0;

for(o=0;o<r-2;o++)
{
for(l=0;l<=j;l++)
{
w[l]=x[m];
m++;
}
w[l]=0;
if(strcmp(q,w)) {p=1; break;}}

if(p) continue;
printf("%d\n\n",j);
return (j);
}
if(p) printf("-1\n\n");
return (-1);
}


main(){
int cycle(int n,int s,int k);
int n,s,k=101;
while(k>100||k<1){
printf("input the number as n s k and k<100\n");
scanf("%d%d%d",&n,&s,&k);}
cycle(n,s,k);
}

呃,战完……好乱,请各位指错(有循环的怎么没发现……全是-1- -||||)
请无视诸如变量命名不规范,提示不友好,计算位数有限(特别是第二个参数),乱什么的……
LOVEHINA-AVC - 2005/11/20 19:25:00
爆,我把K给忘了(直接去掉第一位)……
LOVEHINA-AVC - 2005/11/20 20:46:00
对了要调试着看的话可以用下面的编译选项:
ml /c /coff /Zi /nologo GetCycle.asm
link /debug /debugtype:CV /subsystem:windows /libpath:\masm32\lib /nologo GetCycle.obj

然后直接用OllyDbg加载就可以进行源码级调试了-v-b
(众:需要吗?你都没有用命名变量)
希德船长 - 2005/11/20 21:03:00
“正整数n的正整数次幂”,用C来生成的话,就算用unsigned long 格式的数字,最大才10位,绝对不会有100位尾数的。除非自己写一个无穷位乘法器来生成结果,再进行搜索判断。

我来试试。。。。。。
碇 - 2005/11/20 21:17:00
所以汇编容易做的厚道点吧= =
不然就战去吧……应该也有办法= =
LOVEHINA-AVC - 2005/11/20 21:27:00
比赛不可能用汇编伐,源码量&调试难度跟C/PASCAL相比不是一个级别的=_=
C我只能用来写驱动,做数学题还是PASCAL容易啊,继续看PASCAL基础去……

PS:问一下,楼上的战是啥意思?
碇 - 2005/11/20 21:38:00
希德船长君要战C下面的无穷位乘法器= =
我觉得这其实比题目本身要繁……
动态分配内存全拆成1个单位的位段来?
……
还是写汇编好了- -|||||||
其实这两个我都不熟……破解及邪恶程序爱好者可能会比较清楚
C也一年没摸了……
LOVEHINA-AVC - 2005/11/20 21:54:00
越看越不像是NOIP的题目

至于那个无穷位乘法计算器……[strike]来跟踪一下WINDOWS的calc[/strike]
Miliardo - 2005/11/20 22:02:00
以下引用凌波然在2005-11-20 13:42:12的发言:
信息学奥赛复赛结束!庆祝一下.
我参加的是普及组,这次的题目好简单,比前几届简单多了,提高组好像也是这样。我做出三道题目,第四道题目虽然有思路,程序也打出来了,不过就是不对,希望这次成绩能好一点。

题目大致如下:求一个正整数n的正整数次幂的后k位是否会发生循环?如果
是,最短循环长度是多少?(1<k<=100)输出循环长度,若不存在,输出-1

同祝大家成绩优秀。
[IMG=upload/KFCFile7164_edo2.jpg]上传文件7164[/IMG]


普及组某也不素很清楚……
提高组难度相当BT……
希德船长 - 2005/11/20 22:36:00
无穷位乘法器完成。

按输入输出的是字符串来处理,数字的话则转换后再使用。

这么做比较浪费内存空间,但是便于输出。

int MulFunction(char *Input1, char *Input2, char *Output)
{
    int NumLenInput1,NumLenInput2, i, j;

//判断数字长度
    for(i=0;;i++)
    {
        if(Input1 < 48 || Input1 > 57)
        {
            NumLenInput1 = i;
            break;
        }
        Input1 -= 48;
    }
    for(i=0;;i++)
    {
        if(Input2 < 48 || Input2 > 57)
        {
            NumLenInput2 = i;
            break;
        }
        Input2 -= 48;
    }

//若Output == NULL则将结果所需的长度用返回值告知使用者
    if(Output == NULL)
        return NumLenInput1+NumLenInput2;

//初始化结果字符串
    for(i=NumLenInput1+NumLenInput2-1; i>=0; i--)
        Output = 0;
    Output[NumLenInput1+NumLenInput2] = '\0';

//乘
    for(i=0; i<NumLenInput2; i++)
    {
        for(j=0; j<NumLenInput1; j++)
            Output[NumLenInput1+NumLenInput2-1-i-j] += Input1[NumLenInput1-1-j]*Input2[NumLenInput2-1-i];
        for(j=NumLenInput1+NumLenInput2-1; j>=0; j--)
        {
            if(Output[j] > 9)
            {
                Output[j-1] += Output[j]/10;
                Output[j] %= 10;
            }
        }
    }

//将结果转换为字符串
    for(i=0; i<NumLenInput1+NumLenInput2; i++)
        Output += 48;
    for(i=0; i<NumLenInput1; i++)
        Input1 += 48;
    for(i=0; i<NumLenInput2; i++)
        Input2 += 48;

//返回结果字符串的最大长度。
    return NumLenInput1+NumLenInput2;
}
碇 - 2005/11/20 23:28:00
唔唔唔
出来了么= =
用字符串来么
"int Temp10;"
传说C定义和高级语言不一样一定要放函数开头?
for(i=0;;i++)
{
  if(Input1 < 48 || Input1 > 57)
  {
  NumLenInput1 = i;
  break;
  }

这样NumLenInput1 NumLenInput1都会比数组的数据部分多1 所以Output数组要按减2来算?(这人就是喜欢说数组-v-)
zro……请无视
那么,谁来做修改整合工作捏-v-
东南之风 - 2005/11/20 23:29:00
我提高组彻底挂了,反而最简单的第一题天知道哪出问题,居然没出来,靠,自己测的时候都没问题
LOVEHINA-AVC - 2005/11/20 23:34:00
以下引用在2005-11-20 23:28:11的发言:
唔唔唔
出来了么= =
用字符串来么
"int Temp10;"
传说C定义和高级语言不一样一定要放函数开头?


因为那个要对应
push ebp
mov ebp,esp
sub esp,XXX(add esp,-XXX)
在进入函数区块后首先进行局部变量栈空间的划分

PS:C也是高级语言
碇 - 2005/11/20 23:39:00

那超高级语言好了-v-
希德船长 - 2005/11/21 13:01:00
其实我上面那函数是在C++下写的。

刚才修正了一下,同时修正了执行后输入字符串被改变的毛病。现在应该可以在C下用了。

本来想把成品(MFC应用程序)传上来,可是这几天我的机器带病毒,万一传上来的东西也带病毒就麻烦了,只能在这里直接贴代码了。

以下为将m_Input的m_Power次幂的结果输出到m_Result里的代码,m_Input,m_Power和m_Result是三个编辑框控件。

void CMulDlg::OnBUTTONMul()
{
    // TODO: Add your control notification handler code here
    int i;

    int NumLength = m_Input.GetWindowTextLength();
    char *InputTemp = (char *)malloc(NumLength+1);
    m_Input.GetWindowText(InputTemp,NumLength+1);

    int PowerLength = m_Power.GetWindowTextLength();
    char *PowerTemp = (char *)malloc(PowerLength+1);
    m_Power.GetWindowText(PowerTemp,PowerLength+1);
    int Power = atoi(PowerTemp);

    char *Result = (char *)malloc(NumLength*Power+1);
    char *ResultTemp = (char *)malloc(NumLength*Power+1);

    if(Power == 0)
        strcpy(Result,"1");
    else if(Power == 1)
        strcpy(Result,InputTemp);
    else
    {
        strcpy(ResultTemp,InputTemp);
        for(i=0; i<Power-1; i++)
        {
            MulFunction(ResultTemp,InputTemp,Result);
            strcpy(ResultTemp,Result);
        }
        for(i=0; i<NumLength*Power+1; i++)
            if(ResultTemp != '0')
                break;
        strcpy(Result,ResultTemp+i);
    }
    m_Result.SetWindowText(Result);
}

有了字符串格式的结果,下面的匹配搜索就好办了。
凌波然 - 2005/11/21 20:09:00
其实那道题目我也有思路,只不过内存老是溢出,优化不能
而且高精度乘法也比较耗时,估计测试的时候我的程序会超时
12