LA 3882 And Then There Was One
1587 ワード
この問題はジョセフリングの問題だが、データが強化されただけだ.
削除シーケンスを求める必要はなく、削除した最後の数字を要求するだけで、
だからプッシュする方法とセグメントツリーがあります
.
削除シーケンスを求める必要はなく、削除した最後の数字を要求するだけで、
だからプッシュする方法とセグメントツリーがあります
#include <stdio.h>
#include <string.h>
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
const int maxn = 1000005;
int cnt[maxn << 3];
void Build ( int l, int r, int rt )
{
cnt[rt] = r-l+1;
if ( l == r )
return ;
int m = ( l+r ) >> 1;
Build ( lson );
Build ( rson );
}
void PushUP ( int rt )
{
cnt[rt] = cnt[rt << 1]+cnt[rt << 1 | 1];
}
void update ( int q, int l, int r, int rt )
{
if ( l == r )
{
cnt[rt] = 0;
return ;
}
int m = ( l+r ) >> 1;
if ( q <= cnt[rt << 1] )
update ( q, lson );
else
update ( q-cnt[rt << 1], rson );
PushUP ( rt ); //
}
int query ( int q, int l, int r, int rt )
{
if ( l == r )
return l;
int m = ( l+r ) >> 1;
if ( q <= cnt[rt << 1] )
return query ( q, lson );
else
return query ( q-cnt[rt << 1], rson );
}
int main ( )
{
int n, k, m;
while ( ~ scanf ( "%d%d%d", &n, &k, &m ) && n )
{
memset ( cnt, 0, sizeof ( cnt ) );
Build ( 1, n, 1 );
for ( int i = n-1; i >= 1; i -- ) //n-1
{
update ( m, 1, n, 1 );
m = ( m+k-2+i )%i+1; //
//printf ( "%d
", m );
}
printf ( "%d
", query ( 1, 1, n, 1 ) ); //
}
return 0;
}
.