3872链接：?problemCode=3872
题目大意：给你n个数，问所有的连续的子序列中的所有元素的和（子序列中有相同元素只计算一次）（n<100000）。
即若序列为1 2 3，则组成1，2，3，1 2，2 3，1 2 3，和为20；
若序列为1 2 2，则组成1，2，，2，1 2，2 2，1 2 2，和为13；
解题思路：求不重复的序列和很简单，关键是去重。
现在看一个序列： 3 4 7 6 4；如图中的4，
我们记录每个元素上一次出现的位置2，当下一次到 5 时再碰到这个元素，则在区间[ 3，5 ]这段区间的子序列的和需要当前 蓝色的4 这个元素，在包含[ 1 ,2]这个区间内的所有数的子序列不用计算第 后面的4 这个元素，但是 虽然不用计算 后面的4 ，但前面4个元素的所有子序列的和还是要计算，只是不包括最后的4.
令dp[ i ]表示前i个元素（包含i）的所有子序列的和，则 dp[ i ]=dp[ i-1 ]+(n-mp[ s[i] ])*s[i];其中mp[ s[i] ]表示s[ i ]上次出现的位置；最后用sum计算总的和就行了。
当然 dp[ i ] 可以用dp表示，因为像0/1背包的空间优化类似。
代码如下：
#include<cstdio>#include<cstring>using namespace std;#define LL long long#define M 1000005int mp[M];int main(){int t,n,a;scanf("%d",&t);while(t–){LL sum=0;memset(mp,0,sizeof(mp));scanf("%d",&n);LL dp=0;for(int i=1;i<=n;i++){scanf("%d",&a);dp=dp+(i-mp[a])*a;mp[a]=i;sum+=dp;}printf("%lld\n",sum);}}3870链接：?problemCode=3870
题目大意：给你n个数，问满足 两个数异或之后的值 比这两个数都大的 组合有多少种？(n<100000)
解题思路：对于这样一些数： 1 （1）
1 0 （2）
1 1 （3）
1 0 0 （4）
1 0 1 （5）
1 1 0 （6）
对于上面的数我们发现，其二进制的最高位肯定为1，1^1=0，那么位数相同的肯定不能组合，又发现 只有当某一位出现0时 和 上面同一位出现1的数组合 才有可能增大，为什么说有可能呢？比如3 和6 的组合，最低位为0^1=1是增大的,但次位为1^1=0减小，所以不符合；怎么才一定符合呢？那就是和当前位组合后，较小数的前面所有位（高位）都为0，那么解法就有了，先对所有的数排序，对每个数二进制分解，遍历每一位，当第i位为1时，s[ len ][ i ]++，其中len表示当前这个数的二进制长度，s[ len ][ i ]表示长度为len的数中第i位为1的数的个数；当第i位为0时，查找二进制长度为i的所有数中第i位为1的数的个数，之前遍历的时候已经预处理过了，直接加上就行了。
代码如下：
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;int s[35][35];int d[100005];int bin(int x)///某个数的二进制分解位数{int cnt;for(int i=1;i<32;i++)if((1<<i)-1>=x){cnt=i;return cnt;}}int main(){int t,n;scanf("%d",&t);while(t–){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&d[i]);sort(d,d+n);memset(s,0,sizeof(s));int ans=0;for(int i=0;i<n;i++){int cnt=bin(d[i]);int k=1;while(d[i])///二进制分解{int r=d[i]%2;if(r==1) s[cnt][k]++;else ans+=s[k][k];k++;d[i]/=2;}}printf("%d\n",ans);}return 0;}
爱情唯美短句子
