杂题

1

题意

将整数n拆分为m个数的和，输出这m个数or的最小值。

题解

要想使或值最小，那么m个二进制数中的最高位应尽量小，假如存在k使$(2^k-1)m > n > (2^{k-1}-1)*m$，所以m个二进制数中至少有一个数的最高位为k。因为是取各位取或，所以此时应让尽量多的数的第k位为1，$ans += 2^k$，从高位向低位递推，直到n变为0。

2

题意

$$\Large\sum\limits_{i=1}^n\lfloor\frac n i\rfloor$$

代码

//solution1
int k=sqrt(n+0.1);
for (int i = 1; i <= k; i++) {
	ans+=n/i;
	if (n/(i+1)<i)break;
	else ans+=(n/i-n/(i+1))*i;
}

//solution2
for (int i = 1; i <= k; i++)  ans+=n/i;
ans*=2;
ans-=k*k;

3

题意

设一个排列，当i为奇数，a[i]>a[i-1]，求满足条件的长度为n的数量

题解

设答案是 $f(n)$
考虑最⼤大的数的位置是 i，则变成一个长度为 i-1 的数列列和一个长度为 n-i 的数列列
所以 $f(n)=\sum\frac {f(i)f(n-i-1)} n$
所以 $f(x)’=f(x)^2+1$
解得 $f(x)=tan(x)$

4

题解

n+1个数由1-n 组成，只有一个重复的，找出来。

代码

int findDuplicate(vector<int>& nums) {
    int low = nums[0], fast = nums[nums[0]];
    while (low != fast) {
        low = nums[low];
        fast = nums[nums[fast]];
    }
    fast = 0;
    while (low != fast) {
        low = nums[low];
        fast = nums[fast];
    }
    return low;
}

int findDuplicate(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums[abs(nums[i]) - 1] < 0) return abs(nums[i]);
        nums[abs(nums[i]) - 1] *= -1;
    }
    return -1;
}

5

法一: 求每个点左边连续比它大的最左边的下标，保存在l[]数组里,求每个点右边连续比它大的最右边的下标，保存在r[]数组里

法二: 维护一个单调栈, 如果h大于栈顶元素，则入栈, 否则，将栈内元素出栈，直到满足上面的条件。出栈时，我们要将出栈元素对之后问题的影响全部考虑进行处理，才能保证做法的正确性。

6

只需n+m-1个就可以填满,

当插入点(x1,y1) 时有关系x1<=>y1

当插入点(x2,y1) 时有关系 x2<=>y1<=>x1

当插入点(x1,y2) 时有关系 y2<=>x1<=>y1<=>x2

用并查集来连接

7

给你一个序列n个数组成，然后让你在里面找到m个子序列，让这m个子序列的和最大。

dp[i][j]表示的是第j个数字在第i个子序列时的当前最优值。

dp[i][j] = maxx(dp[i][j-1] + num[j] ,maxx(dp[i-1][k]) + num[j]);  k是从1到j-1.

可以这么理解这个转移方程，对于当前的这个数字，如果把他放到第i个子序列中有两种情况，一个是他作为第i个子序列的第一个数字，另一个就是不作为第一个数字，作为第一个数字的时候是 max(dp[i-2][k] + num[j]) 1<=k<i 的意思是从之前的所有中找到i-1个子序列的最大值+当前的值，不做为第一个的时候那么他前面的那个数字一定是i序列的，同一个子序列，又不是作为第一个，那么前面的那个货就一定是同一个子序列的，那么当前的值是dp[i][j-1] + num[j],在两种决策中选择一个最有的就行了，还有就是maxx(dp[i-1][k]+num[j])的这个地方可以开一个数组记录下来，不能每次都跑，跑不起，再有就是这个题目没有给m的范围，所以开不了二维数组（目测不是很大，大的话会超时，但是肯定是先超内存在超时，所以为了保险，还是吧dp[][]压缩成一维的）那么状态转移就边成这样了dp[j]表示的是 j这个人在当前的这个子序列中的最优值，mk[j]表示的是在上一个子序列中1--j的dp的最大值，所以就变成 dp[j] = maxx(dp[j-1] + num[j] ,mk[j-1]+num[j]);还是 max(作为i个子序列的第一个元素，不是第一个元素取一个最大值)。在解释下代码的核心部分。

8

给一个函数

int f(int x,int y){
	int c=0;
    while(y>0){
		c++;
        t=x%y;
        x=y;
        y=t;
    }
    return c*x*x;
}

给出n,m,p，求$\Large\sum\limits_{i=1}^n\sum\limits_{j=1}^m\lfloor\frac {i*j} {f(i,j)}\rfloor$

$$ans=\sum\limits_{j=1}^m\sum\limits_{i=1}^j\sum\limits_{k=0}^{i+j*k\le n}\lfloor\frac {j*(i+j*k)} {c*x*x}\rfloor\\=\sum\limits_{j=1}^m\sum\limits_{i=1}^j\sum\limits_{k=0}^{c-1}\sum\limits_{p=0}^{i+j*(k+p*c)\le n}\lfloor\frac {j*(i+j*(k+p*c))} {c*x*x}\rfloor\\ =\sum\limits_{j=1}^m\sum\limits_{i=1}^j\sum\limits_{k=0}^{c-1}\sum\limits_{p=0}^{i+j*(k+p*c)\le n}\lfloor\frac {j*(i+j*k)} {c*x*x}\rfloor+\frac {p*j*j} {x*x}$$

9

有n家银行围成一个圈，有个人在有些银行里欠了钱，在一些银行里有存钱，欠的钱总数等于存的钱总数。现在可以有操作，如果两个银行相邻，那么就能在一个银行转任意多的钱到另一个银行。问最少的操作次数，使得在所有银行的存款钱数都为0。

首先我们要发现第一个贪心。如果有一段子串，里面的数字之和等于0，那么在这段子串中移动数字，所需要的代价为子串长度len-1，那么问题就转换成了，我们在这个圈中能找到多少段子串，里面的数字之和等于0，而且段数越多越好，记为k，那么很明显，答案就是n-k，现在问题来了，如何来求满足题意的最大的k。首先，我们考虑用前缀和来存放，如果遇到两个位置，前缀和相等，那么中间那一段数字之和肯定等于0。接下来就是一个跳跃性的思考了，那么如果某个前缀和的值出现了k次，是不是就是我们上述的k呢？答案是正确的！假如有k个位置的前缀和相等，那么中间k-1段子串内数字之和一定都是0，由于总数是0，那么最前面和最后面连着的那一段也肯定是0，所以，我们记录所有的前缀和的值，然后排序。然后用取尺法记录一个数出现的最多次数，就做完了

10

将整数n拆分为m个数的和，输出这m个数or的最小值。

要想使或值最小，那么m个二进制数中的最高位应尽量小，假如存在k使$(2^k-1)m > n > (2^{k-1}-1)*m$，所以m个二进制数中至少有一个数的最高位为k。因为是取各位取或，所以此时应让尽量多的数的第k位为1，$ans += 2^k$，从高位向低位递推，直到n变为0。

11

求a~b间素数个数(1 ≤ a ≤ b < 2^31, b - a ≤ 100000).

memset(visab,0,sizeof(visab));
for (int i = 0; i < cnt && prime[i] <= b; i++) {
	LL k = a / prime[i];
  	if (k * prime[i] < a) k++;
  	for (LL j = k * prime[i]; j <= b; j += prime[i]) {
  		visab[j - a] = 1;
 	}
}

12

求和

$$\Large\sum\limits_{i=1}^n\lfloor\frac n i\rfloor$$

//solution1
int k=sqrt(n+0.1);
for (int i = 1; i <= k; i++) {
	ans+=n/i;
	if (n/(i+1)<i)break;
	else ans+=(n/i-n/(i+1))*i;
}

//solution2
for (int i = 1; i <= k; i++)  ans+=n/i;
ans*=2;
ans-=k*k;

13

设一个排列，当i为奇数，a[i]>a[i-1]，求满足条件的长度为n的数量

设答案是 f(n)

考虑最⼤大的数的位置是 i，则变成⼀一个⻓长度为 i-1 的数列列和一个⻓长度为 n-i 的数列列

所以 f(n)=sum(f(i)f(n-i-1))/n

所以 f(x)’=f(x)^2+1

解得 f(x)=tan(x)

14

n+1个数由1-n 组成，只有一个重复的，找出来。

int findDuplicate(vector<int>& nums) {
    int low = nums[0], fast = nums[nums[0]];
    while (low != fast) {
        low = nums[low];
        fast = nums[nums[fast]];
    }
    fast = 0;
    while (low != fast) {
        low = nums[low];
        fast = nums[fast];
    }
    return low;
}

int findDuplicate(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        if (nums[abs(nums[i]) - 1] < 0) return abs(nums[i]);
        nums[abs(nums[i]) - 1] *= -1;
    }
    return -1;
}