A - box
水题
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
system("pause");
#endif
}
int n, a, b;
inline void solve()
{
cin >> n >> a >> b;
cout << n - a + b;
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf("%d", &Test);
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
B - Various distances
水题。记得用 long double，不然精度要炸。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
system("pause");
#endif
}
long double x[N];
int n;
inline void solve()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> x[i];
long double ans1 = 0, ans2 = 0, ans3 = -llinf;
for (int i = 1; i <= n; ++i)
ans1 += fabs(x[i]), ans2 += x[i] * x[i], ans3 = max(ans3, fabs(x[i]));
cout << setprecision(15) << ans1 << " " << sqrt(ans2) << " " << ans3 << endl;
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf("%d", &Test);
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
C - Cream puff
水题
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
system("pause");
#endif
}
ll n;
vector<ll> ans;
inline void solve()
{
cin >> n;
for (ll i = 1; i * i < n; ++i)
{
if (n % i == 0)
ans.push_back(i), ans.push_back(n / i);
}
if ((ll)sqrt(n) * (ll)sqrt(n) == n)
ans.push_back((ll)sqrt(n));
vecupsort(ans);
for(auto i :ans)
cout << i << '\n';
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf("%d", &Test);
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
D - Takahashi Unevolved
贪心，先乘，直到乘以 $A$ 增加的值大于 $B$ 的时候后面就一直加 $B$，即当 $(A-1)X\ge B$ 的时候就一直加 $B$ 就可以了。
不过在判断 $(A-1)X\ge B$ 的时候要爆 long long......无奈之下我就套了个高精度板子上去。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
system("pause");
#endif
}
// 该模板不可实现负数
// vector 中从高位到低位
// 即输出时需要倒序输出
struct Wint : vector<ll>
{
Wint(ll n = 0)
{
push_back(n);
check();
}
Wint &check()
{
while (!empty() && !back())
pop_back();
if (empty())
return *this;
for (int i = 1; i < (int)size(); ++i)
{
(*this)[i] += (*this)[i - 1] / 10;
(*this)[i - 1] %= 10;
}
while (back() >= 10)
{
push_back(back() / 10);
(*this)[size() - 2] %= 10;
}
return *this;
}
};
istream &operator>>(istream &is, Wint &n)
{
string s;
is >> s;
n.clear();
for (int i = (int)s.size() - 1; i >= 0; --i)
n.push_back(s[i] - '0');
return is;
}
ostream &operator<<(ostream &os, const Wint &n)
{
if (n.empty())
os << 0;
for (int i = (int)n.size() - 1; i >= 0; --i)
os << n[i];
return os;
}
bool operator!=(const Wint &a, const Wint &b)
{
if (a.size() != b.size())
return 1;
for (int i = (int)a.size() - 1; i >= 0; --i)
if (a[i] != b[i])
return 1;
return 0;
}
bool operator==(const Wint &a, const Wint &b)
{
return !(a != b);
}
bool operator<(const Wint &a, const Wint &b)
{
if (a.size() != b.size())
return a.size() < b.size();
for (int i = (int)a.size() - 1; i >= 0; --i)
if (a[i] != b[i])
return a[i] < b[i];
return 0;
}
bool operator>(const Wint &a, const Wint &b)
{
return b < a;
}
bool operator<=(const Wint &a, const Wint &b)
{
return !(a > b);
}
bool operator>=(const Wint &a, const Wint &b)
{
return !(a < b);
}
Wint &operator+=(Wint &a, const Wint &b)
{
if (a.size() < b.size())
a.resize(b.size());
for (int i = 0; i != (int)b.size(); ++i)
a[i] += b[i];
return a.check();
}
Wint operator+(Wint a, const Wint &b)
{
return a += b;
}
Wint &operator-=(Wint &a, Wint b)
{
if (a < b)
swap(a, b);
for (int i = 0; i != (int)b.size(); a[i] -= b[i], ++i)
if (a[i] < b[i])
{
int j = i + 1;
while (!a[j])
++j;
while (j > i)
{
--a[j];
a[--j] += 10;
}
}
return a.check();
}
Wint operator-(Wint a, const Wint &b)
{
return a -= b;
}
Wint operator*(const Wint &a, const Wint &b)
{
Wint n;
if (a.empty() || b.empty())
return Wint(0);
n.assign(a.size() + b.size() - 1, 0);
for (int i = 0; i != (int)a.size(); ++i)
for (int j = 0; j != (int)b.size(); ++j)
n[i + j] += a[i] * b[j];
return n.check();
}
Wint &operator*=(Wint &a, const Wint &b)
{
return a = a * b;
}
Wint divmod(Wint &a, const Wint &b)
{
Wint ans;
for (int t = (int)a.size() - (int)b.size(); a >= b; --t)
{
Wint d;
d.assign(t + 1, 0);
d.back() = 1;
Wint c = b * d;
while (a >= c)
{
a -= c;
ans += d;
}
}
return ans;
}
Wint operator/(Wint a, const Wint &b)
{
return divmod(a, b);
}
Wint &operator/=(Wint &a, const Wint &b)
{
return a = a / b;
}
Wint &operator%=(Wint &a, const Wint &b)
{
divmod(a, b);
return a;
}
Wint operator%(Wint a, const Wint &b)
{
return a %= b;
}
Wint Wpow(Wint a, Wint b)
{
Wint ret = 1;
while (b != 0)
{
if (b % 2 == 1)
ret = ret * a;
a = a * a;
b /= 2;
}
return ret;
}
Wint Wpow(Wint a, Wint b, Wint p)
{
Wint ret = 1;
while (b != 0)
{
if (b % 2 == 1)
ret = ret * a % p;
a = a * a % p;
b /= 2;
}
return ret;
}
Wint Wgcd(Wint a, Wint b)
{
return (b == 0) ? a : Wgcd(b, a % b);
}
Wint A, B, X, Y;
Wint ans;
inline void solve()
{
cin >> X >> Y >> A >> B;
while ((A - 1) * X < B && A * X < Y)
{
X = A * X;
ans = ans + 1;
}
ans += (Y - 1 - X) / B;
cout << ans << endl;
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf("%d", &Test);
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
E - Traveling Salesman among Aerial Cities
水题。直接把 TSP 状压 dp 板子套上去就可以了。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
system("pause");
#endif
}
int dp[20][st(17) + 5];
int x[20], y[20], z[20], n;
int cal(int i, int j)
{
return abs(x[i] - x[j]) + abs(y[i] - y[j]) + max(0, z[i] - z[j]);
}
inline void solve()
{
cin >> n;
for (int i = 0; i < n; ++i)
cin >> x[i] >> y[i] >> z[i];
memarray(dp, inf);
dp[0][0] = 0;
for (int nowst = 1; nowst < st(n); ++nowst)
{
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
{
if ((nowst >> i) & 1)
dp[i][nowst] = min(dp[i][nowst], dp[j][nowst - st(i)] + cal(j, i));
}
}
cout << dp[0][st(n) - 1] << '\n';
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf("%d", &Test);
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
F - Unbranched
嘛这个题画风就不太对了......
一开始去想了一下可不可以生成函数搞，类似于整数划分这种，但是想到还可以有环，以及这个题 $n\le 300$ 比较小，那就考虑 dp 算了（
设 $dp(n,m,lim)$ 表示还剩下 $n$ 个点和 $m$ 条边没用，最大的连通分量点数是否等于 $L$，$lim=1$ 表示达到了，$lim=0$ 表示还没有。
转移其实很简单......容易发现初值就是 $dp(i,0,1)=1,i\in [1,n]$，然后每次转移就拿 $k$ 个点组成一个新的连通分量，以及用这 $k$ 个点组成一个环还是一条链。
组成一个环，那么首先要满足的条件就是 $k\ge 2$。并且如果 $k\ge 3$ 的时候，因为这个环顺时针读还是逆时针读是等价的，那么这个环的总数就是 $\frac{(k-1)!}{2}$。然后要考虑哪些标号在这个环上，还要乘以一个组合数 $C_{n-1}^{k-1}$。那么，dp 方程就是 $dp(i,j) += dp(i-k,j-k) \times \frac{(k-1)!}{2} \times C_{n-1}^{k-1}$. 当然，当 $k=2$ 的时候就不用除以 $2$ 了。
组成一个链，那么首先要满足的条件就是 $k\ge 1$。并且如果 $k\ge 2$ 的时候，因为这个链从头到尾读还是从尾到头读是等价的，那么这个链的总数就是 $\frac{k!}{2}$。同样要乘以一个组合数 $C_{n-1}^{k-1}$。那么，dp 方程就是 $dp(i,j) += dp(i-k,j-k+1) \times \frac{k!}{2} \times C_{n-1}^{k-1}$。当然，当 $k=1$ 的时候就不用除以 $2$ 了。
上面 dp 方程没有把 lim 这一维加进去。加上去之后写一发记忆化搜索实际上很贱单，只要中间枚举的时候当前决策用了 $L$ 个点，那么之后的搜索过程 $lim=1$ 一直成立。那么这个题就做完了~
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 350;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
system("pause");
#endif
}
int n, m, L;
ll dp[N][N][2], C[N][N];
ll fac[N], inv2;
ll mi(ll a, ll b)
{
ll ret = 1;
while (b)
{
if (b & 1)
ret = ret * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return ret;
}
void initC(int lim)
{
C[0][0] = 1;
for (int i = 1; i <= lim; ++i)
{
C[i][0] = 1;
for (int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}
ll work(int n, int m, bool lim)
{
ll &now = dp[n][m][lim];
if (!m)
return lim;
if (!n)
return (!m && lim);
if (now >= 0)
return now;
now = 0;
for (int k = 1; k <= L; ++k)
{
if (k <= min(n, m) && k > 1)
{
now += work(n - k, m - k, lim || k == L) * fac[k - 1] % MOD * C[n - 1][k - 1] % MOD * ((k > 2) ? inv2 : 1) % MOD;
now %= MOD;
}
if (k <= n && k - 1 <= m)
{
now += work(n - k, m - k + 1, lim || k == L) * fac[k] % MOD * C[n - 1][k - 1] % MOD * ((k > 1) ? inv2 : 1) % MOD;
now %= MOD;
}
}
return now;
}
inline void solve()
{
memarray(dp, -1);
fac[0] = 1;
for (int i = 1; i <= 300; ++i)
fac[i] = fac[i - 1] * i % MOD;
inv2 = mi(2, MOD - 2);
initC(300);
cin >> n >> m >> L;
ll ans = work(n, m, 0) % MOD;
// ans = (ans + MOD) % MOD;
printf("%lld\n", ans);
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf("%d", &Test);
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
Comments NOTHING