【题解】牛客CSP-S提高组赛前集训营5

首先定义指针循环一遍为一轮，一轮中J和T(树)会总共操作n次。 最终J胜利必是全1或全0 考虑J的最优操作方式，J如果想要全1胜利，J无法使0变成1，则T也会选择不操作跟J耗着，这样就会死循环，因此J必须操作将1变为0来逼迫T操作，此时全0成为J的目标，T必然不会满足他的目标于是会操作一波，但是T将0变为1后，当前一轮就不能全0了，（注意是当前一轮，J不能操作已经操作过的数)，所以J改变策略(与其说改变不如说J一开始就是要全1胜利，把1变成0只是J逼迫T操作的阴谋)，此轮剩下未操作的1都不操作了，这样一来，以序列的从左向右分别作为二进制数的第1、第2位的话，这个二进制数一定是增大的。 证明为什么增大：这个就比较好证明了，众所周知2^i>2^i-1+2^i-2....而每一轮序列分别是从左向右也就是位数逐渐增大的操作，虽然前面J将1变成了0，但是只要后面出现了0变为1就肯定能把之前的二进制损失的数所弥补回来，而且之后也不会有二进制损失了。 （以上仅个人理解，错误麻烦告知，谢啦😀）

只有我觉得T1的题解很不清楚吗？？？

请问T3两条路径出题人怎么O(1)合并的？

所以同机房一堆巨佬SPFA过T2。。。。。。

十年OI一场空，不开longlong见祖宗🙃T1 60pts祭

S！！！T！！！D！！！

想知道为什么T2的#2能卡掉分层图。。还是说只是我写丑了

请问标算在哪里

T2为什么跑13遍最短路即可？？？

T2可以折半搜索吗？

@溴溴溴 时间复杂度不是2个log的吗，对于每一个询问，需要把每一个重链提出来，然后在单调栈上面二分

T3两个log貌似也能过。。

T3怎么用单调栈维护？ 而且怎么把多条链的信息O（1）维护？

@溴溴溴 大佬能再详细的讲一讲T1吗 话说回来二进制数不是在减少吗

有大佬能告诉我T3的链是什么意思吗？这样的图也算一条链吗？

- T1爆搜 #include <bits/stdc++.h> using namespace std; #define maxn 100 #define maxm 5600 int n; bool vis[maxm]; inline int read_() { int x_=0,f_=1;char c_=getchar(); while(c_<'0'||c_>'9') {if(c_=='-') f_=-1;c_=getchar();} while(c_>='0'&&c_<='9') {x_=(x_<<1)+(x_<<3)+c_-'0';c_=getchar();} return x_*f_; } bool dfs_(int S) { if( !S ) return true; if( vis[S] ) return false; int u = S & 1,pdc; if( u == 1 ) { // 变为0 pdc = S >> 1; vis[S] = true; if( dfs_(pdc) ) { vis[S] = false;return true;} vis[S] = false; // 不变 pdc = ( S >> 1 ) + ( 1 << ( n - 1 ) ); vis[S] = true; if( dfs_(pdc) ) { vis[S] = false;return true;} vis[S] = false; } else { // 变为1  pdc = ( S >> 1 ) + ( 1 << ( n - 1 ) ); vis[S] = true; bool flag = dfs_(pdc); vis[S] = false; // 不变 pdc = ( S >> 1 ); vis[S] = true; if( flag && dfs_(pdc) ) { vis[S] = false;return true;} vis[S] = false; } return false; }  int main() { //freopen("a.txt","r",stdin); scanf("%d",&n); int AKIOI = 0; for(int S = 0;S < ( 1 << n );++S) { memset(vis,false,sizeof(vis)); if( dfs_(S) ) ++AKIOI; } printf("%d",AKIOI); return 0; }

T2能不能直接在原图上面跑13个最短路（个人感觉没啥区别）

t3没说数据随机的情况下...用倍增依次查询最小值的方法可以过大部分点...不应该是每组数据都可以构造一条单调递减的树链然后去卡嘛....（本想着一小时创造奇迹...结果正解思路莽复杂了...暴力分都没拿到QAQ...回头看倍增的写法分那么高...心痛）

T1的策略是n次一循环，神J优先把1变成0，直到神树把0变成1，身后这一循环内就不再变了吗？

毒瘤出题人卡SPFA QAQ