记录一些错题(跑路人笔记)

简介: 记录一些错题(跑路人笔记)

正文

1、现在有一个长度为 n 的正整数序列,其中只有一种数值出现了奇数次,其他数值均出现偶数次,请你找出那个出现奇数次的数值。


输入描述:第一行:一个整数n,表示序列的长度。第二行:n个正整数ai,两个数中间以空格隔开。


输出描述:一个数,即在序列中唯一出现奇数次的数值。


OJ链接【牛客网题号:KS33 寻找奇数】【难度:简单】


答案:


int main()
{
  int n = 0;
  scanf("%d", &n);
  int k = 0;
  int ans = 0;
  for (int i = 0; i < n; i++)
  {
  scanf("%d", &k);
  ans ^= k;
  }
    printf("%d",ans);
  return 0;
}




思路: 按位异或操作符的应用


下面先介绍一下原理

image.png



从上图可以看出


① 0^k(随便一个数) = k;


② k^k = 0;(甚至可以隔着几个数依旧成立)如上图的k^j^k = j


知道这两个原理就可以做出本题了


我们要从数值里找到一个出现数次为奇数的值.就原理②可以看到出现偶数次的数值通过按位异或就变成0 出现次数为奇数的数值就会和答案里的ans(及0)进行按位异或操作得到奇数数值最后打印即可


我们再来看一下答案就能更清楚的明白了.


int main()
{
  int n = 0;
  scanf("%d", &n);
  int k = 0;
  int ans = 0;//因为0按位异或任何数都是那个数值
  for (int i = 0; i < n; i++)
  {
  scanf("%d", &k);
  ans ^= k;//使用^= 时要注意ans一定要初始化为0才能将k保存下来用来下一次的操作
  }
  printf("%d", ans);//最后只有出现为奇数的值被保留了下来
  return 0;
}



1、牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。牛牛希望你能帮他计算一共有多少个可能的数对。


输入描述:输入包括两个正整数n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。


输出描述:对于每个测试用例, 输出一个正整数表示可能的数对数量。


OJ链接【牛客网题号:WY49 数对】【难度:简单】


示例:

输入:5 2

输出:7

说明:满足条件的数对有(2,3),(2,4),(2,5),(3,4),(3,5),(4,5),(5,3)


int main() 
{
  long n, k; 
  while (~scanf("%ld %ld", &n, &k)) 
  {
  if (k == 0) 
  {
    printf("%ld\n", n * n);//任意数对的取模结果都是大于等于0的
    continue;
  }
  long count = 0;
  for(long y = k + 1; y <= n; y++)
  { 
    count += ((n / y) * (y - k)) + ((n % y < k) ? 0 : (n % y - k + 1)); 
  }
  printf("%ld\n", count);
  }
  return 0; 
}



这个几乎就是数学题了


首先当k=0的时候就直接n*n不废话


后面count+=的公式才是关键


首先(n / y) * (y - k)


y-k 是因为在x处于y ~2y 的范围内时符合条件的个数为y-k


而n/y是为了得知区间个数及x能到2y 3y… 所以我们就得到的这些完整区间里的值


但是如果有些值不在这些完整区间内呢?如 当n=10; k=3;y=4时就有9 10这两个数不在区间范围内


这时我们就需要后面的(n % y < k) ? 0 : (n % y - k + 1) 来进行补充了


当超出区间时x/y的余数要还想大于k就必须有比k大的数值


当数值比k大时n%y-k+1就是我们要得到的组合个数


如:


n =5 k = 2


y=3时


超出区间的部分x有4 5 个数为2等于k所以通过(n % y - k + 1) 计算得一.


(写该题的时候一定要注意x在循环内变化的y在循环内不变)


相关文章
【机房重构】—上机&订餐
当用户(我)发出一个订餐(排骨盖饭)指令,它就会通过我们的网络(通道)到达餐馆(DAL层),餐馆通过判断告诉我是否还有排骨盖饭(在机房收费系统中这就相当于判断卡号是否存在);
【机房重构】—上机&订餐
|
搜索推荐 算法
排序总结(跑路人笔记1)
排序总结(跑路人笔记)
排序总结(跑路人笔记1)
|
编译器 C语言 C++
C++入门<一> (跑路人笔记2)
C++入门<一> (跑路人笔记)
C++入门<一> (跑路人笔记2)
|
自然语言处理 C语言 C++
C++入门<一> (跑路人笔记1)
C++入门<一> (跑路人笔记)
C++入门<一> (跑路人笔记1)
|
存储 C语言
指针进阶(一)(跑路人笔记)(2)
指针进阶(一)(跑路人笔记)
指针进阶(一)(跑路人笔记)(2)
|
存储 编译器
指针进阶(四)(跑路人笔记1)
指针进阶(四)(跑路人笔记)
指针进阶(四)(跑路人笔记1)