noip模拟32 solutions
真是无语子，又没上100，无奈死了
虽然我每次都觉得题很难，但是还是有好多上100的
战神都200多了，好生气啊啊啊
从题开始变难之后，我的时间分配越来越不均匀，导致每次都没有时间做最后一题
今天直接挂掉了30pts，因为最后一题没有注意部分分。。
T1 smooth这个最简单了，我考场上一秒出80pts做法，直接一波set维护
自带排序和去重，完全不必担心，就是时间复杂度多了个log
80pts.set #include<bits/stdc++.h> using namespace std; #define re register int #define ll long long const int N=1e5+5; const ll maxn=1e18; int b,k; ll pt[N],tot; ll p[25]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71}; set<ll> st; int sum; signed main(){ scanf("%d%d",&b,&k); if(k==1){ printf("1"); return 0; } st.insert(1); while(st.size()){ set<ll>::iterator it=st.begin(); ll tmp=*it; sum++;//cout<<*it<<endl; //cout<<sum<<endl; if(sum==k){ printf("%lld",tmp); return 0; } for(re i=1;i<=b;i++){ if(sum+st.size()-1>=k&&tmp*p[i]>*st.rbegin())break; if(tmp<=maxn/p[i]) st.insert(tmp*p[i]); } st.erase(it); } }所以考完之后，看一眼题解瞬间就明白了，直接用队列维护，不用优先队列，
使用15个优先队列就够了，
因为我们每次都取所有队列头的最小值，保证了每次取出来的都是最小的
那么我们更新后面的答案的时候，只能向队列头最小的那个队列的后面的队列更新值
因为我们要去重，每一个这样更新出来的值，
一定是由一个质数乘上一个队列头最小值出来的，
而这个队列头又是由他的前面的队列头的最小值更新的，
这样每次都是小的乘大的，直接保证了不重不漏。。。
AC_code #include<bits/stdc++.h> using namespace std; #define re register int #define ll long long const ll inf=0x3f3f3f3f3f3f3f3f; ll b,k; ll p[25]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71}; queue<ll> q[16]; signed main(){ scanf("%lld%lld",&b,&k); for(re i=1;i<=b;i++)q[i].push(p[i]); ll mn,who; if(k==1){ printf("1"); return 0; } for(re i=1;i<k;i++){ mn=inf,who; for(re j=1;j<=b;j++) if(mn>q[j].front()) mn=q[j].front(),who=j; q[who].pop(); for(re j=who;j<=b;j++){ q[j].push(mn*p[j]); } } printf("%lld",mn); } T2 six这个题真的是神题，二维状压，真牛逼！！！
我是从这个题才第一次接触到二维状压的
所以其实这个题我是在zxb的指点之下才明白的，原来这个题是这么压的
对于一般的状压来说，我们只需要压这一位是否出现了，
但是这个题他不一样，因为你无法区分2、3和6
当你要加入一个6的时候，你发现当前的序列里已经有了2、3这两个质数
如果就是2、3这两个数，那么6就不能放进去了，但是如果是6的话，那还可以继续放
这是我们最难区分的点，所以我们需要把这两种情况分开，
对于每个可以放到序列里的数来说，最多包含6个质数，所以我们就直接标记他的每一个质数
这时候你肯定会大叫，这什么玩意，举个例子：
B为6，那么2是他的第一个质因子，3是第二个
2：01=1
3：10=2
6：11=3
我们把这些数拆成这样的状态，所以这就是为什么数据范围只有6
我们再对这些拆分进行状压，判断这样的数是否存在，直接用map记忆化搜索就完了
AC_code #include<bits/stdc++.h> using namespace std; #define re register int #define ll long long #define pa pair<long long,long long> #define mpa(x,y) make_pair(x,y) #define fi first #define se second const ll mod=1e9+7; ll n; map<pa,ll> mp; ll sum[1<<6],id[1<<6]; pa ys[10]; int top; ll dfs(ll s1,ll s2){ map<pa,ll>::iterator it=mp.find(mpa(s1,s2)); if(it!=mp.end())return it->se; mp.insert(mpa(mpa(s1,s2),1)); it=mp.find(mpa(s1,s2)); for(re i=1;i<(1<<top);i++){ int num=0; bool flag=0; for(re j=1;j<(1<<top);j++){ if(!(i&j))continue; if((s1>>j-1)&1)num++; if((s2>>j-1)&1)flag=1; if(flag||num>=2)break; } if(flag||num>=2)continue; if((s1>>i-1)&1)it->se=(it->se+sum[i]*dfs(s1^(1ll<<i-1),s2|(1ll<<i-1))%mod)%mod; else it->se=(it->se+sum[i]*dfs(s1|(1ll<<i-1),s2)%mod)%mod; } return it->se; } signed main(){ scanf("%lld",&n); for(ll i=2;i*i<=n;i++){ if(n%i)continue; ys[++top].fi=i; while(n%i==0){ ys[top].se++; n/=i; } } if(n!=1)ys[++top].fi=n,ys[top].se=1; for(re i=1;i<=top;i++)id[1<<i-1]=i; sum[0]=1;for(re i=1;i<(1<<top);i++) sum[i]=sum[i^(i&(-i))]*ys[id[i&(-i)]].se%mod; printf("%lld",dfs(0,0)-1); }考场上我直接去容斥了，然后发现，这个好像和顺序有关，2、3、6不行，但是2、6、3可以
T3 walker这个简单哈哈哈，虽然我考场上写都没写
但是我还没见过这么出题的，竟然让我搞随机化，让我枚举50组数据，一定能找到答案
还统计了一下失败的概率，这就靠人品了，rp++
就每次枚举两组数据，直接高斯约旦求解