T1 子集和
看出是一道背包的切得都飞快，我没用背包于是做了很长时间。。。
因为代码太难调了！！！！
建议不要看我的，不过如果你想整活儿学一些\(nb\)的算法可以看一看
我拿一个指针从\(m-1\)开始往前扫，发现越到后面的数组成他用的集合的大小就越大
那么从后往前扫，定义指针\(p\)为当前扫到的桶不为空的元素，那么我们将会把\(m-p\)放入答案中
他一定会存在于\(a\)数组中，且\(p\)就是除了这个数的剩下的数的加和
这样我们每找到一个不空的桶就给他更新一个答案，同时对当前的\(a\)数组中所有元素能够组成的数进行统计
把能够组成的数的桶该减的减掉
做法就是拿一个\(set\)，记录二元组\((val,cnt)\)表示一个数\(val\)出现的次数\(cnt\)，每次加入答案数组的时候都更新这个\(set\)里面的元素
其实不难发现，如果代码写的对的话，\(set\)中最后存的所有元素就是\(b\)数组的下标以及其对应的桶的个数
subset(Very disgusting!!)
#include<bits/stdc++.h>
#define int long long
using namespace std; FILE *wsn;
auto read=[](){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
};
const int NN=10001;
int n,m,b[NN],a[NN],top,pot,c[NN];
struct node{
int val; mutable int cnt;
bool operator<(const node&x)const{
return val<x.val;
}
};
set<node>S; node stk[NN],skt[NN];
inline void push(int x){
for(auto s:S)
if(S.find(node{x+s.val,0})==S.end()) stk[++top]=node{x+s.val,s.cnt};
else skt[++pot]=node{x+s.val,s.cnt};
while(pot) S.find(node{skt[pot].val,0})->cnt+=skt[pot].cnt,--pot;
while(top) S.insert(node{stk[top].val,stk[top].cnt}),--top;
if(S.find(node{x,0})==S.end()) S.insert(node{x,1});
else S.find(node{x,0})->cnt++;
for(auto s:S) c[s.val]=b[s.val]-s.cnt;
}
namespace WSN{
inline short main(){
wsn=freopen("subset.in","r",stdin);
wsn=freopen("subset.out","w",stdout);
n=read(); m=read();
for(int i=0;i<=m;i++)c[i]=b[i]=read();
int p=m-1,tmp=0,tim=0;
while(tmp<n-1){
while(!c[p]&&p) --p;
if(!c[m-p]) c[p]=0;
else --c[p],a[++tmp]=m-p,push(m-p);
}int sm=0;
for(int i=1;i<n;i++)sm+=a[i],printf("%lld ",a[i]);printf("%lld\n",m-sm);
return 0;
}
}
signed main(){return WSN::main();}
T2 异或
发现考场上打二维偏序的好像又只有我一个。。。。
好的刚刚发现了一个，sdfz兄弟很棒棒！！！
然而非常不服，发现常数小的\(O(n^3)\)居然也能拿\(40\)!!!很气愤
不懂为啥能跑过\(8e9\)
正解是\(trie\)数思想或者说是跟二进制位有关的，显然。。
考虑\(i,k\)的每一位，发现他们的大小决策于从低到高的第一个不同的位上
那么我们枚举每一位，设枚举的是第\(p\)位，再枚举从\(1\)到\(n\)找到每一位上的数是啥，记一下高于第\(p\)位的数为\(res\)，并进行离散化
那么我们发现如果\(a_k>a_i\)，有以下几种情况
- \(a_k[p]=1,a_i[p]=0,a_j[p]=0\)
- \(a_k[p]=0,a_i[p]=1,a_j[p]=1\)
那么我们枚举的\([1,n]\)相当于是在枚举\(a_k[p]\)，
那么我们只需要知道前缀的\(0/1\)个数\(sum[0/1]\)
和当前的\(k\)的\(res\)相同的\(i\)的前缀的\(0/1\)的个数\(cnt[res][0/1]\)
以及需要容斥掉的算重的个数\(pre[res][0/1]\)即可在\(O(1)\)复杂度内计算答案
xor
#include<bits/stdc++.h>
#define int long long
using namespace std; FILE *wsn;
auto read=[](){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
};
const int NN=5e5+5;
int n,a[NN],ans,id;
int sum[2],cnt[NN][2],pre[NN][2];
unordered_map<int,int>mp;
namespace WSN{
inline short main(){
wsn=freopen("xor.in","r",stdin);
wsn=freopen("xor.out","w",stdout);
n=read();for(int i=1;i<=n;i++)a[i]=read();
for(int i=30;i;i--){
sum[0]=sum[1]=0; id=0; mp.clear();
memset(cnt,0,sizeof(cnt));
memset(pre,0,sizeof(pre));
for(int j=1;j<=n;j++){
int it=a[j]>>i-1&1,res=a[j]>>i;
// cout<<it<<endl;
if(!mp[res])mp[res]=++id;
res=mp[res];
ans+=sum[it^1]*cnt[res][it^1]-pre[res][it^1];
++sum[it]; ++cnt[res][it]; pre[res][it]+=sum[it];
}
}
printf("%lld\n",ans);
return 0;
}
}
signed main(){return WSN::main();}
T3 异或2
珍爱生命，远离高精
关于递推式，我只想说第一次看见要推异或的式子的。。。
比较明显是要按照奇偶分类讨论的，剩下的直接看这个吧，感觉我写出来也是一样的，看着式子就比较好理解了
主要思想就是看每个数字的最后一位上是\(0/1\)对答案的贡献
rox
#include<bits/stdc++.h>
#define int long long
using namespace std; FILE *wsn;
namespace BIG_INT{
const int base=1e16;
typedef __uint128_t ULL;
struct Big_Int{
int p[100];
ULL has;
Big_Int(){}
Big_Int(int x){memset(p,0,sizeof(p));p[0]=1;p[1]=x;}
inline void gethash(){has=p[0];for(int i=1;i<=p[0];i++)has*=p[i];}
inline Big_Int READ(){
Big_Int ret=Big_Int(0); char s[505];
scanf("%s",s+1); int len=strlen(s+1);
for(int i=1;i<=len;i++)ret=ret*10+Big_Int(s[i]-'0');
return ret;
}
inline void print(){
printf("%lld",p[p[0]]);
for(int i=p[0]-1;i>0;--i) printf("%016lld",p[i]);
puts("");
}
Big_Int operator*(const int&x)const{
Big_Int ret=Big_Int(0);int add=0; ret.p[0]=p[0];
for(int i=1;i<=ret.p[0];++i){
ret.p[i]=p[i]*x+add;
add=ret.p[i]/base;
ret.p[i]-=add*base;
}
if(add) ret.p[++ret.p[0]]=add;
ret.gethash();
return ret;
}
Big_Int operator+(const Big_Int&a)const{
Big_Int ret=Big_Int(0);int add=0; ret.p[0]=max(a.p[0],p[0]);
for(int i=1;i<=ret.p[0];++i){
ret.p[i]=a.p[i]+p[i]+add;
add=ret.p[i]/base;
if(ret.p[i]>=base) ret.p[i]-=base;
}
if(add) ret.p[++ret.p[0]]=add;
ret.gethash();
return ret;
}
Big_Int operator-(const int&x)const{
Big_Int ret=Big_Int(0); ret.p[0]=p[0];
for(int i=1;i<=ret.p[0];i++)ret.p[i]=p[i];
ret.p[1]-=x; int pos=1;
while(ret.p[pos]<0){
ret.p[pos]+=base;
++pos; ret.p[pos]--;
}
if(!ret.p[ret.p[0]]) ret.p[0]--;
ret.gethash();
return ret;
}
Big_Int operator/(const int&x)const{
Big_Int ret=Big_Int(0); ret.p[0]=p[0];
for(int i=1;i<=ret.p[0];i++)ret.p[i]=p[i];
if(ret.p[1]&1) ret.p[1]--;
for(int i=ret.p[0];i;i--){
if(ret.p[i]&1) ret.p[i-1]+=base;
ret.p[i]/=x;
}
if(!ret.p[p[0]]) --ret.p[0];
ret.gethash();
return ret;
}
};
map<ULL,Big_Int> has;
}using namespace BIG_INT;
inline Big_Int dfs(Big_Int x){
if(x.p[0]<=1&&x.p[1]<=0) return has[x.has]=Big_Int(0);
if(has.find(x.has)!=has.end()) return has[x.has];
Big_Int k=x/2;
if(x.p[1]&1) has[x.has]=dfs(k)*4+k*6;
else has[x.has]=dfs(k)*2+dfs(k-1)*2+k*4-4;
return has[x.has];
}
Big_Int n,m,ans;
namespace WSN{
inline short main(){
wsn=freopen("rox.in","r",stdin);
wsn=freopen("rox.out","w",stdout);
n=n.READ();
dfs(n).print();
return 0;
}
}
signed main(){return WSN::main();}