富途秋招 2023.09.16 编程题目与题解

发表于 2023-09-20 分类于笔试阅读次数：本文字数： 1.1k 阅读时长 ≈ 1 分钟

1、完美对

有\(n\)个物品，每个物品有\(k\)个属性，第\(i\)件物品的第\(j\)个属性用一个正整数表示记为\(a_{i,j}\)，两个不同的物品\(i,j\)被称为是完美对的当且仅当\(a_{i,1}+a_{j,1}=a_{i,2}+a_{j,2}=\dots=a_{i,k}+a_{j,k}\)，求完美对的个数。

输入

第一行两个数字\(n,k\)。

接下来\(n\)行，第\(i\)行\(k\)个数字表示\(a_{i,1},a_{i,2},\dots,a_{i,k}\)。

\(1\le n\le 10^5,2\le k\le 10,1\le a_i\le 100\)

输出

一行一个数字表示答案。

样例

解答

注意到，这里的\(a_i\)值非常小，仅有\(100\)，我们可以考虑从这里入手。

我们不妨假设\(t=a_{i,1}+a_{j,1}=a_{i,2}+a_{j,2}=\dots=a_{i,k}+a_{j,k}\)。对于一个固定的\(i\)，我们令\(\displaystyle{m_i=\min_{t=1}^k \{a_{i,t}\},M_i=\max_{t=1}^k \{a_{i,t}\}}\)，即所有特征的最大值和最小值，那么\(t\)的取值范围仅可能是\([M_i+1,m_i+100]\)，枚举对应的\(t\)构造出另外一个物品，并统计这个物品的数量即可。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int n,k;
map<vector<int>,int>mp;
int main(){
    ll ans=0;
    scanf("%d %d",&n,&k);
    vector<int>u(k),v(k);
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            scanf("%d",&u[j]);
        }
        int mn=*min_element(u.begin(),u.end()),mx=*max_element(u.begin(),u.end());
        for(int s=mx+1;s<=mn+100;s++){
            for(int j=0;j<k;j++){
                v[j]=s-u[j];
            }
            auto it=mp.find(v);
            if(it!=mp.end()) ans+=it->second;
        }
        ++mp[u];
    }
    printf("%lld\n",ans);
    return 0;
}

2、三的倍数

给定一个\(3\)的任意倍数的正整数\(n\)，输出把这个正整数\(n\)分解为三个\(3\)的倍数的方法数。注意，如果分解数字的顺序不同，则考虑为不同方法。例如，\(12=3+6+3\)和\(12=3+3+6\)是不同的方法。

输入

第一行给出\(T\)，表示题目测试用例

随后每行给出正整数\(n\)。

\(3\le n\le 10^5\)，且\(n\)为\(3\)的倍数。

\(1\le T\le 10^4\)

输出

对于每一个测试用例，

输出正整数\(n\)分解为三个\(3\)的倍数的方法数。当无法将\(n\)分解成三个\(3\)的倍数的时候输出\(0\)；

注意：分解时不可以分解出\(0\)

样例

输入：
2
9
12

输出：
1
3

提示：
9可以分解为3+3+3，一种方法。12可以分解为6+3+3,3+6+3,3+3+6，三种方法。

输入：
3
15
18
21

输出：
6
10
15


提示：
将15分解为三个3的倍数的方法数有6种，将18分解为三个3的倍数的方法数有10种，将21分解为三个3的倍数的方法数有15种。

解答

只有一个数是\(3\)的倍数，才能将它划分成\(3\)个\(3\)的倍数之和。由于这里已经假设了\(n\)是\(3\)的倍数，因此这里只需要考虑\(m=n/3\)能够划分成多少份即可。使用隔板法考虑，目前有\(m\)个连续的物品，需要分成\(3\)段，有多少种分法？也就是说，相当于在这\(m\)个物品的缝隙插\(3-1=2\)个隔板，就能够分出三份。由于这里只有\(m-1\)条缝隙，因此有\(\dbinom{m-1}{2}=\dfrac{(m-1)(m-2)}{2}\)种方法。

代码

T = int(input())
for _ in range(T):
    n = int(input())
    m = n // 3
    print((m - 1) * (m - 2) // 2)