“玲珑杯”算法比赛 Round #14标题与标程

“玲珑杯”算法比赛 Round #14标题与标程

“玲珑杯”算法比赛 Round #14难题与标程,

              “玲珑杯”算法竞技 Round #14By:wxh010910

  Start Time:2017-05-13 16:00:00 End Time:2017-05-13 18:30:00 Refresh
Time:2017-05-20 09:51:24 Public

 

 

 玲珑OJ竞赛提交地址:

      Round#14题解: 

 

A — No Game No Life

Time Limit:1s Memory Limit:256MByte

Submissions:473Solved:226

 

DESCRIPTION

一对叫做 的哥哥和大嫂玩游戏极其厉害,组成代表队吊打全部人,

唯独现实世界对他们很不本身,所以她们就去了异世界,

老大异世界有十七个种族,不能战役,只可以玩游戏。

有一回他们和数据结构种族的人较量,看何人写数据结构写得快,那时候现身了如此一道题:澳门新萄京 1

给七个类别a,每一趟八个操作。

1、把装有数字x产生y2、询问连串三个职位上边的值

INPUT第一行多个数n,m第二行n个数表示a体系前边有m行,每行格式为1 x y要么2
x独家代表把具备值为x的数形成y恐怕打听体系上x地点的数值OUTPUT对于各种2操作,即摸底,输出三个数表示答案SAMPLE
INPUT5 55 5 5 5 52 31 5 22 31 8 32 1SAMPLE OUTPUT522HINTn,m <= 一千,
a[i] <= 一千000000您作为四妹自然要AC掉那题啦SOLUTION“玲珑杯”ACM比赛Round #14

标程:

#include <bits/stdc++.h> #define MAXN 100010 using namespace std;  int n , m , a[ MAXN ]; map < int , int > wocaonimalegebia;  inline int read() {  register int x = 0 , ch = getchar();  while( !isdigit( ch ) ) ch = getchar();  while( isdigit( ch ) ) x = x * 10 + ch - '0' , ch = getchar();  return x; }  int main() {  n = read() , m = read();  for( register int i = 1 ; i <= n ; i++ ) a[i] = read() , wocaonimalegebia[ a[i] ] = a[i];  while( m-- )   if( read() == 1 )   {    int x = read();    wocaonimalegebia[x] = read();   }   else printf( "%d\n" , wocaonimalegebia[ a[ read() ] ] );  return 0; }

B — RE:从零开始的异世界生活

Time Limit:1s Memory Limit:256MByte

Submissions:368Solved:52

DESCRIPTION

486到了异世界,看到了一批可爱的妹子比如蕾姆啊,Aimee莉亚啊,Lamb啊,白鲸啊,怠惰啊等等!
有一天膜女告诉486说他的才具也许不能够再用了,因为膜女在揣摩贰个数据结构题,没心境管486了。
486说自家来帮你做,膜女说您很棒棒哦!
澳门新萄京 2

给一个会合,最开端为空(不是数学上的汇集)
几个操作:

1、插入x
2、把小于x的数产生x
3、把大于x的数产生x
4、求会集中第x小数
5、求集合中型小型于x的数个数

INPUT第一行一个数m前边有m行,每行格式为opt
x,opt表示是怎样操作,x表示操作的值OUTPUT对于各种4,5操作,输出七个值表示答案SAMPLE
INPUT51 11 34 12 334 1SAMPLE OUTPUT133HINTm <= 一千00 , x <=
一千000000SOLUTION“玲珑杯”ACM竞赛 Round #14    标程:

#include <bits/stdc++.h> #define ratio 4 #define MAXN 1000010 #define merge( a , b ) new_Node( a -> size + b -> size , b -> value , a , b ) #define new_Node( s , v , a , b ) ( & ( * st[ cnt++ ] = Node( s , v , a , b ) ) ) #define update( cur ) if( cur -> left -> size ) cur -> size = cur -> left -> size + cur -> right -> size , cur -> value = cur -> right -> value;  using namespace std;  struct Node {  int size , value;  Node * left , * right;  Node( int s , int v , Node * a , Node * b ) : size( s ) , value( v ) , left( a ) , right( b ) {}  Node() {} } * root , * null , * st[300000] , t[300000];  int n , m , x , cnt;  int find( int x , Node * cur ) {  if( !cur -> left -> size ) return cur -> value;  return x > cur -> left -> size ? find( x - cur -> left -> size , cur -> right ) : find( x , cur -> left ); }  int zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( int x , Node * cur ) {  if( !cur -> left -> size ) return ( x > cur -> value ) * cur -> size;  return x > cur -> left -> value ? zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( x , cur -> right ) + cur -> left -> size : zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( x , cur -> left ); }  void split( int x , Node * cur ) {  if( x > cur -> left -> size ) split( x - cur -> left -> size , cur -> right ) , cur -> left = merge( cur -> left , cur -> right -> left ) , st[ --cnt ] = cur -> right , cur -> right = cur -> right -> right;  else if( x < cur -> left -> size ) split( x , cur -> left ) , cur -> right = merge( cur -> left -> right , cur -> right ) , st[ --cnt ] = cur -> left , cur -> left = cur -> left -> left; }  void insert( int x , Node * cur ) {  if( !cur -> left -> size )   if( cur -> value < x ) cur -> left = new_Node( cur -> size , cur -> value , null , null ) , cur -> right = new_Node( 1 , x , null , null );   else cur -> left = new_Node( 1 , x , null , null ) , cur -> right = new_Node( cur -> size , cur -> value , null , null );  else insert( x , x > cur -> left -> value ? cur -> right : cur -> left );  update( cur ); }  void dispose( Node * cur ) {  if( cur -> left -> size ) st[ --cnt ] = cur -> left , st[ --cnt ] = cur -> right , dispose( cur -> left ) , dispose( cur -> right ); }  inline void low( int x ) {  Node * cur = root;  int s = zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( x + 1 , cur );  if( s == 0 );  else if( s == cur -> size )   dispose( cur ) , * cur = Node( s , x , null , null );  else   split( s , cur ) , dispose( cur -> left ) , * cur -> left = Node( s , x , null , null ); }  inline void up( int x ) {  Node * cur = root;  int s = zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( x + 1 , cur );  if( s == 0 )   dispose( cur ) , * cur = Node( cur -> size , x , null , null );  else if( s == cur -> size );  else   split( s , cur ) , dispose( cur -> right ) , * cur -> right = Node( cur -> size - s , x , null , null ); }  struct io {  char ibuf[1 << 23] , * s , obuf[1 << 22] , * t;  int a[24];  io() : t( obuf )  {   fread( s = ibuf , 1 , 1 << 23 , stdin );  }  ~io()  {   fwrite( obuf , 1 , t - obuf , stdout );  }  inline int read()   {   register int u = 0;   while( * s < 48 ) s++;   while( * s > 32 )    u = u * 10 + * s++ - 48;   return u;  }  template< class T >  inline void print( register T u )  {   static int * q = a;   if( !u ) * t++ = 48;   else   {    if( u < 0 )     * t++ = 45 , u *= -1;    while( u ) * q++ = u % 10 + 48 , u /= 10;    while( q != a )     * t++ = * --q;   }   * t++ = '\n';  } } ip;  #define read ip.read #define print ip.print  int main() {  m = read();  for( register int i = 0 ; i < 300000 ; i++ ) st[i] = & t[i];  null = new_Node( 0 , 0 , 0 , 0 );  while( m-- )  {   int opt = read();   if( opt == 1 )    if( root ) insert( read() , root );    else root = new_Node( 1 , read() , null , null );   else if( opt == 2 ) low( read() );   else if( opt == 3 ) up( read() );   else if( opt == 4 ) print( find( read() , root ) );   else print( zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( read() , root ) );  }  return 0; }

C — Another

Time Limit:3s Memory Limit:256MByte

Submissions:230Solved:20

DESCRIPTION

因为始料比不上的缘由,主演榊原恒一转学到了夜见山市,踏入了3年3班,看到了多少个丰富可爱的妹子Misaki。
但是…为什么别的同学都看不见Misaki呢?为何Misaki被称为一纸空文的人吧?为啥班上一贯在尸体呢?
为了搞精晓这件业务,主演去学学了OI,希图用图灵测验看看妹子是否AI(符合规律人不应当狐疑妹子是还是不是鬼吗)
在NOIP day1T2,他超出了一道数据结构题:
澳门新萄京 3
给你五个树,每个点有叁个颜料,每一个颜色有二个值t,定义二个点的跑步程度ans为:
设子树中颜色为x的点有y个,假如y >= t[x] , ans++;
求全数一点的跑动程度的和

INPUT第一行八个数n,h,h表示颜色个数前边有n –
1行,每行贰个数表示该点的阿爸背后有n行,表示各样点的颜色后边有h行,每行表示该颜色的tOUTPUT输出一个值表示答案SAMPLE
INPUT5 512341 2 3 4 511111SAMPLE OUTPUT15HINTn,m,h,t <=
壹仟00若出现爆栈难点,改栈方法请参谋1093难点代码1093地点:
Round #14

               标程:

                     

#define OPENSTACK #include <bits/stdc++.h> using namespace std; #define MAXN 500010  using namespace std;  int n , h , size[ MAXN ] , fa[ MAXN ] , dep[ MAXN ] , son[ MAXN ] , top[ MAXN ] , l[ MAXN ] , r[ MAXN ] , tag[ MAXN ] , tot , p[10000000] , cnt; vector < int > linker[ MAXN ] , wocaonimabi[ MAXN ]; long long ans;  inline int read() {  int x = 0 , ch = getchar();  while( !isdigit( ch ) ) ch = getchar();  while( isdigit( ch ) ) x = x * 10 + ch - '0' , ch = getchar();  return x; }  #define cur linker[x][i]  void dfs1( int x ) {  size[x] = 1;  for( int i = 0 ; i < linker[x].size() ; i++ )   if( cur != fa[x] )   {    fa[ cur ] = x , dep[ cur ] = dep[x] + 1;    dfs1( cur ) , size[x] += size[ cur ];    if( size[ cur ] > size[ son[x] ] ) son[x] = cur;   } }  void dfs2(int x, int t) {  top[x] = t;  l[x] = ++tot;  if (son[x] ) {   dfs2( son[x] , t );  }  for( int i = 0 ; i < linker[x].size() ; i++ )   if( cur != fa[x] && cur != son[x] )    dfs2( cur , cur ); }  inline void modify( int l , int r ) {  tag[l]++ , tag[r + 1]--;  p[ ++cnt ] = l , p[ ++cnt ] = r + 1; }  void modify( int x ) {  while( x )  {   modify( l[ top[x] ] , l[x] );   x = fa[ top[x] ];  } }  inline void addedge(int x, int y) {  linker[x].push_back( y ); }  int main() {  #ifdef OPENSTACK   int size = 128 << 20; // 64MB   char *tangtangtangtanglaoshia = (char*)malloc(size) + size;   #if (defined _WIN64) or (defined __unix)    __asm__("movq %0, %%rsp\n" :: "r"(tangtangtangtanglaoshia));   #else    __asm__("movl %0, %%esp\n" :: "r"(tangtangtangtanglaoshia));   #endif  #endif  n = read() , h = read();  for( int i = 2 ; i <= n ; i++ ) addedge( read() , i );  for( int i = 1 ; i <= n ; i++ ) wocaonimabi[ read() ].push_back( i );  dfs1( 1 );  dfs2( 1 , 1 );  for( int v = 1 ; v <= h ; v++ )  {   int t = read();   for(int i = 0 ; i < wocaonimabi[v].size() ; i++ )    modify( wocaonimabi[v][i] );   p[ ++cnt ] = 1 , p[ ++cnt ] = n + 1;   sort( p + 1 , p + cnt + 1 );   cnt = unique( p + 1 , p + cnt + 1 ) - p;   for(int i = 1 , last = 1 , now = 0 ; i <= cnt ; i++ )   {    if( now >= t ) ans += p[i] - last;    now += tag[ p[i] ] , tag[ p[i] ] = 0;    last = p[i];   }   cnt = 0;  }  cout << ans << endl;  #ifdef OPENSTACK   exit(0);  #else   return 0;  #endif }

D — 轻拍翻转小膜女

Time Limit:1s Memory Limit:256MByte

Submissions:36Solved:4

DESCRIPTION

可可娜是三个迷人的初级中学二年级妹子,本来在认真学习的她偶遇了膜法青娥帕比卡,于是和他一同潜入称为pure
illusion的异世界,寻觅“mimi的碎片”,传闻找齐了具有碎片能够掌握控制pure
illusion进而掌握控制世界。
但是…
那番其实讲的是家庭伦理…
先不管这样多,有二遍可可娜和帕比卡进来了贰个奇妙的异世界,里面整套是多少结构题。
她俩终于做出了有着题,得到了零星,正希图离开,陡然意识相差的言语上还大概有最终一道题没被AC,这些题是这般的:
澳门新萄京 4

一个连串a,叁个操作:
老是询问二个距离,是不是存在四个区别数x,y,使得x = y *
z,这里指的是整除!

INPUT第一行四个数n,m第二行n个数表示a类别前边有m行,每行为l r
z表示三个操作OUTPUT对于每种操作,输出”flip”表示能够,输出“flap”表示不得以SAMPLE
INPUT5 51 2 4 8 161 2 22 4 44 5 21 2 82 4 5SAMPLE
OUTPUTflipflipflipflapflapHINTn,m,a[i] <= 1000002 <= z <=
100000SOLUTION“玲珑杯”ACM比赛 Round #14

  标程:

       

#include<bits/stdc++.h> #define MAXN 100010   using namespace std;   int n , m , block , a[ MAXN ], belong[ MAXN ] , ans[ MAXN ] , cnt[ MAXN ] , last[ MAXN ];   struct ask {         int v , l , r , pos; } q[ MAXN ];   vector < ask > linker[MAXN ];   inline bool cmp( const ask& a , const ask & b ) {         return belong[ a.l ] ^ belong[ b.l ] ? belong[ a.l ] <belong[ b.l ] : belong[ a.l ] & 1 ? a.r < b.r : a.r > b.r; }   inline int read() {         register int x = 0 , ch = getchar();         while( !isdigit( ch ) ) ch = getchar();         while( isdigit( ch ) ) x = x * 10 + ch - '0' , ch =getchar();         return x; }   int main() {         n = read() , m = read();         block = n / sqrt( m / 3 );         for( register int i = 1 ; i <= n ; i++ ) belong[i] = ( i -1 ) / block , a[i] = read();         for( register int i = 1 ; i <= m ; i++ )                q[i].l = read() , q[i].r = read() , q[i].v = read() ,q[i].pos = i;         sort( q + 1 , q + m + 1 , cmp );         for( int i = 1 , l = 1 , r = 0 ; i <= m ; i++ )         {                while( l > q[i].l ) cnt[ a[ --l ] ]++;                while( r < q[i].r ) cnt[ a[ ++r ] ]++;                while( l < q[i].l ) cnt[ a[ l++ ] ]--;                while( r > q[i].r ) cnt[ a[ r-- ] ]--;                if( q[i].v > 300 )                        for( register int j = 1 ; j * q[i].v <=100000 && !ans[ q[i].pos ] ; j++ )                                if( cnt[j] && cnt[ j * q[i].v] )                                       ans[ q[i].pos ] = 1;         }         for( int x = 1 ; x <= 300 ; x++ )         {                 for( registerint i = 1 ; i <= n ; i++ ) linker[i].clear();                for( register int i = 1 ; i <= m ; i++ )                        if( q[i].v == x )                                linker[ q[i].l ].push_back( q[i] );                memset( last , 0x3f , sizeof( last ) );                for( register int i = n , j = n + 1 ; i ; i-- )                {                        if( a[i] * 1ll * x <= 100000 ) j = min( j ,last[ a[i] * 1ll * x ] );                        if( a[i] % x == 0 ) j = min( j , last[ a[i] /x ] );                        for( register int k = 0 ; k <linker[i].size() ; k++ )                                if( linker[i][k].r >= j )                                       ans[ linker[i][k].pos ] = 1;                        last[ a[i] ] = i;                }         }         for( register int i = 1 ; i <= m ; i++ )                puts( ans[i] ? "flip" : "flap" );         return 0; }       

E — 大头日

Time Limit:2s Memory Limit:256MByte

Submissions:69Solved:3

DESCRIPTION

澳门新萄京 5
怼大佬是会掉人品的,要是怼成功了,那么rp–,不然rp不改变。
有n个大佬,任性多少个大佬之间都竞相怼了壹次,他们之间必有贰个怼对方得逞,而另多少个满盘皆输。
具体来讲,这产生了贰个竞技图,即随意两点之间有且只有一条有向边。
种种大佬的初步rp都以0,他们竞相怼之后把全体人的rp排序,问有些许种精神不相同的rp连串?

INPUT一行三个整数表示n。OUTPUT一行一个大背头表示答案模998244353的值。SAMPLE
INPUT1SAMPLE OUTPUT1HINTn <= 一千00SOLUTION“玲珑杯”ACM竞技 Round
#14

澳门新萄京,   标程:

        

#include <bits/stdc++.h> #define xx first #define yy second #define mp make_pair #define pb push_back #define fill( x, y ) memset( x, y, sizeof x ) #define copy( x, y ) memcpy( x, y, sizeof x )  using namespace std;  typedef long long LL; typedef pair < int, int > pa;  inline int read() {  int sc = 0, f = 1; char ch = getchar();  while( ch < '0' || ch > '9' ) { if( ch == '-' ) f = -1; ch = getchar(); }  while( ch >= '0' && ch <= '9' ) sc = sc * 10 + ch - '0', ch = getchar();  return sc * f; }  const int mod = 998244353; const int MAXN = 262145;  inline int qpow(int x, int y, int mod) { int ret = 1; for( ; y ; y >>= 1, x = 1LL * x * x % mod ) if( y & 1 ) ret = 1LL * ret * x % mod; return ret; }  namespace NTT {  int R[MAXN], n, L, inv;   inline void getR() { for( int i = 0 ; i < n ; i++ ) R[ i ] = ( R[ i >> 1 ] >> 1 ) | ( ( i & 1 ) << L - 1 ); inv = qpow( n, mod - 2, mod ); }   inline void NTT(int *a, int f)  {   for( int i = 0 ; i < n ; i++ ) if( i < R[ i ] ) swap( a[ i ], a[ R[ i ] ] );   for( int i = 1, wn = qpow( 3, mod - 1 + f * ( mod - 1 ) / ( i << 1 ), mod ) ; i < n ; i <<= 1, wn = qpow( 3, mod - 1 + f * ( mod - 1 ) / ( i << 1 ), mod ) )    for( int j = 0, w = 1; j < n ; j += i << 1, w = 1 )     for( int k = 0 ; k < i ; k++, w = 1LL * w * wn % mod )     {      int x = a[ j + k ], y = 1LL * w * a[ j + k + i ] % mod;      a[ j + k ] = ( x + y ) % mod; a[ j + k + i ] = ( x - y + mod ) % mod;     }   if( f < 0 ) for( int i = 0 ; i < n ; i++ ) a[ i ] = 1LL * a[ i ] * inv % mod;  }   inline void mul(int *ret, int *a, int *b)  {   NTT( a, 1 ); NTT( b, 1 );   for( int i = 0 ; i < n ; i++ ) ret[ i ] = 1LL * a[ i ] * b[ i ] % mod;   NTT( ret, -1 );  } }  inline void inc(int &x, int y) { x += y; if( x >= mod ) x -= mod; } inline void dec(int &x, int y) { x -= y; if( x < 0 ) x += mod; }  int n, f[MAXN], g[MAXN], fac[MAXN], inv[MAXN], fnv[MAXN], p[MAXN], p_cnt, phi[MAXN], a[MAXN], b[MAXN], c[MAXN];  inline int C(int x, int y) { return 1LL * fac[ x ] * fnv[ y ] % mod * fnv[ x - y ] % mod; }  inline void init() {  fac[ 0 ] = inv[ 0 ] = inv[ 1 ] = fnv[ 0 ] = phi[ 1 ] = f[ 0 ] = 1;  for( int i = 1 ; i <= ( n << 1 ) ; i++ ) fac[ i ] = 1LL * fac[ i - 1 ] * i % mod;     for( int i = 2 ; i <= ( n << 1 ) ; i++ ) inv[ i ] = 1LL * ( mod - mod / i ) * inv[ mod % i ] % mod;     for( int i = 1 ; i <= ( n << 1 ) ; i++ ) fnv[ i ] = 1LL * fnv[ i - 1 ] * inv[ i ] % mod;  for( int i = 2 ; i <= n ; i++ )  {   if( !phi[ i ] ) phi[ p[ ++p_cnt ] = i ] = i - 1;   for( int j = 1 ; i * p[ j ] <= n ; j++ )   {    if( i % p[ j ] == 0 )    {     phi[ i * p[ j ] ] = phi[ i ] * p[ j ];     break;    }    phi[ i * p[ j ] ] = phi[ i ] * ( p[ j ] - 1 );   }  }  for( int i = 1 ; i <= n ; i++ )  {   int t = C( i << 1, i );   for( int j = i, k = 1 ; j <= n ; j += i, k++ )    if( i & 1 ) dec( g[ j ], 1LL * phi[ k ] * t % mod );    else inc( g[ j ], 1LL * phi[ k ] * t % mod );   if( i & 1 ) g[ i ] = ( mod - g[ i ] ) % mod;   g[ i ] = 1LL * g[ i ] * inv[ i << 1 ] % mod;  } }  inline void solve(int l, int r) {  if( l == r ) { f[ l ] = 1LL * f[ l ] * inv[ l ] % mod; return ; }  int mid = l + r >> 1;  solve( l, mid );  for( NTT::n = 1, NTT::L = 0 ; NTT::n <= r - l + 1 ; NTT::n <<= 1 ) NTT::L++;  NTT::getR();  for( int i = 0 ; i < NTT::n ; i++ )   a[ i ] = i + l <= mid ? f[ i + l ] : 0, b[ i ] = ( i + l + 1 ) <= r ? g[ i + 1 ] : 0;  NTT::mul( c, a, b );  for( int i = mid + 1 ; i <= r ; i++ )   inc( f[ i ], c[ i - l - 1 ] );  solve( mid + 1, r ); }  int main() {  n = read();  init();  solve( 0, n );  return printf( "%d\n", f[ n ] ), 0; }

 

Round #14难点与标程,
“玲珑杯”算法竞技 Round #14 By:wxh010910 Start Time: 2017-05-13
16:00:00 End Time: 2017-05-13 18:30:00 Refre…

 
            “玲珑杯”算法竞赛 Round #14By:wxh010910

“玲珑杯”算法比赛 Round #14By:wxh010910

1000 – Spoon Devil’s 3-D Matrix

 
Start Time:2017-05-13
16:00:00 End
Time:2017-05-13
18:30:00 Refresh
Time:2017-05-20
09:51:24 Public

Start Time:2017-05-13
16:00:00End
Time:2017-05-13
18:30:00Refresh
Time:2017-05-20
09:51:24Public

Time Limit:1s Memory Limit:32MByte

 

灵活OJ比赛提交地址:

Submissions:208Solved:65

 

Round#14题解:

DESCRIPTION

 玲珑OJ竞技提交地址:

A — No Game No Life

Spoon Devil build a 3-D matrix, and he(or she) wants to know if he
builds some bases what’s the shortest distance to connect all of them.

     
Round#14题解: 

Time Limit:1sMemory Limit:256MByte

INPUT

 

Submissions:473Solved:226

There are multiple test cases. The first line of input contains an
integer T

A — No Game No Life

DESCRIPTION

, indicating the number of test cases. For each test case:The first line
contains one integer n (0<n<50),
indicating the number of all points. Then the next n
lines, each lines contains three numbers xi,yi,zi
indicating the position of i

Time Limit:1s Memory Limit:256MByte

一对叫做 的哥哥和四嫂玩游戏非常的厉害,组成代表队吊打全部人,

-th point.

Submissions:473Solved:226

不过具体世界对她们很不友好,所以她们就去了异世界,

OUTPUT

 

分外异世界有拾陆个种族,不可能打仗,只好玩游戏。

For each test case, output a line, which should accurately rounded to
two decimals.

DESCRIPTION

有二次他们和数据结构种族的人较量,看什么人写数据结构写得快,那时候出现了如此一道题:澳门新萄京 6

SAMPLE INPUT

一对叫做 的哥哥和三姐玩游戏非常厉害,组成代表队吊打全部人,

给多个连串a,每一回多个操作。

221 1 02 2 031 2 30 0 01 1 1

只是实际世界对她们很不协和,所以他们就去了异世界,

1、把持有数字x形成y2、询问系列叁个职责上边包车型客车值

SAMPLE OUTPUT

老大异世界有十五个种族,不可能战役,只好玩游戏。

INPUT第一行四个数n,m第二行n个数表示a连串前面有m行,每行格式为1 x y要么2
x各自表示把具备值为x的数变成y或然理解种类上x地方的数值OUTPUT对于每一种2操作,即摸底,输出三个数表示答案SAMPLE
INPUT5 55 5 5 5 52 31 5 22 31 8 32 1SAMPLE OUTPUT522HINTn,m <= 一千,
a[i] <= 一千000000你当作堂姐自然要AC掉那题啦SOLUTION“玲珑杯”ACM竞技Round #14

1.413.97

有三遍他们和数据结构种族的人较量,看何人写数据结构写得快,那时候现身了那样一道题:澳门新萄京 6

标程:

SOLUTION

给叁个连串a,每回八个操作。

#include <bits/stdc++.h> #define MAXN 100010 using namespace std;  int n , m , a[ MAXN ]; map < int , int > wocaonimalegebia;  inline int read() { register int x = 0 , ch = getchar(); while( !isdigit ch = getchar(); while( isdigit x = x * 10 + ch - '0' , ch = getchar(); return x; }  int main() { n = read() , m = read(); for( register int i = 1 ; i <= n ; i++ ) a[i] = read() , wocaonimalegebia[ a[i] ] = a[i]; while if == 1 ) { int x = read(); wocaonimalegebia[x] = read(); } else printf( "%d\n" , wocaonimalegebia[ a[ read; return 0; }

“玲珑杯”acm比赛-试运维赛

1、把富有数字x造成y2、询问种类贰个地点上面的值

B — RE:从零开始的异世界生活

思路:

INPUT

Time Limit:1sMemory Limit:256MByte

三个维度点的MST(Krusal)

先是行多少个数n,m第二行n个数表示a类别前边有m行,

Submissions:368Solved:52

#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MAXN=55;
const int MAXM=1200;
int pre[MAXN];
struct node
{
    double x,y,z;
    node()
    {
        x=y=z=0;
    }
}Node[MAXN];
struct edge
{
    int s,e;
    double d;
    edge()
    {
        s=e=d=0;
    }
}Edge[MAXM];
bool cmp(edge a, edge b)
{
    return a.d<b.d;
}
int father(int x)
{
    if(pre[x]==x)
        return x;
    else
    {
        pre[x]=father(pre[x]);
        return pre[x];
    }
}
double krusal(int n)
{
    double cost=0;
    for(int i=0;i<MAXN;i++)pre[i]=i;
    int cnt=0;
    int index=0;
    while(cnt<n-1)
    {
        int ps=father(Edge[index].s);
        int pe=father(Edge[index].e);
        if(ps!=pe)
        {
            pre[ps]=pe;
            cost+=Edge[index].d;
            cnt++;
        }
        index++;
    }
    return cost;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf%lf",&Node[i].x,&Node[i].y,&Node[i].z);
        }
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                Edge[cnt].s=i;Edge[cnt].e=j;
                Edge[cnt].d=sqrt(pow(fabs(Node[i].x-Node[j].x),2.0)+pow(fabs(Node[i].y-Node[j].y),2.0)+pow(fabs(Node[i].z-Node[j].z),2.0));
                cnt++;
            }
        }
        sort(Edge,Edge+cnt,cmp);
        printf("%.2lf\n",krusal(n));
    }
    return 0;
}

每行格式为1 x y或然2
x独家代表把全体值为x的数形成y只怕打听连串上x地点的数值

DESCRIPTION

OUTPUT

486到了异世界,看到了一批可爱的阿妹比如蕾姆啊,Aimee莉亚啊,Lamb啊,白鲸啊,怠惰啊等等!
有一天膜女告诉486说她的本领只怕不可能再用了,因为膜女在动脑筋一个数据结构题,没心绪管486了。
486说自身来帮您做,膜女说您很棒棒哦!
澳门新萄京 8

对此各种2操作,即摸底,输出三个数表示答案

给三个聚众,最发轫为空
多少个操作:

SAMPLE INPUT

1、插入x
2、把小于x的数形成x
3、把大于x的数变成x
4、求会集中第x小数
5、求群集中型小型于x的数个数

5 55 5 5 5 52 31 5 22 31 8 32 1

INPUT第一行叁个数m前面有m行,每行格式为opt
x,opt表示是哪些操作,x表示操作的值OUTPUT对于每一个4,5操作,输出三个值表示答案SAMPLE
INPUT51 11 34 12 334 1SAMPLE OUTPUT133HINTm <= 一千00 , x <=
一千000000SOLUTION“玲珑杯”ACM比赛 Round #14
标程:

SAMPLE OUTPUT

#include <bits/stdc++.h> #define ratio 4 #define MAXN 1000010 #define merge new_Node( a -> size + b -> size , b -> value , a , b ) #define new_Node( s , v , a , b ) ( & ( * st[ cnt++ ] = Node( s , v , a , b ) ) ) #define update if( cur -> left -> size ) cur -> size = cur -> left -> size + cur -> right -> size , cur -> value = cur -> right -> value;  using namespace std;  struct Node { int size , value; Node * left , * right; Node( int s , int v , Node * a , Node * b ) : size , value , left , right {} Node() {} } * root , * null , * st[300000] , t[300000];  int n , m , x , cnt;  int find( int x , Node * cur ) { if( !cur -> left -> size ) return cur -> value; return x > cur -> left -> size ? find( x - cur -> left -> size , cur -> right ) : find( x , cur -> left ); }  int zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( int x , Node * cur ) { if( !cur -> left -> size ) return ( x > cur -> value ) * cur -> size; return x > cur -> left -> value ? zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( x , cur -> right ) + cur -> left -> size : zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( x , cur -> left ); }  void split( int x , Node * cur ) { if( x > cur -> left -> size ) split( x - cur -> left -> size , cur -> right ) , cur -> left = merge( cur -> left , cur -> right -> left ) , st[ --cnt ] = cur -> right , cur -> right = cur -> right -> right; else if( x < cur -> left -> size ) split( x , cur -> left ) , cur -> right = merge( cur -> left -> right , cur -> right ) , st[ --cnt ] = cur -> left , cur -> left = cur -> left -> left; }  void insert( int x , Node * cur ) { if( !cur -> left -> size ) if( cur -> value < x ) cur -> left = new_Node( cur -> size , cur -> value , null , null ) , cur -> right = new_Node( 1 , x , null , null ); else cur -> left = new_Node( 1 , x , null , null ) , cur -> right = new_Node( cur -> size , cur -> value , null , null ); else insert( x , x > cur -> left -> value ? cur -> right : cur -> left ); update; }  void dispose( Node * cur ) { if( cur -> left -> size ) st[ --cnt ] = cur -> left , st[ --cnt ] = cur -> right , dispose( cur -> left ) , dispose( cur -> right ); }  inline void low { Node * cur = root; int s = zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( x + 1 , cur ); if; else if( s == cur -> size ) dispose , * cur = Node( s , x , null , null ); else split( s , cur ) , dispose( cur -> left ) , * cur -> left = Node( s , x , null , null ); }  inline void up { Node * cur = root; int s = zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa( x + 1 , cur ); if dispose , * cur = Node( cur -> size , x , null , null ); else if( s == cur -> size ); else split( s , cur ) , dispose( cur -> right ) , * cur -> right = Node( cur -> size - s , x , null , null ); }  struct io { char ibuf[1 << 23] , * s , obuf[1 << 22] , * t; int a[24]; io() : t { fread( s = ibuf , 1 , 1 << 23 , stdin ); } ~io() { fwrite( obuf , 1 , t - obuf , stdout ); } inline int read()  { register int u = 0; while( * s < 48 ) s++; while( * s > 32 ) u = u * 10 + * s++ - 48; return u; } template< class T > inline void print( register T u ) { static int * q = a; if * t++ = 48; else { if( u < 0 ) * t++ = 45 , u *= -1; while * q++ = u % 10 + 48 , u /= 10; while * t++ = * --q; } * t++ = '\n'; } } ip;  #define read ip.read #define print ip.print  int main() { m = read(); for( register int i = 0 ; i < 300000 ; i++ ) st[i] = & t[i]; null = new_Node( 0 , 0 , 0 , 0 ); while { int opt = read(); if( opt == 1 ) if insert , root ); else root = new_Node( 1 , read() , null , null ); else if( opt == 2 ) low; else if( opt == 3 ) up; else if( opt == 4 ) print( find , root ) ); else print( zhentamashabibuyaoxiajibaqibianlaingminghaobuhaoa , root ) ); } return 0; }

522

C — Another

HINT

Time Limit:3sMemory Limit:256MByte

n,m <= 1000, a[i] <= 一千000000您作为二嫂自然要AC掉那题啦

Submissions:230Solved:20

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图