UVA12918 题解

· · 题解

题目传送门

思路

本题是数学题。

首先选定一把钥匙与每一个门进行尝试。由于小偷不需要打开门，只需要将钥匙与门配对，所以在第 1 次时，假设小偷已经试了 m-1 次都没有成功，那么最后一个门一定与当前钥匙配对。故第 1 次所需次数为 m-1。

在第 2 次尝试中，这把钥匙除了可以不与最后一个门尝试，也可以不与第 1 把钥匙所配对的门尝试。故第 2 次所需次数为 m-2。

以此类推，第 3 次尝试需要 m-3 次，第 i 次尝试需要 m-i 次。到最后的第 n 次需要 m-n 次。

不难发现这构成了一个等差数列。将 n 个 m 提取出，得 mn。然后再减去一个从 1 到 n 的等差数列，即 \frac{n(n+1)}{2}。故答案为 mn-\frac{n(n+1)}{2}。

注意事项

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}

signed main(){
    int T=read();
    while(T--){
        int n=read(),m=read();
        printf("%lld\n",m*n-n*(n+1)/2);
    }
    return 0;
}