在 OI 与 ACM 比赛中进行常数优化

输入输出优化

读取整数

适用于正负整数。
注意:在 C 与 C++ 中函数的求值顺序是不确定的,当多个参数需要调用输入输出挂时,必须引入中间变量。

inline long long LL()
{
    char c;
    bool neg = false;
    while((c = getchar()) < '0' || c > '9')
        neg = c == '-';//等价于 neg = (c == '-'),因为 == 的优先级更高
    int a = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        a = a * 10 + c - '0';
    return neg ? -a : a;
}

输出整数

适用于正负整数。

inline void Out(long long n)
{
    if (n < 0)
        putchar('-'), n = -n;
    if (n >= 10)
       Out(n / 10);
    putchar(n % 10 + '0');
}

前置 ++

使用++i代替i++。不过现在大部分编译器已经会将i++优化为++i了,所以一般不用处理。

关闭同步

由于scanf(), printf()的格式化字符串操作是在运行时解析的,因此取消同步后使用cincout进行处理可以获得更快的速度。
注意:此时不可以再混用scanf()cin, printf()cout

std::ios_base::sync_with_stdio(false);
std::cin.tie(0);

减少循环中不必要的计算

例如,将for循环头部的strlen()的计算引入中间变量,有利于提高程序的运行效率。

循环展开

减少不必要的循环次数。

References

H.凉凉 | 2018 校内选拔赛

Description

这道题难还是不难被nil的原子核「凉凉」所控制。如果原子核「凉凉」发生衰变,放出了\alpha粒子,改变了后台的测评数据,即使题面看起来很简单,仍会使该题变为一道超级难题,很难Accpeted。然而,原子核「凉凉」的衰变是随机事件,连nil也只能精确知道半衰期——衰变一半所需要的时间。如果一种放射性元素的半衰期是一天,则过一天,该元素就少了一半,再过一天,就少了剩下的一半。我们无法知道,它在什么时候衰变,上午,还是下午。如果不提交代码解决这道题,这道题可能难,也可能简单,这也被称作这道题的两种本征态。如果我们用薛定谔方程来描述这道题的状态,则只能说,这道题处于一种难与不难的叠加态。我们只有在 Accpeted 的一瞬间,才能确切地知道这道题是难是简单。此时,这道题构成的波函数由叠加态立即收缩到某一个本征态。量子理论认为:如果没Accpeted,我们永远也不知道这道题是难还是简单,它将永远处于半难不难的叠加态,可这使微观不确定原理变成了宏观不确定原理,客观规律不以人的意志为转移,这道题既简单又难违背了逻辑思维。定态薛定谔方程如下所示:-\frac{\hbar}{2\mu }\bigtriangledown^{2}\Psi + U\Psi =  E\Psi
是一个非相对论的波动方程,反映了描述微观粒子的状态随时间变化的规律,是量子力学的基本假设之一。设描述微观粒子状态的波函数为\Psi(r,t),质量为$m$的微观粒子在势场V(r,t)中运动的薛定谔方程。在给定初始条件和边界条件以及波函数所满足的单值、有限、连续的条件下,可解出波函数\Psi(r,t)。由此可计算粒子的分布概率和任何可能实验的平均值(期望值)。当势函数V不依赖于时间t时,粒子具有确定的能量,粒子的状态称为定态。定态时的波函数可写成式中\Psi(r)称为定态波函数,满足定态薛定谔方程,这一方程在数学上称为本征方程,式中$E$为本征值,是定态能量,\Psi(r)称为属于本征值E的本征函数。

在一次提交后,评测机返回了结果「Accepted」,你赶忙去询问nil此时「凉凉」所剩的部分与原有大小的关系。nil作为「凉凉」的掌控者,清楚地知道此时「凉凉」的状态,并且好心告诉你了「凉凉」的半衰期,请问「凉凉」经过了几个半衰期?

Input

输入包含多行,每行包含一个分数与一个正整数,分别代表此时「凉凉」所剩部分占原有的大小以及其半衰期的长度L(1 <= L <= 10^9)。
其中分数的形式为「1/d」,其中d代表正整数(1 <= d <= 10^18)。

Output

输出n m,代表「凉凉」经历了n个半衰期,总时长为m。

Sample Input

1/2 1

Sample Output

1 1

Hint

题面放烟雾弹的签到题
即对于一个 \frac{1}{2^{n}},求出 n 并计算 nL 的值。
注意数据范围
注意有多行输入数据

题解

#include "bits/stdc++.h"
using namespace std;
int main()
{
    long long a, b, l;
    while(~scanf("%lld/%lld %lld", &a, &b, &l))
    {
        long long sum = 0;
        while (b > 1 && b % 2 == 0)
        {
            sum++;
            b /= 2;
        }   
        printf("%lld %lld\n", sum, sum * l);
    }   
    return 0;
}

B.中国人的智慧 | 2018 校内选拔赛

Description

八卦是《易经》的基本概念,可代表一切自然现象的动静状态,每个卦由三个爻组成。“卦”有“悬挂”的意思,也代表将各种现象的标示竖立起来以便于观察。

八卦的项目组合,可代表各种自然现象或动态,分别为“天、地、水、火、雷、风、山、泽”,卦名则称“乾、坤、坎、离、震、巽、艮、兑”。易经的八卦代表了古代中国的天文地理哲学等文化思想,其理论还涉及到武术、中国音乐等方方面面。

若将八卦两两相重,形成六十四卦。原本八卦(三个爻)亦称为八个“单卦”,而相同的两个八卦的组合(六个爻)则称“重卦”。

八卦中有两个符号,一个是“—”,另一个是“- -”。在《易经》中并没有“阴阳”二字,数百年后的《易传》才把“—”叫阳爻,把“- -”叫阴爻。

本题输出中,使用__表示阳爻,使用–表示阴爻。

伏羲先天六十四卦〈方圆四分四层图〉排列方位图表

Trigramme2637 ☷.svg

坤(地)

Trigramme2636 ☶.svg

艮(山)

Trigramme2635 ☵.svg

坎(水)

Trigramme2634 ☴.svg

巽(风)

Trigramme2633 ☳.svg

震(雷)

Trigramme2632 ☲.svg

离(火)

Trigramme2631 ☱.svg

兑(泽)

Trigramme2630 ☰.svg

乾(天)

← 上卦
↓ 下卦
Iching-hexagram-02.svg (1)

坤为地

Iching-hexagram-23.svg (2)

山地剥

Iching-hexagram-08.svg (3)

水地比

Iching-hexagram-20.svg (4)

风地观

Iching-hexagram-16.svg (5)

雷地豫

Iching-hexagram-35.svg (6)

火地晋

Iching-hexagram-45.svg (7)

泽地萃

Iching-hexagram-12.svg (8)

天地否

Trigramme2637 ☷.svg

坤(地)

Iching-hexagram-15.svg (9)

地山谦

Iching-hexagram-52.svg (10)

艮为山

Iching-hexagram-39.svg (11)

水山蹇

Iching-hexagram-53.svg (12)

风山渐

Iching-hexagram-62.svg (13)

雷山小过

Iching-hexagram-56.svg (14)

火山旅

Iching-hexagram-31.svg (15)

泽山咸

Iching-hexagram-33.svg (16)

天山遁

Trigramme2636 ☶.svg

艮(山)

Iching-hexagram-07.svg (17)

地水师

Iching-hexagram-04.svg (18)

山水蒙

Iching-hexagram-29.svg (19)

坎为水

Iching-hexagram-59.svg (20)

风水涣

Iching-hexagram-40.svg (21)

雷水解

Iching-hexagram-64.svg (22)

火水未济

Iching-hexagram-47.svg (23)

泽水困

Iching-hexagram-06.svg (24)

天水讼

Trigramme2635 ☵.svg

坎(水)

Iching-hexagram-46.svg (25)

地风升

Iching-hexagram-18.svg (26)

山风蛊

Iching-hexagram-48.svg (27)

水风井

Iching-hexagram-57.svg (28)

巽为风

Iching-hexagram-32.svg (29)

雷风恒

Iching-hexagram-50.svg (30)

火风鼎

Iching-hexagram-28.svg (31)

泽风大过

Iching-hexagram-44.svg (32)

天风姤

Trigramme2634 ☴.svg

巽(风)

Iching-hexagram-24.svg (33)

地雷复

Iching-hexagram-27.svg (34)

山雷颐

Iching-hexagram-03.svg (35)

水雷屯

Iching-hexagram-42.svg (36)

风雷益

Iching-hexagram-51.svg (37)

震为雷

Iching-hexagram-21.svg (38)

火雷噬嗑

Iching-hexagram-17.svg (39)

泽雷随

Iching-hexagram-25.svg (40)

天雷无妄

Trigramme2633 ☳.svg

震(雷)

Iching-hexagram-36.svg (41)

地火明夷

Iching-hexagram-22.svg (42)

山火贲

Iching-hexagram-63.svg (43)

水火既济

Iching-hexagram-37.svg (44)

风火家人

Iching-hexagram-55.svg (45)

雷火丰

Iching-hexagram-30.svg (46)

离为火

Iching-hexagram-49.svg (47)

泽火革

Iching-hexagram-13.svg (48)

天火同人

Trigramme2632 ☲.svg

离(火)

Iching-hexagram-19.svg (49)

地泽临

Iching-hexagram-41.svg (50)

山泽损

Iching-hexagram-60.svg (51)

水泽节

Iching-hexagram-61.svg (52)

风泽中孚

Iching-hexagram-54.svg (53)

雷泽归妹

Iching-hexagram-38.svg (54)

火泽睽

Iching-hexagram-58.svg (55)

兑为泽

Iching-hexagram-10.svg (56)

天泽履

Trigramme2631 ☱.svg

兑(泽)

Iching-hexagram-11.svg (57)

地天泰

Iching-hexagram-26.svg (58)

山天大畜

Iching-hexagram-05.svg (59)

水天需

Iching-hexagram-09.svg (60)

风天小畜

Iching-hexagram-34.svg (61)

雷天大壮

Iching-hexagram-14.svg (62)

火天大有

Iching-hexagram-43.svg (63)

泽天夬

Iching-hexagram-01.svg (64)

乾为天

Trigramme2630 ☰.svg

乾(天)

Input

第一行为一个不大于 64 的正整数 T,其后 T 行
每行为一个不大于 64 的正整数

Output

对于输入的第一行之后的每一行,输出该正整数在伏羲先天六十四卦卦象演化序号中所对应的卦象,若需输出多个卦象,则在两个卦象中间空一行。

Sample Input

2
20
21

Sample Output

__
__
--
--
__
--

--
--
__
--
__
--

Hint

签到题,通过卦象来表示二进制数值。

题解

#include "bits/stdc++.h"
int main()
{
    int T;
    scanf("%d", &T);
    for (int i = 0; i < T; i++)
    {
        int n;
        scanf("%d", &n);
        n--;
        bool arr[6];
        memset(arr, 0, sizeof(arr));
        for (int j = 0; j < 6; j++)
        {
            arr[j] = n / (int)pow(2, (5 - j));
            n %= (int)pow(2, (5 - j));
        }
        for (int j = 5; j >= 0; j--)
            printf(arr[j] ? "__\n" : "--\n");
        putchar('\n');
    }

    return 0;
}

E.今天也是元气满满的一天 | 2018 校内选拔赛 预选赛 Day2

Description

我们使用格式 YYYYMMDD 表示一个日期
显然,一个日期由 8 个 0 ~ 9 之间的数码组成
在这 8 个数码组成的数列中
如果有连续 3 个或以上的数码可以构成等差数列

等差数列(又名算术数列)是数列的一种。在等差数列中,任何相邻两项的差相等。该差值称为公差。例如数列 3, 5, 7, 9, 11, 13 就是一个等差数列。 在这个数列中,从第二项起,每项与其前一项之差都等于2,即公差为2。
Sigler, Laurence E. (trans.). Fibonacci’s Liber Abaci.
Springer-Verlag. 2002: 259–260. ISBN 978-0-387-95419-6.

那么这个日期将无法成为密码
请你找出无法成为密码的日期有多少

Input

两行
第一行是开始日期
第二行是结束日期
日期使用格式 YYYYMMDD 表示,且均不在 1900 年 1 月 1 日之前,均不在 2999 年 12 月 31 日之后
保证结束日期不在开始日期之前

Output

一个数字
表示从开始日期到结束日期的日期范围(包括开始日期和结束日期)内,有多少个日期无法成为密码

Sample Input

19980327
19980806

Sample Output

3

Hint

暴力。

题解

// #define debug
#include "bits/stdc++.h"
using namespace std;
inline int query_days_for_year(int y)
{
    return (y % 400 == 0|| (y % 4 == 0 && y % 100 != 0)) ? 366 : 365;
}
int mo[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline int query_days_for_month(int m, int y)
{
    //特别注意
    if (m != 2)
        return mo[m];
    else
        if (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0))
            return 29;
        else
            return 28;
}
inline bool chk(char A[], char B[])//替代strcmp
{
    for (int i = 0; i < 8; i++)
        if (A[i] != B[i])
            return 0;
    return 1;
}
inline int tran(int y, int m, int d, char str[])
{
    // #ifdef debug
    // printf("y m d %d %d %d\n", y, m, d);
    // #endif
    if (d > query_days_for_month(m, y))
    {
        d = 1;
        m++;
        #ifdef debug
        printf("m++\n");
        #endif
        if (m > 12)
        {
            m = 1;
            y++;
            #ifdef debug
            printf("y++\n");
            #endif
        }
    }
    str[0] = y / 1000;
    str[1] = y % 1000 / 100;
    str[2] = y % 100 / 10;
    str[3] = y % 10;

    str[4] = m / 10;
    str[5] = m % 10;

    str[6] = d / 10;
    str[7] = d % 10;
    return y*10000 + m*100 + d;
}
int main()
{
    int y1, m1, d1, y2, m2, d2;
    char str1[9], str2[9];
    scanf("%s%s", str1, str2);
    for (int i = 0; i < 8; i++)
    {
        str1[i] -= '0';
        str2[i] -= '0';
    }
    y2 = str2[0]*1000 + str2[1]*100 + str2[2]*10 + str2[3];
    m2 = str2[4]*10 + str2[5];
    d2 = str2[6]*10 + str2[7];

    int sum = 0;
    y1 = str1[0]*1000 + str1[1]*100 + str1[2]*10 + str1[3];
    m1 = str1[4]*10 + str1[5];
    d1 = str1[6]*10 + str1[7];
    while (1)
    {
        for (int i = 0; i < 6; i++)
            if (str1[i+1] - str1[i] == str1[i+2] - str1[i+1])
            {
                sum++;
                break;
            }

        if (chk(str1, str2))
        {
            printf("%d\n", sum);
            return 0;
        }
        //自增
        d1++;
        y1 = tran(y1, m1, d1, str1);
        m1 = (y1 % 10000) / 100;
        d1 = y1 % 100;
        y1 /= 10000;
        #ifdef debug
        printf("p1 %d %d %d\n", y1, m1, d1);
        #endif
    }

    return 0;
}