CSP-S 2023 第二轮认证 题解
密码锁
#include <bits/stdc++.h>
int n;
int a[13][7], b[7];
bool check(int i) {
int cnt = 0;
for(int j = 1; j <= 5; j++) cnt += (a[i][j] != b[j]);
if(cnt == 1) return true;
else if(cnt != 2) return false;
for(int j = 1; j < 5; j++)
if(a[i][j] != b[j] && a[i][j + 1] != b[j + 1] && (b[j] - a[i][j] + 10) % 10 == (b[j + 1] - a[i][j + 1] + 10) % 10) return true;
return false;
}
bool check() {
for(int i = 1; i <= n; i++) if(!check(i)) return false;
return true;
}
int main() {
freopen("lock.in", "r", stdin);
freopen("lock.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++) for(int j = 1; j <= 5; j++) scanf("%d", &a[i][j]);
int ans = 0;
for(b[1] = 0; b[1] <= 9; b[1]++)
for(b[2] = 0; b[2] <= 9; b[2]++)
for(b[3] = 0; b[3] <= 9; b[3]++)
for(b[4] = 0; b[4] <= 9; b[4]++)
for(b[5] = 0; b[5] <= 9; b[5]++)
ans += check();
printf("%d\n", ans);
return 0;
}消消乐
#include <bits/stdc++.h>
typedef long long LL;
const int N = 2e6 + 5;
int n;
char s[N];
int cnt[N], nxt[N][26];
int main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
scanf("%d%s", &n, s + 1);
for(int i = 1; i <= n; i++) s[i] -= 'a';
for(int i = n - 1; i >= 1; i--) {
if(s[i + 1] == s[i]) {
for(int j = 0; j < 26; j++) nxt[i][j] = nxt[i + 2][j];
if(i + 2 <= n) nxt[i][s[i + 2]] = i + 2;
cnt[i] = cnt[i + 2] + 1;
// printf("%d -> %d\n", i, i + 2);
} else if(nxt[i + 1][s[i]]) {
int i_ = nxt[i + 1][s[i]];
for(int j = 0; j < 26; j++) nxt[i][j] = nxt[i_ + 1][j];
if(i_ + 1 <= n) nxt[i][s[i_ + 1]] = i_ + 1;
cnt[i] = cnt[i_ + 1] + 1;
// printf("%d -> %d\n", i, i_ + 1);
}
}
LL ans = 0;
for(int i = 1; i <= n; i++) ans += cnt[i];
printf("%lld\n", ans);
return 0;
}结构体
#include <bits/stdc++.h>
using std::string;
using std::cin;
using std::cout;
typedef long long LL;
const int N = 100 + 5;
int Q;
struct Type {
std::vector<std::pair<string, Type *>> m;
LL size;
int align;
} buffer[N], *Byte, *Short, *Int, *Long;
int ctype;
Type *nw_type() { ctype++; return &buffer[ctype]; }
std::map<string, Type *> type;
std::vector<std::pair<string, Type *>> vars;
char tmp[21];
inline LL align_to(LL x, int y) { return x % y ? x - x % y + y : x; }
int main() {
freopen("struct.in", "r", stdin);
freopen("struct.out", "w", stdout);
Byte = nw_type(), Short = nw_type(), Int = nw_type(), Long = nw_type();
Byte->size = Byte->align = 1, Short->size = Short->align = 2, Int->size = Int->align = 4, Long->size = Long->align = 8;
type["byte"] = Byte, type["short"] = Short, type["int"] = Int, type["long"] = Long;
cin >> Q;
while(Q--) {
int t;
cin >> t;
if(t == 1) {
string name;
int cnt;
cin >> name >> cnt;
Type *now = nw_type();
type[name] = now;
while(cnt--) {
string typname, varname;
cin >> typname >> varname;
Type *typ = type[typname];
now->m.push_back({varname, typ});
now->size = align_to(now->size, typ->align) + typ->size;
now->align = std::max(now->align, typ->align);
}
now->size = align_to(now->size, now->align);
std::cout << now->size << ' ' << now->align << '\n';
} else if(t == 2) {
string typname, varname;
cin >> typname >> varname;
LL addr = 0;
for(int i = 0; i < (int)vars.size(); i++) addr = align_to(addr, vars[i].second->align), addr += vars[i].second->size;
addr = align_to(addr, type[typname]->align);
std::cout << addr << '\n';
vars.push_back({varname, type[typname]});
} else if(t == 3) {
LL addr = 0;
int now = 0, nxtnow = 0;
string buf;
cin >> buf;
sscanf(buf.c_str() + now, "%[a-z]%n", tmp, &nxtnow), now += nxtnow;
string varname = tmp;
Type *tp;
for(int i = 0; i < (int)vars.size(); i++) {
addr = align_to(addr, vars[i].second->align);
if(vars[i].first != varname) addr += vars[i].second->size;
else { tp = vars[i].second; break; }
}
while(sscanf(buf.c_str() + now, ".%[a-z]%n", tmp, &nxtnow) == 1) {
now += nxtnow;
addr = align_to(addr, tp->align);
string name = tmp;
for(int i = 0; i < (int)tp->m.size(); i++) {
addr = align_to(addr, tp->m[i].second->align);
if(tp->m[i].first != name) addr += tp->m[i].second->size;
else { tp = tp->m[i].second; break; }
}
}
std::cout << addr << '\n';
} else {
LL addr, now_addr = 0;
bool flag = true;
string ans;
cin >> addr;
Type *now = 0;
for(int i = 0; i < (int)vars.size(); i++) {
now_addr = align_to(now_addr, vars[i].second->align);
if(addr < now_addr) { flag = false; break; }
if(addr >= now_addr + vars[i].second->size) now_addr += vars[i].second->size;
else { ans += vars[i].first; now = vars[i].second; break; }
}
if(!now) flag = false;
while(flag && !now->m.empty()) {
now_addr = align_to(now_addr, now->align);
if(addr < now_addr) { flag = false; break; }
bool fl = false;
for(int i = 0; i < (int)now->m.size(); i++) {
now_addr = align_to(now_addr, now->m[i].second->align);
if(addr < now_addr) { flag = false; break; }
if(addr >= now_addr + now->m[i].second->size) now_addr += now->m[i].second->size;
else { ans += "." + now->m[i].first; now = now->m[i].second; fl = true; break; }
}
if(!fl) { flag = false; break; }
}
if(flag) cout << ans << '\n';
else cout << "ERR" << '\n';
}
}
return 0;
}种树
#include <bits/stdc++.h>
typedef long long LL;
const int N = 1e5 + 5;
int n;
LL a[N], qk[N], qb[N];
struct Edge { int to, nxt; } edge[N << 1];
int head[N];
void add_edge(int u, int v) { static int k = 1; edge[k] = (Edge){v, head[u]}, head[u] = k++; }
int bd[N], cnt[N];
void dfs(int u, int fa) {
for(int i = head[u]; i; i = edge[i].nxt) if(edge[i].to != fa) {
int v = edge[i].to;
dfs(v, u);
bd[u] = std::min(bd[u], bd[v] - 1);
}
}
inline LL div_ceil(LL x, LL y) { if(y < 0) x = -x, y = -y; return x < 0 ? x / y : (x + y - 1) / y; }
inline LL div_floor(LL x, LL y) { if(y < 0) x = -x, y = -y; return x < 0 ? (x - y + 1) / y : x / y; }
inline bool calc(LL k, LL b, LL x, LL m, LL target) {
if(k == 0) return (m - x + 1) * b < target;
else if(k > 0) {
LL y = div_ceil(1 - b, k); __int128_t ret = 0;
if(m >= y) ret += (m - std::max(x, y) + 1) * b + (__int128_t)(m + std::max(x, y)) * (m - std::max(x, y) + 1) / 2 * k;
if(x < y) ret += std::min(m + 1, y) - x;
return ret < target;
} else {
LL y = div_floor(1 - b, k); __int128_t ret = 0;
if(x <= y) ret += (std::min(m, y) - x + 1) * b + (__int128_t)(std::min(m, y) + x) * (std::min(m, y) - x + 1) / 2 * k;
if(m > y) ret += m - std::max(x - 1, y);
return ret < target;
}
}
bool check(int m) {
// printf("check %d\n", m);
for(int i = 1; i <= n; i++) {
int l = 1, r = n + 1;
while(l < r) {
int mid = (l + r) >> 1;
if(calc(qk[i], qb[i], mid, m, a[i])) r = mid;
else l = mid + 1;
}
bd[i] = l - 1;
// printf("bd[%d] = %d\n", i, bd[i]);
}
dfs(1, 0);
for(int i = 1; i <= n; i++) if(bd[i] < 1) return false;
// for(int i = 1; i <= n; i++) printf("bd[%d] = %d\n", i, bd[i]);
for(int i = 1; i <= n; i++) cnt[i] = 0;
for(int i = 1; i <= n; i++) cnt[bd[i]]++;
int sum = 0;
for(int i = 1; i <= n; i++) {
sum += cnt[i];
if(sum > i) return false;
}
return true;
}
int main() {
freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lld%lld%lld", &a[i], &qb[i], &qk[i]);
for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); add_edge(u, v), add_edge(v, u); }
// for(int i = 1; i <= n; i++) if(calc(qk[i], qb[i], 1, 1000000000, a[i])) { printf("%lld %lld\n", qk[i], qb[i]); return 0; }
int l = n, r = 1e9;
while(l < r) {
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l);
return 0;
}
最后一题答案有误，提交到洛谷只有80分，还请大家补充
版权声明：本文由mxd's Blog发布，如需转载请注明出处。
如果文章中有风险行为，文章作者不负任何责任。
