集合
直接埃氏筛，边筛边合并就行。注意先 ans = b - a + 1 然后再计算。 分别是 j 和 j - i 这两个数来进行计算。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;bool st[100005];
int f[100005];int find(int x)
{if (x != f[x]) f[x] = find(f[x]);return f[x];
}int main()
{int a, b, p; scanf("%d%d%d", &a, &b, &p);int ans = b - a + 1;for (int i = a; i <= b; i ++) f[i] = i;for (int i = 2; i <= b; i ++){if (!st[i]){if (i >= p)for (int j = i + i; j <= b; j += i) // j 和 j - i 是两个数，他们两个都有 i 这个质数。{st[j] = true;if (j - i >= a && find(j) != find(j - i)){int fa = find(j), fb = find(j-i);f[fa] = fb;ans --;}}else for (int j = i + i; j <= b; j += i)st[j] = true;}}printf("%d", ans);return 0;
}迷宫寻路
这个是一道非常典型的 dfs 问题。
走过的记得更新为 # 即可。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;
constexpr int N = 110;
char g[N][N];int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
int n, m;
int ans;
int cnt;
void dfs(int x, int y)
{if (x == n && y == m){ans = 1;return;}g[x][y] = '#';// // cnt++;// if (cnt > 1e5)// {// ans = 1e9;// return;// }for (int i = 0; i < 4; i++){int ux = x + dx[i], uy = y + dy[i];if (ux > n || ux < 1 || uy > m || uy < 1 || g[ux][uy] == '#')continue;dfs(ux, uy);}
}void solve()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++){char ch;cin >> ch;g[i][j] = ch;}dfs(1, 1);if (ans == 1){printf("Yes");}elseprintf("No");
}signed main()
{int _ = 1;// cin >> t;while (_--){solve();}return 0;
}
P1464 Function
这个题目用到了记忆化搜索的方法。如果我已经计算过 w(a, b, c) 了，那我就把他存下来，这样以后就不需要再进行重复计算了。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;int dp[25][25][25];i64 w(i64 a, i64 b, i64 c)
{if (a <= 0 || b <= 0 || c <= 0) return 1;if (a > 20 || b > 20 || c > 20) {if (dp[20][20][20]) return dp[20][20][20];dp[20][20][20] = w(20, 20, 20); return dp[20][20][20];}if (a < b && b < c){if (dp[a][b][c]) return dp[a][b][c];if (!dp[a][b][c - 1]) dp[a][b][c - 1] = w(a, b, c - 1);if (!dp[a][b - 1][c - 1]) dp[a][b - 1][c - 1] = w(a, b - 1, c - 1);if (!dp[a][b - 1][c]) dp[a][b - 1][c] = w(a, b - 1, c);dp[a][b][c] = dp[a][b][c - 1] + dp[a][b - 1][c - 1] - dp[a][b - 1][c];return dp[a][b][c];}if (!dp[a-1][b][c]) dp[a-1][b][c] = w(a - 1, b, c);if (!dp[a-1][b-1][c]) dp[a-1][b-1][c] = w(a-1, b-1, c);if (!dp[a-1][b][c-1]) dp[a-1][b][c-1] = w(a-1, b, c-1);if (!dp[a-1][b-1][c-1]) dp[a-1][b-1][c-1]=w(a - 1, b - 1, c - 1);return dp[a-1][b][c] + dp[a-1][b-1][c] + dp[a-1][b][c-1] - dp[a-1][b-1][c-1];
}int main()
{i64 a, b, c; while (cin >> a >> b >> c){if (a == -1 && b == -1 && c == -1){return 0;}printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));}return 0;
}P1009 [NOIP 1998 普及组] 阶乘之和
这个题目用到了一个东西叫做大数，也叫高精度。可以用 c++ 代码实现，也可以用 python 来实现。python 来实现比较简单一点。
n = int(input())
x = 1
ans = 0
for i in range(1, n + 1):x *= ians += x
print(ans)
P1496 火烧赤壁
这个题目用到了离散化和差分。
#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
typedef pair<int, int> PII;vector<int> id;int get(int x)
{return lower_bound(id.begin(), id.end(), x) - id.begin() + 1;
}/*
把数映射到另一个东西里面
*/void solve()
{int n;scanf("%d", &n);int mmax = -1, mmin = 2e9;map<i64, i64> c;vector<PII> cor;for (int i = 0; i < n; i++){int l, r;scanf("%d%d", &l, &r);id.push_back(l);id.push_back(r);cor.push_back({l, r});}sort(id.begin(), id.end());id.erase(unique(id.begin(), id.end()), id.end());for (auto [x, y] : cor){int xx = get(x), yy = get(y);c[xx] += 1, c[yy] -= 1;mmin = min(mmin, xx);mmax = max(mmax, yy);}for (int i = mmin; i < mmax; i++){c[i] += c[i - 1];// cout<<c[i]<<' ';}// printf("mmin = %d mmax = %d", mmin, mmax);int ans = 0,l=0,r=0;while(r<mmax){while(l<mmax && c[l]==0)l++,r++;while(r<mmax && c[r]!=0)r++;int ln=id[l-1],rn=id[r-1];ans+=(rn-ln);// printf("l = %d r = %d\n", l, r);l = r;}cout << ans<<'\n';
}signed main()
{int t = 1;// cin >> t;while (t--){solve();}return 0;
}
P1469 找筷子
这个题目用到了异或的一个性质，对一个数同时异或两次的话这个数就相当于没有异或。所以直接默认一开始为 0 ，然后一直异或就行了。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long i64;void solve()
{int n; scanf("%d", &n);int x = 0;for (int i = 0; i < n; i++){int u; scanf("%d", &u);x ^= u;}cout << x;
}signed main()
{int t = 1;// cin >> t;while (t--){solve();}return 0;
}
P2626 斐波那契数列（升级版）
这个题目的关键在于分解质因数。求斐波那契数列的话，直接递推即可。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;
constexpr int N = 50 + 10;
i64 f[N];
const int M = 2147483648;void init()
{f[1] = 1;f[2] = 1;for (int i = 3; i <= 48; i++)f[i] = f[i - 1] + f[i - 2];for (int i = 1; i <= 48; i++){f[i] %= M;}
}void solve()
{init();// for (int i = 1; i <= 48; i ++)// {// cout << f[i] << "\n";// }int n;cin >> n;i64 x = f[n];map<int, int> mp;int mmin = 2e9;for (int i = 2; i * i <= x; i++){if (x % i == 0){mmin = min(mmin, i);while (x % i == 0){mp[i]++;x /= i;}}}if (x > 1){mmin = min(mmin, int(x));mp[x]++;}printf("%lld=", f[n]);for (auto m : mp){if (m.first == mmin){printf("%d", m.first);for (int i = 2; i <= m.second; i++)printf("*%d", m.first);}elsefor (int i = 1; i <= m.second; i++)printf("*%d", m.first);}
}signed main()
{int _ = 1;// cin >> t;while (_--){solve();}return 0;
}
P3879 [TJOI2010] 阅读理解
这个题目用到了 map<string, vector> 这个 stl 容器。会用这个容器的话然后进行一下去重就能做出来了。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;int main()
{int n; scanf("%d", &n);map<string, vector<int>> mp;for (int i = 1; i <= n; i ++){int x; scanf("%d", &x);for (int j = 1; j <= x; j ++){string u; cin >> u;mp[u].push_back(i);}}int m; scanf("%d", &m);while (m --){string s; cin >> s;sort(mp[s].begin(), mp[s].end());mp[s].erase(unique(mp[s].begin(), mp[s].end()), mp[s].end());for (int i = 0; i < mp[s].size(); i ++){printf("%d ", mp[s][i]);}printf("\n");}return 0;
}P1024 [NOIP 2001 提高组] 一元三次方程求解
这个题目直接暴力就行了，不过是浮点数暴力，每次加上 0.01 然后判断这个答案行不行。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;double a, b, c, d;double ck(double x)
{double l = x - 0.001, r = x + 0.001;if ((a * pow(r, 3) + b * pow(r, 2) + r*c + d < 0) && (a * pow(l, 3) + b * pow(l, 2) + c * l + d > 0) ||(a * pow(r, 3) + b * pow(r, 2) + r*c + d > 0) && (a * pow(l, 3) + b * pow(l, 2) + c * l + d < 0))return true;return false;
}void solve()
{cin >> a >> b >> c >> d;for (double i = -100.0; i <= 100.0; i += 0.01){if (ck(i))printf("%.2lf ", i);}
}signed main()
{int _ = 1;// cin >> t;while (_--){solve();}return 0;
}