程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 558(C、D、E)總結

Codeforces 558(C、D、E)總結

編輯:C++入門知識

Codeforces 558(C、D、E)總結


558C

題意:給你n個數,可對每個數進行操作(乘2或者除以2)。求最少的操作使得所有的數都相等。

思路 : dp[ t ] 表示所有的數轉化到 t 所需的最少操作, vis[ t ] 表示有多少數可以轉化成 t 。

對於一個數 num , 把它所能到達的數用上述的數組記錄下就行了(具體看代碼)。

注意 :

輸入:

3

5 4 4

輸出 : 2 (5/2*2=4)

 

 

#include 
#include 
#include 
using namespace std;
const int maxn=100010;
int n,vis[maxn],num[maxn];
void initial()
{
    memset(num,0,sizeof(num));
    memset(vis,0,sizeof(vis));
}
void deal(int op)
{
    int tp=op,ct=0;
    while(tp)
    {
        vis[tp]++;
        num[tp]+=ct;
        if(tp%2==1 && tp!=1)
        {
            int yp=tp/2*2,cnt=ct+2;
            while(yp

 

 

558D

 

題意:給出n條信息,要你判斷信息是否矛盾,或是否有多個出口,或是否有唯一出口。

信息有兩種類型,一個是出口的若干區間,一個不是出口若干區間。

思路: 先通過出口的若干區間找出出口所在的樹中根節點的區間。然後在通過不是出

口的若干區間來判斷。

 

 

#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;

struct node
{
    ll l,r;
    node(){}
    node(ll _l,ll _r):l(_l),r(_r){}
};
vector  G;
int n,m;
ll st,ed;
bool cmp(node p,node q)
{
    if(p.l==q.l)  return p.red)  break;
        if(st

 

 

558E

 

題意:給你一個長度為n的字符串(下標從1開始),然後給你m個操作。每個操作有三個值 l,r,t。

如果t=1,表示將字符串中[ l ,r ]的部分按照升序排列。

如果t=0,表示將字符串中[ l ,r ]的部分按照降序排列。

最後要你輸出原字符串經過m次操作後所形成的新的字符串。

思路:對於26個小寫字母(a-z),分別建立線段樹,即建26個線段樹。

即每次修改 [ l , r ] 區間,則先通過26課線段樹分別求出這個區間內的a–z的個數。然後將26課線

段樹內的這一區間和置為0。最後再根據順序重新給26課線段樹的這一區間賦值就行了。

 

#include 
#include 
#include 
#include 
using namespace std;
const int N=100010;
const int M=26;
struct node
{
    int l,r,sum,cover;
} a[M][N*4];
string str;
int n,m;
void build(int cnt,int l,int r,int k)
{
    a[cnt][k].l=l;
    a[cnt][k].r=r;
    a[cnt][k].sum=0;
    a[cnt][k].cover=-1;
    if(l==r)  return ;
    int mid=(l+r)>>1;
    build(cnt,l,mid,2*k);
    build(cnt,mid+1,r,2*k+1);
}
void push_down(int cnt,int k)
{
    if(a[cnt][k].cover!=-1)
    {
        a[cnt][k*2].cover=a[cnt][k*2+1].cover=a[cnt][k].cover;
        a[cnt][k*2].sum=(a[cnt][k*2].r+1-a[cnt][k*2].l)*a[cnt][k*2].cover;
        a[cnt][k*2+1].sum=(a[cnt][k*2+1].r+1-a[cnt][k*2+1].l)*a[cnt][k*2+1].cover;
        a[cnt][k].cover=-1;
    }
}
void update(int cnt,int l,int r,int k,int num)
{
    if(l==a[cnt][k].l && r==a[cnt][k].r)
    {
        a[cnt][k].cover=num;
        a[cnt][k].sum=(a[cnt][k].r+1-a[cnt][k].l)*num;
        return ;
    }
    push_down(cnt,k);
    int mid=(a[cnt][k].l+a[cnt][k].r)>>1;
    if(r<=mid)      update(cnt,l,r,2*k,num);
    else if(l>mid)  update(cnt,l,r,2*k+1,num);
    else
    {
        update(cnt,l,mid,2*k,num);
        update(cnt,mid+1,r,2*k+1,num);
    }
    a[cnt][k].sum=a[cnt][k*2].sum+a[cnt][k*2+1].sum;
}
int query(int cnt,int l,int r,int k)
{
    if(l==a[cnt][k].l && r==a[cnt][k].r)  return a[cnt][k].sum;
    push_down(cnt,k);
    int mid=(a[cnt][k].l+a[cnt][k].r)>>1;
    if(r<=mid)      return query(cnt,l,r,2*k);
    else if(l>mid)  return query(cnt,l,r,2*k+1);
    else    return query(cnt,l,mid,2*k)+query(cnt,mid+1,r,2*k+1);
}
void input()
{
    for(int i=0; i=0; i--)
                if(num[i])
                {
                    update(i,pos,pos+num[i]-1,1,1);
                    pos=pos+num[i];
                }
        }
    }
    for(int i=1; i<=n; i++)
        for(int j=0; j


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved