1.最长公共子序列 

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
#define endl '\n';
const int N = 100100;
int a[N], b[N], dp[N];
unordered_mapmymap;
int main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;cin >> n;for (int i = 0; i < n; i++){cin >> a[i];mymap[a[i]] = i;}for (int i = 0; i < n; i++){int x;cin >> x;b[i] = mymap[x];}int len = 1;dp[0] = -1e7;for (int i = 0; i < n; i++){int l = 0, r = len;while (l < r){int mid = l + r + 1 >> 1;if (dp[mid] < b[i])l = mid;else r = mid - 1;}len = max(len, r + 1);dp[r + 1] = b[i];}cout << len - 1 << endl;return 0;
}

 2.喵喵序列

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pair PII;
const int N = 300050;
unordered_mapmymap;
void revise(ll k, ll l, ll r, ll x, vector& f, ll v)
{if (l == r){f[k] += v;return;}int m = (l + r) / 2;if (x <= m)revise(k + k, l, m, x, f, v);elserevise(k + k + 1, m + 1, r, x, f, v);f[k] = (f[k + k] + f[k + k + 1]);
}
ll calc(ll k, ll l, ll r, ll x, ll y, vector& f)
{if (l == x && y == r){return f[k];}int m = (l + r) / 2;if (y <= m)return calc(k + k, l, m, x, y, f);elseif (x > m)return calc(k + k + 1, m + 1, r, x, y, f);else{return (calc(k + k, l, m, x, m, f) + calc(k + k + 1, m + 1, r, m + 1, y, f));}
}int main()
{ll n, ans = 1, res = 0;cin >> n;vectora(n + 1), b, f1(4 * n), f2(4 * n);for (int i = 1; i <= n; i++)cin >> a[i];b = a;sort(b.begin(), b.end());mymap[b[1]] = ans++;for (int i = 2; i <= n; i++){if (b[i] != b[i - 1])mymap[b[i]] = ans++;}for (int i = 1; i <= n; i++){if (mymap[a[i]] != 1)res += calc(1, 1, n, 1, mymap[a[i]] - 1, f2);if (mymap[a[i]] != 1){ll ans = calc(1, 1, n, 1, mymap[a[i]] - 1, f1);revise(1, 1, n, mymap[a[i]], f2, ans);}revise(1, 1, n, mymap[a[i]], f1, 1);}cout << res << endl;return 0;
}

3.漂亮数 

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
int main() {int n, k;cin >> n >> k;vectorx(n), y(k);string s;cin >> s;bool flag = true;for (int i = 0; i < n; i++){x[i] = s[i] - '0';if (i < k)y[i] = x[i];}flag = false;for (int i = 0; i < n; i++){for (int j = 0; j < k; j++){if (y[j] < x[i + j]){int ans = k - 1;while (y[ans] == 9)ans--;y[ans]++;for (int l = ans + 1; l < k; l++)y[l] = 0;flag = true;break;}else if (y[j] > x[i + j]){flag = true;break;}}i += k - 1;if (flag)break;}cout << n << endl;for (int i = 0; i < n; i++){cout << y[i % k];}return 0;
}

4.真假字符串 

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
#define endl '\n';
bool dfs(string s1, string s2)
{int n = s1.size(), l = 0, r = 0;bool st = true;while (l < n && r < n){if (s1[l] != s2[r]){if (st){l++;st = false;}else return false;}else l++, r++;}if (l < n)return false;return true;
}int main()
{string s1, s2;cin >> s1 >> s2;int n = s1.size(), ans = -1;for (int i = 0; i < n; i++){if (s1[i] != s2[i]){ans = i;break;}}if (ans == -1){cout << 1 << endl;}else{string str1 = s1, str2 = s2;str1.erase(ans, 1);str2.erase(ans, 1);if (dfs(s2, str1) || dfs(s1, str2)){cout << 1 << endl;}else cout << 0 << endl;}return 0;
}

5.走不出的迷宫 

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
typedef long long ll;
typedef pair PII;
char c[110][110];
PII que[10000];
int moves[110][110];int main()
{cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m, res = 1;string s;cin >> n >> m;for (int i = 0; i < n; i++){cin >> s;for (int j = 0; j < m; j++)c[i][j] = s[j];}moves[0][0] = 1;for (int i = 1; i < n; i++)if (c[i][0] == '.'){moves[i][0] = moves[i - 1][0] + 1;res = max(moves[i][0], res);}else break;for (int i = 1; i < m; i++)if (c[0][i] == '.'){moves[0][i] = moves[0][i - 1] + 1;res = max(res, moves[0][i]);}else break;for (int i = 1; i < n; i++)for (int j = 1; j < m; j++)if (c[i][j] == '.'){if (moves[i - 1][j] == 0 && moves[i][j - 1] == 0)continue;moves[i][j] = max(moves[i - 1][j], moves[i][j - 1]) + 1;res = max(res, moves[i][j]);}cout << res;return 0;
}

6.最长同余子数组 

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pairPII;
const int N = 100010;
ll a[N], f[4 * N];ll gcd(ll a, ll b)
{return b == 0 ? a : gcd(b, a % b);
}void buildtree(ll k, ll l, ll r)
{if (l == r){f[k] = a[l];return;}int m = (l + r) / 2;buildtree(k + k, l, m);buildtree(k + k + 1, m + 1, r);f[k] = gcd(f[k + k], f[k + k + 1]);
}ll calc(ll k, ll l, ll r, ll x, ll y)
{if (l == x && r == y)return f[k];int m = (l + r) / 2;if (y <= m)return calc(k + k, l, m, x, y);elseif (x > m)return calc(k + k + 1, m + 1, r, x, y);else{return gcd(calc(k + k, l, m, x, m), calc(k + k + 1, m + 1, r, m + 1, y));}
}int main()
{cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, t;cin >> n;vectorv(n + 1);for (int i = 1; i <= n; i++)cin >> v[i];for (int i = 1; i <= n; i++){a[i] = abs(v[i] - v[i - 1]);}buildtree(1, 1, n);ll l = 1, r = 1, len = 1, ans = 1;while (r <= n){ll num = calc(1, 1, n, l, r);if (num > 1)r++;else l++;while (l > r)r++;ans = l;while (num > 1 && ans <= n && ans > 1 && v[ans] % num == v[ans - 1] % num){ans--;}if (r - ans > len){len = r - ans;}}cout << len;return 0;
}

7.互质 

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pairPII;
const int N = 100500;
bool mymap[N], prime[N], st[N];
int maxp[N];
int main()
{int n, m, x;cin >> n >> m;maxp[1] = 1;for (ll i = 2; i <= N; i++){if (st[i])continue;for (ll j = i * 2; j <= N; j += i){st[j] = true;maxp[j] = i;}maxp[i] = i;}for (int i = 0; i < n; i++){int x;cin >> x;if (mymap[x])continue;mymap[x] = true;while (x != 1){prime[maxp[x]] = 1;x /= maxp[x];}}vectork;k.push_back(1);for (int i = 2; i <= m; i++){if (prime[i] && !st[i])for (int j = i; j <= m; j += i)mymap[j] = 1;}for (int i = 2; i <= m; i++)if (!mymap[i])k.push_back(i);cout << k.size() << endl;for (auto i : k){cout << i << endl;}return 0;
}

 8.排队

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pairPII;
const int N = 1e5 + 50, MOD = 1e8 - 7;
ll f[4 * N];void revise(int k, int l, int r, int x)
{if (l == r){f[k] += 1;return;}int m = (l + r) / 2;if (x <= m)revise(k + k, l, m, x);else revise(k + k + 1, m + 1, r, x);f[k] = (f[k + k] + f[k + k + 1]) % MOD;
}ll calc(int k, int l, int r, int x, int y)
{if (l == x && y == r){return f[k];}int m = (l + r) / 2;if (y <= m)return calc(k + k, l, m, x, y);elseif (x > m)return calc(k + k + 1, m + 1, r, x, y);else return (calc(k + k, l, m, x, m) + calc(k + k + 1, m + 1, r, m + 1, y)) % MOD;
}int main() {int n;cin >> n;vectora(n), b(n);for (int i = 0; i < n; i++){cin >> a[i].first;a[i].second = i;}for (int i = 0; i < n; i++){cin >> b[i].first;b[i].second = i;}sort(a.begin(), a.end());sort(b.begin(), b.end());vectorv(n);for (int i = 0; i < n; i++){v[a[i].second] = b[i].second + 1;}ll res = 0;for (int i = n - 1; i >= 0; i--){if (v[i] != 1)res = (res + calc(1, 1, n, 1, v[i] - 1)) % MOD;revise(1, 1, n, v[i]);}cout << res << endl;return 0;
}

9.最短路计数 

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
#define endl '\n';
typedef long long ll;
typedef pairPII;
const int N = 1e6 + 50, MOD = 100003;
int n, m, f[N], v[N];
bool st[N];
vectordist[N];inline int read() {int x = 0; char ch = getchar();while (ch < '0' || ch > '9') ch = getchar();while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();return x;
}
inline void write(int x) {if (x > 9) write(x / 10);putchar(x % 10 | '0');
}void bfs()
{v[1] = 1;f[1] = 0;queueque;que.push(1);st[1] = true;while (!que.empty()){int len = que.size();for (int i = 0; i < len; i++){int t = que.front();que.pop();for (int j = 0; j < dist[t].size(); j++){if (f[dist[t][j]] > f[t] + 1){v[dist[t][j]] = v[t];f[dist[t][j]] = f[t] + 1;}else if (f[dist[t][j]] == f[t] + 1){v[dist[t][j]] = (v[dist[t][j]] + v[t]) % MOD;}if (!st[dist[t][j]]){que.push(dist[t][j]);st[dist[t][j]] = true;}}}}
}int main()
{n = read(), m = read();memset(f, 127, sizeof f);for (int i = 0; i < m; i++){int x, y;x = read(), y = read();dist[x].push_back(y);dist[y].push_back(x);}bfs();for (int i = 1; i <= n; i++){write(v[i]);putchar('\n');}return 0;
}

10.最后的舞会

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;#define endl '\n';
typedef long long ll;
typedef pairPII;
const int N = 1e6 + 50, MOD = 100003;
ll n, ans = 0, mx = 0;
vector>v;
int mymap[20];inline int read() {long long x = 0; char ch = getchar();while (ch < '0' || ch > '9') ch = getchar();while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();return x;
}inline void write(int x) {if (x > 9) write(x / 10);putchar(x % 10 | '0');
}void dfs(int u, ll res, int x)
{mymap[u] = 1;for (int i = u + 1; i <= 2 * n; i++){if (mymap[i] == 0){ll ans = res ^ v[u][i];mymap[i] = 1;bool flag = true;int j = 1;for (; j < 2 * n; j++)if (mymap[j] == 0)break;if (j < 2 * n){mymap[j] = 1;flag = false;dfs(j, ans, x + 1);mymap[j] = 0;}if (flag){mx = max(mx, ans);}mymap[i] = 0;}}mymap[u] = 0;
}int main()
{n = read();int  x;int m = 2 * n;v.push_back({ 0 });for (int i = 1; i < m; i++){vectorv0(2 * n + 1);for (int j = i + 1; j <= m; j++){v0[j] = read();}v.push_back(v0);}dfs(1, 0, 0);write(mx);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！