没写的有些多,所以一块写
EVA
原题:忘了;
贪心;
赛时将每条鱼放在了右端点,导致分的情况太多,最后没打完;
贪心的想一下,将每条鱼放在网的左或右端点肯定不会更劣;
将每条鱼作为网的左端点,然后利用相对运动的知识统计出剩下 $ n - 1 $ 条鱼的进入和出去网的范围的时间(可以将出去的时间稍微调慢一些,方便统计在同一时刻出去和进来的鱼),取最大贡献即可;
我写的代码挺长的,主要是分类讨论了一下;
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, a;
int q[5005], d[5005], h[5005];
struct sas{
long double f;
int s, id;
bool operator <(const sas &A) const {
return f < A.f;
}
}t[5005];
int qcnt, dcnt, hcnt;
struct sss{
long long w, x, v;
bool operator <(const sss &A) const {
return x < A.x;
}
}e[5005];
long long ans;
int main() {
cin >> n >> a;
for (int i = 1; i <= n; i++) {
cin >> e[i].w >> e[i].x >> e[i].v;
}
sort(e + 1, e + 1 + n);
for (int i = 1; i <= n; i++) {
long long sum = 0;
memset(t, 0, sizeof(t));
for (int j = 1; j <= n; j++) {
int v = e[j].v - e[i].v;
t[j].s = 1;
t[j + n].s = 2;
t[j].id = j;
t[j + n].id = j;
if (v < 0) {
if (e[j].x < e[i].x) {
t[j].f = -1.00;
t[j + n].f = -1.00;
continue;
}
if (e[j].x == e[i].x) {
t[j].f = 0.00;
t[j + n].f = 0.00000001;
continue;
}
if (e[j].x > e[i].x) {
if (e[j].x - e[i].x <= a) {
t[j].f = 0.00;
} else {
t[j].f = 1.00 * (e[j].x - e[i].x - a) / (1.00 * (-v));
}
t[j + n].f = 1.00 * (e[j].x - e[i].x) / (1.00 * (-v)) + 0.00000001;
}
}
if (v == 0) {
t[j].f = -1.00;
t[j].s = 1;
t[j + n].f = -1.00;
t[j + n].s = 2;
if (e[j].x >= e[i].x && e[j].x - e[i].x <= a) sum += e[j].w;
}
if (v > 0) {
if (e[j].x > e[i].x) {
if (e[j].x - e[i].x > a) {
t[j].f = -1.00;
t[j + n].f = -1.00;
continue;
}
if (e[j].x - e[i].x == a) {
t[j].f = 0.00;
t[j + n].f = 0.00000001;
continue;
}
if (e[j].x - e[i].x < a) {
t[j].f = 0.00;
t[j + n].f = 1.00 * (a + e[i].x - e[j].x) / (1.00 * v) + 0.00000001;
}
}
if (e[j].x == e[i].x) {
t[j].f = 0.00;
t[j + n].f = 1.00 * a / (1.00 * v) + 0.00000001;
continue;
}
if (e[j].x < e[i].x) {
t[j].f = 1.00 * (e[i].x - e[j].x) / (1.00 * v);
t[j + n].f = 1.00 * (e[i].x - e[j].x + a) / (1.00 * v) + 0.00000001;
}
}
}
sort(t + 1, t + 1 + 2 * n);
ans = max(ans, sum);
int j = 1;
while(j <= 2 * n) {
if (t[j].f == -1) {
j++;
continue;
}
long double o = t[j].f;
if (t[j].s == 1) sum += e[t[j].id].w;
if (t[j].s == 2) sum -= e[t[j].id].w;
j++;
ans = max(ans, sum);
}
}
cout << ans;
return 0;
}
黑客
原题:没找;
发现最后的和很小,只有 $ 999 $,所以考虑枚举和为 $ 999 $ 的所有的两个数,则这两个数是由原数除以一个相同的数得来的;
所以去算一下到两个区间左右端点分别需要多少倍,最后用右端点的 $ \min $ 值减去左端点的 $ \max $ 值即可得出以这两个数形成的最简分数一共有多少个了,然后乘一下这两个数的和即可;
注意前提是这两个数互质,因为如果不互质的话就已经被前面互质的数算过了;
细节请看代码;
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const long long mod = 1e9 + 7;
long long a, b, c, d;
long long ans;
long long w(long long aa, long long i) {
if (aa % i == 0) return aa / i;
else return aa / i + 1;
}
int main() {
cin >> a >> b >> c >> d;
for (long long i = 1; i <= 999; i++) {
for (long long j = 1; j <= 999; j++) {
if (i + j > 999) break;
if (__gcd(i, j) != 1) continue;
long long la = w(a, i);
long long lc = w(c, j);
long long rb = b / i;
long long rd = d / j;
if (rb == 0 || rd == 0) break;
if (lc > rb) continue;
if (rd < la) continue;
long long ml = max(la, lc);
long long mr = min(rb, rd);
if (mr - ml < 0) continue;
ans = (ans + (mr - ml + 1) * (i + j)) % mod;
}
}
cout << ans;
return 0;
}
密码技术
原题:yuan ti;
很显然,可以发现行列互不影响,所以我们分别算一下然后乘起来即可;
考虑可以互相转化的 $ n $ 组行(列同理),很显然有 $ A^{n}_{n} $ 种方法(全排列);
对于能互相转化,举个例子,考虑 $ 1 $ 和 $ 3 $ 可以互换,$ 1 $ 和 $ 2 $ 可以互换,则 $ 2 $ 和 $ 3 $ 就能互换(因为可以以 $ 1 $ 为中转点);
所以我们可以用并查集维护可以互换的每组行(或者列)的大小与连通性,最后将它们的阶乘乘起来即可;
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define int long long
const int mod = 998244353;
int n, kk;
int a[55][55];
bool vis[55];
int fac[55];
int fa[55];
int b[505];
int find(int x) {
if (fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
main() {
cin >> n >> kk;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i % mod;
}
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
bool vi = true;
for (int k = 1; k <= n; k++) {
if (a[i][k] + a[j][k] > kk) {
vi = false;
break;
}
}
if (vi) {
int ii = find(i);
int jj = find(j);
fa[ii] = jj;
}
}
}
for (int i = 1; i <= n; i++) {
b[find(i)]++;
}
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
bool vi = true;
for (int k = 1; k <= n; k++) {
if (a[k][i] + a[k][j] > kk) {
vi = false;
break;
}
}
if (vi) {
int ii = find(i);
int jj = find(j);
fa[ii] = jj;
}
}
}
for (int i = 1; i <= n; i++) {
b[find(i) + n]++;
}
long long ans = 1;
for (int i = 1; i <= 2 * n; i++) {
if (b[i]) ans = ans * fac[b[i]] % mod;
}
cout << ans;
return 0;
}
小孩召开法 1
原题:$ OT $;
赛时看到 $ n \leq 16 $,想到了状压,但没想到博弈论的一条性质:必败走到必胜,所以没做出来,打的暴搜还不对;
所以状压,考虑下一步如果是必胜,则这一步必败;
终态只有一个字符串,所以必胜;
又是没有签到的一场;
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
char c[25][15];
int len[25];
struct sss{
int t, ne;
}e[1005];
int h[1005], cnt;
void add(int u, int v) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
}
int f[18][(1 << 17)];
bool dfs(int x, int now) {
if (f[x][now]) return f[x][now] == 2 ? 0 : 1;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if ((1 << u) & now) continue;
if (dfs(u, now | (1 << u))) {
f[x][now] = 2;
return 0;
}
}
f[x][now] = 1;
return 1;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%s", c[i] + 1);
len[i] = strlen(c[i] + 1);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if (c[i][len[i]] == c[j][1]) {
add(i, j);
}
}
}
for (int i = 1; i <= n; i++) {
if (dfs(i, (1 << i))) {
cout << "First";
return 0;
}
}
cout << "Second";
return 0;
}