Codeforces Round #472 (rated, Div. 2, based on VK Cup 2018 Round 2)-白红宇

Codeforces Round #472 (rated, Div. 2, based on VK Cup 2018 Round 2)

阅读量：5153 次

发布时间：2019-06-13

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

题解：分类讨论。注意题目要求，至少有两种方案。

1 #pragma warning(disable:4996) 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 using namespace std; 8  9 int n, m;10 string s;11 12 int main()13 {14     while (cin >> n) {15         cin >> s;16         int cnt = 0;17         for (int i = 0; i < n; i++) if (s[i] == '?') cnt++;18         if (!cnt) printf("No\n");19         else {20             bool flag1 = false;21             bool flag2 = true;22             for (int i = 1; i < n; i++) {23                 if (s[i] == s[i - 1] && s[i] == '?') flag1 = true;24                 if (s[i] == s[i - 1] && s[i] != '?') flag2 = false;25             }26             if (!flag2) printf("No\n");27             else {28                 if (flag1) printf("Yes\n");29                 else {30                     bool flag3 = false;31                     for (int i = 1; i < n - 1; i++) {32                         if (s[i] == '?') {33                             if (s[i - 1] == s[i + 1]) flag3 = true;34                         }35                     }36                     if (s[0] == '?' || s[n - 1] == '?') flag3 = true;37                     if (!flag3) printf("No\n");38                     else printf("Yes\n");39                 }40             }41         }42     }43     return 0;44 }

题解：对于同一列的"#"所在行应该是对称的。

1 #pragma warning(disable:4996) 2 #include 3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 #include
           
             9 #include
            
             10 #include
             
              11 using namespace std;12 13 const int maxn = 60;14 15 int n, m;16 int mp[maxn][maxn];17 18 int main()19 {20 scanf("%d%d", &n, &m);21 getchar();22 for (int i = 1; i <= n; i++) {23 for (int j = 1; j <= m; j++)24 mp[i][j] = (getchar() == '#');25 getchar();26 }27 for (int i = 1; i <= n; i++) {28 for (int j = i + 1; j <= n; j++) {29 bool flag1 = true, flag2 = true;30 for (int k = 1; k <= m; k++) {31 if (mp[i][k] != mp[j][k]) flag1 = false;32 if (mp[i][k] && mp[j][k]) flag2 = false;33 }34 if (!flag1 && !flag2) { puts("No"); return 0; }35 }36 }37 puts("Yes"); return 0;38 }

题解：分析式子，当 E_j 选定后，i=j-1，所以只需要考虑 E_k ,显然 k 的位置离 j 越远答案越优。

注意：精度。

1 #pragma warning(disable:4996) 2 #include 3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 #include
           
             9 #include
            
             10 using namespace std;11 typedef long long ll;12 13 const int maxn = 1e5 + 5;14 15 16 int n, U;17 int a[maxn];18 19 int main()20 {21 while (scanf("%d%d", &n, &U) != EOF) {22 for (int i = 1; i <= n; i++) scanf("%d", a + i);23 double ans = 0;24 for (int i = 2; i < n; i++) {25 int p = lower_bound(a + 1, a + n + 1, a[i - 1] + U) - (a);26 27 if (a[p] != a[i - 1] + U) p--;28 if (p == i) continue;29 30 double tp = 1.0*(a[p] - a[i]) / (a[p] - a[i - 1]);31 ans = max(ans, tp);32 }33 if (!ans) printf("-1\n");34 else printf("%.12lf\n", ans);35 }36 return 0;37 }