网站开发软件搭配,那个网站做网编好,网站美工外包公司,现在流行的网站开发制作工具文章目录[USACO12DEC]First! G[JSOI2009]电子字典[IOI2008] Type PrinterNikitosh and xor[USACO12DEC]First! G
luogu3065
考虑每一个字符串成为答案的可能
这意味着从字典树根到字符串最后一位就恰好对应重新定义的字典序
在第iii层的时候#xff0c;想要走特定点#…
文章目录[USACO12DEC]First! G[JSOI2009]电子字典[IOI2008] Type PrinterNikitosh and xor[USACO12DEC]First! G
luogu3065
考虑每一个字符串成为答案的可能
这意味着从字典树根到字符串最后一位就恰好对应重新定义的字典序
在第iii层的时候想要走特定点意味着这个点的字典序必须大于该层隶属于同一个父亲的所有点(兄弟)
建立u→vu\rightarrow vu→v的有向边表示uuu的字典序vvv
最后肯定字典序不能出现环
拓扑判环
#include queue
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 300005
queue int q;
int n, cnt, tot;
string s[maxn];
bool tag[maxn], vis[maxn], in[26];
int d[26];
bool E[26][26];
int trie[maxn][26];void insert( string s ) {int now 0;int len s.length();for( int i 0;i len;i ) {int son s[i] - a;if( ! trie[now][son] ) trie[now][son] cnt;now trie[now][son];}tag[now] 1;
}bool check( string s ) {memset( d, 0, sizeof( d ) );memset( E, 0, sizeof( E ) );memset( in, 0, sizeof( in ) );int len s.length();int now 0;for( int i 0;i len;i ) {if( tag[now] ) return 0;int son s[i] - a;for( int j 0;j 26;j )if( son ^ j and ! E[son][j] and trie[now][j] ) {E[son][j] 1;d[j] ;}now trie[now][son];}for( int i 0;i 26;i )if( ! d[i] ) q.push( i );while( ! q.empty() ) {int now q.front(); q.pop();in[now] 1;for( int i 0;i 26;i )if( E[now][i] ) {d[i] --;if( ! d[i] ) q.push( i );}}for( int i 0;i 26;i )if( ! in[i] ) return 0;return 1;
}int main() {scanf( %d, n );for( int i 1;i n;i ) {cin s[i];insert( s[i] );}int ans 0;for( int i 1;i n;i )if( check( s[i] ) ) vis[i] 1, ans ;printf( %d\n, ans );for( int i 1;i n;i )if( vis[i] ) cout s[i] endl;return 0;
}[JSOI2009]电子字典
luogu4407
由于一个字符串长度不超过202020且要求相异必须为111
其实状态数是可以直接爆搜的
#include map
#include cstdio
#include cstring
using namespace std;
#define maxs 25
#define maxn 200005
map int, int mp;
int n, m, ans, cnt, len;
char s[maxn];
bool tag[maxn];
int trie[maxn][26];void insert() {int now 0;len strlen( s 1 );for( int i 1;i len;i ) {int c s[i] - a;if( ! trie[now][c] ) trie[now][c] cnt;now trie[now][c];}tag[now] 1;
}bool find() {int now 0;len strlen( s 1 );for( int i 1;i len;i ) {int c s[i] - a;if( ! trie[now][c] ) return 0;now trie[now][c];}return tag[now];
}void dfs( int ip, int now, bool k ) {if( ip len ) {if( k ) {ans ( tag[now] and ! mp[now] );mp[now] 1;}else for( int i 0;i 26;i )if( ! mp[trie[now][i]] and tag[trie[now][i]] )ans , mp[trie[now][i]] 1;return;}int c s[ip] - a;if( k ) {if( ! trie[now][c] ) return;else dfs( ip 1, trie[now][c], 1 );}else {if( trie[now][c] ) dfs( ip 1, trie[now][c], 0 );dfs( ip 1, now, 1 );for( int i 0;i 26;i )if( trie[now][i] ) {dfs( ip, trie[now][i], 1 );dfs( ip 1, trie[now][i], 1 );}}
}int main() {scanf( %d %d, n, m );for( int i 1;i n;i ) {scanf( %s, s 1 );insert();}for( int i 1;i m;i ) {scanf( %s, s 1 );if( find() ) printf( -1\n );else {dfs( 1, 0, 0 );printf( %d\n, ans );ans 0;mp.clear();}}return 0;
}[IOI2008] Type Printer
luogu4683
建立字典树
贪心的最后剩的字符越多越好
如果这个串不是最后一个那么这个串肯定会原路返回直到遇到分叉点走兄弟点
所以求出每个串与最近分叉点的距离选最大值
然后把这个串一路上的点打上最后访问标记
接着开始遍历先访问未标记点再访问标记点都清空打印机
最后把直到最后一个打印P为止的所有-操作都扔出操作顺序集合
#include cstdio
#include vector
#include cstring
#include iostream
using namespace std;
#define maxn 500005
vector char ans;
vector pair int, int G;
int n, cnt;
char s[25];
bool tag[maxn], vis[maxn];
int dep[maxn], son[maxn];
int trie[maxn][26];void insert() {int len strlen( s 1 ), now 0;for( int i 1;i len;i ) {int c s[i] - a;if( ! trie[now][c] ) trie[now][c] cnt;dep[trie[now][c]] dep[now] 1;now trie[now][c];}tag[now] 1;
}void dfs1( int now, int lst ) {if( tag[now] ) G.push_back( make_pair( now, max( lst, 0 ) ) );int tot 0;for( int i 0;i 26;i )if( trie[now][i] ) tot ;for( int i 0;i 26;i )if( trie[now][i] )dfs1( trie[now][i], lst -1 ? ( tot 1 ? now : lst ) : lst );
}void dfs2( int now, int End, bool flag ) {if( now End ) { flag 1; return; }for( int i 0;i 26;i )if( trie[now][i] ) {vis[trie[now][i]] 1;dfs2( trie[now][i], End, flag );if( flag ) return;vis[trie[now][i]] 0;}
}void dfs3( int now ) {if( tag[now] ) ans.push_back( P );for( int i 0;i 26;i ) {if( trie[now][i] and ! vis[trie[now][i]] ) {ans.push_back( i a );dfs3( trie[now][i] );ans.push_back( - );}}for( int i 0;i 26;i )if( vis[trie[now][i]] ) {ans.push_back( i a );dfs3( trie[now][i] );ans.push_back( - );}
}int main() {memset( son, -1, sizeof( son ) );scanf( %d, n );for( int i 1;i n;i ) {scanf( %s, s 1 );insert();}dfs1( 0, -1 );int Dep 0, pos;for( int i 0;i G.size();i ) {if( dep[G[i].first] - dep[G[i].second] Dep ) {Dep dep[G[i].first] - dep[G[i].second];pos G[i].first;}}bool flag 0;dfs2( 0, pos, flag );dfs3( 0 );for( int i ans.size() - 1;~ i;i -- )if( ans[i] ! P ) continue;else { cnt i 1; break; }printf( %d\n, cnt );for( int i 0;i cnt;i )printf( %c\n, ans[i] );return 0;
}Nikitosh and xor
CodeChef
⨁ilrai→br⨁bl−1\bigoplus_{il}^r a_i\rightarrow b_r\bigoplus b_{l-1}⨁ilrai→br⨁bl−1
枚举iii利用字典树边插入边询问将bib_ibi的二进制位从高到低放入字典树
求出bib_ibi与前面某个bjb_jbj的异或最大值
同理从后往前操作一样
⨁ilrai→cl⨁cr1\bigoplus_{il}^r a_i\rightarrow c_l\bigoplus c_{r1}⨁ilrai→cl⨁cr1
枚举iii利用字典树边插入边询问将bib_ibi的二进制位从高到低放入字典树
求出bib_ibi与后面某个bjb_jbj的异或最大值
然后前缀/后缀max递推
枚举断点iii直接利用preisufi1pre_isuf_{i1}preisufi1更新答案
#include cstdio
#include cstring
#include iostream
using namespace std;
#define int long long
#define maxn 400005
int trie[maxn * 30][2];
int a[maxn], b[maxn], c[maxn], pre[maxn], suf[maxn];
int n, cnt;void insert( int x ) {int now 0;for( int i 29;~ i;i -- ) {int k x i 1;if( ! trie[now][k] ) trie[now][k] cnt;now trie[now][k];}
}int query( int x ) {int now 0, ans 0;for( int i 29;~ i;i -- ) {int k x i 1;if( trie[now][k ^ 1] )ans 1 i, now trie[now][k ^ 1];elsenow trie[now][k];}return ans;
}signed main() {scanf( %lld, n );for( int i 1;i n;i )scanf( %lld, a[i] );for( int i 1;i n;i )b[i] a[i] ^ b[i - 1];for( int i n;i;i -- )c[i] c[i 1] ^ a[i];insert( 0 );for( int i 1;i n;i ) {pre[i] max( pre[i - 1], query( b[i] ) );insert( b[i] );}memset( trie, 0, sizeof( trie ) );cnt 0;insert( 0 );for( int i n;i;i -- ) {suf[i] max( suf[i 1], query( c[i] ) );insert( c[i] );}int ans 0;for( int i 1;i n;i )ans max( ans, pre[i] suf[i 1] );printf( %lld\n, ans );return 0;
}
