Codeforces Round #494 (Div. 3)

刚好在考完当天有一场div3，就开了个小号打了，打的途中被辅导员喊去帮忙，搞了二十分钟-_-||，最后就出了四题，题解如下：
题目链接：http://codeforces.com/contest/1003

题目：

思路：求众数出现的次数

代码如下：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 #define debug(x) cout <<"[" <<x <<"]" <<endl

 const int inf = 0x3f3f3f3f;

 const int maxn = 1e5 + ;

 int n;

 int a[], vis[];

 int main() {

     cin >>n;

     int mx = -;

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

         cin >>a[i];

         vis[a[i]]++;

         if(mx < vis[a[i]]) {

             mx = vis[a[i]];

         }

     }

     cout <<mx <<endl;

     return ;

 }

题目：

思路：构造一个01串，其中0的个数为a,1的个数为b，中间刚好有k次01的交替，题目保证有解。模拟即可。

代码实现如下：

 #include <bits/stdc++.h>

 using namespace std;

 int a, b, x, flag;

 int vis[];

 int main() {

     cin >> a >> b >> x;

     int flag = x & ;

     if(a >= b) {

         vis[] = ;

         a--;

         for(int i = ; i < x; i++) {

             vis[i] = !vis[i-];

             if(i & ) b--;

             else a--;

         }

         for(int i = ; i < x; i++) {

             cout <<vis[i];

         }

         if(flag) {

             for(int i = ; i < a; i++) {

                 cout <<"";

             }

             for(int i = ; i < b; i++) {

                 cout <<"";

             }

         } else {

             for(int i = ; i < b; i++) {

                 cout <<"";

             }

             for(int i = ; i < a; i++) {

                 cout <<"";

             }

         }

         cout <<endl;

     } else {

         vis[] = ;

         b--;

         for(int i = ; i < x; i++) {

             vis[i] = !vis[i-];

             if(i & ) a--;

             else b--;

         }

         for(int i = ; i < x; i++) {

             cout <<vis[i];

         }

         if(flag) {

             for(int i = ; i < b; i++) {

                 cout <<"";

             }

             for(int i = ; i < a; i++) {

                 cout <<"";

             }

         } else {

             for(int i = ; i < a; i++) {

                 cout <<"";

             }

             for(int i = ; i < b; i++) {

                 cout <<"";

             }

         }

         cout <<endl;

     }

     return ;

 }

题目：

思路：求长度大于等于k的连续字串的平均值的最大值，因为本题数据小，可以用n^2水过，数据大了需要用二分，这里就只贴比赛时写的n^2的代码了~先用一个前缀和来维护分子，分母用一个循环处理。

代码如下：

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn =  * ;

 const double eps = 1e-;

 int n, k;

 double ans;

 int a[maxn], sum[maxn];

 int main() {

     scanf("%d%d", &n, &k);

     sum[] = ;

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

         scanf("%d", &a[i]);

         sum[i] = sum[i-] + a[i];

     }

     ans = -;

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

         for(int j = k; j <= n; j++) {

             double t = 1.0 * (sum[i + j - ] - sum[i-]) / j;

             if(t - ans >= eps) {

                 ans = t;

             }

         }

     }

     printf("%.7f\n", ans);

     return ;

 }

题目：

题意：给你n个数，ai保证是2的幂次，q次查询，每次查询给你一个数x，问使用最少的a来组成这个数，如果无法组成就输出-1.

思路：先将ai转换成2^t，用个数组来储存；将x转换成二进制，然后从最大为开始贪心，当题目给的某一次方（t次方）不够时，就用2个t-1次方来构成一个t次方，最后判断0次方是否足够即可。用样例来解释：题目给的2的1次方有2个，2次方有2个，3次方有1个。第一个x的二进制为1000，需要一个2的3次方，题目给的刚好有一个3次方，因此答案为1；第二个x的二进制为101，需要2的2次方1个，0次方1个，2次方足够，但是没有0次方，所以答案为-1；第三个x的二进制为1110，需要1个3次方，1个2次方，1个1次方，均足够，故为3。

代码实现如下：

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = 2e5 + ;

 int n, q, t;

 int a[maxn], b[maxn], num[], p[];

 long long vis[maxn];

 void prepare() {

     vis[] = ;

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

         vis[i] = vis[i-] * ;

     }

 }

 int main() {

     prepare();

     cin >>n >>q;

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

         cin >>a[i];

         t = lower_bound(vis, vis + , a[i]) - vis;

         num[t]++;

     }

     for(int i = ; i < q; i++) {

         cin >>b[i];

         int k = , ans = ;

         while(b[i]) {

             p[k++] = b[i] % ;

             b[i] = b[i] / ;

         }

         for(int j = k - ; j >= ; j--) {

             if(num[j] < p[j]) {

                 ans += num[j];

                 p[j-] +=  * (p[j] - num[j]);

             } else {

                 ans += p[j];

             }

         }

         if(num[] < p[]) cout <<"-1" <<endl;

         else cout <<ans + p[] <<endl;

     }

     return ;

 }

赛后补题，一定要假装出是自己比赛时A的~

题目：

题意：生成一棵树，树的直径（本题的直径是指两节点间距离的最大值）为d，度数不超过k。

思路：首先生成一条链，此处节点分别为1~d+1，然后以这条链上的节点为根生成树，用dfs处理，此处生成的树的深度为min(i-1,d-i+1)（因为两节点间的距离不能超过d嘛~），注意处理NO的情况。

代码实现如下：

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = 4e5 + ;

 int n, k, d, cnt;

 vector<int> G[maxn];

 void dfs(int u, int deep, int mx) {

     if(deep == mx) return;

     for(int i = ; i < k -  - (deep == ) && cnt < n; i++) {

         int v = ++cnt;

         G[u].push_back(v);

         dfs(v, deep + , mx);

     }

 }

 int main() {

     cin >>n >>d >>k;

     if(k==){

         if(n!= || d!=)printf("NO\n");

         else printf("YES\n1 2\n");

         return ;

     }

     if(d >= n) {

         cout <<"NO" <<endl;

         return ;

     }

     for(int i = ; i <= d; i++) {

         G[i].push_back(i+);

     }

     cnt = d + ;

     for(int i = ; i <= d + ; i++) {

         dfs(i, , min(i - , d - i + ));

     }

     if(cnt < n) {

         cout <<"NO" <<endl;

         return ;

     }

     cout <<"YES" <<endl;

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

         for(int j = ; j < G[i].size(); j++) {

             cout <<i <<" " <<G[i][j] <<endl;

         }

     }

     return ;

 }

巴特西

Codeforces Round #494 (Div. 3)

最新文章

热门文章