蓝精灵之走格子

Time Limit: 2000/1000ms (Java/Others) 64bit IO Format: %lld & %llu

Problem Description:

有一个圆形，半径为r，圆周上均匀分布着2的8r次方个格子。记其中一个格子为0，0的逆时针方向数字减1，0的顺时针方向数字加1，依次操作，这样一直填满整个圆周。问，现在你在数字为a的位置上，先顺时针走b个格子，再逆时针走c个格子，最后你站的格子标号是多少。

Input:

输入数据有多组，每组数据包含四个整数r, a, b, c
数据范围：
r=1, 2, 4, 8
-2^(8r-1) <= a < 2^(8r-1)
0 <= b,c <= 10^18。

Output:

对于每组数据，输出最后站的格子标号

Sample Input:

1 -1 4 0

Sample Output:

3

做题感想

可能是模拟出问题了把……13次wa，莫名的2的31次方乘2为0.。。很崩溃。
……跟ull和ll的存储关系有关，很毒

WA模拟

#include <stdio.h>
long long r,a,i,len[3]={256,65536,4294967296};
unsigned long long b,c,l;
int main(void)
{
    while (scanf("%lld%lld%llu%llu",&r,&a,&b,&c)!=EOF)
    if (r==8)
    {
        l=128; i=r;
        while (i>1)
        {
            l=l*l*2;
            i/=2;
        }
        if (b>c)
        {
            b-=c;
            c=0;
        }
        else
        {
            c-=b;
            b=0;
        }
        if (b>0)
            if (a<=0)
                a+=b;
            else if ((a-l)+b>=0)
                a=((a-l)+b)-l;
            else a+=b;
        if (c>0)
            if (a>=0)
                a-=c;
            else if ((a+l)-c<0)
                a=((a+l)-c)+l;
            else a-=c; 
        printf("%lld\n",a);
    }
    else
    {
        l=128; i=0;
        while (r>1)
        {
            l=l*l*2;
            r/=2;
            i++;
        }
        b=b%len[i];
        c=c%len[i];
        a=a+b-c;
        if (a>=l)
            a=a-len[i];
        if (-a>(long long)l)
            a=a+len[i];
        printf("%lld\n",a);
    }
    return 0;
}

AC模拟

#include <stdio.h>
long long r,a,i,d,len[3]={256,65536,4294967296};
unsigned long long b,c,l;
int main(void)
{
    while (scanf("%lld%lld%llu%llu",&r,&a,&b,&c)!=EOF)
    if (r==8)
    {
        l=128; i=r;
        while (i>1)
        {
            l=l*l*2;
            i/=2;
        }
        if (b>c)
        {
            b-=c;
            c=0;
        }
        else
        {
            c-=b;
            b=0;
        }
        if (b>0)
            if (a<=0)
                a+=b;
            else if ((a-l)+b>=0)
                a=((a-l)+b)-l;
            else a+=b;
        if (c>0)
            if (a>=0)
                a-=c;
            else if ((a+l)-c<0)
                a=((a+l)-c)+l;
            else a-=c; 
        printf("%lld\n",a);
    }
    else
    {
        l=128; i=0;
        while (r>1)
        {
            l=l*l*2;
            r/=2;
            i++;
        }
        b=b%len[i];
        c=c%len[i];
        a=a+b-c;
        if (a>=l && a>0)
            a=a-len[i];
        d=-a;
        if (d>l && a<0)
            a=a+len[i];
        printf("%lld\n",a);
    }
    return 0;
}

AC强制转换

#include <stdio.h>
long long r,a,b,c;
int main(void)
{
    while (scanf("%lld%lld%lld%lld",&r,&a,&b,&c)!=EOF)
    if (r==1)
        printf("%hd\n",(char)(a+b-c));
    else if (r==2)
        printf("%d\n",(short)(a+b-c));
    else if (r==4)
        printf("%ld\n",(long)(a+b-c));
    else
        printf("%lld\n",(long long)(a+b-c));
    return 0;
}

标准答案（不解释了自己看）

#include <stdio.h>

int main() {
    int r;
    long long a, b, c;
    while(scanf("%d %lld %lld %lld", &r, &a, &b, &c) == 4) {
        long long ans = a + b - c;
        long long test = 1LL << (8*r - 1), mod = test << 1;
        mod --;
        ans &= mod;
        ans = (ans & test) ? - ((~ans+1)&mod) : ans;
        printf("%lld\n", ans);
    }
    return 0;
}