拼多多笔试 第三批 3.1 更新了第四题答案
#写了第四题答案，但线下造的例子过了，线上不知道
#直接拉最下面就可以看了
'''
算法工程师方向，和后端、前端题目一样。由于我肯定去不了拼多多了所以直接屏幕截图了，估计被判作弊了。很简单，算法工程师都知道，检测视频频谱最高的部分抽帧，直接就能检测到打开word并复制截图的关键帧，这种抽帧作弊检测很好写，我不相信牛客没有这技术。但无所谓了
或者检测Ptr键也行。
总共花了不到一小时，但是最后一题无思路，就交了，求一波第四题答案。
'''
求求求求求求求第四题思路。
题1：不等式推导
n = int(input()) for _ in range(n): a,b,c = list(map(int,input().split())) res = min((a+b+c)//3,min(a,b)) print(res)
思路：成团要至少有一个a,b。那么输出的结果一定有res<=min(a,b)
然后成团要配三个，那么去掉用来配对的a或b后还要有两个备胎，即
sum - min(a,b) 和 2*min(a,b)比较，如果去掉配对的sum - min(a,b) 还有很多，那么只用min(a,b)输出就行了。
但不够配对了，那么就要输出(sum - res)//2了。
所以结果
res<=(sum - res)//2，即res<=sum//3
res<=a
res<=b
因此res = min{sum//3,a,b};
python //是整除号，C++直接/就行。
发现最小值周期是4就简单了，所谓的绝对值减过来减过去无非就是数组选一部分减另一部分的绝对值。
dp1 = [0,1,1,0] def get_min(n): if n<=0: return 0 else: return dp1[n%4] def get_max(n): return n - get_min(n-1) T = int(input()) for _ in range(T): n = int(input()) print(get_min(n),get_max(n))
首先一定要得知道F(N)代表了1-N这N个数选一部分减去另一部分的绝对值。
最小值如何算呢？我一开始以为是奇偶关系，发现不是，无规律。然后突然注意到四个数可以配出来0。举个例子，1 2 3 4 5 6 7。
4 5 6 7是能凑出来0的，那么5 6 7 8啊 8 9 10 11都可以凑出来0，则4是周期。
N=1的时候只要1个数,min=1。
N=2，min=2-1=1。
N=3，min=3-2-1=0。示例
N=4，根据周期性得出N=4等于N=0，min=1+4-2-3=0。
最大值等于 最后一个数 -(前面N-1个数的最小值) 且最后一个数一定是N，因为最小值值域是0,1，这种方法得出来的结果一定是N或者N-1。无论其他情况怎么配，只要最后一个数不比N-1大，那么它减去一个绝对值一定是<=N-1的，不会比这种配法得到的最大值要大。
题3：动态规划，不同上升子序列的个数 n = int(input()) data = list(map(int,input().split())) c_data = sorted(list(set(data))) dp = [0]*n dpi = [0]*n for val in data: index = c_data.index(val) dpi[index]=1 cur = sum(dpi[:index]) + sum(dp[:index]) dp[index] = cur print(sum(dp))
动态规划*2，不同的上升子序列的数目。
我是把上升子序列分成了两种情况，第一种是配出序列长度为2的子序列，配法是读出当前的值，判断有多少个值小于他，那么就能配出来多少个长度为2的子序列。dpi对应各个val的个数，取值0,1。
另一种情况是长度大于3的，这里记录了所有以val结尾的子序列长度>=2的数目，则对于新来的数，以他结尾的大于2的子序列数目为：判断有多少个值小于他，把这些值结尾的子序列数目加起来即可。
最后对于每个新值，其子序列数目为长度为2的部分加上长度大于2的部分。
由于要求去重，所以用了set()。
题4：不会 暴力10% 一个数组，得分是任选两个数，他们的和与他们的距离定义为得分。距离是圆周距离。
换成C/C++写依旧是10%
暴力走了一遍，无思路。
翻译一下：一个数组，取两个数，算他们的距离与值的和。
距离为圆周距离，好比1,2,3。1,3的距离是1，因为他们挨着。
可能关于手串的项链啊什么的动态规划有类似的题吧，还是题刷少了，但连续三题动态规划吗。。。
n = int(input()) data = list(map(int,input().split())) res = 0 cur_index = 0 for i in range(n): for j in range(i+1,n): tmp = min((i-j+n)%n,j-i) + data[i]+data[j] if tmp>res: res =tmp cur_index = 0 elif tmp==res: cur_index+=1 print(res,cur_index+1)
#########################################################################
第四题：简单扫描模拟
一个数组，得分是任选两个数，他们的和与他们的距离定义为得分。距离是圆周距离。
返回最大得分，和最大得分的情况个数。
每次进来一个新的数，选择前面的最大值和他配对
优弧：data[j]+j+(data[i]-i)
劣弧：data[j]-j+(data[i]+n+i)
优弧存(data[i]-i)，最大值max1，劣弧存(data[i]+n+i)，最大值max2。优弧得分为data[j]+j+max1，劣弧得分为data[j]-j+max2
题干又臭又长，但是题意非常之简单，选择数组两个数，他们的得分是各自的和加上距离。
距离是圆周上的距离，举个例子就知道了
数组是 1 2 3 4 5 6。
1和2的距离是1，1和3的距离是2，1和4的距离是3，1和5的距离是2，1和6的距离是1。
问数组最大得分，和取到最大得分的情况数目。
（默认j>i）
如果直接是距离，这题就很简单很简单，直接把data[i]-i存起来读data[i]-i的最大就行了。然后对新数据j，判断data[j]+j-data[i]-i有没有超过最大值，超过就更新。然后再把data[j]-j存起来。
这个题麻烦就麻烦在距离变了，当时还有一小时，我是一点思路也没有，急着看比赛就交了。事后和评论讨论了一下，写了一版代码出来。
思路就是：
建立两个map存数据，一个存优弧，一个存劣弧。这是因为优弧和劣弧的得分计算方式不一样。
优弧 data[j]+data[j]+data[i]-i
劣弧 data[j]-j+data[i]+n+i
所以优弧存的是data[i]-i，劣弧存的是data[i]+n+i。对于过半的数据，每次把data[i]-i的数据弹出来放在劣弧里就行了。
这里由于数据很大1e6，所以只能用C/C++写，不要用iostream，太慢了。然后划数据放在了栈里面，因为栈开辟很快。
但是存数据有两种，一种是红黑树，读数据最坏复杂度O(nlog2n)。一种是哈希，读数据是O(1)。考虑到这样一种情况，因为要很快的读出来最大值，哈希表万一退化到O(n)就凉凉了，所以用的红黑树。对应C++的map。
为了能够更快的找到最大值，这里用了延迟更新。因为找最大值这一步是在弹出数据这一步，如果最大值全弹出了就要更新，所以每次弹出数据的时候记录个数-1，但只在最大值的个数<0的时候更新。
现在想想也没那么难。。。。。。
但是STL总归在堆里开辟，是比较慢的，但是没办法，总不能手写带删除的红黑树吧，过分了。
n = 1的时候，返回0 0吧，不知道题目判例有没有写这种恶心的特殊情况，写了就再特判下。
#include <stdio.h>
#include <map>
using namespace std;
inline int get_maxkey(map<int,int,greater<int>>&m)
{
return m.begin()->first;
}
inline int get_maxnums(map<int,int,greater<int>>&m)
{
return m.begin()->second;
}
int main()
{
int n;scanf("%d",&n);
int data[100005];//开辟的快点，不默认初值
for(int i=0;i<n;++i)
scanf("%d",&data[i]);
//C++的map是红黑树，时间复杂度最坏O(log2n)，找到最大值O(logn)
int mid_index = (n+1)/2;
map<int,int,greater<int>>data_i1;
map<int,int>data_i2;
int data_max1 = -0x3f3f3f3f;
int data_nums1 = 0;
int data_max2 = -0x3f3f3f3f;
int data_nums2 = 0;
int res_max = -0x3f3f3f3f;
int res_nums = 0;
for(int i=0;i<n/2;++i)
{
int cur_max = data[i]+i+data_max1;
//结果最大值更新
if(cur_max>res_max)
{
res_max = cur_max;res_nums=data_nums1;
}else if(cur_max==res_max)
{
res_nums+=data_nums1;
}
//数据最大值更新
if(data[i]-i>data_max1)
{
data_max1 = data[i]-i;data_nums1=1;
}else if(data[i]-i==data_max1)
{
++data_nums1;
}
//数据插入
if(data_i1.count(data[i]-i))
{
++data_i1[data[i]-i];
}else
{
data_i1[data[i]-i]=1;
}
//printf("insert:%d\n",data[i]-i);
}
//开始存在劣弧，方法就是每次从优弧中弹出变成劣弧的数据，把劣弧转成优弧存起来。
for(int i=mid_index;i<n;++i)
{
//先弹出劣弧
int delete_i = i-mid_index;
int delete_key = data[delete_i]-delete_i;
data_i1[delete_key]-=1;
if(delete_key==data_max1)
{
data_nums1-=1;
if(data_nums1==0)
{
//最大值被删掉了，要重找最大值
while(get_maxnums(data_i1)==0)
{
data_i1.erase(get_maxkey(data_i1));
}
data_max1 = get_maxkey(data_i1);
data_nums1 = get_maxnums(data_i1);
}
}
//插入优弧,数据最大值更新
if(data[delete_i]+n+delete_i>data_max2)
{
data_max2 = data[delete_i]+n+delete_i;data_nums2=1;
}else if(data[delete_i]+n+delete_i==data_max2)
{
++data_nums2;
}
if(data_i2.count(data[delete_i]+n+delete_i))
{
++data_i2[data[delete_i]+n+delete_i];
}else
{
data_i2[data[delete_i]+n+delete_i]=1;
}
//劣弧已更新，更新最大值，原优弧区
int cur_max = data[i]+i+data_max1;
if(cur_max>res_max)
{
res_max = cur_max;res_nums=data_nums1;
}else if(cur_max==res_max)
{
res_nums+=data_nums1;
}
//新优弧区，即劣弧区
cur_max = data[i]-i+data_max2;
if(cur_max>res_max)
{
res_max = cur_max;res_nums=data_nums2;
}else if(cur_max==res_max)
{
res_nums+=data_nums2;
}
//数据插入
if(data_i1.count(data[i]-i))
{
++data_i1[data[i]-i];
}else
{
data_i1[data[i]-i]=1;
}
//printf("insert:%d\n",data[i]-i);
}
//输出结果
printf("%d %d",res_max,res_nums);
return 0;
} 
投递拼多多集团-PDD等公司9个岗位