Codeforces Round #540 (Div. 3)题解

2023-07-29 08:26:58

题目链接：

　　https://codeforces.com/contest/1118

A题：

Codeforces Round #540 (Div. 3)题解

题意：

　　q次查询，给你一个n，要你用1和2来凑出n，1的花费为a，2的花费为b，求花费的最小值。

思路：

　　我们知道当2*a<=b时全用1来肯定是最优的，当2*a>b时，若n为奇数就是1个1其他全是2，若n为偶数就全都是2这样是最优的。

代码实现如下：

 #include <set>

 #include <map>

 #include <deque>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <ctime>

 #include <bitset>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 typedef pair<LL, LL> pLL;

 typedef pair<LL, int> pLi;

 typedef pair<int, LL> pil;;

 typedef pair<int, int> pii;

 typedef unsigned long long uLL;

 #define lson rt<<1

 #define rson rt<<1|1

 #define lowbit(x) x&(-x)

 #define name2str(name) (#name)

 #define bug printf("*********\n")

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

 #define FIN freopen("D://code//in.txt","r",stdin)

 #define IO ios::sync_with_stdio(false),cin.tie(0)

 const double eps = 1e-;

 const int mod = ;

 const int maxn = 2e5 + ;

 const double pi = acos(-);

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3fLL;

 int q;

 LL n, a, b;

 int main(){

     scanf("%d", &q);

     while(q--) {

         scanf("%lld%lld%lld", &n, &a, &b);

         LL ans = ;

         if( * a <= b) {

             ans = n * a;

         } else {

             ans = n /  * b + (n % ) * a;

         }

         printf("%lld\n", ans);

     }

     return ;

 }

B题：

Codeforces Round #540 (Div. 3)题解

Codeforces Round #540 (Div. 3)题解

题意：

　　给你n个数，要你去掉一个数，然后剩余的n-1个数保持相对顺序不变，问有多少种方案使得剩下的数中奇数项的和等于偶数项的和。

思路：

　　我们知道去掉一个数后对前面的数的位置的奇偶性不会产生影响，后面的数的位置的奇偶性变为对立的，因此我们只需要求下奇数项和偶数项的前缀和即可。

代码实现如下：

 #include <set>

 #include <map>

 #include <deque>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <ctime>

 #include <bitset>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 typedef pair<LL, LL> pLL;

 typedef pair<LL, int> pLi;

 typedef pair<int, LL> pil;;

 typedef pair<int, int> pii;

 typedef unsigned long long uLL;

 #define lson rt<<1

 #define rson rt<<1|1

 #define lowbit(x) x&(-x)

 #define name2str(name) (#name)

 #define bug printf("*********\n")

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

 #define FIN freopen("D://code//in.txt","r",stdin)

 #define IO ios::sync_with_stdio(false),cin.tie(0)

 const double eps = 1e-;

 const int mod = ;

 const int maxn = 2e5 + ;

 const double pi = acos(-);

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3fLL;

 int n;

 LL a[maxn], sum1[maxn], sum2[maxn];

 int main(){

     scanf("%d", &n);

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

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

         sum1[i] = sum1[i-];

         sum2[i] = sum2[i-];

         if(i & ) sum1[i] += a[i];

         else sum2[i] += a[i];

     }

     int ans = ;

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

         if(sum1[i-] + sum2[n] - sum2[i] == sum2[i-] + sum1[n] - sum1[i]) {

             ans++;

         }

     }

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

     return ;

 }

C题：

Codeforces Round #540 (Div. 3)题解

Codeforces Round #540 (Div. 3)题解

题意：

　　给你n*n个数要你构建一个每行每列都是回文的矩阵。

思路：

　　模拟即可。

代码实现如下：

 #include <set>

 #include <map>

 #include <deque>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <ctime>

 #include <bitset>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 typedef pair<LL, LL> pLL;

 typedef pair<LL, int> pLi;

 typedef pair<int, LL> pil;;

 typedef pair<int, int> pii;

 typedef unsigned long long uLL;

 #define lson rt<<1

 #define rson rt<<1|1

 #define lowbit(x) x&(-x)

 #define name2str(name) (#name)

 #define bug printf("*********\n")

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

 #define FIN freopen("D://code//in.txt","r",stdin)

 #define IO ios::sync_with_stdio(false),cin.tie(0)

 const double eps = 1e-;

 const int mod = ;

 const int maxn = 2e5 + ;

 const double pi = acos(-);

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3fLL;

 int n, x;

 int mp[][], cnt[];

 int main(){

     scanf("%d", &n);

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

         scanf("%d", &x);

         cnt[x]++;

     }

     if(n %  == ) {

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

             if(cnt[i] %  != ) {

                 return printf("NO\n") * ;

             }

         }

         int pp = ;

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

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

                 while(cnt[pp] == ) pp++;

                 mp[i][j] = mp[i][n-j+] = mp[n-i+][j] = mp[n-i+][n-j+] = pp;

                 cnt[pp] -= ;

             }

         }

     } else {

         int num1 = , num2 = , num3 = ;

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

             if(cnt[i] %  == ) num1++;

             else if(cnt[i] %  == ) num2++;

             else if(cnt[i] %  == ) num3++;

         }

         if(num2 > (n-) || (num1 >  && num3 > ) || (num1 ==  && num3 != ) || (num3 ==  && num1 != )) return printf("NO\n") * ;

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

             if(cnt[i] %  ==  || cnt[i] %  == ) {

                 mp[n/+][n/+] = i;

                 cnt[i]--;

                 break;

             }

         }

         int pp = ;

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

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

                 while(cnt[pp] < ) pp++;

                 mp[i][j] = mp[i][n-j+] = mp[n-i+][j] = mp[n-i+][n-j+] = pp;

                 cnt[pp] -= ;

             }

         }

         pp = ;

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

             while(cnt[pp] == ) {

                 pp++;

                 if(pp > ) return printf("NO\n") * ;

             }

             mp[i][n/+] = mp[n-i+][n/+] = pp;

             cnt[pp] -= ;

         }

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

             while(cnt[pp] < ) {

                 pp++;

                 if(pp > ) return printf("NO\n") * ;

             }

             if(pp > ) return printf("NO\n") * ;

             mp[n/+][i] = mp[n/+][n-i+] = pp;

             cnt[pp] -= ;

         }

     }

     printf("YES\n");

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

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

             printf("%d ", mp[i][j]);

         }

         printf("\n");

     }

     return ;

 }

D题：

Codeforces Round #540 (Div. 3)题解

Codeforces Round #540 (Div. 3)题解

题意：

　　有n杯咖啡，m页作业，每杯咖啡的权值为ai，假如你某一天喝了k杯咖啡那么你写的作业页数为a1,a2-1,a3-2……这里的1,2,3指当天喝的顺序而非原序列的下标，要你用最少的天数写完作业。

思路：

　　先将ai从大到小排序，二分天数，然后把所有会产生正贡献的咖啡求和，与m比较即可。

代码实现如下：

 #include <set>

 #include <map>

 #include <deque>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <ctime>

 #include <bitset>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 typedef pair<LL, LL> pLL;

 typedef pair<LL, int> pLi;

 typedef pair<int, LL> pil;;

 typedef pair<int, int> pii;

 typedef unsigned long long uLL;

 #define lson rt<<1

 #define rson rt<<1|1

 #define lowbit(x) x&(-x)

 #define name2str(name) (#name)

 #define bug printf("*********\n")

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

 #define FIN freopen("D://code//in.txt","r",stdin)

 #define IO ios::sync_with_stdio(false),cin.tie(0)

 const double eps = 1e-;

 const int mod = ;

 const int maxn = 2e5 + ;

 const double pi = acos(-);

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3fLL;

 int n, m;

 int a[maxn];

 bool check(int x) {

     int tmp = ;

     LL sum = ;

     for(int i = ; i <= min(n, x); i++) {

         sum += a[i];

     }

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

         if(i % x ==  || x == ) tmp++;

         if(a[i] - tmp > ) {

             sum += a[i] - tmp;

         } else {

             break;

         }

     }

     return sum >= m;

 }

 bool cmp(int a, int b) {

     return a > b;

 }

 int main(){

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

     LL sum = ;

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

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

         sum += a[i];

     }

     sort(a + , a + n + , cmp);

     if(sum < m) {

         return printf("-1\n") * ;

     }

     int ub = inf, lb = , mid, ans = ;

     while(ub >= lb) {

         mid = (ub + lb) >> ;

         if(check(mid)) {

             ub = mid - ;

             ans = mid;

         } else {

             lb = mid + ;

         }

     }

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

     return ;

 }

E题：

Codeforces Round #540 (Div. 3)题解

Codeforces Round #540 (Div. 3)题解

题意：

　　给你n和k，要你构建n对数，假设第i对为ai，bi，第j对为aj，bj，需满足一下条件：

  1. ai!=bi;
  2. ai==aj与bi==bj不能同时成立；
  3. 若j==i+1时，ai!=aj且bi!=bj。

思路：

　　第一个数一直是1~k的循环，第二个数则是2~k~1,3~k~2,4~k~2这样循环，我们知道满足题意的总排列对数只有k*(k-1)种（第一位放置方法有k种选择，第二位也有k种，故总的排列方法是k*k，其中只有1-1,2-2这种是不满足要求的），因此当n>k*(k-1)时输出NO。

代码实现如下：

 #include<bits/stdc++.h>

 using namespace std;

 int n,k;

 pair<int,int> ans[];

 int main(){

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

     if(n>1LL*k*(k-)) return puts("NO")*;

     int a=,x=,y=;

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

         ans[i]={x,y};

         x++,y++;

         if(x>k) x = ;

         if(y>k) y =;

         if(y==a) {

             a++;

             if(a>k) a=;

             y = a;

         }

     }

     puts("YES");

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

         printf("%d %d\n",ans[i].first,ans[i].second);

     }

     return ;

 }

F1题：

Codeforces Round #540 (Div. 3)题解

Codeforces Round #540 (Div. 3)题解

题意：

　　给你一棵树，每个结点的颜色可以是0,1,2，要你删除一条边使得得到的两个联通块内不能同时出现1和2。

思路：

　　dfs记一下子树中的1和2的个数与总的1和2的个数比较即可。

代码实现如下：

 #include <set>

 #include <map>

 #include <deque>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <ctime>

 #include <bitset>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 typedef pair<LL, LL> pLL;

 typedef pair<LL, int> pLi;

 typedef pair<int, LL> pil;;

 typedef pair<int, int> pii;

 typedef unsigned long long uLL;

 #define lson rt<<1

 #define rson rt<<1|1

 #define lowbit(x) x&(-x)

 #define name2str(name) (#name)

 #define bug printf("*********\n")

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

 #define FIN freopen("D://code//in.txt","r",stdin)

 #define IO ios::sync_with_stdio(false),cin.tie(0)

 const double eps = 1e-;

 const int mod = ;

 const int maxn = 3e5 + ;

 const double pi = acos(-);

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3fLL;

 int n, u, v, num1, num2;

 LL ans = ;

 int a[maxn], sum1[maxn], sum2[maxn];

 vector<int> G[maxn];

 void dfs(int u, int p) {

     if(a[u] == ) sum1[u]++;

     else if(a[u] == ) sum2[u]++;

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

         int v = G[u][i];

         if(v == p) continue;

         dfs(v, u);

         if((sum1[v] == num1 && sum2[v] == ) || (sum2[v] == num2 && sum1[v] == )) ans++;

         sum1[u] += sum1[v], sum2[u] += sum2[v];

     }

 }

 int main(){

     scanf("%d", &n);

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

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

         if(a[i] == ) num1++;

         else if(a[i] == ) num2++;

     }

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

         scanf("%d%d", &u, &v);

         G[u].push_back(v);

         G[v].push_back(u);

     }

     dfs(, );

     printf("%lld\n", ans);

     return ;

 }
上一篇：FromBottomToTop第十二周项目博客


下一篇：Sencha touch中Ext.List的使用及高度自适应