游记就不写了，为了防止别人认为我似了所以写一下题解。
赛时挂太惨了。
顺便给订阅我博客的访客们道个歉，我自认为写不出什么有深度的文章，且大多数思路我一般都是记下来自己看的，所以文章更新频率会很低。
在退役之后说不定会有每周/两周杂谈？说不准，有时间的话我会尝试的。（内心os：这玩意最好不要变成我每周放几道数学题上去）
提高组T1 - 密码锁 | 暴力
我们机房的人写这道题的平均用时甚至短于 J 组的第一题。
不过这个倒是不难写，暴力枚举所有可能性然后状压一下扔进 set 去重即可。
代码简单不贴。
提高组T2 - 消消乐 | hash 和简单的计数
原题？但是没做过，考场上一直在想拆成多个回文串这个错误的思路。
这里的做法是与值域无关的做法。
然后我们发现我们本质上就是要找括号匹配的对数。
我们考虑每个字母构成一种括号，贪婪地匹配，也就是说 A..A..A..A 用 (..)..(..) 的匹配方法一定不劣于 (..(..)..) 的方法。
这一部分我们可以用栈模拟，若栈顶元素与栈顶上一个元素相同，则弹出。
那什么时候是合法的呢？栈在每个位置会有一种状态，如果存在两个不同的位置 ，且在这两个位置时，栈的状态相同，则就有一对匹配。
为什么？仔细思考一下，栈在每个位置都会加入元素，并且可能弹出元素。我们加入了一些元素，然后弹出了一些元素，栈的状态仍然不变，所以这些元素（加入又弹出的元素）应当构成了一些合法的匹配。
如何快速判断相同的元素呢？考虑对栈进行 hash，最后开个 map 扫一遍统计一下相同就行了。
栈 hash
为了照顾一下大家，这里讲讲我的思考。
对栈进行 hash，我们需要同时维护内部的权值和元素的位置关系，设栈顶到栈底元素依次为 ，那么我们可以考虑将它的 hash 值设为 （ 可以是你选择的任意数）。
在入栈元素的时候，相当于所有元素都向下移动了一位，所以我们将原先的 hash 值乘上 ，然后再加上当前的权值。
出栈元素的时候，相当于弹出当前元素，其他元素都向上移动了以为，所以我们将原先的 hash 值减去当前的权值，然后再除 （实际上你应该乘上乘法逆元，这个是肯定的）。
然后这道题就做完了，我写了个双 hash 防止被卡。
下面的是 CF1223F 的通过代码，这道题的话，去掉多测，输入更改一下即可，不要直接复制哦。
// Problem: F. Stack Exterminable Arrays
// Contest: Codeforces - Technocup 2020 - Elimination Round 1
// URL: https://codeforces.com/problemset/problem/1223/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// we hash like this (stack hash)
// p^k*a_0 + p^{k-1}*a_1 + ......
// add : f*p + a
// del : (f-a)/p
#include<stdio.h>
#include<stack>
#include<map>
#include<random>
const int maxn = 3.2e5;
const int mod1 = 998244353,
mod2 = 1000000007;
int pow1(int x, int p){
int res = 1;
while(p){
if(p&1)
res = 1ll * res * x % mod1;
x = 1ll * x * x % mod1;
p>>=1;
}
return res;
}
int pow2(int x, int p){
int res = 1;
while(p){
if(p&1)
res = 1ll * res * x % mod2;
x = 1ll * x * x % mod2;
p>>=1;
}
return res;
}
int inv1(int x) { return pow1(x, mod1-2); }
int inv2(int x) { return pow2(x, mod2-2); }
const int lucky1 = 387, lucky1inv = inv1(387),
lucky2 = 961, lucky2inv = inv2(961);
int hsh1[maxn], hsh2[maxn];
std::stack<int> st;
std::map<std::pair<int,int>,int> cnts;
int hs1, hs2;
void in_stack(int x){
hs1 = (1ll * hs1 * lucky1 + hsh1[x])%mod1;
hs2 = (1ll * hs2 * lucky2 + hsh2[x])%mod2;
st.push(x);
}
void pop_stack(){
hs1 = 1ll * (hs1 + mod1 - hsh1[st.top()])%mod1 * lucky1inv %mod1;
hs2 = 1ll * (hs2 + mod2 - hsh2[st.top()])%mod2 * lucky2inv %mod2;
st.pop();
}
int T, n, li[maxn];
std::mt19937 rng(std::random_device{}());
long long ans;
int main(){
for(int i=0 ; i<maxn ; i++)
hsh1[i] = rng() % mod1,
hsh2[i] = rng() % mod2;
scanf("%d", &T);
while(T--){
hs1 = hs2 = ans = 0;
while(!st.empty())
st.pop();
cnts.clear();
scanf("%d", &n);
for(int i=1;i<=n;i++)
scanf("%d",li+i);
cnts[{0,0}]++;
for(int i=1;i<=n;i++){
in_stack(li[i]);
while(st.size() >= 2){
int v = st.top();
pop_stack();
if(st.top() == v)
pop_stack();
else{
in_stack(v);
break;
}
}
cnts[{hs1,hs2}]++;
}
for(auto x:cnts)
ans += 1ll * (x.second) * (x.second-1) / 2;
printf("%lld\n", ans);
}
return 0;
}
提高组T3 - 结构体 | 超级大模拟
提前声明一下：本文中间的代码片段均是从最后的代码中截取，没有经过测试，若出现错误请及时联系我更正，并结合最后的代码理解。
这道题题意不难，我们主要是要优化模拟的思路，降低码量，让自己更有可能在考场上写出来。
我的思路是这样的：「结构体」之间有依赖关系，构成一个 DAG，我们可以用一个 struct 加上指针来存。
// 简单的工具函数，用于内存对齐，为了防止下文突然出现，所以放在这里
i64 justify(i64 siz, i64 alignment) { while(siz % alignment) siz++; return siz; }
i64 assign (i64 siz, i64 mem, i64 alignment) { return justify(siz, alignment)+mem; }
struct structure{
i64 alignment, size;
vector<pair<structure*, std::pair<string, i64>>> sons; // 三项分别是 指向成员的指针，成员的名称，成员相对于自己的偏移量
structure(i64 alignment_, i64 size_) : alignment(alignment_), size(size_) {}
};
为了方便根据结构体类型名查询结构体对象，开一个 map<string, structure*> 来存。
我们为结构体添加成员的代码可以这么写：
map<string, structure* > pool;
struct structure{
i64 alignment, size;
vector<pair<structure*, std::pair<string, i64>>> sons;
structure(i64 alignment_, i64 size_) : alignment(alignment_), size(size_) {}
void append_child_type(const string& name, const string& prop_name){
structure* typ = pool[name];
sons.push_back({typ, {prop_name, justify(size, typ->alignment)}});
size = assign(size, typ->size, typ->alignment);
alignment = max(alignment, typ->alignment);
}
void final_append(){ // 结束插入的时候按题意需要对齐
size = justify(size, alignment);
}
};
structure* register_basic_type(const string& name, i64 size) { return pool[name] = new structure(size, size); }
structure* register_structure_type(const string& name) { return pool[name] = new structure(0, 0); }
最后声明一个结构体的代码是这样的：
void register_structure(string name, int count){
typed::structure* typ = typed::register_structure_type(name);
string type_name, prop;
for(int i=0;i<count;i++)
cin >> type_name >> prop,
typ->append_child_type(type_name, prop);
typ->final_append();
cout << typ->size << " " << typ->alignment << endl;
}
然后我们发现，「变量」和「结构体」二者是有区别的，且名字可能重复，但是二者又有关联——「变量」依赖于「结构体」的类型，所以我们最好的方法是对「变量」再开一个 struct，存储所属的结构体和它的成员。
同样开一个 map<string, variable*> var_pool; 用于快速查询。
我们发现一个性质：变量和它的成员们的关系构成一棵树，所以还应该有指向其儿子的指针。
为什么不一上来就开完呢？看看数据范围，，这个空间量不允许开完，所以我们使用指针来维护变量构成的树，并且动态地为变量分配空间。
因为 ，所以这没有问题。
struct variable;
map<string, variable*> var_pool;
struct variable{
i64 mem_begin;
structure* type;
variable* subnum[maxn];
variable(structure* type_ = nullptr) : type(type_) { for(int i=0; i<maxn; i++) subnum[i] = nullptr; }
variable* get_prop(const string& s){ // 获取变量的属性（变量对应的结构体的成员）
for(int i=0; i<type->sons.size(); i++)
if(type->sons[i].second.first == s){
if(subnum[i] == nullptr)
subnum[i] = new variable(type->sons[i].first),
subnum[i]->mem_begin = mem_begin + type->sons[i].second.second;
return subnum[i];
}
}
}root;
那么声明变量的时候，我们就可以这么写：
void register_variable(string type, string name){
typed::variable* res = new typed::variable(typed::pool[type]);
typed::var_pool[name] = res;
typed::root.subnum[typed::cntroot++] = res;
typed::root.type->append_child_type(type, name);
res->mem_begin = typed::justify(typed::varbegin, res->type->alignment);
typed::varbegin = res->mem_begin + res->type->size;
cout << res->mem_begin << endl;
}
然后我们看看剩下的操作：根据变量访问内存和根据内存访问变量，本质上就是在变量树上进行寻址，代码不难。
void assign_variable(){
cin.get();
string buffer, buf2;
bool jumped = 0;
typed::variable* v = nullptr;
std::getline(cin, buffer);
for(int i=0;i<buffer.size();i++){
if(buffer[i] == '.'){
if(not jumped)
jumped = 1,
v = typed::var_pool[buf2];
else
v = v->get_prop(buf2);
buf2 = "";
}
else
buf2 += buffer[i];
}
if(not jumped)
v = typed::var_pool[buf2];
else
v = v->get_prop(buf2);
cout << v->mem_begin << endl;
}
void assign_memory(typed::variable* v, i64 delta_remain, string prefix){
if(v->type->sons.size() == 0) {
if(prefix.size() == 0)
cout << "ERR" << endl;
else
cout << prefix.substr(0, prefix.size()-1) << endl;
return;
}
for(int i=0; i<v->type->sons.size(); i++){
i64 l = v->type->sons[i].second.second;
i64 r = l + v->type->sons[i].first->size;
if(l <= delta_remain and delta_remain < r){
if(v->subnum[i] == nullptr){
v->subnum[i] = new typed::variable(v->type->sons[i].first);
v->subnum[i]->mem_begin = v->mem_begin + v->type->sons[i].second.second;
}
return assign_memory(v->subnum[i], delta_remain-l, prefix + v->type->sons[i].second.first+'.');
}
}
cout << "ERR" << endl;
}
最后将它们拼凑在一起，你就得到了本题的 AC 代码。
码量不算小，但写起来比较简洁，且方便调试。
// Problem: P9754 [CSP-S 2023] 结构体
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9754?contestId=140859
// Memory Limit: 512 MB
// Time Limit: 1000 ms
#include<iostream>
#include<stdio.h>
#include<string>
#include<map>
#include<vector>
using namespace std;
const int maxn = 107;
typedef long long i64;
namespace typed{
i64 justify(i64 siz, i64 alignment) { while(siz % alignment) siz++; return siz; }
i64 assign (i64 siz, i64 mem, i64 alignment) { return justify(siz, alignment)+mem; }
struct structure;
map<string, structure* > pool;
struct structure{
i64 alignment, size;
vector<pair<structure*, std::pair<string, i64>>> sons;
structure(i64 alignment_, i64 size_) : alignment(alignment_), size(size_) {}
void append_child_type(const string& name, const string& prop_name){
structure* typ = pool[name];
sons.push_back({typ, {prop_name, justify(size, typ->alignment)}});
size = assign(size, typ->size, typ->alignment);
alignment = max(alignment, typ->alignment);
}
void final_append(){
size = justify(size, alignment);
}
};
structure* register_basic_type(const string& name, i64 size) { return pool[name] = new structure(size, size); }
structure* register_structure_type(const string& name) { return pool[name] = new structure(0, 0); }
struct variable;
map<string, variable*> var_pool;
struct variable{
i64 mem_begin;
structure* type;
variable* subnum[maxn];
variable(structure* type_ = nullptr) : type(type_) { for(int i=0; i<maxn; i++) subnum[i] = nullptr; }
variable* get_prop(const string& s){
for(int i=0; i<type->sons.size(); i++)
if(type->sons[i].second.first == s){
if(subnum[i] == nullptr)
subnum[i] = new variable(type->sons[i].first),
subnum[i]->mem_begin = mem_begin + type->sons[i].second.second;
return subnum[i];
}
}
}root;
i64 cntroot, varbegin;
void prework(){
register_basic_type("byte" , 1),
register_basic_type("short", 2),
register_basic_type("int" , 4),
register_basic_type("long" , 8),
root.type = new structure(1, 0);
}
}
namespace operations{
void register_structure(string name, int count){
typed::structure* typ = typed::register_structure_type(name);
string type_name, prop;
for(int i=0;i<count;i++)
cin >> type_name >> prop,
typ->append_child_type(type_name, prop);
typ->final_append();
cout << typ->size << " " << typ->alignment << endl;
}
void register_variable(string type, string name){
typed::variable* res = new typed::variable(typed::pool[type]);
typed::var_pool[name] = res;
typed::root.subnum[typed::cntroot++] = res;
typed::root.type->append_child_type(type, name);
res->mem_begin = typed::justify(typed::varbegin, res->type->alignment);
typed::varbegin = res->mem_begin + res->type->size;
cout << res->mem_begin << endl;
}
void assign_variable(){
cin.get();
string buffer, buf2;
bool jumped = 0;
typed::variable* v = nullptr;
std::getline(cin, buffer);
for(int i=0;i<buffer.size();i++){
if(buffer[i] == '.'){
if(not jumped)
jumped = 1,
v = typed::var_pool[buf2];
else
v = v->get_prop(buf2);
buf2 = "";
}
else
buf2 += buffer[i];
}
if(not jumped)
v = typed::var_pool[buf2];
else
v = v->get_prop(buf2);
cout << v->mem_begin << endl;
}
void assign_memory(typed::variable* v, i64 delta_remain, string prefix){
if(v->type->sons.size() == 0) {
if(prefix.size() == 0)
cout << "ERR" << endl;
else
cout << prefix.substr(0, prefix.size()-1) << endl;
return;
}
for(int i=0; i<v->type->sons.size(); i++){
i64 l = v->type->sons[i].second.second;
i64 r = l + v->type->sons[i].first->size;
if(l <= delta_remain and delta_remain < r){
if(v->subnum[i] == nullptr){
v->subnum[i] = new typed::variable(v->type->sons[i].first);
v->subnum[i]->mem_begin = v->mem_begin + v->type->sons[i].second.second;
}
return assign_memory(v->subnum[i], delta_remain-l, prefix + v->type->sons[i].second.first+'.');
}
}
cout << "ERR" << endl;
}
}
i64 n, op, u, v;
string s, typ, nam;
int main(){
typed::prework();
scanf("%d", &n);
for(int i=1;i<=n;i++){
cin >> op;
if(op == 1)
cin >> s >> u, operations::register_structure(s, u);
else if(op == 2)
cin >> typ >> nam, operations::register_variable(typ, nam);
else if(op == 3)
operations::assign_variable();
else if(op == 4)
cin >> u, operations::assign_memory(&typed::root, u, string());
}
return 0;
}
对于那些要求极致码量的人，我这里有一份压行版，共 1.78K，但是你考场上肯定打的不是这个。
提高组T4 | 二分答案 贪心
先留个坑。