[机房测试]10.21
ssw02为了保持csp前rp的稳定，又来写博客了
欢迎转载ssw02的博客:https://www.cnblogs.com/ssw02/p/11716560.html
斐波那契
思路很不错的一道题。
第一眼，waa好难啊。然后，等等，这几项的差怎么都是斐波拉契数呢？然后ssw02模拟了一下，好像是找第一个小于这个数的斐波拉契数，他们的差值就是他的父亲节点。然后写了个暴力对拍掉即可。
代码
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
inline ll read(){
ll s=0 ; char g=getchar() ; while( g>'9'||g<'0' )g=getchar() ;
while( g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s ;
}
ll f[61] , N , m1 , m2 ;//59
void prepare(){
f[0] = f[1] = 1LL ;
for( int i = 2 ; i <= 60 ; ++i )f[i] = f[i-1] + f[i-2] ;
}
inline ll find( ll x ){
int l = 1 , r = 60 , ans = r , mid ;
while( l <= r ){
mid = (l+r)>>1 ;
if( f[mid] < x )ans = mid , l = mid+1 ; else r = mid-1 ;
}
return f[ans] ;
}
inline ll work( ll x , ll y ){
while( x != y ){
if( x < y)swap( x , y ) ;
x -= find(x) ;
}
return x ;
}
int main(){
freopen("fibonacci.in","r",stdin);
freopen("fibonacci.out","w",stdout);
prepare() ;
N = read() ;
while( N-- ){
m1 = read() , m2 = read() ;
printf("%lld
",work(m1,m2) ) ;
}
return 0 ;
}
数颜色
ssw02学数据结构学疯了。
最早开的就是T2，当时先看到，嗯嗯嗯，这不是树套树吗？不可做。。
等等，好像这个相邻交换有点东西，好像有点思路。。。
苦思冥想半天想不出数据结构的优化。。
然后形心态崩了，分块空间不够啊，然后ssw02写了个65分带修莫队，最后还多了5分，改块大小2600后还得了75分。。
#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 300005 ;
inline int read(){
int s=0 ; char g=getchar() ; while( g>'9'||g<'0' )g=getchar() ;
while( g>='0'&&g<='9' )s=s*10+g-'0',g=getchar() ; return s ;
}
int N , M , block , a[ MAXN ] , cnt[ MAXN ] , pos[ MAXN ] , ans[MAXN];
int ask , tim ;
struct ap{
int l , r , id , tim , col ;
}t[MAXN];
struct sp{
int pos , aft ;
}q[MAXN];
inline bool cmp( ap x , ap y ){
if( pos[x.l]!=pos[y.l] )return pos[x.l]<pos[y.l] ;
if( pos[x.r]!=pos[y.r] )return pos[x.r]<pos[y.r] ;
return x.tim < y.tim ;
}
void updata( int x , int opt ){
if( opt ){cnt[ a[x] ]++ ;return ;}
cnt[a[x]]-- ;
}
inline void change( int now , int i ){
if( q[now].pos == t[i].l-1 )cnt[ a[ q[now].pos ] ]++ , cnt[ a[ q[now].aft ] ]-- ;
else if( q[now].pos == t[i].r )cnt[ a[ q[now].pos ] ]-- , cnt[ a[ q[now].aft ] ]++ ;
swap( a[ q[now].pos ] , a[ q[now].aft ] ) ;
}
void Mo(){
for( register int i=1,l=1,r=0,now=0;i<=ask;++i ){
while( l<t[i].l )updata( l++ , 0 ) ; while( l>t[i].l )updata( --l , 1 ) ;
while( r<t[i].r )updata( ++r , 1 ) ; while( r>t[i].r )updata( r-- , 0 ) ;
while( now < t[i].tim )change( ++now , i ) ; while( now > t[i].tim )change( now-- , i ) ;
ans[ t[i].id ] = cnt[ t[i].col ] ;
}
}
int main(){
N = read() , M = read() , block = 2600 ; int m1 , m2 , m3 ;
for( register int i = 1 ; i <= N ; ++i )a[i] = read(),pos[i] = (i-1)/block+1 ;
for( register int i = 1 ; i <= M ; ++i ){
m1 = read() ;
if( m1==1 )t[++ask].l=read(),t[ask].r=read(),t[ask].col=read(),t[ask].id=ask,t[ask].tim=tim ;
else q[++tim].pos = read() , q[tim].aft = q[tim].pos+1 ;
}
sort( t+1 , t+ask+1 , cmp ) ;
Mo() ;
for( register int i = 1 ; i <= ask ; ++i )printf("%d
",ans[i]) ;
}
正解嘛，用vector，由于相邻交换仍然具有单调性。然后就暴力修改vector。
ssw02 STL菜出水平啊。
#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 300005 ;
inline int read(){
int s=0 ; char g=getchar() ; while( g>'9'||g<'0' )g=getchar() ;
while( g>='0'&&g<='9' )s=s*10+g-'0',g=getchar() ; return s ;
}
int N , M , a[MAXN] ;
vector<int>q[MAXN] ;
int main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
N = read() , M = read() ; int m1 , m2 , m3 , m4 ;
for( int i = 1 ; i <= N ; ++i ){
a[i] = read() ; q[ a[i] ].push_back(i) ;
}
while( M-- ){
m1 = read() ;
if( m1 == 1 ){
m2 = read() , m3 = read() , m4 = read() ;
int l = lower_bound( q[m4].begin() , q[m4].end() , m2 ) - q[m4].begin() ;
int r = upper_bound( q[m4].begin() , q[m4].end() , m3 ) - q[m4].begin()-1 ;
printf("%d
",max( r-l+1,0 ) ) ;
}
else{
m2 = read() ;
m3 = lower_bound( q[a[m2]].begin(),q[a[m2]].end(),m2)-q[a[m2]].begin() ;
q[ a[m2] ][ m3 ]++ ;
m2++ ;
m3 = lower_bound( q[a[m2]].begin(),q[a[m2]].end(),m2)-q[a[m2]].begin() ;
q[ a[m2] ][ m3 ]-- ;
swap( a[m2],a[m2-1] ) ;
}
}
return 0 ;
}
分组
其实ssw02是打了40分的，不过ssw02菜得精彩，然后爆0了。
K = 1 和 K = 2 肯定是不同算法。
K = 1 ，我们只要暴力枚举 1~512 的平方数即可（这个思想和 小清新人渣的本愿 有点像）
最小字典序，倒叙枚举即可，否则我们会多维护一个之前每个数不切实际的冲突位置。
K = 2 , 用数值并查集维护一个类似 关押罪犯 的敌对关系 。 多想想存在2个数重复的情况，细节很多。（毕竟我们维护的是下标）。