没改完题就过来沽博客是不是有点不好……
ZJ一下：
好好好题。
T1数组大小……
$$10^7 ightarrow 60$$
事实上……
$$7 imes 10^7 ightarrow 0$$
$kuku$
重点是，我还开了$7 imes 10^7$个 vector
一定要检查检查代码，一定要！不要因为数组开小挂部分分，也不要因为数组开大挂全部分
$huge QAQ$
|
44
|
Miemeng | 0
03:12:34
|
8
03:12:37
|
30
03:12:36
|
38
03:12:37
|
T1
因为$log$会被卡，于是直接开$B$个队列，这样通过向队尾增加元素来维护单调。
这样就直接优化掉一个$log$
复杂度：$Theta(KB)$
（直接开$7 imes 10^7$的就行，作者是不会叫你MLE的=。=）
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#define B 17
#define LL unsigned long long
#define N 11111111
using namespace std;
const LL pri[B]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
template<typename Tp>
class Myqueue{
Tp A[N];int f,b;
public:
Myqueue(){f=b=0;}
void clear(){f=b=0;}
void push(const Tp k){A[b++]=k;}
void pop(){f++;}
Tp front(){return A[f];}
bool empty(){return f==b;}
void pour(){
puts("------------");
for(int i=f;i<b;i++)
cout<<A[i]<<" ";
cout<<endl;
puts("------------");
}
};
int kth,b;
Myqueue<LL>qs[B];
void prerun(){
for(int i=1;i<=b;i++)qs[i].push(pri[i]);
}
main(){
cin.sync_with_stdio(false);
cin>>b>>kth;
prerun();
int cnt=1;
LL minn;
while(cnt<kth){
// if(cnt>850000)
for(int i=1;i<=b;i++){
cout<<pri[i]<<":
";
qs[i].pour();
}
minn=LLONG_MAX;
int id;
for(int i=1;i<=b;i++){
if(!qs[i].empty()&&minn>qs[i].front()){
minn=qs[i].front();
id=i;
}
}
qs[id].pop();
cnt++;
for(int i=id;i<=b;i++){
qs[i].push(minn*pri[i]);
}
}
cout<<minn<<endl;
}
T2
没有过，
但是可以传（$zhugrave{a}n$）达题解思想。
首先使用记忆化搜索，
状态由两部分组成，
当前队列中总共有的质因子情况，
有共同因子的数在质因子层面上的数对情况。
用第二个来保证不会有三个数有共同的质因子。
（说实话我不会）
T3
又没有过
很神奇的一道题，因为有错的，但不超过$1 over 2$
于是使用随机化，每两个坐标对可以求出一组可能解。
$check$一下，尝试$50$次，
非酋全没找到正解的概率$(frac{3}{4})^{50} approx 0.000000566$