马上省赛，为了应付一下这个考试，得看看往年题，总结一下经验。
B. Build Roads 一个王国，有n个城市。想建n-1条边连接城市，第i个城市有一个建筑公司经验值为ai。想在i和j城市之间建一条路，需要两个城市的建筑公司互相竞争，在修路中两家公司会起冲突，从而造成材料浪费。浪费材料为gcd(ai,aj)
请设计一条路连接n个城市用n条边，花费最少。
1 2 3 int gen () { return xorshitf64() % (R - L + 1 ) + L; }
分析：如果R = L，那么ai = L，相邻城市之间花费L，总花费L*(n-1)。如果R ≠ L，n较小时暴力连边建生成树(n^2)；如果n较大，若R - L + 1较大，根据素数分布，素数相距大概几百左右，这样L到(R - L + 1) + L之间必然有一个素数，有一个数为素数，gcd就为1，答案为(n - 1)，若R - L + 1较小，R - L + 1区间之内会被取满，根据连续的两个数必然互质可得结果仍然为(n - 1)。
暴力建树，单向建边，取其中任意n-1条边一定会把n个城市给连在一起。所以不需要并查，直接排序依据最小权取n-1个即可。
1 2 3 4 5 6 7 8 9 vector<int > e; int ans = 0 ;for (int i = 1 ; i <= n; i++) a[i] = gen ();for (int i = 1 ; i <= n; i++) for (int j = i + 1 ; j <= n; j++) e.push_back (__gcd(a[i], a[j])); sort (e.begin (), e.end ());for (int i = 0 ; i <= n - 1 ; i++) ans += e[i];
1 2 3 4 ans = n - 1 ; ans = (n - 1 ) * L;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <bits/stdc++.h> using namespace std;using ull = unsigned long long ;ull n, L, R, seed, a[200002 ]; ull xorshift64 () { ull x = seed; x ^= x << 13 ; x ^= x >> 7 ; x ^= x << 17 ; return seed = x; } int gen () return xorshift64 () % (R - L + 1 ) + L; } int main (void ) ull ans = 0 ; cin >> n >> L >> R >> seed; if (L == R) ans = (n - 1 ) * L; else if (n <= 20 ) { vector<ull> e; for (int i = 1 ; i <= n; i++) a[i] = gen (); for (int i = 1 ; i <= n; i++) for (int j = i + 1 ; j <= n; j++) e.push_back (__gcd(a[i], a[j])); sort (e.begin (), e.end ()); for (int i = 0 ; i < n - 1 ; i++) ans += e[i]; } else { ans = n - 1 ; } cout << ans << "\n" ; return 0 ; }
C. Cat Virus 一个国家，有很多族可以被视为有根树。一个族包含黑色和白色，改族新生儿可能是黑色，如果一个新生儿是黑色，那么它的后代也是黑色。
给一个整数k，可以有k种方式标记黑色和白色组成家族成员。两种方式肯定有不完全相同的成员，至少有一个黑色，而另一个为白色。
问如何建一个有根树使得方式为k。
设f(u)为染色u及u所有子树的方案树，若将u染成黑色，则只有一种方案，若将u染成白色，则设u的子节点为v，f(u)=proc(f(v))+1，u方案数为子树方案数之积在加上黑色的一种方案。各子树之间互不影响，所以是乘积。
若k为奇数，我们给k弄一个左儿子和右儿子，向右儿子方向走，f(r) = (k - 1) / 2，f(l) = 2, f(u) = f(l) * f(r) + 1，若k为偶数，我们直接让u连接一个子节点，然后到下一层，方案数边成k - 1。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include <bits/stdc++.h> using namespace std;#define int long long using ull = unsigned long long ;int k;vector<pair<int , int >> ans; int res = 0 ;void dfs (int idx, int pw) if (pw < 3 ) return ; if (pw == 3 ) { ans.push_back (make_pair (idx, idx + 1 )); res++; return ; } if (pw & 1 ) { ans.push_back (make_pair (idx, idx + 1 )); ans.push_back (make_pair (idx, idx + 2 )); res += 2 ; dfs (idx + 2 , pw >> 1 ); } else { ans.push_back (make_pair (idx, idx + 1 )); res++; dfs (idx + 1 , pw - 1 ); } } signed main (void ) cin >> k; if (k == 2 ) { cout << "1" << "\n" ; return (0 ); } else if (k == 3 ) { cout << "2\n1 2\n" ; return (0 ); } else dfs (1 , k); cout << res + 1 << "\n" ; for (auto &i: ans) { cout << i.first << " " << i.second << "\n" ; } return (0 ); }
D. Dyson Box 一个盒子二维方格，左下角坐标为（0，0），右上角坐标为（2×10 ^ 5，2×10 ^ 5）。
将有n个事件发生，第i次事件时出现一个立方体，左下角坐标为（xi-1，yi-1），右上角坐标为（xi，yi）。
盒子里有两个地心引力的方向，水平和竖直，有一半的可能是水平，剩下一半是竖直。她开始测量所有立方体轮廓的总长。如果引力方向是水平，所有立方体水平向左移动，如果是竖直，则竖直向下移动。
计算每次事件后两种情况（两种情况是指向左移动或向下移动）的轮廓总长。
对于竖直情况，当已经有一块，添加下一块时要减去2，对于旁边的两列，如果旁边两栋大楼更高，就减2。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include <bits/stdc++.h> #define int long long #define debug(x) cout << "[*]" << #x << " = " << x << "\n" ; using namespace std ; const int maxn = 2e5 + 5 ;int n, a[maxn], b[maxn];int ans_x, ans_y;signed main (void ) { cin >> n; while (n--) { int x, y; cin >> x >> y; if (a[x]) ans_x -= 2 ; a[x]++; if (a[x] <= a[x - 1 ]) ans_x -= 2 ; if (a[x] <= a[x + 1 ]) ans_x -= 2 ; ans_x += 4 ; if (b[y]) ans_y -= 2 ; b[y]++; if (b[y] <= b[y - 1 ]) ans_y -= 2 ; if (b[y] <= b[y + 1 ]) ans_y -= 2 ; ans_y += 4 ; cout << ans_x << " " << ans_y << "\n" ; } return (0 ); }
F. Birthday Cake 请帮助Yamabuki分蛋糕，Yamabuki有n种不同的蛋糕，可以用小写拉丁字母表示，表示蛋糕上面有什么，字符串的拼接表示蛋糕的合并。
若AB满足CC结构，（A，B两个字符串拼接后可以拆成两个相同的字符串即满足此规律），若AB满足，则BA也满足，所以枚举A的时候找可以满足条件的B即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include <bits/stdc++.h> using namespace std;const int mod[2 ] = {999999929 ,1000000007 };const int maxn = 4e5 +5 ;const int sz = 233 ;using ll = long long ;string a[maxn]; ll Hase[maxn][2 ]; ll fac[maxn][2 ]; map<pair<ll,ll>,int > mp; ll length (ll now, int small, int mod) { return (now * sz + small) % mod; } ll fetch (int l, int r, int idx) { return (Hase[r][idx]-Hase[l-1 ][idx]*fac[r-l+1 ][idx]%mod[idx]+mod[idx])%mod[idx]; } int main () ios::sync_with_stdio (false ); fac[0 ][0 ] = fac[0 ][1 ] = 1 ; for (int i = 1 ;i <= 400000 ;++i){ fac[i][0 ] = fac[i-1 ][0 ]*sz%mod[0 ]; fac[i][1 ] = fac[i-1 ][1 ]*sz%mod[1 ]; } int n; cin>>n; for (int i = 1 ;i <= n;++i){ cin>>a[i]; } sort (a+1 ,a+1 +n,[](const string&a,const string &b)->bool { return a.size ()<b.size (); }); ll ans = 0 ; for (int i = 1 ;i <= n;++i){ ll val[2 ] = {0 ,0 }; for (int j = 0 ;j < a[i].size ();++j){ val[0 ] = length (val[0 ], a[i][j], mod[0 ]); Hase[j+1 ][0 ] = val[0 ]; val[1 ] = length (val[1 ], a[i][j], mod[1 ]); Hase[j+1 ][1 ] = val[1 ]; } ans += mp[make_pair (val[0 ],val[1 ])]; int len = a[i].size (); for (int j = 1 ;j <= len/2 ;++j){ if (fetch (1 , j, 0 ) == fetch (len - j + 1 , len, 0 ) && fetch (1 , j, 1 ) == fetch (len - j + 1 , len, 1 )) { ans += mp[make_pair (fetch (j + 1 , len - j, 0 ), fetch (j + 1 , len - j, 1 ))]; } } mp[make_pair (val[0 ],val[1 ])]++; } cout<<ans<<endl; return 0 ; }
