网站开发费用怎么入账,在线生成logo设计,惠州网站建设 鑫,修改网站需要什么D - Delete Prime Gym - 102875D
题意#xff1a;
长度为n的序列#xff0c;每次从中取出编号为1或质数的数#xff0c;组成新的序列d 现在给一个k#xff0c;问序列中哪一位的值是k以及序列中第k位是多少 共T个询问 T 2 * 105 n#xff0c;k 105
题解#…D - Delete Prime Gym - 102875D
题意
长度为n的序列每次从中取出编号为1或质数的数组成新的序列d 现在给一个k问序列中哪一位的值是k以及序列中第k位是多少 共T个询问 T 2 * 105 nk 105
题解
其实这题巨简单。。。 一开始被吓住了看了看数据范围不知道d数组怎么求 其实直接暴力求数组d就可以不要想太多先筛出不符合要求的数然后依次将这些数按照第一批第二批的顺序存在vec[][]中 vec[i][j]表示第i批存的第j个数是。。 然后询问1和2直接用二分查找就可以 自己一开始想太多了
代码
#include bits/stdc.h
using namespace std;
const int N 1e6 10;
vectorint ans[110];
bool vis[N];
int a[N], k 0;
inline void get_prime() {for (int i 2; i N; i) {if (vis[i] 0) {for (int j i i; j N; j i) vis[j] 1;}}
}
inline void get_array() {int r 1e6, l, i;for (i 1; i N; i) a[i] i;while (r) {l 1;for (i 1; i r; i) {if (vis[i] 0) {ans[k].push_back(a[i]);} elsea[l] a[i];}ans[k].push_back(1e7);r l - 1;}
}
int solve1(int n, int m) {//根据结果选位置 int ans1 0;for (int i 0; i k; i) {int x upper_bound(ans[i].begin(), ans[i].end(), n) - ans[i].begin();int y upper_bound(ans[i].begin(), ans[i].end(), m) - ans[i].begin() - 1;if (ans[i][y] m) {ans1 y 1;break;} elseans1 x;}return ans1;
}
int solve2(int n, int m) {//输出第k位 int ans2;for (int i 0; i k; i) {int x upper_bound(ans[i].begin(), ans[i].end(), n) - ans[i].begin();if (m x)m - x;else {ans2 ans[i][m - 1];break;}}return ans2;
}
int main() {ios::sync_with_stdio(false);get_prime();get_array();int T, n, m, i, j, k;cin T;while (T--) {cin k n m;if (k 1)cout solve1(n, m) \n;elsecout solve2(n, m) \n;}return 0;
}
