CF EDU 23

题解

B:makes and the product
题意：
找出一个数组中有多少个3元组使得ai * aj * ak 等于最小的三个数的乘积。
思路：
一开始老是想不通，怎么都是O(n^2)的复杂度嘛，后来看了tuorial，用了前缀最大值和后缀最小值的思想，orz写了b并写不出来。
再后来看到了别人的代码，就是简单的组合问题orz，自己的脑子就是想不出来，题不能停啊。
先对数组进行排序，然后我们看n个数中有多少个数与a[2]相同，设为cnt，如果a[0] == a[2],那么就说明n个数全为一样的，所以就C(n,3)；如果只是a[1] == a[2]，且a[0] != a[2]的话，那么我们就从这cnt个数中选择两个，即C(cnt,2)；如果前两个条件都不满足的话，那么直接就是cnt个结果。
比如1 1 1 1，C(4,3);
比如1 2 2 2 3 4，这样的，就是C(3,2);
比如1 2 3 3 4 4，就是2.

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[100005];
int main()
{
  int n;
  scanf("%d",&n);
  for (int i = 0;i < n;i++)
    scanf("%d",a+i);
  sort(a,a+n);
  long long cnt = 0;
  for (int i = 0;i < n;i++)
  {
    if (a[i] == a[2]) cnt++;
  }
  if (a[2] == a[0]) printf("%I64d\n",(cnt - 1)*(cnt - 2)*cnt / 6);
  else if (a[1] == a[2]) printf("%I64d\n",(cnt-1) * cnt / 2);
  else printf("%I64d\n",cnt);
  return 0;
}

C:really big numbers
题意：
定义一个数为rbn，当且仅当它的每位上的数字之和与它的之差的绝对值大于等于给定的s，问在1到n的范围内这样的数字有多少个。
思路：
看了tutorial才知道当x为rbn，那么x+1也为rbn，因为x+1要么使得sum加1，这是普通情况；特殊情况是x+1有进位，这时x+1的sum反而变小了，所以我们找到最小的rbn为minn，n - minn + 1就是我们的答案。
注意当 n - minn + 1 < 0的时候需要特判输出0.
因为n的规模比较大，所以我们用二分找就可以了，其实可以发现数字的规律是非递减，那么自然就可以用二分了。

代码：

#include <stdio.h>
long long n,s;
long long mabs(long long t)
{
  return t >= 0 ? t : -t;
}
bool meet(long long t)
{
  int sum = 0;
  long long tt = t;
  while (t != 0)
  {
    sum += t % 10;
    t /= 10;
  }
  if (mabs(tt - sum) >= s) return 1;
  return 0;
}
int main()
{
  scanf("%I64d %I64d",&n,&s);
  long long l = 1,r = n;
  while (l <= r)
  {
    long long mid = (l + r) >> 1;
    if (meet(mid)) r = mid - 1;
    else l = mid + 1;
  }
  while (!meet(r)) r++;
  while (meet(r-1)) r--;
  printf("%I64d\n",n - r + 1 > 0 ? n - r + 1 : 0);
  return 0;
}