首页 > 代码库 > hdu--4407--一不留神就TLE了
hdu--4407--一不留神就TLE了
相比于上次我做过的一个容斥题 和他很相似 就是多了一个modify操作
不过也不难 只要 通过 加加减减 操作就能完成了
这个操作 我想过很多种方法 最后觉得用Map迭代访问是最好的选择
如果遍历x->y这个区间 因为y<=400000可能会太大
如果我记录操作1之前执行了多少次的操作2 然后来访问这些操作2 但是可能同一个位置上的数据被多次修改 这样统计也会出错
这边 使用map还有一个原因 就是操作总共也就1000次 那么我最差的情况也就是修改了999次 询问了1次 那map里面最多也就是插入了999个元素 很快的
------
然后我的tle也是发生在了map身上 还是我自己的思维不好 这个加加减减操作被我搞复杂了 后来去看了别人的 瞬间 fml
1 void modify( LL x , LL y , LL p ) 2 { 3 LL a , b c , d; 4 map<LL,LL>::iterator it; 5 for( it=mp.begin();it!=mp.end();it++ ) 6 { 7 c = it->first; 8 d = it-second; 9 a = gcd( c , p );10 b = gcd( d , p );11 if( it->first == it->second || it->first<=x-1 || it->first >y )12 {13 continue;14 }15 else if( a==1 )16 {17 if( b==1 )18 ans = ans - c + d;19 else20 ans = ans - c;21 }22 else23 {24 if( b==1 )25 ans = ans + d;26 }27 }28 }
1 void modify( LL x , LL y , LL p ) 2 { 3 map<LL,LL>::iterator it; 4 for( it=mp.begin();it!=mp.end();it++ ) 5 { 6 if( it->first == it->second || it->first<=x-1 || it->first >y ) 7 { 8 continue; 9 }10 if( gcd(it->first,p)==1 )11 ans-=it->first;12 if( gcd(it->second,p)==1 )13 ans+=it->second;14 }15 }
第一个 罗里吧嗦的版本就是我写的 真TM 又臭又长啊 害我TLE了
1 #include <iostream> 2 #include <map> 3 #include <vector> 4 using namespace std; 5 6 typedef long long LL; 7 LL ans; 8 vector<int> ve; 9 map<LL,LL>mp; 10 void getPrime( int n ) 11 { 12 for( int i = 2 ; i<=n/i ; i++ ) 13 { 14 if( n%i==0 ) 15 { 16 ve.push_back( i ); 17 while( n%i==0 ) 18 n /= i; 19 } 20 } 21 if( n>1 ) 22 ve.push_back( n ); 23 } 24 25 LL gcd( LL x , LL y ) 26 { 27 return x % y == 0 ? y : gcd( y , x%y ); 28 } 29 30 LL solve( LL x ) 31 { 32 LL ans = 0 , var , num; 33 int veSize = ve.size() , cnt; 34 for( int i = 1 ; i<( 1<<veSize ) ; i++ ) 35 { 36 var = 1; 37 cnt = 0; 38 for( int j = 0 ; j<veSize ; j++ ) 39 { 40 if( i&(1<<j) ) 41 { 42 var = (LL) (var * ve[j]); 43 ++ cnt; 44 } 45 } 46 num = x / var; 47 if( cnt&1 ) 48 ans += num * ( var + num * var ) / 2; 49 else 50 ans -= num * ( var + num * var ) / 2; 51 } 52 return ans; 53 } 54 55 void modify( LL x , LL y , LL p ) 56 { 57 map<LL,LL>::iterator it; 58 for( it=mp.begin();it!=mp.end();it++ ) 59 { 60 if( it->first == it->second || it->first<=x-1 || it->first >y ) 61 { 62 continue; 63 } 64 if( gcd(it->first,p)==1 ) 65 ans-=it->first; 66 if( gcd(it->second,p)==1 ) 67 ans+=it->second; 68 } 69 } 70 71 int main() 72 { 73 cin.sync_with_stdio(false); 74 int t , n , m , op; 75 LL x , y , p , c , ans1 , ans2 , sum1 , sum2; 76 cin >> t; 77 while( t-- ) 78 { 79 cin >> n >> m; 80 mp.clear(); 81 while( m-- ) 82 { 83 cin >> op; 84 if( op==1 ) 85 { 86 cin >> x >> y >> p; 87 ve.clear( ); 88 getPrime( p ); 89 sum1 = (x-1) * x / 2; 90 ans1 = solve( x-1 ); 91 sum2 = y * (y+1) / 2; 92 ans2 = solve( y ); 93 ans = sum2 - ans2 - ( sum1 - ans1 ); 94 modify( x , y , p ); 95 cout << ans << endl; 96 } 97 else 98 { 99 cin >> x >> c;100 mp[x] = c;101 }102 }103 }104 return 0;105 }
这种题目 还有一个很烦的地方就是 要用到long long或者__int64来处理
today:
对于 性格 外向的女生 毫无 招架之力
hdu--4407--一不留神就TLE了
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。