博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
Codeforces Round #533 (Div. 2) 部分题解A~D
阅读量：6592 次
发布时间：2019-06-24

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

A. Salem and Sticks

题目描述

Salem gave you n n n sticks with integer positive lengths a1,a2,…,an a_1, a_2, \ldots, a_n a1​,a2​,…,an​ .

For every stick, you can change its length to any other positive integer length (that is, either shrink or stretch it). The cost of changing the stick's length from a a a to b b b is ∣a−b∣ |a - b| ∣a−b∣ , where ∣x∣ |x| ∣x∣ means the absolute value of x x x .

A stick length ai a_i ai​ is called almost good for some integer t t t if ∣ai−t∣≤1 |a_i - t| \le 1 ∣ai​−t∣≤1 .

Salem asks you to change the lengths of some sticks (possibly all or none), such that all sticks' lengths are almost good for some positive integer t t t and the total cost of changing is minimum possible. The value of t t t is not fixed in advance and you can choose it as any positive integer.

As an answer, print the value of t t t and the minimum cost. If there are multiple optimal choices for t t t , print any of them.

输入输出格式

输入格式：

The first line contains a single integer n n n ( 1≤n≤1000 1 \le n \le 1000 1≤n≤1000 ) — the number of sticks.

The second line contains n n n integers ai a_i ai​ ( 1≤ai≤100 1 \le a_i \le 100 1≤ai​≤100 ) — the lengths of the sticks.

输出格式：

Print the value of t t t and the minimum possible cost. If there are multiple optimal choices for t t t , print any of them.

输入输出样例

输入样例#1： 
310 1 4
输出样例#1： 
3 7
输入样例#2： 
51 1 2 2 3
输出样例#2： 
2 0 直接暴力遍历就行了；
#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        //#include
                        
                         //#pragma GCC optimize(2)using namespace std;#define maxn 1000005#define inf 0x7fffffff//#define INF 1e18#define rdint(x) scanf("%d",&x)#define rdllt(x) scanf("%lld",&x)#define rdult(x) scanf("%lu",&x)#define rdlf(x) scanf("%lf",&x)#define rdstr(x) scanf("%s",x)typedef long long ll;typedef unsigned long long ull;typedef unsigned int U;#define ms(x) memset((x),0,sizeof(x))const long long int mod = 1e9 + 7;#define Mod 1000000000#define sq(x) (x)*(x)#define eps 1e-4typedef pair
                         
                           pii;#define pi acos(-1.0)//const int N = 1005;#define REP(i,n) for(int i=0;i<(n);i++)typedef pair
                          
                            pii;inline ll rd() { ll x = 0; char c = getchar(); bool f = false; while (!isdigit(c)) { if (c == '-') f = true; c = getchar(); } while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return f ? -x : x;}ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b);}int sqr(int x) { return x * x; }/*ll ans;ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ans = exgcd(b, a%b, x, y); ll t = x; x = y; y = t - a / b * y; return ans;}*/int n;int a[maxn];int main() { //ios::sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; i++)rdint(a[i]); int t = 0; int minn = inf; int pos = 0; for (t = 1; t <= 101; t++) { int sum = 0; for (int i = 1; i <= n; i++) { sum += min(abs(a[i] - t), min(abs(a[i] - (t - 1)), abs(a[i] - (t + 1)))); } if (sum < minn) { minn = sum; pos = t; } } cout << pos << ' ' << minn << endl; return 0;}

 

 

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        //#include
                        
                         //#pragma GCC optimize(2)using namespace std;#define maxn 1000005#define inf 0x7fffffff//#define INF 1e18#define rdint(x) scanf("%d",&x)#define rdllt(x) scanf("%lld",&x)#define rdult(x) scanf("%lu",&x)#define rdlf(x) scanf("%lf",&x)#define rdstr(x) scanf("%s",x)typedef long long ll;typedef unsigned long long ull;typedef unsigned int U;#define ms(x) memset((x),0,sizeof(x))const long long int mod = 1e9 + 7;#define Mod 1000000000#define sq(x) (x)*(x)#define eps 1e-4typedef pair
                         
                           pii;#define pi acos(-1.0)//const int N = 1005;#define REP(i,n) for(int i=0;i<(n);i++)typedef pair
                          
                            pii;inline ll rd() { ll x = 0; char c = getchar(); bool f = false; while (!isdigit(c)) { if (c == '-') f = true; c = getchar(); } while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return f ? -x : x;}ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b);}int sqr(int x) { return x * x; }/*ll ans;ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ans = exgcd(b, a%b, x, y); ll t = x; x = y; y = t - a / b * y; return ans;}*/int n, k;string s;map
                           
                            mp;int main() { //ios::sync_with_stdio(0); cin >> n >> k; cin >> s; int ans = 0; int maxx = -inf; int cnt = 1; int len = 1; for (int i = 1; i < n; i++) { if (s[i] == s[i - 1]) { len++; cnt++; if (i == n - 1) { mp[s[i - 1]] += len / k; } } else { mp[s[i - 1]] += len / k; len = 1; cnt = 1; } } if (n == 1 && k == 1) { cout << 1 << endl; return 0; } for (char ch = 'a'; ch <= 'z'; ch++) { maxx = max(maxx, mp[ch]); } cout << max(0, maxx) << endl; return 0;}

 

套路的DP？

设 dp[ i ][ j ]表示前i 个数余数为j的方案数；

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        //#include
                        
                         //#pragma GCC optimize(2)using namespace std;#define maxn 1000005#define inf 0x7fffffff//#define INF 1e18#define rdint(x) scanf("%d",&x)#define rdllt(x) scanf("%lld",&x)#define rdult(x) scanf("%lu",&x)#define rdlf(x) scanf("%lf",&x)#define rdstr(x) scanf("%s",x)typedef long long ll;typedef unsigned long long ull;typedef unsigned int U;#define ms(x) memset((x),0,sizeof(x))const long long int mod = 1e9 + 7;#define Mod 1000000000#define sq(x) (x)*(x)#define eps 1e-4typedef pair
                         
                           pii;#define pi acos(-1.0)//const int N = 1005;#define REP(i,n) for(int i=0;i<(n);i++)typedef pair
                          
                            pii;inline ll rd() { ll x = 0; char c = getchar(); bool f = false; while (!isdigit(c)) { if (c == '-') f = true; c = getchar(); } while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return f ? -x : x;}ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b);}int sqr(int x) { return x * x; }/*ll ans;ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ans = exgcd(b, a%b, x, y); ll t = x; x = y; y = t - a / b * y; return ans;}*/int n;int l, r;ll dp[maxn][3];int main() { //ios::sync_with_stdio(0); cin >> n >> l >> r; dp[1][0] = r / 3 - l / 3; dp[1][1] = dp[1][0]; if (r % 3 > 0)dp[1][1]++; if (l % 3 > 1)dp[1][1]--; dp[1][2] = dp[1][0]; if (r % 3 == 2)dp[1][2] ++; if (l % 3 == 0)dp[1][0]++; for (int i = 2; i <= n; i++) { dp[i][0] = ((dp[i - 1][0] * (dp[1][0]) % mod) + (dp[i - 1][1] * dp[1][2]) % mod + (dp[i - 1][2] * dp[1][1]) % mod) % mod; dp[i][1] = ((dp[i - 1][0] * (dp[1][1]) % mod) + (dp[i - 1][1] * dp[1][0]) % mod + (dp[i - 1][2] * dp[1][2]) % mod) % mod; dp[i][2] = ((dp[i - 1][0] * (dp[1][2]) % mod) + (dp[i - 1][1] * dp[1][1]) % mod + (dp[i - 1][2] * dp[1][0]) % mod) % mod; } cout << (ll)dp[n][0] % mod << endl; return 0;}

 

多源bfs就行了；

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       
                        //#include
                        
                         //#pragma GCC optimize(2)using namespace std;#define maxn 200005#define inf 0x7fffffff//#define INF 1e18#define rdint(x) scanf("%d",&x)#define rdllt(x) scanf("%lld",&x)#define rdult(x) scanf("%lu",&x)#define rdlf(x) scanf("%lf",&x)#define rdstr(x) scanf("%s",x)typedef long long ll;typedef unsigned long long ull;typedef unsigned int U;#define ms(x) memset((x),0,sizeof(x))const long long int mod = 1e9 + 7;#define Mod 1000000000#define sq(x) (x)*(x)#define eps 1e-4typedef pair
                         
                           pii;#define pi acos(-1.0)//const int N = 1005;#define REP(i,n) for(int i=0;i<(n);i++)typedef pair
                          
                            pii;inline ll rd() { ll x = 0; char c = getchar(); bool f = false; while (!isdigit(c)) { if (c == '-') f = true; c = getchar(); } while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return f ? -x : x;}ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b);}int sqr(int x) { return x * x; }/*ll ans;ll exgcd(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ans = exgcd(b, a%b, x, y); ll t = x; x = y; y = t - a / b * y; return ans;}*/int vis[1002][1002];bool used[1002][1002];int dis[10][1002][1002];int n, m;int p;int s[10];vector
                           
                            vc[10];int ans[10];char chp[1003][1003];int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };bool OK(int x, int y) { return x <= n && x >= 1 && y >= 1 && y <= m;}int main() { ios::sync_with_stdio(0); cin >> n >> m >> p; for (int i = 1; i <= p; i++)cin >> s[i]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> chp[i][j]; if (!(chp[i][j] == '.') && !(chp[i][j] == '#')) { used[i][j] = chp[i][j] - '0'; ans[chp[i][j] - '0']++; vc[chp[i][j]-'0'].push_back(make_pair(i, j)); } } } for (int i = 1; i <= p; i++)memset(dis[i], 0x3f, sizeof(dis[i])); while (1) { int fg = 0; for (int i = 1; i <= p; i++) { queue
                            
                             qu; for (auto it : vc[i]) { int tmpx = it.first; int tmpy = it.second; dis[i][tmpx][tmpy] = 0; qu.push(make_pair(tmpx, tmpy)); } vc[i].clear(); while (!qu.empty()) { int x = qu.front().first; int y = qu.front().second; qu.pop(); if (dis[i][x][y] + 1 > s[i]) { continue; } for (int j = 0; j < 4; j++) { int nx = x + dx[j]; int ny = y + dy[j]; if (!used[nx][ny] && chp[nx][ny] == '.'&&dis[i][nx][ny] > dis[i][x][y] + 1&&OK(nx,ny)) { dis[i][nx][ny] = dis[i][x][y] + 1; vis[nx][ny] = 1; fg = 1; ans[i]++; used[nx][ny] = 1; qu.push(make_pair(nx, ny)); vc[i].push_back(make_pair(nx, ny)); } } } } if (fg == 0)break; } for (int i = 1; i <= p; i++) { cout << ans[i] << ' '; } return 0;}

 

 
    
 
   
 
   
       
   
 
  
 
  
转载于:https://www.cnblogs.com/zxyqzy/p/10297314.html
 

        

        

            你可能感兴趣的文章
        

        
            

                
词法分析与语法分析简介

                
查看>>

            

        
            

                
JS中的默认行为

                
查看>>

            

        
            

                
Checkio代码闯关小计

                
查看>>

            

        
            

                
从oracle到mysql，主从到分库，一个普通项目数据库架构的变迁

                
查看>>

            

        
            

                
从零开始学wordpress 之四

                
查看>>

            

        
            

                
[LeetCode] Course Schedule

                
查看>>

            

        
            

                
selenium层级定位及鼠标键盘操作

                
查看>>

            

        
            

                
SpringBoot跨域问题解决方案

                
查看>>

            

        
            

                
（转载）hibernate3.0配置文件模板

                
查看>>

            

        
            

                
46、练习：输出指定目录下的所有文件名称

                
查看>>

            

        
            

                
IP地址与数字地址相互转换

                
查看>>

            

        
            

                
Knockout.Js官网学习（创建自定义绑定）

                
查看>>

            

        
            

                
win10 x64中 windbg x64 安装配置符号库

                
查看>>

            

        
            

                
python 抽象类、抽象方法、接口、依赖注入、SOLIP

                
查看>>

            

        
            

                
笔记1

                
查看>>

            

        
            

                
POJ1068 Parencodings 解题报告

                
查看>>

            

        
            

                
字符串连接[不用库函数]

                
查看>>

            

        
            

                
使用Hystrix实现自动降级与依赖隔离-微服务

                
查看>>

            

        
            

                
Parcelbale接口

                
查看>>

            

        
            

                
新建一个express工程，node app无反应

                
查看>>

            

        
    






    

            

                
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

                

                    当前时间: 2025-01-23 17:53:13  
                    当前IP: 3.14.255.181  
                    联系邮箱:javaeecc@qq.com
                        Copyright © 2020 - 2022 baihongyu.com
                    京ICP备2021015314号-2
                

            


                
                    

                    强烈建议你试试无所不能的CHAT-GPT，快点击我
                    

                
                
                    

                        强烈建议你试试无所不能的CHAT-GPT，快点击我