什么是网站内链,天津建设工程信息网专家库官网,阜阳学网站建设,做网站是属于哪个专业T1:小X的质数 小 X 是一位热爱数学的男孩子#xff0c;在茫茫的数字中#xff0c;他对质数更有一种独特的情感。小 X 认为#xff0c;质数是一切自然数起源的地方。 在小 X 的认知里#xff0c;质数是除了本身和 1 以外#xff0c;没有其他因数的数字。 但由于小 X 对质数… T1:小X的质数 小 X 是一位热爱数学的男孩子在茫茫的数字中他对质数更有一种独特的情感。小 X 认为质数是一切自然数起源的地方。 在小 X 的认知里质数是除了本身和 1 以外没有其他因数的数字。 但由于小 X 对质数的热爱超乎寻常所以小 X 同样喜欢那些虽然不是质数但却是由两个质数相乘得来的数。 于是我们定义一个数是小 X 喜欢的数当且仅当其是一个质数或是两个质数的乘积。 而现在小 X 想要知道在 L 到 R 之间有多少数是他喜欢的数呢 输入格式 第一行输入一个正整数 Q表示询问的组数。 接下来 Q行。包含两个正整数 L 和 R。保证 L≤R。 输出格式 输出 Q 行每行一个整数表示小 X 喜欢的数的个数。 数据范围与约定 样例解释 1 666 以内的质数有 2,3,5而 42∗2,62∗3。因此 2,3,4,5,6 都是小 X 喜 欢的数而 1 不是。 样例输入1 1
1 6 样例输出1 5 样例输入2 10
282 491
31 178
645 856
227 367
267 487
474 697
219 468
582 792
315 612
249 307 样例输出2 97
78
92
65
102
98
114
90
133
29 样例输入3 10
20513 96703
15236 86198
23185 78205
40687 48854
42390 95450
63915 76000
36793 92543
35347 53901
44188 76922
82177 90900 样例输出3 24413
23001
17784
2669
16785
3833
17712
6028
10442
2734T2:小X的密室 小 X 正困在一个密室里他希望尽快逃出密室。 密室中有 N 个房间初始时小 X 在 1 号房间而出口在 N 号房间。 密室的每一个房间中可能有着一些钥匙和一些传送门一个传送门会单向地创造一条从房间 X 到房间 Y 的通道。另外想要通过某个传送门就必须具备一些种类的钥匙每种钥匙都要有才能通过。幸运的是钥匙在打开传送门的封印后并不会消失。 然而通过密室的传送门需要耗费大量的时间因此小 X 希望通过尽可能少的传送门到达出口你能告诉小 X 这个数值吗 另外小 X 有可能不能逃出这个密室如果是这样请输出 No Solution。 输入格式 第一行三个整数 N,M,K分别表示房间的数量、传送门的数量以及钥匙的种类数。 接下来 N 行每行 K 个 0 或 1若第 iii 个数为 1则表示该房间内有第 iii 种钥匙若第 iii 个数为 0则表示该房间内没有第 iii 种钥匙。 接下来 M 行每行先读入两个整数 X,Y表示该传送门是建立在 X 号房间通向 Y 号房间的再读入 K 个 0 或 1若第 iii 个数为 1则表示通过该传送门需要 iii 种钥匙若第 iii 个数为0则表示通过该传送门不需要第 iii 种钥匙。 输出格式 输出一行一个 No Solution或一个整数表示最少通过的传送门数。 数据规模与约定 更多测试样例 输入样例 4 输出样例 4 样例输入1 3 3 2
1 0
0 1
0 0
1 3 1 1
1 2 1 0
2 3 1 1 样例输出1 2 样例输入2 20 40 0
10 18
18 14
19 13
4 14
13 10
5 18
14 1
13 13
10 16
19 11
11 15
10 18
5 8
12 19
7 8
18 6
14 5
9 5
2 17
13 14
18 15
8 18
7 1
13 5
4 6
17 4
1 4
10 10
13 8
19 2
4 9
3 3
5 10
17 5
12 8
19 11
3 16
17 10
18 16
13 13 样例输出2 No Solution 样例输入3 20 50 0
8 10
7 17
5 11
14 20
20 16
8 19
12 11
18 7
17 5
4 15
16 11
11 8
10 12
8 9
16 8
3 16
1 6
3 20
6 10
11 12
6 8
18 17
14 17
3 11
4 19
9 2
8 6
13 2
5 2
12 19
8 10
14 7
6 12
6 4
13 2
8 7
13 19
17 9
3 14
18 20
2 14
4 17
20 15
14 15
2 15
7 20
12 12
18 10
15 9
15 9 样例输出3 4 T3:小X的佛光 小 X 是远近闻名的学佛平日里最喜欢做的事就是蒸发学水。 小 X 所在的城市 X 城是一个含有 N 个节点的无向图同时由于 X 国是一个发展中国家为了节约城市建设的经费X 国首相在建造 X 城时只建造 N – 1 条边使得城市的各个地点能够相互到达。 小 X 计划蒸发 Q 天的学水每一天会有一名学水从 A 地走到 B 地并在沿途各个地点留下一个水塘。此后小 X 会从 C 地走到 B 地并用佛光蒸发沿途的水塘。由于 X 城是一个学佛横行的城市学水留下的水塘即使没有被小 X 蒸发也会在第二天之前被其他学佛蒸发殆尽。 现在小 X 想要知道他每一天能够蒸发多少水塘呢? 输入格式 第一行三个整数 N,Q,num分别表示 X 城地点的个数小 X 蒸发学水的天数以及测试点编号。注意测试点编号是为了让选手们更方便的获得部分分你可能不需要用到这则信息在下发的样例中测试点编号的含义是该样例满足某一测试点限制。 接下来 N – 1 行每行两个整数 X,Y表示 X 地与 Y 地之间有一条边。 接下来 Q 行每行三个整数 A,B,C表示一天中有一名学水从 A 地走到 B 地而小 X 会从 C 地走到 B 地。 输出格式 输出 Q 行每行一个整数表示小 X 能够蒸发的水塘数。 数据规模与约定 特殊性质 1第 i 条边连接第 i 和第 i1个地点。 特殊性质 2AC。 更多测试样例 样例输入 2 样例输出 2 样例输入 3 样例输出 3 样例输入 4 样例输出 4 样例输入 3 3 1
1 2
2 3
1 2 3
1 1 3
3 1 3 样例输出 1
1
3 T1:将线性筛数变形即可可见线性筛数既可以筛质数也可以顺便判断质数的一些情况 1 #includecstdio2 #includecstdlib3 #includealgorithm4 #includecstring5 #define MAXN 100000016 using namespace std;7 int prime[MAXN],cnt;8 bool b[MAXN];9 bool c[MAXN];
10 int f[MAXN];
11 int main()
12 {
13 // freopen(data.in,r,stdin);
14 b[1]1;
15 for(int i2;iMAXN;i){
16 if(!b[i]){
17 prime[cnt]i;
18 }
19 for(int j1;jcnti*prime[j]MAXN;j){
20 b[i*prime[j]]1;
21 c[i*prime[j]](!b[i]);
22 if(i%prime[j]0){
23 break;
24 }
25 }
26 }
27 for(int i1;iMAXN;i){
28 f[i]f[i-1];
29 if(!b[i]||c[i]){
30 f[i];
31 }
32 }
33 int Q;
34 scanf(%d,Q);
35 for(int i1;iQ;i){
36 int L,R;
37 scanf(%d%d,L,R);
38 printf(%d\n,f[R]-f[L-1]);
39 }
40 return 0;
41 } Code1 T2: 由于每条边的边权都是1宽搜即可 钥匙用二进制存贮然后可以预处理下子集即可高效判断 1 #includecstdio2 #includecstdlib3 #includealgorithm4 #includecstring5 #includevector6 #define MAXN 50057 #define MAXM 60058 #define INF 0x7f7f7f7f9 using namespace std;
10 int qL[11000005],qK[11000005],L1,R;
11 int d[MAXN][2050];
12 int n,m,k;
13 int key_room[MAXN];
14 int first[MAXN],Next[MAXM],to[MAXM],w[MAXM],cnt;
15 //single edge
16 int bel[2050][2050];
17 void Add(int x,int y,int key){
18 Next[cnt]first[x];first[x]cnt;to[cnt]y;w[cnt]key;
19 }
20 void bfs(){
21 memset(d,0x7f,sizeof(d));
22 qL[R]1;
23 qK[R]key_room[1];
24 d[qL[R]][qK[R]]0;
25 while(LR){
26 int pqL[L],keyqK[L];L;
27 int Dd[p][key];
28 for(int ifirst[p];i;iNext[i]){
29 int jto[i];
30 if(!bel[key][w[i]]) continue;
31 int dk(key|key_room[j]);
32 if(d[j][dk]D1){
33 d[j][dk]D1;
34 qL[R]j;
35 qK[R]dk;
36 if(nj){
37 printf(%d\n,d[j][dk]);
38 return ;
39 }
40 }
41 }
42 }
43 printf(No Solution\n);
44 }
45 int main()
46 {
47 // freopen(data.in,r,stdin);
48 scanf(%d%d%d,n,m,k);
49 for(int i1;in;i){
50 for(int j0;jk;j){
51 int c;
52 scanf(%d,c);
53 key_room[i](cj);
54 }
55 }
56 for(int i1;im;i){
57 int x0,y0,need0;
58 scanf(%d%d,x,y);
59 for(int j0;jk;j){
60 int c;
61 scanf(%d,c);
62 need(cj);
63 }
64 Add(x,y,need);
65 }
66 bel[0][0]1;
67 for(int i1;i(1k);i){
68 for(int ji;;jij){
69 bel[i][j]1;
70 j--;
71 if(j0){
72 break;
73 }
74 }
75 }
76 bfs();
77 return 0;
78 } Code2 T3 裸LCA 注意下分类讨论 1 #includecstdio2 #includecstdlib3 #includealgorithm4 #includecstring5 #define MAXN 2000056 #define LOG 217 using namespace std;8 int n,num;9 int first[MAXN],Next[MAXN*2],to[MAXN*2],cnt;
10 int dep[MAXN];
11 int fa[LOG][MAXN];
12 //double edge
13 void Add(int x,int y){
14 Next[cnt]first[x];first[x]cnt;to[cnt]y;
15 Next[cnt]first[y];first[y]cnt;to[cnt]x;
16 }
17 void dfs(int x){
18 for(int efirst[x];e;eNext[e]){
19 int yto[e];
20 if(yfa[0][x]){
21 continue;
22 }
23 fa[0][y]x;
24 dep[y]dep[x]1;
25 dfs(y);
26 }
27 }
28 int lca(int x,int y){
29 if(dep[x]dep[y]){
30 swap(x,y);
31 }
32 for(int idep[x]-dep[y],p0;i;i1,p){
33 if(i1){
34 xfa[p][x];
35 }
36 }
37 if(xy){
38 return x;
39 }
40 for(int kLOG-1;k0;k--){
41 if(fa[k][x]!fa[k][y]){
42 xfa[k][x];
43 yfa[k][y];
44 }
45 }
46 return fa[0][x];
47 }
48 int dist(int x,int y){
49 int LCAlca(x,y);
50 return dep[x]-dep[LCA]dep[y]-dep[LCA];
51 }
52 int main()
53 {
54 int T;
55 scanf(%d%d%d,n,T,num);
56 for(int i1;in;i){
57 int x,y;
58 scanf(%d%d,x,y);
59 Add(x,y);
60 }
61 dfs(1);
62 for(int k1;kLOG;k){
63 for(int i1;in;i){
64 fa[k][i]fa[k-1][fa[k-1][i]];
65 }
66 }
67 for(int i1;iT;i){
68 int A,B,C;
69 scanf(%d%d%d,A,B,C);
70 printf(%d\n,(dist(B,A)dist(B,C)-dist(A,C))/21);
71 }
72 return 0;
73 } Code3 转载于:https://www.cnblogs.com/w-h-h/p/7623588.html
