本文最后更新于15 天前，其中的信息可能已经过时，如有错误请发送邮件到big_fw@foxmail.com
赛时只写了三道题，第四道思路错了从而改不出来答案。
但是我的水平也就到这里了，属于正常发挥。
后续补题发现题的质量都非常高，每一道都能学到一些东西。
（赛后发现是 hdu 出的题，还得是你 hdu）
H. Hututu（签到，构造）
思路
之前在 codeforces 见过一道类似的题喵（只不过他和奇偶性有关，比这一道难），如果把能抵达的点化成一张图，注意到，如果起点的十字是不能一步到达的，我们至少需要两步。
复杂度分析
- 时间复杂度：$O(1)$。
- 空间复杂度：$O(1)$。
代码
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
template <class T>
void debug(T x) {cout << x << endl;}
template <class T>
void debug(vector<T> a) {for(int i = 0; i < a.size(); ++i) cout << a[i] << " "; cout << endl;}
void debug(string s) {cout << s << endl;}
void solve() {
int sx,sy,ex,ey;
cin>>sx>>sy>>ex>>ey;
int dx=abs(ex-sx),dy=abs(ey-sy);
if(dx==0&&dy==0){
cout<<0<<endl;
return;
}
int ans=max(dx+1,dy+1)/2;
if(dx==0&&ans<2)ans++;
if(dy==0&&ans<2)ans++;
cout<<ans<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while(t--) solve();
return 0;
}
I. Essentially Different Suffixes（字符串，构造，数学）
思路
赛时用哈希去存储后缀结果空间复杂度过高，改用方法将每个字符串 reverse，接着进行排序让相同前缀的字符能够在一块，接着去统计第1位,第2位,第3位…分别有多少个不同的数，可以用哈希代表有没有和他相同的数。
复杂度分析
- 时间复杂度：$O(\sum|S_i| \log \sum|S_i|)$，瓶颈在于字符串反转后的排序。
- 空间复杂度：$O(\sum|S_i|)$。
代码
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
template <class T>
void debug(T x) {cout << x << endl;}
template <class T>
void debug(vector<T> a) {for(int i = 0; i < a.size(); ++i) cout << a[i] << " "; cout << endl;}
void debug(string s) {cout << s << endl;}
void solve() {
int n;
cin >> n;
string s;
vector<string> ss(n);
for(int i = 0; i < n; ++i) {
cin>>s;
reverse(s.begin(),s.end());
ss[i]=s;
}
sort(ss.begin(),ss.end());
vector<bool> vis(n,true);
int ans=0;
int curr=1;
for(int j=0;j<(int)s.size();j++){
for(int i=1;i<n;i++){
if(vis[i]&&ss[i][j]!=ss[i-1][j]){
vis[i]=false;
curr++;
}
}
ans+=curr;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
F. Inversion Pairs（数学，构造，字符串，贪心）
思路
不难发现对于每一位，如果是 0 能对他产生贡献的是前者为 1 的数字，如果是 1 能对他产生贡献的是后者是 0 的数字，那么我们可以做出一个判定：
前者要尽可能是一，后者要尽可能是零。
那么问题就是从哪里开始后面是零。我们可以通过前后缀分别维护他 0 或者 1 的贡献。
复杂度分析
- 时间复杂度：$O(n)$，正反两遍遍历预处理前后缀，再遍历一次统计答案。
- 空间复杂度：$O(n)$，用于维护前后缀数组。
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
template <class T>
void debug(T x) {cout << x << endl;}
template <class T>
void debug(vector<T> a) {for(int i = 0; i < a.size(); ++i) cout << a[i] << " "; cout << endl;}
void debug(string s) {cout << s << endl;}
void solve() {
int n;cin>>n;
string s;cin>>s;
vector<int> pre(n+1,0);
vector<int> suf(n+1,0);
for(int i=n-2;i>=0;i--){
suf[i]+=suf[i+1]+((s[i+1]=='0'||s[i+1]=='?')?1:0);
}
int ans=0;
for(int i=0;i<n;i++){
if(i>=1)pre[i]=pre[i-1]+(s[i-1]=='1'?1:0);
if(pre[i]<suf[i]){
if(s[i]=='?'){
s[i]='1';
}
}else{
if(s[i]=='?'){
s[i]='0';
}
}
}
for(int i=0;i<n;i++){
if(s[i]=='0'){
ans+=pre[i];
}
}
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while(t--) solve();
return 0;
}
J. Sichuan Provincial Contest（树形DP）
思路
（赛时由于只考虑了顺序因此整个代码从树形DP的思路到了错误的DFS思路，DFS只有正序，没有倒序）
凑齐字符串它说的是包括顺着顺序和逆着顺序进而想到用树形 DP 的方法，每次记录他当前能凑到第几个 target，将前后的 dp 组合起来并加入贡献（将字符串分为两段，分别由前缀和后缀组成），接着将新的一位加入并维护前后的 dp 当中。
复杂度分析
- 时间复杂度：$O(n)$，树形 DP 一次 DFS 即可完成，状态转移常数极小。
- 空间复杂度：$O(n)$。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using PII=pair<int,int> ;
const int MAXN=1000010;
int n;string s;
int ans=0;
vector<int> adj[MAXN];
string target=" SCCPC";
int dp_up[MAXN][6];
int dp_down[MAXN][6];
void dfs(int u,int fa){
for(int i=1;i<=5;i++){
dp_up[u][i]=0;
dp_down[u][i]=0;
}
if(s[u]==target[1])dp_up[u][1]=1;
if(s[u]==target[5])dp_down[u][5]=1;
for(auto v:adj[u]){
if(v==fa)continue;
dfs(v,u);
for(int k=1;k<4;k++){
ans+=dp_up[u][k]*dp_down[v][k+1];
ans+=dp_up[v][k]*dp_down[u][k+1];
}
for(int k=1;k<=4;k++){
if(s[u]==target[k+1]){
dp_up[u][k+1]+=dp_up[v][k];
}
if(s[u]==target[k]){
dp_down[u][k]+=dp_down[v][k+1];
}
}
}
}
void solve(){
cin>>n;
cin>>s;
s=" "+s;
for(int i=1;i<=n;i++){
adj[i].clear();
}ans=0;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1,0);
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t;cin>>t;while(t--)
solve();
return 0;
}
A. Minimum Product（DP，图论）
思路
个人认为最神奇一道题，给的是图论，题面看着像图论，但是基本没怎么用图论，谁也不会想到他用 DP。
如果用图论暴力的话必然超时，因为 n 最高有 300，让他们互相组合，排列组合的组合数会相当爆炸（300！）。
因为每一位贡献都是正数，我们需要用 DP 的一维去维护这是第几个点，二维维护 a，它的值存储 b，进行 DP。
也正由于他的贡献是正数，因此这个 DP 是符合拓扑排序的。
（DP又何尝不是一种 DFS）
这是最让我受益匪浅的一道题。
复杂度分析
- 时间复杂度：$O(m \times n \max(a_i))$，最大计算次数在 6 \times 10^7 左右，可以顺利通过。
- 空间复杂度：$O(n^2 \max(a_i))$，用于维护二维 DP 数组。
代码
// Sunshine sunshine ladybugs awake,
// Clap your hooves and do a little shake.
#ifdef _GLIBCXX_DEBUG
#undef _GLIBCXX_DEBUG
#endif
#ifdef _GLIBCXX_DEBUG_PEDANTIC
#undef _GLIBCXX_DEBUG_PEDANTIC
#endif
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18;
void solve() {
int n,m;cin>>n>>m;
int max_s=200*(n-1);
vector<vector<int>> dp(n+1,vector<int>(max_s+1,INF));
dp[1][0]=0;
vector<int> U(m),V(m),A(m),B(m);
for(int i=0;i<m;i++){
cin>>U[i]>>V[i]>>A[i]>>B[i];
}
for(int s=0;s<=max_s;s++){
for(int i=0;i<m;i++){
int u=U[i],v=V[i],a=A[i],b=B[i];
if(dp[u][s]!=INF){
if(s+a<=max_s){
dp[v][s+a]=min(dp[v][s+a],dp[u][s]+b);
}
}
}
}
int ans_prod=INF;
int ans_a=-1,ans_b=-1;
for(int s=0;s<=max_s;s++){
if(dp[n][s]!=INF){
int prod=1ll*s*dp[n][s];
if(prod<ans_prod){
ans_prod=prod;
ans_a=s;
ans_b=dp[n][s];
}else if(prod==ans_prod&&ans_a>s){
ans_a=s;
ans_b=dp[n][s];
}
}
}
cout<<ans_a<<" "<<ans_b<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t; while (t--) solve();
return 0;
}
K. Point Divide and Conquer（构造，并查集）
思路
如果我们真按题意去正向模拟，时间复杂度是 N 的平方，这样必然超时。
正确的思路是正难则反，我们每加上一个点能将几个连通块连接起来，并将原来的根节点再指向新的点。
复杂度分析
- 时间复杂度：$O(n \cdot \alpha(n))$，倒序遍历一次加上并查集的路径压缩，极快。
- 空间复杂度：$O(n)$。
代码
// Sunshine, sunshine, ladybugs awake!
// Clap your hooves and do a little shake!
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
using PII=pair<int,int> ;
using PIC=pair<int,char> ;
const int MAXN=100005;
int n;
int a[MAXN];
int f[MAXN];
int ans[MAXN];
bool vis[MAXN];
vector<int> adj[MAXN];
int Find(int x){
if(f[x]==x){
return x;
}
return f[x]=Find(f[x]);
}
void Union(int u,int v){
int root_u=Find(u),root_v=Find(v);
if(root_u!=root_v){
f[root_v]=root_u;
ans[root_v]=u;
}
}
void init(){
for(int i=1;i<=n;i++){
f[i]=i;
ans[i]=0;
vis[i]=false;
adj[i].clear();
}
}
void solve() {
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
init();
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=n;i>=1;i--){
int u=a[i];
vis[u]=true;
for(auto v:adj[u]){
if(vis[v]){
Union(u,v);
}
}
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;cin >> t;
while (t--) solve();
return 0;
}
至于为什么后面的题没补因为后面的过题数明显减少我应该再提高一下个人水平。
