考的非常崩。。挺水的一套题，自己却犯了很严重的错误，在临考前暴露的很多不足点
一眼题，但是自己一直过不了样例，然后就开始自闭。因为运算是32位以内，所以当超32位是就可以直接取模即可，这是之前自己没有想到的，要划重点
#include <bits/stdc++.h> using namespace std; #define ll unsigned long long const int MAXN = 1e5 + 3; int n , m; int f[MAXN][19] , head[MAXN] , maxx[MAXN] , po[20];//18 ll seed1 , seed2 , tseed , ans , mul , k; struct edge{ int to , nex; }G[MAXN<<1]; int cnt = 1 , dep[MAXN]; void add_edge( int x , int y ){ G[cnt].nex = head[x] , G[cnt].to = y; head[x] = cnt ++; } void dfs( int x , int ff ){ for( int i = head[x] ; i ; i = G[i].nex ){ int v = G[i].to; if( v == ff ) continue; dep[v] = dep[x] + 1; f[v][0] = x; dfs( v , x ); } } inline void write(ll x){ if (x < 0) x = ~x + 1, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } int main(){ //freopen( "ancester.in" , "r" , stdin ); //freopen( "ancester.out" , "w" , stdout ); po[0] = 1; for( int i = 1 ; i <= 16 ; i ++ ){ po[i] = po[i-1] * 2; } ll r = 4294967296; scanf( "%lld%lld" , &seed1 , &seed2 ); scanf( "%d%d%lld" , &n , &m , &k ); for( int i = 1 ; i < n ; i ++ ){ int u , v;scanf( "%d%d" , &u , &v ); add_edge( u , v ); add_edge( v , u ); } dep[1] = 1; dfs( 1 , 0 ); for( int j = 1 ; j <= 16 ; j ++ ) for( int i = 1 ; i <= n ; i ++ ) f[i][j] = f[f[i][j-1]][j-1]; tseed = 0 , ans = 0 , mul = 1; while( m -- ){ tseed = ( ( tseed * seed1 % r + seed2 ) ^ ans ) % r; ll x = tseed % n + 1; tseed = ( ( tseed * seed1 % r + seed2 ) ^ ans ) % r; ll d = tseed % k; ll t = 0; if( d <= 50000 ){ int g = d; for( int i = 16 ; i >= 0 && g ; i -- ){ if( f[x][i] && g >= po[i] ){ g-= po[i]; x = f[x][i]; } } t = x; if( g ) t = 0; } ans = ( ans + mul * t % r + seed2 ) % r; mul = mul * seed2 % r; } write( ans ); return 0; }题目描述 对于一张有向图，定义d(u,v,w)为从u号点出发，不经过v号点，最终到达w号点的最短路径长度。如果不存在这样的路径，d(u,v,w)的值为−1。 你也可以认为d(u,v,w)是删去v点和其相关的边后，图中u到w的最短路。 现在给定这张有向图每两个点之间的有向边的长度（如果不存在连边则为−1），对于所有满足1≤x,y,z≤n,x≠y,y≠z的有序数对(x,y,z)，求它们d(x,y,z)的和。 你可以借助样例一解释来理解上面这句话的意思。 输入 第一行输入一个正整数n，表示该地区的点数。
接下来输入n行，每行输入n个整数。第i行第j个数Gi,j表示从i号点到j号的有向路径长度。如果这个数为−1，则表示不存在从i号点出发到j号点的路径。
输出 输出一个整数表示答案。
样例输入 3 0 1 -1 100 0 2 -1 -1 0
样例输出 100
直接用floyd直接暴力求即可
这里还是要用floyd，但是发现这里必须要选择优化，将题意简述之后发现其实就是外层循环k松弛时要保证指定的一个点不能作为松弛点，所以才需要考虑优化最外层循环
那么考虑分治，区间[L,R]表示删掉L-R中的点（即不让他们做松弛点所得到的矩形），那么现在松弛点已经操作过[1,L-1]与[R+1,N]了，所以在求左儿子[L,MID]时，就让当前矩形在跑一次[mid+1,R]作为松弛点得到的矩形传给左儿子，右儿子亦然。
故在叶子节点时统计答案
#include <bits/stdc++.h> using namespace std; #define ll long long const int MAXN = 303; int n , G[MAXN][MAXN] ; ll dis[10][MAXN][MAXN] , p[10][MAXN][MAXN] , ans; void cdq( int l , int r , int step ){ if( l == r ){ for( int i = 1 ;i <= n ; i ++ ){ for( int j = 1 ; j <= n ; j ++ ){ if( i == l || j == l || i == j ) continue; if( dis[step][i][j] == 0x3f3f3f3f ) ans --; else ans += dis[step][i][j]; } } return; } int mid = l + r >> 1; for( int i = 1 ; i <= n ; i ++ ) for( int j = 1 ; j <= n ; j ++ ) p[step][i][j] = dis[step][i][j]; for( int k = mid + 1 ; k <= r ; k ++ ){ for( int i = 1 ;i <= n ; i ++ ){ for( int j = 1 ; j <= n ; j ++ ){ if( i != j && i != k && j != k ){ dis[step][i][j] = min( dis[step][i][k] + dis[step][k][j] , dis[step][i][j] ); } } } } for( int i = 1 ; i <= n ; i ++ ) for( int j = 1 ; j <= n ; j ++ ) dis[step+1][i][j] = dis[step][i][j]; cdq( l , mid , step + 1 ); for( int i = 1 ; i <= n ; i ++ ) for( int j = 1 ; j <= n ; j ++ ) dis[step][i][j] = p[step][i][j]; for( int k = l ; k <= mid ; k ++ ){ for( int i = 1 ;i <= n ; i ++ ){ for( int j = 1 ; j <= n ; j ++ ){ if( i != j && i != k && j != k ){ dis[step][i][j] = min( dis[step][i][k] + dis[step][k][j] , dis[step][i][j] ); } } } } for( int i = 1 ; i <= n ; i ++ ) for( int j = 1 ; j <= n ; j ++ ) dis[step+1][i][j] = dis[step][i][j]; cdq( mid + 1 , r , step + 1 ); } int main(){ scanf( "%d" , &n ); for( int i = 1 ; i <= n ; i ++ ){ for( int j = 1 ; j <= n ; j ++ ){ scanf( "%d" , &G[i][j]) ; if( G[i][j] == -1 ) G[i][j] = 0x3f3f3f3f; dis[0][i][j] = G[i][j]; } } cdq( 1 , n , 0 ); printf( "%lld" , ans ); return 0; }当答案具有可合并性的时候，可以考虑使用分治，同时要加强对基本算法的理解
好像之前做过...
想到trie，但发现是错解，且错得很离谱，爆炸了
因为这里是异或，且dp不太可做，故只考虑线性基或者Trie，容易发现只能用Trie，显然要让一个子树里的点先把它们连成一棵小的树，在考虑往外贡献，那么对于左儿子与右儿子合并，使用启发式合并！！！！！让siz小的在siz大的里面一个一个暴力匹配，取最小值即可，时间复杂度是O(nlognloga)的
#include <bits/stdc++.h> using namespace std; #define ll long long const int MAXN = 1e5 + 3; ll a[MAXN] , ans ; int n , ncnt , trie[MAXN*31][2] , root , b[MAXN*31] , o2[MAXN*31]; vector<int>G[MAXN*31]; void insert_( ll x ){ root = 0; o2[0] = 30; for( int i = 30 ; i >= 0 ; i -- ){ int p = ( ( x >> i ) & 1ll ); if( !trie[root][p] ){ trie[root][p] = ++ncnt; root = ncnt; o2[ncnt] = i - 1; } else root = trie[root][p]; } b[root] = x; } void find_( int x, ll &sum , int st ){ root = st; // bool flag = 0; for( int i = o2[st] ; i >= 0 ; i -- ){ int p = ( ( x >> i ) & 1ll ); if( trie[root][p] == 0 ){ sum += ( 1ll << i ); root = trie[root][p^1]; } else if( trie[root][p] ) root = trie[root][p]; } } void dfs( int x ){ if( trie[x][0] ) dfs( trie[x][0] ); if( trie[x][1] ) dfs( trie[x][1] ); for( int i = 0 ; trie[x][0] && i < G[trie[x][0]].size() ; i ++ ){ int v = G[trie[x][0]][i]; G[x].push_back( v ); } for( int i = 0 ; trie[x][1] && i < G[trie[x][1]].size() ; i ++ ){ int v = G[trie[x][1]][i]; G[x].push_back( v ); } if( !trie[x][0] || !trie[x][1] ){ if( !trie[x][0] && !trie[x][1] ) G[x].push_back( b[x] ); return ; } else{ int siz0 = G[trie[x][0]].size() , siz1 = G[trie[x][1]].size(); ll minn = 0x3f3f3f3f; if( siz0 < siz1 ){ for( int i = 0 ;i < siz0 ; i ++ ){ ll tot = 0;int v = G[trie[x][0]][i]; find_( v , tot , trie[x][1] ); minn = min( minn , tot ); } } else{ for( int i = 0 ;i < siz1 ; i ++ ){ ll tot = 0;int v = G[trie[x][1]][i]; find_( v , tot , trie[x][0] ); minn = min( minn , tot ); } } ans += minn + ( 1ll << o2[x]); } //printf( "%d\n" , x ); } int main(){ scanf( "%d" , &n ); for( int i = 1 ; i <= n ; i ++ ){ scanf( "%lld" , &a[i] ); insert_( a[i] ); } dfs( 0 ); printf( "%lld\n" , ans ); return 0; }
