牛客小白月赛16-白红宇

牛客小白月赛16

阅读量：4622 次

发布时间：2019-06-09

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

A、小石的签到题

思路：签到题。简单列举一下即可发现当且仅当 $n == 1$ 时，先手小石必输，其他情况下都必赢！

AC代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 13 #include 
                  
                   14 #include 
                   
                    15 #include 
                    
                     16 #include 
                     
                      17 using namespace std;18 typedef long long LL;19 typedef unsigned long long ULL;20 const double eps = 1e-6;21 const double PI = acos(-1.0);22 const int maxn = 1e5+5;23 const int inf = 0x3f3f3f3f;24 25 int n;26 27 int main(){28 while(cin >> n) {29 if(n == 1)cout <<"Yang" << endl;30 else cout << "Shi" <

View Code

B、小雨的三角形

思路：暴力就完事了！+1

AC代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 13 #include 
                  
                   14 #include 
                   
                    15 #include 
                    
                     16 #include 
                     
                      17 using namespace std;18 typedef long long LL;19 typedef unsigned long long ULL;20 const double eps = 1e-6;21 const double PI = acos(-1.0);22 const int maxn = 1e5+5;23 const int inf = 0x3f3f3f3f;24 const LL mod = 1e9+7;25 26 int n, m, x, y;27 LL mp[1005][1005], ans[1005];28 29 int main(){30 memset(mp, 0, sizeof(mp));31 mp[1][1] = 1;32 mp[2][1] = mp[2][2] = 2;33 for(int i = 3; i <= 1000; ++i) mp[i][1] = mp[i][i]= i;34 for(int i = 3; i <= 1000; ++i) {35 for(int j = 2; j < i; ++j) {36 mp[i][j] = (mp[i - 1][j] + mp[i - 1][j - 1] ) % mod;37 }38 }39 memset(ans, 0, sizeof(ans));40 for(int i = 1; i <= 1000; ++i) {41 for(int j = 1; j <= i; ++j) {42 ans[i] = (ans[i] + mp[i][j]) % mod;43 }44 }45 while(cin >> n >> m) {46 for(int i = 1; i <= m; ++i) {47 cin >> x >> y;48 LL res = 0;49 for(int i = x; i <= y; ++i) {50 res = (res + ans[i]) % mod;51 }52 cout << res << endl;53 }54 }55 return 0;56 }

View Code

C、小石的海岛之旅

思路：暴力就完事了！+2

AC代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 13 #include 
                  
                   14 #include 
                   
                    15 #include 
                    
                     16 #include 
                     
                      17 using namespace std;18 typedef long long LL;19 typedef unsigned long long ULL;20 const double eps = 1e-6;21 const double PI = acos(-1.0);22 const int maxn = 1e5+5;23 const int inf = 0x3f3f3f3f;24 25 int n, m, a, cnt, h[1005];26 27 int main(){28 while(cin >> n >> m) {29 for(int i = 0; i < n; ++i) cin >> h[i];30 for(int i = 1; i <= m; ++i) {31 cin >> a;32 cnt = 0;33 bool flag = false;34 for(int i = 0; i < n; ++i) {35 if(a < h[i] && !flag) ++cnt, flag = true;36 else if(a >= h[i] && flag) flag = false;37 }38 cout << cnt << endl;39 }40 }41 return 0;42 }

View Code

D、小阳买水果

思路：前缀和的差即所求答案 $ [k, i] = [1, i] - [1, k) , ( k \leq i) $，关键点：维护一个不增序列a和最长连续子序列的和大于0。因为要求最长连续子序列（区间和大于0）的长度，那么对于第 i 个数，从不增序列a中找到一个小于当前前缀和 $ sum_i $ 的最小值，因为是不增序列，所以可以用二分来查找这个最小值的位置。为什么要维护这么一个不增序列呢？如果能从 $ [1, i - 1] $ 找到，因为从小 ---> 变大，那么所求区间 $ [k , i] $ 中所有元素的和一定是正数，也就是在他满意的条件下即可求出最长连续子序列的长度！

AC代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 13 #include 
                  
                   14 #include 
                   
                    15 #include 
                    
                     16 #include 
                     
                      17 #include 
                      
                       18 using namespace std;19 typedef long long LL;20 typedef unsigned long long ULL;21 const int dir[4][2] = { {-1, 0}, { 0, 1}, { 1, 0}, { 0, -1}}; // 上右下左22 const int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; // 马可走的八个方向23 const int my[8] = {-2, -1, 1, 2, 2, 1, -1, -2};24 const double eps = 1e-6;25 const double PI = acos(-1.0);26 const int maxn = 2e6+5;27 const int inf = 0x3f3f3f3f;28 29 int n, x, sum, res, lt, rt, ans, mid, a[maxn];30 31 int main() {32 while(~scanf("%d", &n)) {33 memset(a, 0, sizeof(a));34 ans = sum = 0;35 for(int i = 1; i <= n; ++i) {36 scanf("%d", &x);37 sum += x; // 前i个数的前缀和38 a[i] = min(a[i - 1], sum); // 维护不增序列39 lt = 0, rt = i - 1, res = -1; 40 while(lt <= rt) { // 从不增序列中找出最小值41 mid = (lt + rt) >> 1;42 if(a[mid] >= sum) lt = mid + 1;43 else rt = mid - 1, res = mid;44 }45 if(res != -1) ans = max(ans, i - res); 46 }47 printf("%d\n", ans);48 }49 return 0;50 }

View Code

E、小雨的矩阵

思路：深搜入门题！

AC代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 13 #include 
                  
                   14 #include 
                   
                    15 #include 
                    
                     16 #include 
                     
                      17 #include 
                      
                       18 using namespace std;19 typedef long long LL;20 typedef unsigned long long ULL;21 const int dir[4][2] = { {-1, 0}, { 0, 1}, { 1, 0}, { 0, -1}}; // 上右下左22 const int mx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; // 马可走的八个方向23 const int my[8] = {-2, -1, 1, 2, 2, 1, -1, -2};24 const double eps = 1e-6;25 const double PI = acos(-1.0);26 const int maxn = 1e5+5;27 const int inf = 0x3f3f3f3f;28 29 int n, a[10][10];30 set
                       
                         syt;31 32 bool check(int x, int y) {33 if(x < 0 || y < 0 || x >= n || y >= n) return false;34 return true;35 }36 37 void dfs(int x, int y, int sum) {38 if(x == n - 1 && y == n - 1) {39 syt.insert(sum);40 return;41 }42 for(int i = 1; i <= 2; ++i) {43 int dx = x + dir[i][0], dy = y + dir[i][1];44 if(check(dx, dy)) dfs(dx, dy, sum + a[dx][dy]);45 }46 }47 48 int main() {49 while(cin >> n) {50 syt.clear();51 for(int i = 0; i < n; ++i) {52 for(int j = 0; j < n; ++j) {53 cin >> a[i][j];54 }55 }56 dfs(0, 0, a[0][0]);57 cout << syt.size() << endl;58 }59 return 0;60 }

View Code

G、小石的图形

思路：小学数学，当且仅当绳子围成半圆时面积最大！

AC代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 13 #include 
                  
                   14 #include 
                   
                    15 #include 
                    
                     16 #include 
                     
                      17 using namespace std;18 typedef long long LL;19 typedef unsigned long long ULL;20 const double eps = 1e-6;21 const double PI = acos(-1.0);22 const int maxn = 1e5+5;23 const int inf = 0x3f3f3f3f;24 const LL mod = 1e9+7;25 26 int n;27 28 int main(){29 while(cin >> n) {30 printf("%.3f\n", 0.5 * n * n / PI);31 }32 return 0;33 }

View Code

转载于:https://www.cnblogs.com/acgoto/p/11180306.html

你可能感兴趣的文章