正文
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; }
思路: 按位异或操作符的应用
下面先介绍一下原理
从上图可以看出
① 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在循环内不变)
