好吧，脑残的孩子仅仅能慢慢来。
。
1002、RGCDQ
题目传送：RGCDQ
人脑残到写了个线段树。。。然后跪啦好久。
。。然后就滚去睡觉了
事实上这个题不须要用到线段树，仅仅须要维护前缀和就ok了，
由于f的值非常小。所以能够暴力筛出来。然后用一个s[i][j]数组存储，s[i][j]代表前i个f值中有多少个等于j的
线段树仅仅有要更新的时候才拿出来！
不更新的时候要先想到前缀和。
AC代码（前缀和）：
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
using namespace std;
const int maxn = 1000005;
int f[maxn];
int s[maxn][8];
void init() {
for(int i = 2; i < maxn; i ++) {
if(f[i] == 0)
for(int j = i; j < maxn; j += i) {
f[j] ++;
}
}
for(int i = 2; i < maxn; i ++) {
for(int j = 1; j < 8; j ++) {
s[i][j] += s[i-1][j];
}
s[i][f[i]] ++;
}
}
int main() {
init();
int T;
scanf("%d", &T);
while(T --) {
int L, R;
scanf("%d %d", &L, &R);
int t1 = s[R][1] - s[L-1][1];
int t2 = s[R][2] - s[L-1][2];
int t3 = s[R][3] - s[L-1][3];
int t4 = s[R][4] - s[L-1][4];
int t5 = s[R][5] - s[L-1][5];
int t6 = s[R][6] - s[L-1][6];
int t7 = s[R][7] - s[L-1][7];
if(t7 >= 2) {
printf("7
");
continue;
}
if(t6 >= 2) {
printf("6
");
continue;
}
if(t5 >= 2) {
printf("5
");
continue;
}
if(t4 >= 2) {
printf("4
");
continue;
}
if(t3 >= 2 || (t3 >= 1 && t6 >= 1)) {
printf("3
");
continue;
}
if(t2 >= 2 || (t2 >= 1 && t4 >= 1) || (t2 >= 1 && t6 >= 1) || (t4 >= 1 && t6 >= 1)) {
printf("2
");
continue;
}
printf("1
");
}
return 0;
}AC代码（线段树）：
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#define LL long long
#define INF 0x7fffffff
#define max(a, b) a > b ? a : b
using namespace std;
const int maxn = 1000005;
int biao[maxn];
void init() {
for(int i = 2; i < maxn; i ++) {
if(biao[i] == 0)
for(int j = i; j < maxn; j += i) {
biao[j] ++;
}
}
}
int x2[maxn << 2];
int x3[maxn << 2];
int x4[maxn << 2];
int x5[maxn << 2];
int x6[maxn << 2];
int x7[maxn << 2];
void build(int l, int r, int rt) {
if(l == r) {
switch(biao[l]) {
case 2: x2[rt] = 1; break;
case 3: x3[rt] = 1; break;
case 4: x4[rt] = 1; break;
case 5: x5[rt] = 1; break;
case 6: x6[rt] = 1; break;
case 7: x7[rt] = 1; break;
}
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
x2[rt] = x2[rt << 1] + x2[rt << 1 | 1];
x3[rt] = x3[rt << 1] + x3[rt << 1 | 1];
x4[rt] = x4[rt << 1] + x4[rt << 1 | 1];
x5[rt] = x5[rt << 1] + x5[rt << 1 | 1];
x6[rt] = x6[rt << 1] + x6[rt << 1 | 1];
x7[rt] = x7[rt << 1] + x7[rt << 1 | 1];
}
int query2(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return x2[rt];
}
int ret = 0;
int mid = (l + r) >> 1;
if(L <= mid) ret += query2(L, R, l, mid, rt << 1);
if(R >= mid + 1) ret += query2(L, R, mid + 1, r, rt << 1 | 1);
return ret;
}
int query3(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return x3[rt];
}
int ret = 0;
int mid = (l + r) >> 1;
if(L <= mid) ret += query3(L, R, l, mid, rt << 1);
if(R >= mid + 1) ret += query3(L, R, mid + 1, r, rt << 1 | 1);
return ret;
}
int query4(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return x4[rt];
}
int ret = 0;
int mid = (l + r) >> 1;
if(L <= mid) ret += query4(L, R, l, mid, rt << 1);
if(R >= mid + 1) ret += query4(L, R, mid + 1, r, rt << 1 | 1);
return ret;
}
int query5(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return x5[rt];
}
int ret = 0;
int mid = (l + r) >> 1;
if(L <= mid) ret += query5(L, R, l, mid, rt << 1);
if(R >= mid + 1) ret += query5(L, R, mid + 1, r, rt << 1 | 1);
return ret;
}
int query6(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return x6[rt];
}
int ret = 0;
int mid = (l + r) >> 1;
if(L <= mid) ret += query6(L, R, l, mid, rt << 1);
if(R >= mid + 1) ret += query6(L, R, mid + 1, r, rt << 1 | 1);
return ret;
}
int query7(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return x7[rt];
}
int ret = 0;
int mid = (l + r) >> 1;
if(L <= mid) ret += query7(L, R, l, mid, rt << 1);
if(R >= mid + 1) ret += query7(L, R, mid + 1, r, rt << 1 | 1);
return ret;
}
int main() {
init();
build(1, maxn, 1);
int T;
scanf("%d", &T);
while(T --) {
int L, R;
scanf("%d %d", &L, &R);
int t7 = query7(L, R, 1, maxn, 1);
if(t7 >= 2) {
printf("7
");
continue;
}
int t6 = query6(L, R, 1, maxn, 1);
if(t6 >= 2) {
printf("6
");
continue;
}
int t5 = query5(L, R, 1, maxn, 1);
if(t5 >= 2) {
printf("5
");
continue;
}
int t4 = query4(L, R, 1, maxn, 1);
if(t4 >= 2) {
printf("4
");
continue;
}
int t3 = query3(L, R, 1, maxn, 1);
if(t3 >= 2 || (t3 >= 1 && t6 >= 1)) {
printf("3
");
continue;
}
int t2 = query2(L, R, 1, maxn, 1);
if(t2 >= 2 || (t2 >= 1 && t4 >= 1) || (t2 >= 1 && t6 >= 1) || (t4 >= 1 && t6 >= 1)) {
printf("2
");
continue;
}
printf("1
");
}
return 0;
}1011、Work
题目传送：Work
简单题。仅仅需建立起有向图。然后遍历就可以，遍历的时候累加一下
AC代码：
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
using namespace std;
const int maxn = 105;
vector<int> mp[105];
int ans[105];
void dfs(int x) {
int m = mp[x].size();
for(int i = 0; i < m; i ++) {
ans[mp[x][i]] ++;
dfs(mp[x][i]);
}
}
int main() {
int n, k;
while(scanf("%d %d", &n, &k) != EOF) {
for(int i = 1; i < n; i ++) {
int u, v;
scanf("%d %d", &u, &v);
mp[v].push_back(u);
}
memset(ans, 0, sizeof(ans));
for(int i = 1; i <= n; i ++) {
dfs(i);
}
int cnt = 0;
for(int i = 1; i <= n; i ++) {
if(ans[i] == k) cnt ++;
}
printf("%d
", cnt);
for(int i = 0; i <= n; i ++) {
mp[i].clear();
}
}
return 0;
}