ecjtu-summer training #3-白红宇

ecjtu-summer training #3

阅读量：4663 次

发布时间：2019-06-09

本文共 6166 字，大约阅读时间需要 20 分钟。

选择排序或冒泡排序下就行，看交换的次数。（如果数量很多时可以用树状数组来求逆对数）

1 #include 
     
       2 #define ll long long 3 using namespace std; 4 int a[1010]; 5 int main(){ 6     int n; 7     while(scanf("%d",&n)!=EOF){ 8         for(int i = 0; i < n; i ++){ 9             //scanf("%d",a[i]);10             cin>>a[i];11         }12         ll ans = 0;13         for(int i =0; i < n; i ++){14             for(int j = i+1; j 
      
       a[j]){16                     ans++;17                     swap(a[i],a[j]);18                 }19             }20         }21         cout << ans << endl;22         //printf("")23     }24     return 0;25 }

就这题卡主了，数学差写了一个小时多都没有写出来，赛后发现有R>=r这个条件，可惜比赛时没有看到，想复杂了。

二分就可以做出来。

1 #include 
     
       2 #define ll long long 3 using namespace std; 4 double r,R,h,v; 5 const double ef = 1e-9; 6 const double PI = acos(-1); 7 double fun(double xx){ 8     double RR = xx/h*(R-r)+r; 9     return PI*(RR*RR+r*r+RR*r)*xx/3.0;10 }11 12 int main(){13     int n;14     cin>>n;15     while(n--){16         cin>>r>>R>>h>>v;17         double l = 0, r = 100,mid;18         while(r-l>ef){19             mid = (l+r)/2;20             if(fun(mid) < v) l = mid;21             else r = mid;22         }23         printf("%.6lf\n",mid);24     }25     return 0;26 }

水题，可就是W了一次，不知咋地int就是过不了，long long 就过了，别人int都可以过。

1 #include 
     
       2 #define ll long long 3 using namespace std; 4  5 int main(){ 6     ll n,a,b; 7     //scanf("%d",&n); 8     cin>>n; 9     while(n--){10         //scanf("%d%d",&a,&b);11         cin>>a>>b;12         for(ll c = 1; ; c ++){13             if(c!= b && __gcd(a,c) == b){14                 //printf("%d\n",c);15                 cout << c << endl;16                 break;17             }18         }19     }20     return 0;21 }

签到题，所以简单些。算下谁的时间短就行。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define ll long long 5 using namespace std; 6  7 int main(){ 8     int n; 9     cin>>n;10     while(n--){11         int h1,h2,m2,m1,s1,s2;12         cin >> h1>>m1>>s1>>h2>>m2>>s2;13         int ans1 = h1*3600+m1*60+s1;14         int ans2 = h2*3600+m2*60+s2;15         if(ans1 > ans2){16             printf("Player2\n");17         }else if(ans1 == ans2){18             printf("Tie\n");19         }else if(ans1 < ans2){20             printf("Player1\n");21         }22     }23     return 0;24 }

线段树的模板题，求一个区间内的最大差，不过赛后题解说RMQ也可以，没听过，要去学学了。还有线段树要复习复习了，模板题都写了半个小时多，一直调试错误。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define rson m+1,r,rt<<1|1 5 #define lson l,m,rt<<1 6 using namespace std; 7 const int MAX = 2e5+10; 8 int cow1[MAX<<2],cow2[MAX<<2]; 9 10 void Push(int rt){11     cow1[rt] = min(cow1[rt<<1],cow1[rt<<1|1]);12     cow2[rt] = max(cow2[rt<<1],cow2[rt<<1|1]);13 }14 void build(int l,int r, int rt){15     if(r == l){16         scanf("%d",&cow1[rt]);17         cow2[rt] = cow1[rt];18         //printf(" %d  %d\n",l,rt);19         return;20     }21     int m = (l+r)/2;22     build(lson);23     build(rson);24     Push(rt);25 }26 27 int query(int l, int r, int rt, int LL, int RR){28     //cout << l << ' ' << r << endl;29     if(LL <= l && r <= RR){30         //printf("%d\n",rt);31         return cow2[rt];32     }33     int m = (l+r)/2;34     int MAX = -1;35     if(m >= LL) MAX = max(MAX,query(lson,LL,RR));36     if(m < RR) MAX = max(MAX,query(rson,LL,RR));37     return MAX;38 }39 int query1(int l, int r, int rt, int LL, int RR){40     if(LL <= l && r <= RR){41         //printf("%d\n",rt);42         return cow1[rt];43     }44     int m = (l+r)/2;45     int MIN = 100000000;46     if(m >= LL) MIN = min(MIN,query1(lson,LL,RR));47     if(m < RR) MIN = min(MIN,query1(rson,LL,RR));48     return MIN;49 }50 int main(){51     int n, q;52     cin >>n>>q;53     build(1,n,1);54     while(q--){55         int ll,rr;56         scanf("%d%d",&ll,&rr);57         int MAX = query(1,n,1,ll,rr);58         int MIN = query1(1,n,1,ll,rr);59         //cout << MAX << ' ' << MIN << endl;60         printf("%d\n",MAX - MIN);61     }62 }

-------------------------------------------更新线----------------------------------------------------

RMQ算法就是用来求区间最大最小值的，与这题只好符合。下面贴下代码：

有个细节要注意下，加减法比位运算高，1<<(j-1)+i就相当于1<<(j-1+i)了，所以要写成(1<<(j-1))+i这个地方坑了我好久。

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int n,q,dmin[50010][25],dmax[50010][25],a[50010]; 5 void init(){ 6     for(int i = 1; i <= n; i ++){ 7         dmin[i][0] = dmax[i][0] = a[i]; 8     } 9     for(int j = 1; (1<
       
        <= n; j ++){10         for(int i = 1; i+(1<
        
         <= n; i ++){11             dmin[i][j] = min(dmin[i][j-1],dmin[(1<<(j-1))+i][j-1]);12             dmax[i][j] = max(dmax[i][j-1],dmax[(1<<(j-1))+i][j-1]);13         }14     }15 }16 int getValue(int l, int r){17     int k = 0;18     while(1<<(k+1) <= (r-l+1))k++;19     //cout << max(dmax[l][k],dmax[r-(1<
         
          << ' ' << min(dmin[l][k],dmin[r-(1<
          
           << endl;20 return max(dmax[l][k],dmax[r-(1<
           
            <

-------------------------------------------------------------------------------------------------------

‘#’是墙，'.'是路，@是人，求人可以走多少个'.'，直接dfs就可以了，也要复习复习了，好久没写一写就好多错误。

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int n, m, ans; 5 char a[50][50]; 6 int dx[] = {
   1, 0, -1, 0}, dy[] = {
   0, -1, 0, 1}; 7 void dfs(int x, int y){ 8     a[x][y] = '#'; 9     for(int i = 0; i < 4; i ++){10         int nx = x + dx[i], ny = y + dy[i];11         if(0 <= nx && nx < n && 0 <= ny && ny < m && a[nx][ny] == '.'){12             ans ++;13             dfs(nx,ny);14         }15     }16 }17 int main(){18     while(~scanf("%d%d",&m,&n)&&m&&n){19         ans = 1;20         for(int i = 0; i < n; i ++) cin >> a[i];21         int nx, ny;22         for(int i = 0; i < n; i ++){23             for(int j = 0; j < m; j ++){24                 if(a[i][j] == '@'){25                     nx = i; ny = j;26                     goto tt;27                 }28             }29         }30         tt: ;31         dfs(nx, ny);32         cout << ans << endl;33     }34 }

转载于:https://www.cnblogs.com/xingkongyihao/p/7132909.html

你可能感兴趣的文章

数据结构和算法单向链表一之单向链表的简单实现