A
签到
int main() {
for (int i = 2; i <= 2020; ++i) {
if (!v[i]) prime[++tot] = i;
for (int j = 1; j <= tot && prime[j] <= 2020 / i; ++j) {
v[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
cout << 2020 - 1 - tot;
return 0;
}
B
我sb, 没算年份是2的, 还搁那里沾沾自喜, 算了闰年的2月, 臭sb
using ll = long long;
bool check(int x) {
while (x) {
if (x % 10 == 2) return 1;
x /= 10;
}
return 0;
}
int main () {
ll ans = 0;
rep (i, 1900, 9999) {
if (i % 100 == 0 && i % 400 == 0) ans += 1;//闰年多一天
else if (i % 100 && i % 4 == 0) ans += 1;//闰年多一天
if (check(i)) ans += 365;//年份带2,直接+365
else ans += 179;//除了(2,12)其他每个月只有(2,12,20~29), 即10*12 + 28 + 31
}
cout << ans;
return 0;
}
C
O(n^2)
int main() {
string s; cin >> s;
set<string> st;
for (int i = 0; i < s.size(); ++i) {
string t = "";
for (int j = i; j < s.size(); ++j) {
if (t == "" || s[j] > t.back()) t += s[j];
else break;
st.insert(t);
}
}
cout << st.size();
//tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdc
//djstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvi
//cfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoy
//wakgnfjjaihtniptwoulxbaeqkqhfwl
return 0;
}
D
看大题的代码, 自己慢慢暴力跑吧
E
爆搜
struct node {
int s[16];
bool operator <(const node b) const {
for (int i = 0; i < 16; ++i)
if (s[i] != b.s[i]) return s[i] < b.s[i];
return false;
}
} c;
bool v[16];
int d[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
set<node> st;
bool check(int x, int y) {
if (x < 0 || x > 3 || y < 0 || y > 3) return 1;
return v[x * 4 + y];
}
void dfs(int x, int y, int k, node& c) {
if (k == 16) { st.insert(c); return; }
for (int i = 0; i < 4; ++i) {
int nx = x + d[i][0], ny = y + d[i][1];
if (check(nx, ny)) continue;
c.s[k] = nx * 4 + ny; v[nx * 4 + ny] = 1;
dfs(nx, ny, k + 1, c);
v[nx * 4 + ny] = 0;
}
}
int main() {
for (int i = 0; i < 16; ++i) {
v[i] = 1; c.s[0] = i;
dfs(i / 4, i % 4, 1, c);
v[i] = 0;
}
cout << st.size();
return 0;
}
F
我用long double 精度会丢失, 还是不是正解
要么写高精
要么看题目, 保证答案在1e9内, 那就要在递归的时候考虑更多的东西, 不能直接记步数
而是记录你走了 3 的几次方 的步, 有点像倍增, 但是记录的基地为3 而不是 2,
最后根据两个坐标点走过的 (3^i) 的数量做差, 在记录差和, ((3^i) = (3 * 3^{i-1})), 不断自顶向下做差, 最后答案在1e9内
代码就不写了, 就在原基础上改改就行
以下为原思路
跟分型之城有点像, 不过这题分9块
而且是 (3^{100} * 3^{100}), 要开long double
int tt[3][3] = {
{1, 6, 7},
{2, 5, 8},
{3, 4, 9}
};
long double fac[205];
long double solve(long long x, long long y, long long k) {
if (k == 1) return tt[x][y];
int idx = x / fac[k - 1], idy = y / fac[k - 1];
int id = idx * 3 + idy;
switch (id) {
case 0: return solve(x, y ,k - 1);
case 1: return fac[k - 1 << 1] * 5 + solve(fac[k - 1] - 1 - x, y - fac[k - 1], k - 1);
case 2: return fac[k - 1 << 1] * 6 + solve(x, y - 2 * fac[k - 1], k - 1);
case 3: return fac[k - 1 << 1] + solve(x - fac[k - 1], fac[k - 1] - 1 - y, k - 1);
case 4: return fac[k - 1 << 1] * 4 + solve(2 * fac[k - 1] - 1 - x, 2 * fac[k - 1] - 1 - y, k - 1);
case 5: return fac[k - 1 << 1] * 7 + solve(x - fac[k - 1], fac[k] - 1 - y, k - 1);
case 6: return fac[k - 1 << 1] * 2 + solve(x - 2 * fac[k - 1], y, k - 1);
case 7: return fac[k - 1 << 1] * 3 + solve(fac[k] - 1 - x, y - fac[k - 1], k - 1);
case 8: return fac[k - 1 << 1] * 8 + solve(x - 2 * fac[k - 1], y - 2 * fac[k - 1], k - 1);
default:break;
}
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
long long k, x, y, a, b; cin >> k >> y >> x >> b >> a;
fac[0] = 1;
for (int i = 1, j = k << 1; i <= j; ++i) fac[i] = fac[i - 1] * 3;
long long ans = fabs(solve(x, y, k) - solve(a, b, k));
cout << ans;
return 0;
}
G
搁着阅读理解呢? 太长不看, 输出样例结束
H
国王硬币类似, 证明就不给了(懒
pair<ll, ll> s[1001];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
ll a, b, c; cin >> a >> b >> c;
s[i].first = a + b + c; s[i].second = a + b;
}
sort(s + 1, s + 1 + n);
ll ans = 0, cur = 0;
for (int i = 1; i <= n; ++i) {
ans += cur + s[i].second;
cur += s[i].first;
}
cout << ans;
return 0;
}
I
扫描线的板子题稍微改改
const int N = 2e5 + 5;
struct BIT {
struct node {
int l, r;
ll cnt, a, b, len;
} t[N << 2];
void build(int rt, int l, int r, vector<int>& st) {
t[rt].l = l, t[rt].r = r, t[rt].len = st[r] - st[l];
if (l + 1 == r) return;
int mid = l + r >> 1;
build(rt << 1, l, mid, st);
build(rt << 1 | 1, mid, r, st);
}
void change(int rt, int l, int r, int k) {
if (t[rt].l >= l && t[rt].r <= r && t[rt].l + 1 == t[rt].r) {
t[rt].cnt += k;
if (t[rt].cnt & 1) t[rt].a = t[rt].len, t[rt].b = 0;
else if (t[rt].cnt) t[rt].b = t[rt].len, t[rt].a = 0;
else t[rt].a = t[rt].b = 0;
return;
}
int mid = t[rt].l + t[rt].r >> 1;
if (mid > l) change(rt << 1, l, r, k);
if (mid < r) change(rt << 1 | 1, l, r, k);
t[rt].a = t[rt << 1].a + t[rt << 1 | 1].a;
t[rt].b = t[rt << 1].b + t[rt << 1 | 1].b;
}
ll ask(bool k) {
return k ? t[1].a : t[1].b;
}
} T;
int n;
vector<int> st;
pair<ll, pair<pair<ll, ll>, int> > lin[N];
int get(int x) {
return lower_bound(st.begin(), st.end(), x) - st.begin();
}
bool cmp(pair<ll, pair<pair<ll, ll>, int> > a, pair<ll, pair<pair<ll, ll>, int> > b) {
if (a.fi != b.fi) return a.fi < b.fi;
return a.se.se > b.se.se;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
int x, y, a, b; cin >> x >> y >> a >> b;
if (x > a) swap(a, x);
if (y > b) swap(y, b);
lin[i << 1] = { y, { { x, a }, 1 } };
lin[i << 1 | 1] = { b, { { x, a}, -1 } };
st.push_back(x); st.push_back(a);
}
st.push_back(-2e9);
sort(st.begin(), st.end());
st.erase(unique(st.begin(), st.end()), st.end());
sort(lin, lin + (n << 1), cmp);
T.build(1, 1, st.size() - 1, st);
T.change(1, get(lin[0].se.fi.fi), get(lin[0].se.fi.se), lin[0].se.se);
ll a = 0, b = 0;
for (int i = 1; i < n << 1; ++i) {
ll h = lin[i].fi - lin[i - 1].fi;
a += T.ask(1) * h; b += T.ask(0) * h;
T.change(1, get(lin[i].se.fi.fi), get(lin[i].se.fi.se), lin[i].se.se);
}
cout << a << '
' << b;
return 0;
}
J
数据太大了, 直接写了个假的 dp 骗分, 就不写了, 又不是正解