Codeforces Round #390 (Div. 2) A B C D-白红宇

Codeforces Round #390 (Div. 2) A B C D

阅读量：7202 次

发布时间：2019-06-29

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

这是一场比较难的div2 ... 比赛的时候只出了AB

A很有意思给出n个数要求随意的把相邻的数合并成任意多数最后没有为0的数输出合并区间个数与区间

可以想到0可以合到任何数上并不改变该数的性质所以如果不全是0 最后一定是有答案的把所有的0都合并到最近的非0数上去非0数不变

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;#define L long longint n ;int a[105];int l[105];int r[105];int main(){ scanf("%d",&n); for(int i = 1 ;i<=n;i++)scanf("%d",&a[i]); bool ok = true; int res = 0; int cnt = 0; for(int i = 1; i<=n;i++){ if(a[i]!= 0){ cnt ++ ; l[cnt] = i; r[cnt] = i; } } if(cnt == 0){ printf("NO\n"); return 0 ; } r[0] = 0 ; l[cnt+1] = n + 1; for(int i = 1; i<= cnt ;i ++){ l[i] = r[i-1] + 1; r[i] = l[i+1] - 1; } printf("YES\n"); printf("%d\n",cnt); for(int i = 1 ; i<=cnt ; i ++){ printf("%d %d\n",l[i],r[i]); }}

B很无聊..下三子棋现在该我们下x了能否一步胜利或者不走就胜利了呢?

写一个很手动的check函数先判断能否直接胜利再枚举每一个可以放的位置放下再check

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;#define L long longchar s[50][50];bool check(char a){ for(int i = 1 ; i<=4 ; i ++){ for(int j = 1 ; j<= 2 ; j ++ ){ if(s[i][j] == s[i][j+1] &&s[i][j+1] == s[i][j+2] && s[i][j+1] == a){ return true; } } } for(int j = 1 ; j<=4 ; j ++){ for(int i = 1 ; i<= 2 ; i ++ ){ if(s[i][j] == s[i+1][j] &&s[i+1][j] == s[i+2][j] && s[i][j] == a){ return true; } } } for(int i = 1; i<=2 ;i ++){ if(s[i][i] == s[i+1][i+1] &&s[i+1][i+1] == s[i+2][i+2] && s[i][i] == a)return true ; } if(s[2][1] == s[3][2] && s[3][2] == s[4][3] &&s[4][3] == a)return true; if(s[1][2] == s[2][3] && s[2][3] == s[3][4] &&s[3][4] == a)return true; if(s[2][4] == s[3][3] && s[3][3] == s[4][2] &&s[4][2] == a)return true; if(s[1][3] == s[2][2] && s[2][2] == s[3][1] &&s[3][1] == a)return true; if(s[1][4] == s[2][3] && s[2][3] == s[3][2] && s[3][2] == a)return true; if(s[2][3] == s[3][2] && s[3][2] == s[4][1] && s[4][1] == a)return true; return false ;}int main(){ for(int i = 1;i<=4 ; i++)scanf("%s",s[i] + 1); if(check('x')){ printf("YES\n"); return 0; } if(check('o')){ printf("NO\n"); return 0 ; } for(int i = 1 ; i <= 4;i++){ for(int j = 1 ; j<=4 ;j ++){ if(s[i][j] == '.'){ s[i][j] = 'x'; if(check('x')){ printf("YES\n"); return 0 ; } s[i][j] = '.'; } } } printf("NO\n");}

C一个比较耗费时间的字符串模拟给出一些人的名字和他们说的话有些话的发言人用?代替要求相邻的两句话不会是同一个人说的一个人说的话不会提到自己的名字

先做一个字符串模拟用map把人名编号再用r[]记录每句话的发言人用cx[][]来记录每句话中出现的人名用ans[]来处理最后的答案

最后我们会得到一个cx数组记录每句没有主人的话能选择的人

会发现贪心好像是不可做的当前这句话如果我们做出一些选择可能会影响到下一个人的选择

搜索的话如果100句话都是?也会超时

可以利用cx[][]数组和r[]数组做一个dp题

如果想不到怎么dp 可以去代码中寻找注释~

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;#define L long longstring name[1050];map
              
               p;int n , m ;char s[1050];string ans[1050];int r[1050];bool cx[105][105];int cnt ;int us[105];int main(){ int t; scanf("%d",&t); while(t -- ){ memset(r , -1 ,sizeof(r)); scanf("%d",&n); p.clear(); string tm = ""; for(int i = 1; i<=n ;i ++){ scanf("%s",s); int len = strlen(s); tm = "" ; for(int j = 0 ; j
               
                 dp[i][j] = true pre[i][j] = pre[i-1][!j] */ memset(dp , false , sizeof(dp)) ; for(int i = 1 ; i <= n ; i ++ )dp[0][i] = true ; for(int i = 1 ; i <= m ; i ++ ){ if(r[i] != -1) { if(i == 1) { dp[i][r[i]] = true ; continue ; } for(int j = 1; j <= n ; j ++ ){ if(j != r[i] && dp[i-1][j] == true) { dp[i][r[i]] = true ; pre[i][r[i]] = j ; } } continue ; } for(int j = 1; j <=n ; j ++ ){ if(cx[i][j] == true) continue ; if(j == r[i+1]) continue ; if(j == r[i-1]) continue ; for(int k = 1; k <= n ; k ++ ){ if(j == k && i != 1)continue ; if(dp[i-1][k] == true){ dp[i][j] = true ; pre[i][j] = k ; } } } } /// 利用pre数组反转录入答案 cnt = m ; bool fin = false ; for(int i = 1; i <= n ;i ++ ){ if(dp[m][i] == true){ us[cnt] = i ; int w = i; while(cnt >= 2) { int k = pre[cnt][w] ; cnt -- ; us[cnt] = k ; w = k ; } fin = true ; break ; } } if(fin == false){ printf("Impossible\n"); continue ; } ///ans for(int i = 1; i <= m ; i ++ ){ if(r[i] != -1){ cout << ans[i] << endl ; } else { cout << name[us[i]] << ans[i] << endl ; } } }}

D给出n个区间要求必须选择k个区间使这k个区间的交集最大

k个区间的交集形成的区间它的l是这几个区间中的最大的l 而r是这几个区间中的最小的r

应当选择k个区间使它们有最小的l和最大的r 所以动态的去想我们可以将l从小往大选并选择最大化的r 维护一个ans

先进行排序使l尽可能的小在其基础上r尽可能的小这样我们从1-n枚举区间就可以直接得到最大的l了

因为我们选择的l 是逐渐增大的所以为了保存足够大的r 需要一个优先队列来做维护一个 < 的优先队列存放每个区间的r

1-n枚举区间的过程每次我们选择一个区间向优先队列中压入它的r 如果当前队列的size < k 说明未达到题目要求暂且不管

如果size > k 我们就q.pop 弹出当前最小的r 由于我们是动态维护了ans 所以如果弹出最小的r 使我们失去了一个l

1 如果这个l 是当前区间最大的l 那么当前结果已经保留进了ans

2 如果这个l 不是当前区间最大的l 那么这个区间的移除会使ans增大

如果size == k 这个状态可能是size < k 或者 size > k 来的如果是前者我们就需要开始更新ans(事实上这一幕只会在第k个数字出现)

如果是后者我们就需要分析这个新区间会不会已经被弹出去了?

1 弹出去了那么现在其实没变化不需要做什么改变

2 没弹出去那么现在就需要更新一下答案我们可以肯定当前的交集区间的l 一定是新区间的l(sort的结果) 而r 就是优先队列的top 所以 res = q.top - 新区间.l + 1

判断是否弹出需要判断新区间的r与top的关系

有一个问题是新区间的r 可能已经被弹出去了当前区间并没有加进去但是因为优先队列有r=新区间.r 所以被误判

其实是不会造成影响的因为对于这种情况一定会有过去的res >= 现在的res

所以这样模拟完最后就可以得出ans了

题目要求输出一下区间的选择

如果ans是0 随便输出k个数就可以了

如果不是的话由于我们不确定当前解是不是最优解所以过程中我们无法更新区间数的ans

但是我们可以在优先队列中伴随r加上一个id 然后再跑一遍枚举当res == ans的时候队列里的id就是答案啦

聪明的你一定看到这里就完全理解了吧

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;#define L long longint n , m ;struct node { int l , r ; int id ; bool operator < (const node &a )const{ return a.r < r ; }}a[300050];bool cmp(node a, node b ){ if(a.l == b.l )return a.r < b.r ; else { return a.l < b.l ; }}int c[300050] ;int main(){ scanf("%d%d",&n, &m ); for(int i = 1; i <= n ;i ++ ){ scanf("%d%d",&a[i].l , & a[i].r ) ; a[i].id = i ; } sort(a+1,a+1+n,cmp) ; int ans = 0 ; priority_queue
              
               q; int l = 0; for(int i = 1; i <= n ; i ++ ){ node b = a[i] ; q.push(b) ; if(q.size() < m){ l = a[i].l ; } if(q.size() > m){ q.pop() ; } if(q.size() == m){ if(b.r >= q.top().r){ int res = q.top().r - b.l + 1 ; if(res > ans)ans = res ; l = b.l ; } } } printf("%d\n",ans) ; if(ans == 0){ for(int i = 1; i <= m ; i ++ ){ printf("%d",i); if(i == m)printf("\n"); else printf(" "); } } else { while(!q.empty())q.pop(); for(int i = 1; i <= n ; i ++ ){ node b = a[i] ; q.push(b) ; if(q.size() < m){ l = a[i].l ; } if(q.size() > m){ q.pop() ; } if(q.size() == m){ if(b.r >= q.top().r){ int res = q.top().r - b.l + 1 ; if(res == ans){ int z = q.size(); while(!q.empty()){ c[z] = q.top().id ; q.pop() ; z-- ; } sort(c+1,c+1+m); for(int j = 1; j <=m ;j ++ ){ printf("%d",c[j]); if(j == m)printf("\n"); else printf(" "); } break ; } } } } }}

转载于:https://www.cnblogs.com/rayrayrainrain/p/6275757.html

你可能感兴趣的文章