CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Rotation
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, n, m, ti, L;
ll ans;
char ch[10];
int main()
{
scanf("%d", &T);
for (int t = 1; t <= T; t++)
{
scanf("%d%d%d", &n, &m, &ti);
vector<vector<ll>> v(n + 9, vector<ll>(m + 9));
for (int i = 1, nowx = 1, nowy = 1; i <= ti; ++i)
{
scanf("%s%d", ch, &L);
if (ch[0] == 'R')
{
++v[nowx][nowy];
--v[nowx][nowy += L];
}
if (ch[0] == 'L')
{
++v[nowx][nowy];
--v[nowx][nowy -= L];
}
if (ch[0] == 'D')
nowx += L;
if (ch[0] == 'U')
nowx -= L;
}
ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];
ans += v[i][j] * v[i][j];
}
printf("Case #%d: %lld\n", t, ans);
}
}
Room Assignment
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mod
{
const ll M, SM;
Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
ll qadd(ll &a, ll b) const { return a += b, a >= M ? a -= M : a; } //假如a+b<2*M，就不必取模了，取模运算耗时很高
ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); } //考虑a和b不在同余系内甚至为负数的情况
ll mul(ll a, ll b) const { return add(a * b, M); }
ll inv(ll a) const { return pow(a, M - 2); } //要求M为素数，否则return pow(a, phi(M) - 1);
ll pow(ll a, ll b) const
{
ll r = 1;
/*
if (b < 0)
b = -b, a = inv(a);
*/
for (a = add(a, M); b; b >>= 1, a = mul(a, a))
if (b & 1)
r = mul(r, a);
return r;
}
/*
ll mul(ll a, ll b) const { return add(a * b, -M * ll((long double)a / M * b)); } //long double 有效位数16~18位，模数过大时慎用！
ll mul(ll a, ll b) const //Head算法，无循环快速计算同余乘法，根据a*b是否爆ll替换a*b%M，需要a<M且b<M，可以调用时手动取模
{
ll c = a / SM, d = b / SM;
a %= SM, b %= SM;
ll e = add(add(a * d, b * c), c * d / SM * (SM * SM - M));
return add(add(a * b, e % SM * SM), add(c * d % SM, e / SM) * (SM * SM - M));
}
ll mul(ll a, ll b) const //龟速乘
{
ll r = 0;
for (a %= M; b; b >>= 1, qadd(a, a))
if (b & 1)
qadd(r, a);
return r;
}
ll inv(ll a) const //模m下a的乘法逆元，不存在返回-1（m为素数时a不为0必有逆元）
{
ll x, y, d = gcd(a, M, x, y);
return d == 1 ? add(x, M) : -1;
}
vector<ll> sol(ll a, ll b) const //解同余方程，返回ax=b(mod M)循环节内所有解
{
vector<ll> ans;
ll x, y, d = gcd(a, M, x, y);
if (b % d)
return ans;
ans.push_back(mul((b / d) % (M / d), x));
for (ll i = 1; i < d; ++i)
ans.push_back(add(ans.back(), M / d));
return ans;
}
ll log(ll a, ll b) const
{
unordered_map<ll, ll> x;
for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
if (!x.count(e))
x[e] = i;
for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
if (x.count(b))
return i * SM + x[b];
return -1;
}
*/
};
struct Factorial : Mod
{
vector<ll> fac, ifac;
Factorial(int N, ll M) : fac(N, 1), ifac(N, 1), Mod(M)
{
for (int i = 2; i < N; ++i)
fac[i] = mul(fac[i - 1], i), ifac[i] = mul(M - M / i, ifac[M % i]);
for (int i = 2; i < N; ++i)
ifac[i] = mul(ifac[i], ifac[i - 1]);
}
ll c(int n, int m)
{
if (m > n || m < 0 || n < 0)
return 0;
return mul(mul(fac[n], ifac[m]), ifac[n - m]);
}
} F(1e5 + 9, 1e9 + 7);
ll t, n, m, k, kase, c[31], p[31], f[31][127];
int main()
{
for (scanf("%lld", &t); t--;)
{
memset(f, 0, sizeof(f));
scanf("%lld%lld%lld", &n, &m, &k);
for (int i = 1; i <= m; ++i)
{
scanf("%lld", &c[i]);
p[i] = p[i - 1] + c[i];
}
f[0][k] = 1;
for (int i = 1; i <= m; ++i)
for (int j = 0, sum = p[m] - p[i - 1]; j <= k; ++j)
for (int l = 0; l <= j; ++l)
F.qadd(f[i][j - l], F.mul(F.mul(f[i - 1][j], F.c(j, l)), F.c(sum - (j - l) * 2 - l, c[i] - l)));
printf("Case #%lld: %lld\n", ++kase, f[m][0]);
}
}
Defeat the Enemy
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
pair<int, int> p[N], q[N];
int t, n, m, kase;
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d", &n, &m);
multiset<int> se;
for (int i = 0; i < n; ++i)
scanf("%d%d", &p[i].first, &p[i].second);
for (int i = 0; i < m; ++i)
scanf("%d%d", &q[i].second, &q[i].first);
sort(p, p + n);
sort(q, q + m);
for (int j = m - 1, i = n - 1; ~j; --j)
{
for (; (~i) && p[i].first >= q[j].first; --i)
se.insert(p[i].second);
if (se.empty())
{
n = -1;
break;
}
auto it = se.lower_bound(q[j].second);
if (it == se.end())
it = se.begin(), --n;
se.erase(it);
}
printf("Case #%d: %d\n", ++kase, n);
}
}
World Cup
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int T;
LL n, m, a, b, c;
int main()
{
scanf("%d", &T);
for (int t = 1; t <= T; t++)
{
scanf("%lld%lld%lld%lld%lld", &n, &m, &a, &b, &c);
if (c > a)
swap(a, c);
printf("Case #%d: %lld %lld\n", t,
max(a, b) * (n - m - 1) + max(m / 2 * (a + c) + m % 2 * max(b, c), b * m),
min(b, c) * (m - 1) + min((n - m) / 2 * (a + c) + (n - m) % 2 * min(a, b), (n - m) * b));
}
return 0;
}