admin管理员组文章数量:1660167
题解/算法 {F - Estimate Order}
@LINK: https://atcoder.jp/contests/abc352/tasks/abc352_f;
错误做法: 如果用差分约束, 虽然说x = y + K 可以表示成不等式形式, 但是 对于x!=y这个条件 这就很难转换了 因为他可以是x>y 也可以是x<y 如果暴力枚举到底是x>y ? x<y 他有N!方案 太多了;
正解是, 首先你应该想到Floyd, 即比如D(a,b)=2 (表示a在b的前面2个位置 即排队一定形如[队头...a,?,b,...]) 然后又有D(b,c) = -3, 那么此时 关系是可以传递的, 即此时一定有D(a,c) = -1 即排队一定形如[..., c, a, ?, b, ...]);
. 此时可以用{(维护深度的)并查集, Floyd}, 其实他俩在本问题里 是同一个东西, 因为本题中 任意两点之间的最简路径 最多只有1条;
. 用Floyd, 注意一个错误: 别把距离初始化为-1 这是错误的, 因为我们会涉及到负数!!!
于是我们分成了 若干个组, 同一个组里 他们的相对位置是固定的, 即意味着只要其中1个人 他的位置固定了 那么整个组其他所有人的位置就固定了, 也意味着 他们的答案 要么全是-1 要么全不是-1; 因此 我们直接考虑单个组;
比如某个组 元素是{x,y,z} 然后D(z,x)=4, D(z,y)=2, 那么我们用st=10101这个二进制 来表示他们的相对位置 (到时候再加上一个偏移量delta 即st<<delta 就表示他们的绝对位置), 元素要排序 即最高位的1是z 最低位的1是x, 即一个组 我们用vector: [z,y,x]; mask: 10101来记录;
即不是啥高深的算法, 就是直接暴力枚举, 即枚举每个组 他的绝对位置有多少个;
DFS剪枝
暴力的枚举每一个组 以及他的delta (即枚举该组的绝对位置), 看所有组能否放到一起;
dfs( mask: 1<<N, used: 1<<M) 表示 占据了mask这些位置, 且选择了used这些组;
. 你可能认为, used直接用M就可以了 为什么要用1<<M, 确定是的, 因为比如当前用了第[0...,i]组了 那么一下次 必须放i+1组 不可以跳过他的; 但有个问题 因为我们要枚举当前组cur 他要放的位置 因此这个组cur要除外, 因此 DFS状态里 要记录下这个cur;
对于单个元素, 别放到组里面, 而是单独记录一下Singles; 即每个组 元素个数都是>1的, 比如有M个组;
. 因为, 只要这个M个组 他们可能不冲突的放到一起, 那么剩下的位置 一定可以放单个元素(单个元素是没有任何拘束的); 而且, 如果单个元素的个数>1个 那么这些单个元素的答案 一定是-1 (因为答案保证了一定有解 那么单个元素他们之间可以相互交换);
. 但是, 如果单个元素只有1个, 那么此时还是要认真处理的, 这个单个元素 可能是-1也可能不是, 需要计算他;
总时间是8(每个组最多的能放的位置) ^ 8(组个数) 因此即使不用记忆化DFS, 也没问题, 而实际上 他的效率非常高;
int N, M; cin>> N>> M;
int Dist[ 20][ 20];
std::memset( Dist, 0x7F, sizeof( Dist));
FOR_( m, 0, M-1){
int a, b, w; cin>>a>>b>>w; --a,--b;
Dist[a][b] = w; Dist[b][a] = -w;
}
{ // floyd
FOR_( i, 0, N-1){ Dist[i][i] = 0;}
FOR_( m, 0, N-1){
FOR_( l, 0, N-1){
FOR_( r, 0, N-1){
if( Dist[l][m]!=0x7F7F7F7F && Dist[m][r]!=0x7F7F7F7F){
Dist[l][r] = Dist[l][m] + Dist[m][r];
}
}
}
}
}
vector< pair<vector<int>, int> > Groups;
vector< int> Singles;
{
vector<int> vis( N, 0);
FOR_( i, 0, N-1){
if( vis[i]){ continue;}
vector< pair<int,int> > dist;
FOR_( j, 0, N-1){
if( Dist[j][i] != 0x7F7F7F7F){
vis[j] = 1;
dist.emplace_back( Dist[j][i], j);
}
}
if( dist.size() == 1){ Singles.push_back( dist.front().second); continue;}
std::sort( dist.begin(), dist.end());
vector<int> id;
int mask = 0;
for( auto it = dist.rbegin(); it != dist.rend(); ++it){
mask |= (1<< (it->first - dist.front().first));
id.emplace_back( it->second);
}
Groups.emplace_back( id, mask);
}
}
M = Groups.size();
vector<int> ANS( N, -1);
auto Dfs = [&]( auto _dfs, int _mask, int _gID, const int _first)->bool{ // [0,gID)和`first` 这些组已经使用了;
if( _gID >= M){ return 1;}
int mask = Groups[_gID].second;
for( int delta = 0; (mask<< delta) < (1<<N); ++delta){
if( (_mask & (mask<<delta)) == 0){
if( _dfs( _dfs, _mask | (mask<< delta), (_gID+1==_first ? _gID+2:_gID+1), _first)){
return 1;
}
}
}
return 0;
};
FOR_( i, 0, M-1){
auto const& curElements = Groups[i].first;
auto const& curMask = Groups[i].second;
int ans = -1;
for( int delta = 0; (curMask<< delta) < (1<<N); ++delta){
if( Dfs( Dfs, curMask<< delta, i==0 ? 1:0, i)){
if( ans == -1){ ans = delta;}
else{ ans = -1; break;}
}
}
if( ans != -1){
for( int mask = curMask, ele = (int)curElements.size()-1; mask > 0;){
int bit = ___Binary_LowBit_1(mask);
ANS[ curElements[ele]] = (bit + ans) + 1;
mask -= (1<< bit);
-- ele;
}
}
}
if( Singles.size() == 1){
int cur = Singles.front();
int ans = -1;
FOR_( pos, 0, N-1){
if( Dfs( Dfs, (1<<pos), 0, -1)){
if( ans == -1){ ans = pos;}
else{ ans = -1; break;}
}
}
if( ans != -1){ ANS[ cur] = ans+1;}
}
for( auto i : ANS){
cout<< i << " ";
}
DP
还是枚举（每个组的绝对位置），用unordered_set<int> DP 来存储所有可以凑出来的状态， 那么比如当前组是i 他的绝对位置在delta, 那么DP的初始状态是DP.insert( Mask(i) << delta); 然后对于其他所有组 每个组都有若干种选择(即每个组的绝对位置有若干情况), 这就变长了DP模型, DP存储 这些组 每个组都选择1个绝对位置 且他们不冲突, 只要最终DP里有状态 就说明当前的(i,delta) 是合法的;
时间是8(组数) * 8(每个组的绝对位置) * ?(DP状态数 不多 因为我们用来set来优化) * 8(DP状态 枚举下一组的绝对位置);
为了方便, 把单独元素的组 也放到Group里面 即不进行这个技巧Trick优化, 当然如果单独处理单个元素 时间会优化很多, 因为我们这里只是介绍DP思想 为了代码简化 就不优化了);
FOR_( i, 0, M-1){ // 所有组 (包含了*单独元素*)
auto const& curElements = Groups[i].first;
auto const& curMask = Groups[i].second;
int ans = -1;
{
unordered_set<int> preDP, curDP;
for( int delta = 0; (curMask<<delta)<(1<<N); ++delta){
preDP.clear();
preDP.insert( curMask<<delta);
FOR_( j, 0, M-1){
if( j == i){ continue;}
auto nexMask = Groups[j].second;
curDP.clear();
for( auto pre : preDP){
for( int deltaa = 0; (nexMask<<deltaa)<(1<<N); ++deltaa){
if( (pre & (nexMask<<deltaa)) == 0){
curDP.insert( pre | (nexMask << deltaa));
}
}
}
preDP.swap( curDP);
}
if( preDP.size() > 0){
if( ans == -1){ ans = delta;}
else{ ans = -1; break;}
}
}
}
if( ans != -1){
for( int mask = curMask, ele = (int)curElements.size()-1; mask > 0;){
int bit = ___Binary_LowBit_1(mask);
ANS[ curElements[ele]] = (bit + ans) + 1;
mask -= (1<< bit);
-- ele;
}
}
}
DP(优化)
上面DP是: 当前组 * 当前组的绝对位置 * DP, 其实 我们可以把枚举每个组的绝对位置 这步骤 给优化掉, 把过程反过来;
之前是: 最初状态是00000 选择所有组 来凑出来1111111, 而现在是 最初是11....1 然后去掉所有组(除了当前组) 即最终会得到比如11001, 110111 (假如当前组有3个元素 且状态是1101 那么显然110111是合法的 左移2位);
{
unordered_set<int> preDP, curDP;
preDP.insert( (1<<N)-1);
FOR_( j, 0, M-1){
if( j == i){ continue;}
curDP.clear();
auto nexMask = Groups[j].second;
for( auto pre : preDP){
for( int deltaa = 0; (nexMask<<deltaa)<(1<<N); ++deltaa){
if( (pre & (nexMask<<deltaa)) == (nexMask<<deltaa)){
curDP.insert( pre ^ (nexMask << deltaa));
}
}
}
preDP.swap( curDP);
}
for( int delta = 0; (curMask<<delta)<(1<<N); ++delta){
if( preDP.count( curMask<<delta) > 0){
if( ans == -1){ ans = delta;}
else{ ans = -1; break;}
}
}
}
上面用的map, 假如我们去掉他呢? 即还原出最初的DP定义;(因为使用map来存有效状态 不一定就优化 因为可能有效状态很多); set<int> DP他的本质是bool DP[1<<N] 此时他的DP转移是当前组 * N(其他组) * DP(1<<N) (实际上(你即使用map 理论上 也是这个时间 因为map的本质上 就是这个[1<<N]数组);
即时间是N*N * DP; (没优化的 即之前的那个DP 是当前组N * 当前组的绝对位置N * 其他组N * DP, 我们现在已经把一个N给优化掉了; (我们这里分析的时间 是基于: 把单独元素的组 也放到Group里面 即不进行这个技巧Trick优化, 当然如果单独处理单个元素 时间会优化很多);
@DELI;
此时, 我们还可以把当前组N * 其他组N * DP中的其他组N 给优化掉;
原来是bool DP[1<<N], 我们直接把 当前正在枚举的其他组的编号 放到DP里面 即int DP[1<<N] 表示 b=DP[a] 我们要消除a 且此时已经消除了[0...,b)这些组(不含当前组) 现在要从b组开始消除; (比如当前组号是1, 那么3 = DP[11100001]表示 我们用[0,2]组 消除了00011110 然后现在剩余了11100001 还有3,4,...这些组没有消除; 即要跳过当前组, DP的终止状态是DP[?] = 当前组, 此时 他就等价于 上面之前DP里 最终DP里的所有状态 其实就等价于这里的满足DP[?]==当前组;
. jiangly的代码 就是这样写的; 这样时间是当前组N * DP;
{
static int DP[ 1<<16];
std::memset( DP, -1, sizeof(DP));
{
int beg = 0;
if( beg == i){ ++ beg;}
if( beg >= M){ beg = i;}
DP[ (1<<N)-1] = beg; // 表示要消除`(1<<N)-1` 且从`beg`组开始消除;
}
FORrev_( st, (1<<N)-1, 1){
if( DP[st] == -1){ continue;} // 非法状态（即凑不成的状态）
auto & curInd = DP[ st]; // 表示要消除掉`st` 此时要从`[curInd]`组 开始消除; 一旦`curInd==i` 即当前组 他是*DP的终止* 即说明消除其他所有组后 剩余了`st`这个状态;
ASSERTcustom_( curInd>=0 && curInd<M, curInd);
if( curInd == i){ // 此时这个`st`表示 我们用*其他所有组*(除了当前`i`组)把`((1<<N)-1) ^ st`给消除了 就剩了一个`st`留给当前组;
int delta = ___Binary_LowBit_1( st); // 别写成是`( curInd)`;
ASSERT( `st,curMask`的二进制1个数是一样的);
if( (st>>delta) == curMask){
if( ans == -1){ ans = delta;}
else{ ans = -1; break;}
}
continue;
}
auto const& nexMask = Groups[curInd].second;
for( int delta = 0; (nexMask<<delta)<(1<<N); ++delta){
if( (st & (nexMask<<delta)) == (nexMask<<delta)){
int nexInd = curInd+1;
if( nexInd == i){ ++ nexInd;}
if( nexInd >= M){ nexInd = i;} // 别写成是`>M`
DP[ st ^ (nexMask<<delta)] = nexInd;
}
}
}
}
版权声明：本文标题：题解算法 {F - Estimate Order} 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dianzi/1729849492a1215222.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论