A
#include <bits/stdc++.h>
using namespace std;
int a, b , n, c;
int main()
{
cin >> a >> b >> n;
for (int i = 1; i <= n; ++i)
{
cin >> c; cout << c << ' ';
int res = 0;
if (c <= 1000) res = c * a;
else res = 1000 * a + (c - 1000) * b;
cout << res << '
';
}
return 0;
}
B
#include <bits/stdc++.h>
#define P pair<int, int>
using namespace std;
P p[26];
int n;
char a[25], b[25];
int is(int a, int b)
{
int x = abs(p[a].first - p[b].first),
y = abs(p[a].second - p[b].second);
if (x + y == 0) return 1;
if (x <= 1 && y <= 1) return 2;
return 3;
}
int main ()
{
for (int i = 0; i <= 8; ++i) p[i] = {0, i};
for (int i = 9; i <= 17; ++i) p[i] = {1, i - 9};
for (int i = 18; i <= 25; ++i) p[i] = {2, i - 18};
cin >> n;
while (n--)
{
int ans = 0; cin >> a + 1 >> b + 1;
for (int i = 1; a[i] || b[i]; ++i)
{
if ((!a[i] && b[i]) || (!b[i] && a[i])) ans = 3;
if (ans == 3) break;
ans = max(ans, is(a[i] - 'a', b[i] - 'a'));
}
cout << ans << '
';
}
return 0;
}
C
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int t, n, k;
int main()
{
cin >> t;
while (t--)
{
ll ans = 0, c, d;
cin >> n >> k >> c;
while (--k)
{
cin >> d;
ans += min((c + n - d + 1) % n, (d - c - 1 + n) % n);
c = d;
}
cout << ans << '
';
}
return 0;
}
D(广搜)
#include <bits/stdc++.h>
#define P pair<int, int>
#define PP pair<int, P>
#define inf 1e9
using namespace std;
int t, n, a[121], mp[121][81];
priority_queue<PP, vector<PP>, greater<PP> > q;
void updown(int x, int y, int aa, int cur, int c)
{
if (x < 1 || x > n) return;
y = min(y, a[x]);
if (mp[x][y] > cur + 1)
{
mp[x][y] = cur + 1;
q.push({ mp[x][y], {x, y} });
}
y = a[x] * aa;
if (mp[x][y] > c + cur + 1)
{
mp[x][y] = c + cur + 1;
q.push({ mp[x][y], {x, y} });
}
}
int main()
{
cin >> t;
while (t--)
{
cin >> n; memset(mp, 0x7f7f, sizeof mp);
priority_queue<PP, vector<PP>, greater<PP> >().swap(q);
for (int i = 1; i <= n; ++i) cin >> a[i];
int x, y, lx, ly, ans = inf;
cin >> x >> y >> lx >> ly;
q.push({ 0, {x, y} }); mp[x][y] = 0;
while (!q.empty())
{
int cur = q.top().first;
if (cur >= ans) break;
P p = q.top().second; q.pop();
if (p.first == lx) ans = min(ans, abs(ly - p.second) + cur);
updown(p.first - 1, p.second, 1, cur, p.second);
updown(p.first + 1, p.second, 0, cur, a[p.first] - p.second);
}
cout << ans << '
';
}
return 0;
}
E(就是对三角函数的应用)
#include <bits/stdc++.h>
#define PI 3.141592653589793
using namespace std;
int t, w, a, b, c, n;
int calc(double x, double y)
{
double r = x * x + y * y;
if (r < a * a) return 1;
if (r < b * b) return 2;
if (r < c * c) return 3;
return 4;
}
int main()
{
cin >> t;
while (t--)
{
cin >> w >> a >> b >> c >> n;
double g = 2 * PI / w;
int ans = 0;
while (n--)
{
double x, y; cin >> x >> y;
double angle = atan(abs(y/x));
if (x < 0 && y > 0) angle = PI - angle;
else if (x < 0 && y < 0) angle += PI;
else if (x > 0 && y < 0) angle = PI * 2 - angle;
int ww = ceil(angle / g), r = calc(x, y);
if (r == 1) {ans += 50; continue;}
else if (r == 2) ans += 2 * ww;
else if (r == 3) ans += ww;
}
cout << ans << '
';
}
return 0;
}
F(图论是真的菜)
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define P pair<int, int>
using namespace std;
const int maxn = 1605, maxm = 90005;
int t, n, m, v[maxn];
int h[maxn], to[maxm], nxt[maxm], co[maxm], tot;
char nam[25], a[25], b[25];
char fu[4][10] = { "AIR", "SEA", "RAIL", "TRUCK" };
int d[maxn];
void add(int u, int v, int cost)
{
nxt[++tot] = h[u], h[u] = tot, co[tot] = cost, to[tot] = v;
}
inline ull getid(char s[])
{
ull res = 0; int p = 131;
for (int i = 1; s[i]; ++i) res = res * p + s[i];
return res;
}
priority_queue<P, vector<P>, greater<P>> ji;
void work(int s)
{
d[s] = d[s + 1] = d[s + 2] = d[s + 3] = 0;
ji.push({ 0, s }), ji.push({ 0, s + 1 });
ji.push({ 0, s + 2 }), ji.push({ 0, s + 3 });
while (!ji.empty())
{
int x = ji.top().second; ji.pop();
if (v[x]) continue; v[x] = 1;
for (int i = h[x]; i; i = nxt[i])
{
int y = to[i], z = co[i];
if (d[y] > d[x] + z)
{
d[y] = d[x] + z;
ji.push({ d[y], y });
}
}
}
}
int main()
{
scanf("%d", &t);
while (t--)
{
map<ull, int> mp; int cnt = 0;
scanf("%d", &n);
priority_queue<P, vector<P>, greater<P>>().swap(ji);
memset(h, 0, sizeof h); tot = 0;
for (int i = 1, ab; i <= n; ++i)
{
int id = 1 + (i - 1) * 4;
scanf("%s%d", nam + 1, &ab);
mp[getid(nam)] = id;
v[id] = v[id + 1] = v[id + 2] = v[id + 3] = 0;
d[id] = d[id + 1] = d[id + 2] = d[id + 3] = 1e9;
for (int x = 0; x < 4; ++x)
for (int y = 0; y < 4; ++y)
if (x != y) add(id + x, id + y, ab);
}
scanf("%d", &m);
for (int i = 1, co; i <= m; ++i)
{
scanf("%s%s%s%d", a + 1, b + 1, nam, &co);
int a1 = mp[getid(a)], b1 = mp[getid(b)], id = 0;
for (int j = 0; j < 4; ++j)
if (strcmp(nam, fu[j]) == 0) { id = j; break; }
add(a1 + id, b1 + id, co), add(b1 + id, a1 + id, co);
}
scanf("%s%s", a + 1, b + 1);
int v = mp[getid(b)];
work(mp[getid(a)]);
int ans = 1e9;
for (int i = 0; i < 4; ++i) ans = min(ans, d[v + i]);
printf("%d
", ans);
}
return 0;
}
G（模拟）
#include <bits/stdc++.h>
using namespace std;
const int maxn = 51;
int n, t, c[maxn], m, p[2505];
double a[maxn], d[2505];
int main()
{
cin >> t;
while (t--)
{
cin >> n;
for (int i = 1, j; i <= n; ++i)
{
cin >> j >> a[i];
c[i] = c[i - 1] + j;
for (int j = c[i - 1] + 1; j <= c[i]; ++j) p[j] = i;
}
cin >> m;
memset(d, 0, sizeof d); d[0] = 1;
if (m < c[n]) {printf("%.3lf
", 0.000); continue;}
for (int i = 1; i <= m; ++i)
{
for (int j = min(c[n], i); j; --j)
{
if (j < c[n]) d[j] *= (1 - a[p[j + 1]]);
d[j] += d[j - 1] * a[p[j]];
}
d[0] *= (1 - a[1]);
}
printf("%.3lf
", d[c[n]]);
}
return 0;
}
H（dp）见代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 101, inf = 1e7;
int t, n, f[maxn][maxn][maxn];
int a[maxn], d[maxn][maxn];
int calc(int l, int r)
{
int d[maxn] = {-inf}, mx = 0;
for (int i = l; i <= r; ++i)
{
if (d[mx] < a[i]) d[++mx] = a[i];
for (int j = mx; j; --j)
if (d[j] > a[i] && a[i] > d[j - 1]) d[j] = a[i];
}
return mx;
}
int main()
{
cin >> t;
while (t--)
{
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
d[i][j] = calc(i, j); //计算【i，j】最长上升子序列
f[1][1][n] = n;
for (int k = 2; k <= n; ++k)
for (int len = 2; len <= n; ++len)
for (int i = 1; i + len - 1 <= n; ++i)
{
int j = i + len - 1;
f[k][i][j] = d[i][j] >= k? d[i][j] : 0;
for (int mid = i; mid < j; ++mid)
f[k][i][j] = max(f[k][i][j], f[k][i][mid] + f[k][mid + 1][j]);
}
cout << f[1][1][n];
for (int i = 2; i <= n; ++i) cout << ' ' << f[i][1][n];
puts("");
}
return 0;
}
I(树状数组)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
int t, n, a[maxn], p[maxn];
ll c[maxn];
void add(int x, int y)
{
for (; x <= n; x += -x & x) c[x] += y;
}
ll ask(int x)
{
ll ans = 0;
for (; x; x -= x & -x) ans += c[x];
return ans;
}
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) cin >> a[i], p[a[i]] = i, add(i, a[i]);
int cur = a[1];
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
ll x = ask(p[i] - 1) - ask(p[cur] - 1);
ll y = ask(p[cur] - 1) - ask(p[i] - 1);
if (p[i] < p[cur]) x += ask(n);
if (p[i] > p[cur]) y += ask(n);
add(p[i], -i); cur = i;
ans += min(x, y);
}
printf("%lld
", ans);
}
return 0;
}