Problem E. TSP 问题
将所有点按照 \(x\) 分块，设块长为 B，则 \(x\) 在同一个块中的点，按照 \(y\) 排序，不在同一个块中的点，按照 \(x\) 排序
共有 \(n/B\) 个块，每一个块内对答案的贡献是：\(B+Y_{max}=2*10^5\)，两个块之间对答案的共贡献是 \(X_{max}=2*10^5\)
总贡献即为 \(B*2e5+n/B * 2e5\)，当 \(B=sqrt(n)\) 时最优
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;struct node{int x,y,idx;
};void solve(){int n;cin>>n;vector<node> p(n+1);for(int i=1;i<=n;i++){cin>>p[i].x>>p[i].y;p[i].idx=i;}int B=sqrt(n);sort(p.begin()+1,p.end(),[&](node a,node b)-> bool {if(a.x/B==b.x/B){return a.y<b.y;}return a.x<b.x;});for(int i=1;i<=n;i++){cout<<p[i].idx<<" ";}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t=1;// cin>>t; while(t--){solve(); }}
Problem A. 逆序对
首先想到根号分治
当 $ b<=\sqrt n\ $ 时，可以暴力统计所有的 \(b\)，这一步复杂度 \(\sqrt n\ * log(n) * log(n)\)。
当 $ b>\sqrt n\ $ 时，\(n\) 的二进制表示只有两位，第 0 位是 \(n~mod~b\)，第 1 位是 \(\lfloor n/b \rfloor\)
此时可以按照 \(\lfloor n/b \rfloor\) 的值分块，对于一对 \(l,r\)， 使得 \(\lfloor n/l \rfloor\) 到 \(\lfloor n/r \rfloor\) 的值都相等
设此时 \(\lfloor n/b \rfloor\) 的值为 \(k\)
则若 \(n~mod~b~>~k\) 则代表 \(b\) 进制时会产生一个逆序对
等价于 \(n-b*k>k\)
推出 \(b_{max}=(n-k-1)/k\)
所以在 \(l,r\) 范围内，\(l - b_{max}\) 会对答案有 1 的贡献
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n;cin>>n;int ans=0;int l=2,r;for(int i=2;i*i<=n;i++){l=i+1;vector<int> d;int val=n;while(val){d.push_back(val%i);val/=i;}for(int i=0;i<d.size();i++){for(int j=i+1;j<d.size();j++){if(d[i]>d[j]) ans++;}}}while(1){int k=n/l;r=min(n/k,n-1);int b=min((n-k-1)/k,r);ans+=max(0ll,b-l+1);l=r+1;if(l>n-1) break;}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0;
}
Problem B. NPC 挑战
找一个汉密尔顿路径，要求复杂度优化到 \(O(2^n * n)\)
点击查看代码
#include<bits/stdc++.h>
// #define int long long
using namespace std;
using pii = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;int popcount(int x){return __builtin_popcount(x);
}int lowbit(int x){return x&-x;
}void solve(){int n,m;cin>>n>>m;vector<int> g(n+1);while(m--){int u,v;cin>>u>>v;v--,u--;g[u]|=1<<v;}vector<int> f((1<<n)+1);for(int i=0;i<n;i++){f[1<<i]=1<<i;}//f[mask1]=mask2, mask2 中第 i 位为 1 表示可以 i 为起点走完路径 mask1for(int mask=0;mask<(1<<n);mask++){if(popcount(mask)==1) continue;int u=mask;while(u){int v=__builtin_ctz(u);u-=lowbit(u);//找到上一个位置v，如果mask^v 可以以 k 为起点，且 v 可以走到 k//则 f[mask] 可以从 f[mask^v] 转移过来if(f[mask^(1<<v)] & g[v]){f[mask]|=1<<v;}}}if(f[(1<<n)-1]) cout<<"YES";else cout<<"NO";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}return 0;
}