AtCoder Beginner Contest 114 Solution

Solved.

     #include <bits/stdc++.h>

     using namespace std;

     int mp[];

     int main()

     {

         mp[] = mp[] = mp[] = ;

         int x; cin >> x;

         puts(mp[x] ? "YES" : "NO");

     }

B 754

Solved.

     #include <bits/stdc++.h>

     using namespace std;

     char s[];

     int f(int x)

     {

         int res = ;

         for (int i = ; i < ; ++i) res = res *  + s[i + x] - '';

         return res;

     }

     int main()

     {

         while (scanf("%s", s + ) != EOF)

         {

             int res = 0x3f3f3f3f, len = strlen(s + );

             for (int i = ; i <= len - ; ++i) res = min(res, abs(f(i) - ));

             printf("%d\n", res);

         }

         return ;

     }

C 755

Solved.

题意：

找出$[1, n]中有多少个只由'7', '5', '3' 组成，并且每个字符至少出现一次的数$

思路：

这样的数不会太多，DFS构造，然后二分

     #include <bits/stdc++.h>

     using namespace std;

     vector <int> v;

     bool ok(int x)

     {

         int flag[] = {false};

         while (x)

         {

             flag[x % ] = ;

             x /= ;

         }

         if (flag[] ==  || flag[] ==  || flag[] == ) return false;

         return true;

     }

     void DFS(int cur, int num)

     {

         if (cur == )

         {

             if (ok(num)) v.push_back(num);

             return;

         }

         DFS(cur + , num);

         DFS(cur + , num *  + );

         DFS(cur + , num *  + );

         DFS(cur + , num *  + );

     }

     int main()

     {

         DFS(, );

         sort(v.begin(), v.end());

         v.erase(unique(v.begin(), v.end()), v.end());

         int n;

         while (scanf("%d", &n) != EOF) printf("%d\n", (int)(upper_bound(v.begin(), v.end(), n) - v.begin()));

         return ;

     }

D 756

Upsolved.

题意：

有$N!中所有因子中，有多少因子其拥有的因子个数恰好为75个$

思路：

我们考虑$75 = 75 \cdot 1 = 25 \cdot 3 = 15 \cdot 5 = 5 \cdot 5 \cdot 3$

那么我们处理出$N!中每个质因子一共有多少个，然后考虑质因子个数如何组成因子个数$

考虑一个数$x = a_1^{p_1} \cdot a_2^{p_2} \cdot a_3^{p_3}$

那么$a_1 可以提供的因子个数为 (p_1 + 1) 那么x 的因子个数即 (p_1 \cdot p_2 \cdot p_3)$

然后简单组合一下就可以了

         #include <bits/stdc++.h>

         using namespace std;

         int n;

         int cnt[];

         int tot[];

         int f(int l, int r)

         {

             int res = ;

             for (int i = l; i <= r; ++i) res += tot[i];

             return res;

         }

         int main()

         {

             while (scanf("%d", &n) != EOF)

             {

                 memset(cnt, , sizeof cnt);

                 memset(tot, , sizeof tot);

                 for (int i = ; i <= n; ++i)

                 {

                     int tmp = i;

                     for(int j = ; ; ++j)

                     {

                         while (tmp % j == )

                         {

                             ++cnt[j];

                             tmp /= j;

                         }

                         if (tmp == ) break;

                     }

                 }

                 for (int i = ; i <= ; ++i) ++tot[cnt[i] + ];

                 int res = f(, );

                 res += f(, ) * f(, );

                 res += f(, ) * (f(, ) - );

                 res += f(, ) * f(, );

                 res += f(, ) * (f(, ) - );

                 res += (f(, ) * (f(, ) - ) / ) * f(, );

                 res += ((f(, ) * (f(, ) - ) / ) * (f(, ) - ));

                 printf("%d\n", res);

             }

             return ;

         }

巴特西

AtCoder Beginner Contest 114 Solution

最新文章

热门文章