topcoder srm 697 div1 -3
1、给定长度为n 的数组b，构造长度为n 的且没有重复元素的数组a，令p_{i}表示a中除a_{i}外其他元素的乘积。构造出的a满足a_{i}^{b_{i}}能够被p_{i}整除。这样的数组a存在否？
思路：因为a_{i}^{b_{i}}中所有素因子的指数大于等于p_{i}。所以可以假设所有的a_{i}只含有素因子2。令a_{i}=2^{A_{i}},s=\sum_{i=1}^{n}A_{i}，那么有A_{i}b_{i}\geq s-A_{i}，即A_{i}\geq \frac{s}{1+b_{i}}。所有这些加起来约去s得到\sum_{i=1}^{n}\frac{1}{1+b_{i}}\leq 1。令K=\sum_{i=1}^{n}\frac{1}{1+b_{i}}。所以K>1K=1但是存在相同的b时无解。因为K=1说明A_{i}= \frac{s}{1+b_{i}}，但是相同的b 导致出现了相同的A。
#include <stdio.h>
#include <string>
#include <stack>
#include <vector>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
class DivisibleSetDiv1
{
public:
string isPossible(vector <int> b)
{
const int n=(int)b.size();
sort(b.begin(),b.end());
double ans=0;
for(int i=0;i<n;++i) ans+=1.0/(b[i]+1);
if(ans>1+1e-10) {
return "Impossible";
}
else if(ans>1-1e-10) {
for(int i=1;i<n;++i) if(b[i]==b[i-1]) {
return "Impossible";
}
}
return "Possible";
}
};2、有n匹马，每个马有个各不相同的值a_{i}。有2^{m}场比赛。第i匹马在第j场比赛中的用时为a_{i}^j（抑或）。每场比赛所有的马排名为[0,n-1]。排名为k的马得到的罚时为k^{2}。所有比赛结束后每匹马的所有罚时加起来得到第i匹马的总罚时p_{i}，计算所有p_{i}%1000000007的抑或值。
思路：将每匹马的值a_{i}建立一课二叉树，并在节点上记录子树中插入的马的个数。然后依次计算每一匹马的p_{i}值。对于第i匹马，设比赛j的二进制高t位等于a_{i}的高t位的所有比赛中它的罚时为g=\sum_{r=1}^{2^{m-t}}s_{r}^{2}。2^{m-t}是因为已经进行了这么多长比赛。那么在进行比赛的二进制第m-t位不同于a_{i}的第m-t位但是它们的高t-1 位相同时的所有比赛中，它的罚时为g^{‘}=\sum_{r=1}^{2^{m-t}}(s_{r}+x)^{2}。其中x为与a_{i} 的第m-t位不同的一侧所有马的个数。那么g^{‘}=g+2^{m-t}x^{2}+2x\sum_{r=1}^{2^{m-t}}s_{r}。这样记录已经遍历的子树的前缀和\sum_{r=1}^{2^{m-t}}s_{r}即可。
#include <stdio.h>
#include <string>
#include <stack>
#include <vector>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
const int N=200005;
const int mod=1000000007;
int a[N];
int T[N*32][2];
int S[N*32];
int e;
int m;
void add(int x)
{
int p=1;
for(int i=m-1;i>=0;--i)
{
int t=(x>>i)&1;
if(!T[p][t]) T[p][t]=++e;
p=T[p][t];
++S[p];
}
}
int c[32];
void cal(int x)
{
int p=1;
for(int i=m-1;i>=0;--i)
{
int t=(x>>i)&1;
c[i]=S[T[p][t^1]];
p=T[p][t];
}
}
class XorOrderDiv1
{
public:
int get(int M,int n,int a0,int b)
{
m=M;
a[1]=a0;
for(int i=2;i<=n;++i) a[i]=(a[i-1]+b)&((1<<m)-1);
e=1;
for(int i=1;i<=n;++i) add(a[i]);
int ans=0;
for(int i=1;i<=n;++i)
{
cal(a[i]);
int tmp=0,sum=0;
for(int j=0;j<m;++j)
{
tmp=(tmp+(long long)(1<<j)*c[j]%mod*c[j]%mod+(long long)2*c[j]%mod*sum%mod+tmp)%mod;
sum=(sum*2+(long long)c[j]*(1<<j))%mod;
}
ans^=tmp;
}
return ans;
}
};发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/101196.html原文链接：https://javaforall.cn
腾讯云开发者
