文章目录

• B. Cat Cycle
• C. Minimum Ties
• D. Pythagorean Triples

B. Cat Cycle

题解：

我们通过简单打表发现，没经过 n 2 \frac{n}{2} 2n​次，AB两只猫就会走到相同的位置，此时B猫就会跳一次， 那么k个小时跳的次数就是 k n 2 \frac{k}{\frac{n}{2}} 2n​k​下取整，则最后B猫就相当于走了 k + k n 2 k+\frac{k}{\frac{n}{2}} k+2n​k​次，然后对n进行取余便是最后答案。

这里可以先将k–，便于取模操作，最后再加上1即可

void solve()
{
    int n, k; scanf("%d%d", &n, &k);
    k --;
    if (!(n & 1)) 
    {
        printf("%d\n", k % n + 1);
        return ;
    }
    int t = k / (n >> 1);
    printf("%d\n", (k + t) % n + 1);
}

C. Minimum Ties

题解：

根据题意可以得出，每个队伍都与其他队伍打一场比赛，即每个队伍要打 n − 1 n-1 n−1场比赛。不难发现， n n n为奇数时所有队伍就不需要有平局就可以满足题目要求，而当 n n n为偶数时，所有的队伍就都必须要一场平局。而不管 n n n是奇数还是偶数都有 n − 1 2 \frac{n-1}{2} 2n−1​场胜利， n − 1 2 \frac{n-1}{2} 2n−1​场失败。

将 n n n分为奇数和偶数分别讨论，假如 i i i和 j j j打，如果他们奇偶性相同，就让 i i i获胜，如果相反，就让 j j j获胜，反之也可以。这样就可以不重不漏的满足所有条件。

void solve()
{
    int n; scanf("%d", &n);
    if (n & 1)
    {
        for (int i = 1; i < n; i ++ )
        for (int j = i + 1; j <= n; j ++ )
        {
            if ((i + j) & 1) printf("1 ");
            else printf("-1 ");
        }
    }
    else
    {
        for (int i = 1; i < n; i ++ )
        {
            for (int j = i + 1; j <= n; j ++ )
            {
                if ((j == i + 1) && (i & 1)) printf("0 ");
                else if ((i + j) & 1) printf("1 ");
                else printf("-1 ");
            }
        }
    }
    puts("");
}

D. Pythagorean Triples

题解：

题目问 n n n的范围内，同时满足 c = a 2 − b c=a^{2} -b c=a2−b和 c 2 = a 2 + b 2 c^{2}=a^{2}+b^{2} c2=a2+b2的直角三角形有多少个。

不妨先将两个式子联立化简，得到 c = b + 1 c=b+1 c=b+1， 即 a 2 = c + c − 1 a^{2}=c + c - 1 a2=c+c−1，那么 n + n − 1 \sqrt{n+n-1} n+n−1 ​取整就是 a a a在 n n n的范围内最大的整数，又因为两个相邻的数相加为奇数，所以 a 2 a^{2} a2一定为奇数，所以题目就转化为了求 [ 3 ， n + n − 1 ] [3，\sqrt{n+n-1}] [3，n+n−1 ​]内的奇数个数(1不满足条件)。

void solve()
{
    int n; scanf("%d", &n);
    printf("%d\n", ((int)sqrt(2 * n - 1) - 1) / 2);
}