T1 基于1的算术
标签
暴力枚举
思路1
赛时想了个假的 DP，只拿了 77 分，，，
小于 \(10^{15}\) 的仅由 \(1\) 组成的数只有 \(15\) 个，直接枚举即可。
想了一个做法，就是直接枚举第 \(i\) 位作为最高位的 \(1\) 串取了几个，分解每位，设从高到低 \(i\) 位为 \(a_i\)，\(a_i - 3\sim a_i + 3\) 全部枚举即可，加个剪枝，就是答案大于当前答案时退出，然后改变一下枚举顺序即可，跑的飞快。
代码
好像这份代码多枚举几种反而更快，只枚举 \([-2, +2]\) 的不仅会 WA 还会 TLE。玄学复杂度。
code
void dfs(ll i, ll f, ll tot, ll res) {
if (f >= ans)
return;
if (i == 1)
return cmin(ans, abs(a[1] + tot + res) + f);
a[i] = a[i] + res + tot;
ll t;
t = -a[i];
dfs(i - 1, f + abs(t) * i, tot + t, (t + a[i]) * 10);
t = -a[i] - 1;
dfs(i - 1, f + abs(t) * i, tot + t, (t + a[i]) * 10);
t = -a[i] + 1;
dfs(i - 1, f + abs(t) * i, tot + t, (t + a[i]) * 10);
t = -a[i] - 2;
dfs(i - 1, f + abs(t) * i, tot + t, (t + a[i]) * 10);
t = -a[i] + 2;
dfs(i - 1, f + abs(t) * i, tot + t, (t + a[i]) * 10);
t = -a[i] - 3;
dfs(i - 1, f + abs(t) * i, tot + t, (t + a[i]) * 10);
t = -a[i] + 3;
dfs(i - 1, f + abs(t) * i, tot + t, (t + a[i]) * 10);
a[i] = a[i] - res - tot;
}
思路二
题解里说，从高到低枚举，每位只会取当前的 \(\lfloor\frac{n}{x_i}\rfloor\) 或 \(\lfloor\frac{n}{x_i}\rfloor + 1\)，其中 \(x_i\) 是长为 \(1\) 的全 \(1\) 串。复杂度 \(O(2^{\lg n})\)。
代码
code
ll n, x[20], ans;
void dfs(int i, ll n, ll res) {
if(res >= ans) return;
if(i == 1) return cmin(ans, res + abs(n));
dfs(i - 1, n % x[i], res + abs (n / x[i]) * i);
if(n % x[i] == 0) return;
dfs(i - 1, x[i] - n % x[i], res + (abs (n / x[i]) + 1) * i);
}
int main() {
freopen("add.in", "r", stdin);
freopen("add.out", "w", stdout);
rd(n); ans = n;
rep(i, 1, 16) x[i] = x[i - 1] * 10 + 1;
dfs(16, n, 0);
printf("%lld\n", ans);
return 0;
}
T2 逃离
标签
二分，贪心
思路
二分结束时间，对每辆车特殊设置终点，即 \(t\) 时必须给后面的车留足空位。
小数二分，别忘了加 \(eps\)。
代码
好写，就是卡了下精度。
code
bool _st;
ci N = 3e5 + 9;
const db INF = 1e18;
constexpr db eps = 1e-7;
struct car {
ll l, r, v;
void input() { rd(l, r, v); }
bool operator<(const car &rhs) { return l < rhs.l; }
} c[N];
int n, m, k;
ll t;
ll sum[N];
bool _ed;
int check(db dl) {
ll tot = 0;
rep(i, 1, n) {
db nv = (t + sum[i - 1] - c[i].l) / dl;
if (nv <= c[i].v)
continue;
tot = tot + ceil((nv - c[i].v) / k);
}
return tot <= m;
}
int main() {
// cerr << -(&_ed - &_st) / 1048576.0 << "MB" << endl;
freopen("car.in", "r", stdin);
freopen("car.out", "w", stdout);
rd(n, t, m, k);
rep(i, 1, n) c[i].input();
sort(c + 1, c + n + 1);
rep(i, 1, n) sum[i] = sum[i - 1] + (c[i].r - c[i].l);
db L = 0, R = INF;
while ((R - L) > eps) {
db mid = (L + R) / 2;
if (check(mid))
R = mid;
else
L = mid + eps * 10;
}
printf("%.3lf\n", L);
return 0;
}
T3 南斯拉夫
标签
小清新
构造
乱搞
思路
好像其他人有些乱搞的过了，SPJ 也出了好几次锅，后来我提供了一个 SPJ，发现如果读入的是无法识别（非可操作种类）则不会修改，然后就 AC 了，，，貌似这题很容易出解，随便搞个情况就好了。
我是转换思路，首先可以对有解的情况构造方案使其永远在 \(\{0, 1\}\) 中改变，相当于异或，每条边即令其一个端点的点值异或 \(1\)。
这样不太好搞，考虑相异转相同。对每条边，选择任意一个端点（代码中选的是较小的）将点权异或上 \(1\)，对每条边的操作就变成了不变或将两个端点同时异或上 \(1\)，因为异或和不变，若一个连通块内异或和不为 \(0\) 则无解，发现等价于边数为奇数。
然后对每一个连通块考虑，因为异或的可消除性，这个连通块内必有偶数个黑点（即点权不为 \(0\) 的点），任选两个黑点，考虑选取任一路径上的所有边，将是否操作的状态反转，这个可以求任一生成树，树上差分即可。
代码
代码难度不高。
code
ci N = 1e6 + 9;
int T;
int n, m;
int l[N], r[N], id[N], lz[N], x[N], swp[N];
vector<int> A[N];
int pa[N], sz[N];
int find(int i) { return pa[i] == i ? i : pa[i] = find(pa[i]); }
void init() {
rd(T, n, m);
rep(i, 1, n) pa[i] = i;
rep(i, 1, m) {
int u, v;
rd(u);
rd(v);
l[i] = u;
r[i] = v;
if (find(u) == find(v)) {
++sz[find(u)];
} else {
sz[find(v)] += sz[find(u)];
pa[find(u)] = find(v);
++sz[find(v)];
}
}
rep(i, 1, n) {
if (find(i) == i) {
if (sz[i] % 2 != 0) {
puts("Yugoslavia is unstable!");
exit(0);
}
}
}
}
queue<int> q;
int vis[N];
vector<int> B[N];
void dfs(int u, int la) {
if (x[u] == 1)
q.push(u);
vis[u] = 1;
for (int i : A[u]) {
int v = l[i] ^ r[i] ^ u;
if (v == la || vis[v])
continue;
dfs(v, u);
B[u].eb(i);
}
}
void dfs1(int u) {
for (int i : B[u]) {
int v = l[i] ^ r[i] ^ u;
dfs1(v);
swp[i] = lz[v];
lz[u] ^= lz[v];
}
}
bool _ed;
int ret[N];
int main() {
// cerr << -(&_ed - &_st) / 1048576.0 << "MB" << endl;
freopen("yugo.in", "r", stdin);
freopen("yugo.out", "w", stdout);
init();
rep(i, 1, m) {
x[l[i]] ^= 1;
A[l[i]].eb(i);
A[r[i]].eb(i);
}
rep(i, 1, n) {
if (find(i) == i) {
dfs(i, 0);
while (q.size()) {
lz[q.front()] ^= 1;
q.pop();
lz[q.front()] ^= 1;
q.pop();
}
dfs1(i);
}
}
rep(i, 1, n) x[i] = 0;
rep(i, 1, m) {
if (swp[i] == 0) {
// l[i]
if (x[l[i]]) {
printf("3 ");
--ret[l[i]];
} else {
printf("1 ");
++ret[l[i]];
}
x[l[i]] ^= 1;
} else {
// r[i]
if (x[r[i]]) {
printf("4 ");
--ret[r[i]];
} else {
printf("2 ");
++ret[r[i]];
}
x[r[i]] ^= 1;
}
}
// puts(""); rep(i, 1, n) printf("%d ", ret[i]);
return 0;
}
T4 数数
标签
喵喵题
Hash 表
高中数学-换元
思路
T4 出这种题？有点奇怪，，，但是妙妙题。
首先看这个式子，发现可以换元。
\(a_i^2 + a_i + a_j^2\equiv a_i\times a_j\pmod p\)
令 \(x = a_i + 1, y = a_j\)
\((x - 1)^2 + x - 1 + y^2\equiv (x - 1)\times y\pmod p\)
\(x^2 - x + y^2 - xy + y\equiv 0\pmod p\)
\(x^2 - xy + y^2 \equiv x - y\pmod p\)
两边同乘 \(x + y\)（啊这）。
得到 \(x^3 + y^3\equiv x^2 - y^2\pmod p\)
即 \(x^3 - x^2 \equiv - y^3 - y^2\pmod p\)
然后拿 \(map\) 什么的维护一下即可。
我就知道，，，
代码
code
ci N = 5e5 + 9;
int n, p;
ll ans;
ll x[N], y[N];
int a[N], b[N];
map<int, int> H;
int inmod(int x) {
x %= p;
return x < 0 ? x + p : x;
}
int main() {
// freopen("count.in", "r", stdin);
// freopen("count.out", "w", stdout);
rd(n, p);
rep(i, 1, n) rd(y[i]), y[i] %= p;
rep(i, 1, n) {
x[i] = (y[i] + 1) % p;
a[i] = inmod(x[i] * x[i] % p * x[i] % p - x[i] * x[i] % p);
b[i] = inmod(- y[i] * y[i] % p * y[i] % p - y[i] * y[i] % p);
if(a[i] == b[i]) -- ans;
++ H[b[i]];
}
rep(i, 1, n) {
if(H.find(a[i]) != H.end()) {
ans += H[a[i]];
}
}
printf("%lld\n", ans);
return 0;
}