Codeforces Round #677 (Div. 3)

Powered by:AB_IN 局外人

（补一补陈年老番）

看大佬的答题实录真的受益匪浅qwq，以前总是觉得$py$更加方便，但其实$py$有的一些东西$C++$也有，我还是太菜了。

A. Boring Apartments

模拟即可。

for _ in range(int(input())):
    s=input()
    ans=0
    if len(s)==1:
      ans+=1
    elif len(s)==2:
      ans+=3
    elif len(s)==3:
      ans+=6
    else:
      ans+=10
    ans+=(int(s[0])-1)*10
    print(ans)

B. Yet Another Bookshelf

求使原数列中任意两个 $1$ 之间不存在 $0$的最小操作数。
其实问题就转换为了，两个最远的$1$之间$0$的个数。

for _ in range(int(input())):
  n=int(input())
  lst=list(map(int,input().split()))
  for i in range(n):
    if lst[i]==1:
      index1=i
      break
  for i in range(n-1,-1,-1):
    if lst[i]==1:
      index2=i
      break
  if index1==index2:
    print(0)
  else:
    print(lst[index1:index2].count(0))

C. Dominant Piranha

题意挺有意思的：任选一项，每次可以把消去比其小的相邻项，同时该项$+1$，问能否找到某项，使得若干次操作后数列只剩一项。
如果能，输出任一可行的最初找的项的下标，否则输出 $-1$。

所以找的数越大越好，就输出这个数的下标就行了。但是如果遇到这种情况：
$$33233$$
就不是哪个$3$都可以了。所以在这个数是最大值的前提下，还得保证他的周围有比他小的数。

for _ in range(int(input())):
  n=int(input())
  lst=list(map(int,input().split()))
  index=-1
  ans=max(lst)
  for i in range(n):
    if lst[i]==ans and ((i>0 and lst[i-1]<lst[i]) or (i<n-1 and lst[i+1]<lst[i])):
      index=i+1
  print(index)

D. Districts Connection

这个题我一开始理解错题意了，以为必须要首尾连成一个环。但其实不是，题意是要连成一个树，然后每条边的端点不一样就行了。

那这样的话，只有一种情况不成立，就是端点全是一样的。
如果不全是一样的，我们可以开始随便挑选一个端点$a$，然后把不和$a$一样的点和$a$连起来，最后随意挑一个异于$a$的点，吧剩余的$a$连在它上。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;
int a[N];
int t;

void solve()
{
    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    if(count(a + 1, a + 1 + n, a[1]) == n){
        puts("No");
        return;
    }
    else{
        puts("Yes");
        int las = 0;
        for(int i = 1; i <= n; i++){
            if(a[i] != a[1]){
                printf("1 %d\n", i);
                las = i;
            }
        }
        for(int i = 2; i <= n; i++){
            if(a[i] == a[1]){
                printf("%d %d\n", i, las);
            }
        }
    }
}

int main()
{
    scanf("%d", &t);
    while(t--){
        solve();
    }
    return 0;
}

$PS:$

• 多组数据的话，写$solve()$函数，结束直接$return$，好处颇多！
• 见识到了像$max\_element$：求最大值；$count$：求数组中某个元素的个数，这样的函数，大开眼界。
• 大佬手速可太快了。。

E. Two Round Dances

排列组合。
这里用到了一个知识点：循环排列（也称圆排列）

指从n个不同元素中取出m（1≤m≤n）个不同的元素排列成一个环形，既无头也无尾。两个循环排列相同当且仅当所取元素的个数相同并且元素取法一致，在环上的排列顺序一致。（百度百科）

这个圈旋转相同视为一种组合。
公式如下：

$$C_n^m\times (m-1)!$$

进而得出
$$\frac{A_n^m}{m}$$

那么这个题就迎刃而解了，题意是从$n$个人中分成各 $\frac{n}{2}$ 人的两堆，先选出 $\frac{n}{2}$人放在左圈（其余$\frac{n}{2}$人自然放在右圈）。
先看左圈，相当于从$n$个人中选出$\frac{n}{2}$个人组成一个圈：

$$\frac{C_n^{\frac{n}{2}}\times A_{\frac{n}{2}}^{\frac{n}{2}}}{\frac{n}{2}}$$

再看右圈，相当于从$\frac{n}{2}$个人中选出$\frac{n}{2}$个人组成一个圈：
$$\frac{C_{\frac{n}{2}}^{\frac{n}{2}}\times A_{\frac{n}{2}}^{\frac{n}{2}}}{\frac{n}{2}}$$
最后由于两个圈是等价的，所以最后结果除以$2$。

结果就是

$$\frac{\frac{C_n^{\frac{n}{2}}\times A_{\frac{n}{2}}^{\frac{n}{2}}}{\frac{n}{2}}\times \frac{C_{\frac{n}{2}}^{\frac{n}{2}}\times A_{\frac{n}{2}}^{\frac{n}{2}}}{\frac{n}{2}}}{2}$$

化简得到：
$$\frac{2\times (n-1)!}{n}$$

import math
n = int(input())
print( 2 * math.factorial(n-1) // n )

最后推荐一个查询数列的网站：$$http://oeis.org/$$
完结。