1003
题意：d(i)为i的因子的个数，求区间[l, r] 所有d(i) l<=i <=r 的和
因子个数求法：传送门
思路：这样直接去求还是会TLE，所以我们用类似素数筛法进行区间筛来减少计算次数
每次在区间内找到第一个能整除素数p的，假设这个数是x，那么x + p 也是可以整除p的。就是普通的线性筛类似
#include <cstdio> #include <cstring> #include <cmath> #include <sstream> #include <iostream> #include <algorithm> #include <string> #include <stack> #include <queue> #include <vector> #include <map> #include <set> #include <utility> using namespace std; #define LL long long #define pb push_back #define mk make_pair #define pill pair<int, int> #define ft first #define sd second #define mst(a, b) memset(a, b, sizeof a) #define REP(i, x, n) for(int i = x; i <= n; ++i) const int qq = 5e6 + 10; const LL MOD = 998244353; LL prime[qq], tot = 0; bool ispirme[qq]; LL l, r, k; LL num[qq], ans[qq]; void Init() { for(int i = 2; i < qq; ++i) { if(!ispirme[i]) { prime[++tot] = i; } for(int j = 1; j <= tot && (LL)i * prime[j] < qq; ++j) { ispirme[(LL)i * prime[j]] = true; if(i % prime[j] == 0) break; } } // printf("QQQ\n"); } int main(){ Init(); int t; scanf("%d", &t); while(t--) { scanf("%lld%lld%lld", &l, &r, &k); for(LL i = l; i <= r; ++i) { num[i - l] = i; ans[i - l] = 1; } // printf("QQQ\n"); for(LL i = 1; i <= tot; ++i) { LL j = (l + prime[i] - 1LL) / prime[i] * prime[i]; // printf("%lld\n", j); // if(r < prime[i]) break; while(j <= r) { LL p = 0; while(num[j - l] % prime[i] == 0) { p++; num[j - l] /= prime[i]; } ans[j - l] = (ans[j - l] * (p * k + 1LL)); if(ans[j - l] >= MOD) ans[j - l] %= MOD; j = j + prime[i]; // printf("%lld\n", j); } } LL sum = 0; for(LL i = l; i <= r; ++i) { if(num[i - l] != 1) sum = sum + ans[i - l] * (k + 1LL); else sum = sum + ans[i - l]; if(sum >= MOD) sum %= MOD; } printf("%lld\n", sum); } return 0; }
1007
题意：给定二分图，求出图中所有完全匹配图的边权乘积的和，保证至少有一种完全匹配
思路：参考这位聚聚的代码 传送门
e[i] = e[i ^ 1] = 1 是标记了边。之前在想标记点为什么不行后来比对了两份标记边和点的代码发现
标记点访问顺序：8 16 9 18
标记边的访问顺序：8 16 9 18 8
感觉做一下处理标记点也是可以的，不过好像比较麻烦
#include <cstdio> #include <cstring> #include <cmath> #include <sstream> #include <iostream> #include <algorithm> #include <string> #include <stack> #include <queue> #include <vector> #include <map> #include <set> #include <utility> using namespace std; #define LL long long #define pb push_back #define mk make_pair #define pill pair<int, int> #define ft first #define sd second #define mst(a, b) memset(a, b, sizeof a) #define REP(i, x, n) for(int i = x; i <= n; ++i) const int qq = 300000 + 10; const int MOD = 998244353; struct Edge { int nxt, to, w; bool mrk; }e[qq << 2]; int T, n, head[qq << 1], cnt, deg[qq << 1], used[qq << 1]; LL part[2]; void Init() { mst(head, -1); mst(deg, 0); mst(used, 0); cnt = 0; } void AddEdge(int u, int v, int w) { e[cnt].nxt = head[u]; e[cnt].to = v; e[cnt].w = w; e[cnt].mrk = 0; head[u] = cnt++; } void Dfs(int cur, int idx) { printf("%d ", cur); used[cur] = 1; for(int i = head[cur]; i != -1; i = e[i].nxt) { if(e[i].mrk) continue; e[i].mrk = e[i ^ 1].mrk = 1; (part[idx] *= e[i].w) %= MOD; Dfs(e[i].to, 1 - idx); } } int main(){ scanf("%d", &T); while(T--) { scanf("%d", &n); Init(); for(int u = 1, v, w; u <= n; ++u) { for(int j = 0; j < 2; ++j) { scanf("%d%d", &v, &w); AddEdge(u, v + n, w); AddEdge(v + n, u, w); deg[u]++, deg[v + n]++; } } LL ans = 1; queue<int> Q; for(int v = n + 1; v <= n + n; ++v) { if(deg[v] == 1) { Q.push(v); } } while(!Q.empty()) { int v = Q.front(); Q.pop(); used[v] = 1; for(int i = head[v]; i != -1; i = e[i].nxt) { if(e[i].mrk) continue; e[i].mrk = e[i ^ 1].mrk = 1; used[e[i].to] = 1; (ans *= e[i].w) %= MOD; for(int j = head[e[i].to]; j != -1; j = e[j].nxt) { e[j].mrk = e[j ^ 1].mrk = 1; deg[e[j].to]--; if(deg[e[j].to] == 1) Q.push(e[j].to); } } } printf("%lld\n", ans); for(int u = 1; u <= n; ++u) { if(used[u]) continue; part[0] = part[1] = 1; Dfs(u, 0); puts(""); printf("%lld %lld\n", part[0], part[1]); (ans *= (part[0] + part[1]) % MOD) %= MOD; } printf("%lld\n", ans); } return 0; }
1009
题意：给出n个数字，要你求m k，要求给出的n个数%m = k 的数字的个数要大于一半
思路：固定m = 2， 那么k只有两种情况0和1统计下等于1和等于0的情况，谁多k就是那个
#include <cstdio> #include <cstring> #include <cmath> #include <sstream> #include <iostream> #include <algorithm> #include <string> #include <stack> #include <queue> #include <vector> #include <map> #include <set> #include <utility> using namespace std; #define LL long long #define pb push_back #define mk make_pair #define pill pair<int, int> #define ft first #define sd second #define mst(a, b) memset(a, b, sizeof a) #define REP(i, x, n) for(int i = x; i <= n; ++i) const int qq = 1e5 + 10; const int MOD = 1e9 + 7; int num[qq]; int main(){ int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); int a, b; a = b = 0; for(int x, i = 0; i < n; ++i) { scanf("%d", &x); if(x % 2 == 0) a++; else b++; } if(a > b) puts("2 0"); else puts("2 1"); } return 0; }
1011
题意：给出图像要你判断时间是多少
思路：观察每个数字缺少那一块，标记那一块，然后做一下判断
#include <cstdio> #include <cstring> #include <cmath> #include <sstream> #include <iostream> #include <algorithm> #include <string> #include <stack> #include <queue> #include <vector> #include <map> #include <set> #include <utility> using namespace std; #define LL long long #define pb push_back #define mk make_pair #define pill pair<int, int> #define ft first #define sd second #define mst(a, b) memset(a, b, sizeof a) #define REP(i, x, n) for(int i = x; i <= n; ++i) const int qq = 1e5 + 10; const int MOD = 1e9 + 7; char st[10][105], match[10][10]; bool digit[10]; int num[10][10]; int ans[10]; void Init() { mst(num, 0); num[0][4] = 1; num[1][1] = num[1][2] = num[1][4] = num[1][5] = num[1][7] = 1; num[2][2] = num[2][6] = 1; num[3][2] = num[3][5] = 1; num[4][1] = num[4][5] = num[4][7] = 1; num[5][3] = num[5][5] = 1; num[6][3] = 1; num[7][2] = num[7][4] = num[7][5] = num[7][7] = 1; num[9][5] = 1; } void Judge(int id) { for(int i = 0; i < 10; ++i) digit[i] = false; if(match[1][2] == 'X' && match[1][3] == 'X') { digit[1] = true; } if(match[2][1] == 'X' && match[3][1] == 'X') { digit[2] = true; } if(match[2][4] == 'X' && match[3][4] == 'X') { digit[3] = true; } if(match[4][2] == 'X' && match[4][3] == 'X') { digit[4] = true; } if(match[5][1] == 'X' && match[6][1] == 'X') { digit[5] = true; } if(match[5][4] == 'X' && match[6][4] == 'X') { digit[6] = true; } if(match[7][2] == 'X' && match[7][3] == 'X') { digit[7] = true; } for(int i = 0; i < 10; ++i) { bool f = true; for(int j = 1; j <= 7; ++j) { int a = num[i][j]; int b = (digit[j] == true ? 0 : 1); if(a != b) f = false; } if(f){ ans[id] = i; break; } } } int main(){ int t; scanf("%d", &t); Init(); while(t--) { for(int i = 1; i <= 7; ++i) { scanf("%s", st[i] + 1); } int x, y; x = y = 0; for(int i = 1; i <= 7; ++i) { ++x; y = 0; for(int j = 1; j <= 4; ++j) { ++y; match[x][y] = st[i][j]; } } Judge(1); x = y = 0; for(int i = 1; i <= 7; ++i) { ++x; y = 0; for(int j = 6; j <= 9; ++j) { ++y; match[x][y] = st[i][j]; } } Judge(2); x = y = 0; for(int i = 1; i <= 7; ++i) { ++x; y = 0; for(int j = 13; j <= 17; ++j) { ++y; match[x][y] = st[i][j]; } } Judge(3); x = y = 0; for(int i = 1; i <= 7; ++i) { ++x; y = 0; for(int j = 18; j <= 21; ++j) { ++y; match[x][y] = st[i][j]; } } Judge(4); for(int i = 1; i <= 4; ++i) { printf("%d", ans[i]); if(i == 2) printf(":"); } puts(""); } return 0; }
