学步园

这轮的三道题目比较有水准，充分反映了Tc的前沿水平。

D1 250p UnluckyIntervals

首先计算得到以下公式：

UnluckyNumber = ( K - LuckySet[left] ) * ( luckySet[right] - K ) - 1

然后建立pair < long long, int > 代表UnluckyNumber 和K。

由于题目要求只需要N个(N=100)，因此对每个间隔枚举100个，排序，前N个就是解。

class UnluckyIntervals<br /> {<br /> pair < long long int, int > l[10001];<br /> int len;<br /> public:<br /> vector <int> getLuckiest(vector <int> luckySet, int n)<br /> {<br /> luckySet.push_back ( 0 );<br /> sort ( luckySet.begin (), luckySet.end () );<br /> len = 0;<br /> int i;<br /> for ( i = 1; i < luckySet.size (); i ++ )<br /> l[len ++] = make_pair ( 0ll, luckySet[i] );<br /> for ( i = 0; i < luckySet.size () - 1; i ++ )<br /> {<br /> int j, k, cnt;<br /> for ( j = luckySet[i] + 1, k = luckySet[i + 1] - 1, cnt = 0; ; )<br /> {<br /> if ( j > k )<br /> break;<br /> l[len ++] = make_pair ( ( long long ) ( j - luckySet[i] ) * ( luckySet[i + 1] - j ) - 1, j );<br /> if ( j != k )<br /> l[len ++] = make_pair ( ( long long ) ( k - luckySet[i] ) * ( luckySet[i + 1] - k ) - 1, k );<br /> cnt += 2;<br /> if ( cnt > 100 )<br /> break;<br /> j ++, k --;<br /> }<br /> }<br /> int j, cnt = 0;<br /> for ( j = luckySet[luckySet.size () - 1] + 1; cnt < 100; j ++, cnt ++ )<br /> {<br /> l[len ++] = make_pair ( 1ll << 60, j );<br /> }<br /> sort ( l, l + len );<br /> vector < int > sol ( n );<br /> for ( i = 0; i < n ; i++ )<br /> sol[i] = l[i].second;<br /> return sol;<br /> }<br /> }

 D1 500p EndlessStringMachine

很好的一道分形题，在2区中酿成了32sub/0ac的灭团惨案。

首先要确定，当s超过一定数量时，后面的迭代没有任何意义：因为他们远远超出了max和min的值。不确定这点，此题根本无法完成……

由于max和min之间只有100个字符，可以考虑逐个求解。

分形题的关键是如何划分层次，从而从最外层确定到最内层。

如$xy$z,$=ab,s=3的例子

最终字符串为 

abxyabzxyabxyabzz

如何确定8位的y？（以开头a为0位）

我们可以在$前后分层 abxyabz | xy | abxyabz | z 。这是最外的第三层分割方案。abxyabz的长度可以预先算出F(2)=7，8 = 7 - 1 +2，因此落在$xy$z的2位。

假如是确定10位的b，同样观察abxyabz | xy | abxyabz | z。

最外层的第二个$从9位到15位，10 - 7 - 2 = 1因此进入下层递归函数，求abxyabz的1位。

 class EndlessStringMachine<br /> {<br /> string a, b;<br /> int num;<br /> long long l[50];<br /> char get1 ( long long pos, long long s )<br /> {<br /> if ( pos < a.size () )<br /> return a[pos];<br /> if ( pos < ( long long ) s * ( b.size () - 1 ) + a.size () )<br /> return b[( pos - a.size () ) % ( b.size () - 1 ) + 1];<br /> return '-';<br /> }<br /> char get2 ( int pos, int s )<br /> {<br /> if ( s == 0 )<br /> return a[pos];<br /> long long off = 0;<br /> int i;<br /> for ( i = 0; i < b.size (); i ++ )<br /> {<br /> if ( b[i] == '$' )<br /> {<br /> if ( pos < off + l[s - 1] )<br /> return get2 ( pos - off, s - 1 );<br /> off += l[s - 1];<br /> }<br /> else<br /> {<br /> if ( pos == off )<br /> return b[i];<br /> off ++;<br /> }<br /> }<br /> return '-';<br /> }<br /> public:<br /> string getFragment(string input, string program, int s, int min, int max)<br /> {<br /> int i;<br /> num = 0;<br /> a = input, b = program;<br /> for ( i = 0; i < program.size (); i ++ )<br /> {<br /> if ( program[i] == '$' )<br /> num ++;<br /> }<br /> l[0] = a.size ();<br /> for ( i = 1; i < 40; i ++ )<br /> {<br /> l[i] = l[i - 1] * num + b.size () - num;<br /> if ( l[i] > 2000000000ll )<br /> l[i] = 2000000000ll;<br /> }<br /> if ( s > 40 && num > 1 )<br /> s = 40;<br /> string ret;<br /> min --, max --;<br /> for ( i = min; i <= max; i ++ )<br /> {<br /> if ( num == 1 )<br /> ret += get1 ( i, s );<br /> else<br /> ret += get2 ( i, s );<br /> }<br /> return ret;<br /> }<br /> }