CCF-NOIP-2018 提高組(復(fù)賽) 模擬試題(五)

T1 相遇

【問(wèn)題描述】

在一場(chǎng)奇怪的夢(mèng)里篮幢，小 Y 來(lái)到了一個(gè)神奇的國(guó)度笤受。這個(gè)國(guó)度可以用一根數(shù)軸表示穷缤，小 Y 在 N 處，而小 Y 想吃的美食在 K 處箩兽。小 Y 有兩種方式移動(dòng)津肛，一種叫做步行，一種叫做瞬移汗贫。對(duì)于每次步行操作身坐，小 Y 可以從 $x$ 移動(dòng)到 $x + 1$ 或者 $x – 1$ ，而對(duì)于每次瞬移操作小 Y 可以從 $x$ 瞬移到 $2x$ 芳绩。那么小 Y 最少要移動(dòng)多少次才能到達(dá) K 處吃到食物呢掀亥？

【輸入格式】

僅有兩個(gè)整數(shù) $N$ 和 $K$

【輸出格式】

共一行，包含一個(gè)整數(shù)妥色，表示最少的移動(dòng)次數(shù)

【樣例1】

樣例輸入
5 17

樣例輸出
4

數(shù)據(jù)規(guī)模與約定

$0 ≤ N, K ≤ 100,000$

題解

方法很多搪花，然而考試時(shí)本蒟蒻只想到了DP的做法。我們?cè)O(shè) $f[i]$ 表示從 $n$ 到 $i$ 的最短路徑，此時(shí)我們已經(jīng)可以得知所有 $\forall i \le n$ 時(shí)的情況撮竿，因?yàn)楫?dāng)當(dāng)前位置大于想要到達(dá)的位置時(shí)吮便，我們只能通過(guò)每次移動(dòng)到 $x-1$ 來(lái)逐步逼近位置，即： $f[i] = \begin{cases} 0 & i=n \\ f[i+1]+1 & i < n \end{cases}$
此時(shí)我們發(fā)現(xiàn)幢踏，當(dāng) $i>n$ 時(shí)髓需，任意一個(gè) $f[i]$ 都可以通過(guò) $f[i-1]$ 到達(dá)。特殊的房蝉，當(dāng) $i$ 為偶數(shù)時(shí)僚匆，每個(gè) $f[i]$ 位置都可以經(jīng)由 $f[i/2]$ 到達(dá)。同時(shí)搭幻，我們?nèi)匀恍枰紤] $f[i]=f[i-1]$ 的情況咧擂。事實(shí)上若 $i$ 為偶數(shù)時(shí)并不需要考慮，因?yàn)閺?img class="math-inline" src="https://math.jianshu.com/math?formula=f%5Bi%2B1%5D" alt="f[i+1]" mathimg="1">到達(dá) $f[i]$ 的步驟必然要大于從 $min(f[i/2],f[i-1])$ 到達(dá)的步驟（可以想想為什么）而當(dāng) $i$ 為奇數(shù)時(shí)檀蹋，我們可以考慮取從 $f[i-1]$ 到達(dá) $f[i]$ 所需步驟和從 $f[(i+1)/2]$ 到達(dá) $f[i]$ 的步驟的最小值松申。因此，我們的轉(zhuǎn)移方程為：
$f[i] = \begin{cases} 0 & i=n\\ f[i+1]+1 & i<n\\ min(f[i/2]+1,f[i-1]+1) & i>n,i\%2=0\\ min(f[(i+1)/2]+2,f[i-1]+1) & i>n,i\%2=1 \end{cases}$
ps:本蒟蒻的dp水平極低俯逾，因此推出的式子極為冗長(zhǎng)贸桶，但是整體思維層次不高，畢竟本蒟蒻都能AC
代碼如下：

#include<bits/stdc++.h>
#define maxn 100000
using namespace std;
long long n,k;
long long f[maxn];
int main(){
    //freopen("meet.in","r",stdin);
    //freopen("meet.out","w",stdout);
    scanf("%d%d",&n,&k);
    f[n]=0;
    for(register long long i=n-1;i>=0;i--)f[i]=f[i+1]+1;
    for(register long long i=n+1;i<=k;i++){
        if(i%2==0){
            f[i]=min(f[i/2]+1,f[i-1]+1);
        }
        else f[i]=min(f[i-1]+1,f[(i+1)/2]+2);
        //cout<<i<<":"<<f[i]<<endl;
    }
    //for(register long long i=0;i<=n;i++)cout<<i<<":"<<f[i]<<endl;
    cout<<f[k]<<endl;
    return 0;
}

T2 秘密郵件

【問(wèn)題描述】

小 $A$ 收到了一封來(lái)自外星球的秘密郵件桌肴。郵件由 $n$ 個(gè)大寫(xiě)英文字母組成皇筛，不巧的是小 $A$ 收到郵件以后一不小心打亂了原來(lái)的字母順序。但是聰明的小 $A$ 記住了原郵件的完整內(nèi)容识脆，現(xiàn)在她每次可以選擇打亂后的郵件中相鄰的兩個(gè)字母進(jìn)行交換设联，問(wèn)最少交換多少次能夠?qū)⒋騺y的郵件恢復(fù)成原郵件。

【輸入格式】

第一行一個(gè)整數(shù) $n$ 表示郵件的長(zhǎng)度灼捂。
第二行一個(gè)長(zhǎng)度為 $n$ 的只包含大寫(xiě)字母的字符串表示打亂后的郵件离例。
第三行一個(gè)長(zhǎng)度為 $n$ 的只包含大寫(xiě)字母的字符串表示原郵件。
為保證打亂后的郵件可以恢復(fù)成原郵件悉稠，所有的測(cè)試數(shù)據(jù)滿(mǎn)足任意一種大寫(xiě)字母在兩封郵件中的出現(xiàn)次數(shù)相同宫蛆。

【輸出格式】

共一行包含一個(gè)整數(shù)，表示最少的交換次數(shù)的猛。

【樣例1】

樣例輸入
4
ABCD
DBCA

樣例輸出
5

數(shù)據(jù)規(guī)模與約定

$n \le 1,000,000$ 耀盗。

題解

蒟蒻的我考試時(shí)竟然只寫(xiě)了60分的暴力代碼QAQ事實(shí)上，這道題比 $T1$ 還要簡(jiǎn)單卦尊。我們只需要給第二個(gè)字符串中每個(gè)字符一個(gè)哈希值叛拷，并將這個(gè)哈希值帶入第一個(gè)字符串中，求一下逆序?qū)Φ臄?shù)量即可岂却！
貼出代碼QAQ

#include <bits/stdc++.h>
using namespace std;
long long a[1000100],b[1000100],ans = 0;
long long n;
void merge_sort(long long l,long long r){
    long long p1,p2,p,mid;
    if(l == r){
        return ;
    }
    mid = (l+r) >> 1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    p1 = l,p2 = mid+1,p = 0;
    while(p1 <= mid || p2 <= r){
        if(p1 <= mid && (p2 > r || a[p1] <= a[p2])){
            b[++p] = a[p1];
            p1++;
        }else{
            b[++p] = a[p2];
            p2++;
            ans += mid-p1+1;
        }
    }
    for(long long i = 1;i <= p;i++){
        a[l+i-1] = b[i];
    }
}
int main(){
    //freopen("letter.in","r",stdin);
    //freopen("letter.out","w",stdout);
    cin >> n;
    string A,B;
    cin >> A >> B;
    queue<int> q[26];
    for(int i = 0;i < A.size();i++){
        q[(int)(A[i]-'A')].push(i+1);
    }
    for(int i = 0;i < B.size();i++){
        a[i+1] = q[(int)(B[i]-'A')].front();
        q[(int)(B[i]-'A')].pop();
    }
    ans = 0;
    merge_sort(1,n);
    cout << ans;
    return 0;
}

T3 小喬

【問(wèn)題描述】

戀之微風(fēng)·小喬忿薇，是手游《王者榮耀》中的法師型英雄裙椭，擅長(zhǎng)遠(yuǎn)程消耗。小喬有一把神奇的扇子署浩，借助靈活的走位可以對(duì)敵人造成高額的傷害揉燃。小喬是小 $A$ 最喜歡（會(huì)玩）的英雄之一。在一場(chǎng)夢(mèng)里筋栋，小 $A$ 與小喬來(lái)到了一個(gè)異次元世界炊汤。異次元世界位于極坐標(biāo)系中。小喬定義了一個(gè)值 $m$ 弊攘，以等分 $[-π,π]$ 弧度（詳見(jiàn)樣例）抢腐。小喬還有一把神奇的扇子，她將進(jìn)行 $n$ 次“綻放之舞”操作襟交。對(duì)于第 $i$ 次"綻放之舞”操作氓栈，小喬將設(shè)定半徑 $r_i$ ，起始位置 $s_i$ 婿着，終止位置 $t_i$ ，她借助自己神奇的扇子醋界，以坐標(biāo)系原點(diǎn)為圓心竟宋，) $r_i$ 為半徑，將圓心角 $\frac{πs_i}{m}$ 到圓心角 $\frac{πt_i}{m}$ 這部分扇形區(qū)域逆時(shí)針疊加一層“治愈微笑” 形纺。
小喬想到了一個(gè)有趣（奇怪）的問(wèn)題丘侠，她希望知道有多大面積的區(qū)域被疊加過(guò)至少2層“治愈微笑” 。這個(gè)問(wèn)題難倒了平日里善于發(fā)現(xiàn)并解決問(wèn)題的小 A≈鹧現(xiàn)在小 A 求助于你蜗字，希望你能幫他解決這個(gè)問(wèn)題。我們?cè)O(shè)答案的值為 $T$ 脂新，為了方便表達(dá)挪捕，你只需要輸出 $T*\frac{2m}{π}$ (可以證明這是一個(gè)非負(fù)整數(shù))的值即可。

【輸入格式】

第一行是三個(gè)整數(shù) $n争便，m级零，k$ 。
接下來(lái) $n$ 行滞乙，依次描述每個(gè)“綻放之舞”操作奏纪，每行包含三個(gè)整數(shù) $r_i,s_i,t_i$ 。

【輸出格式】

輸出只包含一個(gè)整數(shù)斩启，表示 $T*\frac{2m}{π}$ 的值序调。

【樣例輸入1】

3 8 2
1 -8 8
3 -7 3
5 -5 5

【樣例輸出1】

樣例輸出
76

image

【數(shù)據(jù)規(guī)模與約定】

$1\le n \le 100000，1 \le m \le 10^5$

【題解】

原諒我淺薄的幾何知識(shí)兔簇。

image

#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
 
using namespace std;

typedef long long int64;
const int MAXN=400005;

int n,m,lim;
int na,nb;

struct A{
    int l,r,R;
    A(void){}
    A(int _l,int _r,int _R):l(_l),r(_r),R(_R){}
    inline void print()
    {
        printf("l = %d, r = %d, R = %d.\n",l,r,R);
    }
}a[MAXN],b[MAXN];

struct B{
    int p,r;
    bool f;
    #define SHANCHU 0
    #define CHARU 1
    B(void){}
    B(int _p,int _r,bool _f):p(_p),r(_r),f(_f){}
    friend bool operator < (const B &a,const B &b)
    {
        return a.p<b.p;
    }
}eve[MAXN];
int elen;

struct Size_Balanced_Tree{
    int left,right,size,data;
}SBT[MAXN*5];
int pn,root;

inline void left_rotate(int &p)
{
    int k=SBT[p].right;
    SBT[p].right=SBT[k].left;
    SBT[k].left=p;
    SBT[k].size=SBT[p].size;
    SBT[p].size=SBT[SBT[p].left].size+SBT[SBT[p].right].size+1;
    p=k;
}

inline void right_rotate(int &p)
{
    int k=SBT[p].left;
    SBT[p].left=SBT[k].right;
    SBT[k].right=p;
    SBT[k].size=SBT[p].size;
    SBT[p].size=SBT[SBT[p].left].size+SBT[SBT[p].right].size+1;
    p=k;
}

void maintain(int &p,bool f)
{
    if (!f)
    {
        if (SBT[SBT[SBT[p].left].left].size>SBT[SBT[p].right].size) right_rotate(p);
        else if (SBT[SBT[SBT[p].left].right].size>SBT[SBT[p].right].size) left_rotate(SBT[p].left),right_rotate(p);
        else return;
    }
    else
    {
        if (SBT[SBT[SBT[p].right].right].size>SBT[SBT[p].left].size) left_rotate(p);
        else if (SBT[SBT[SBT[p].right].left].size>SBT[SBT[p].left].size) right_rotate(SBT[p].right),left_rotate(p);
        else return;
    }
    maintain(SBT[p].left,0);
    maintain(SBT[p].right,1);
    maintain(p,0);
    maintain(p,1);
}

void Insert(int &p,int v)
{
    if (!p)
    {
        p=++pn;
        SBT[p].left=SBT[p].right=0;
        SBT[p].size=1;
        SBT[p].data=v;
    }
    else
    {
        SBT[p].size++;
        if (v<SBT[p].data) Insert(SBT[p].left,v);
        else Insert(SBT[p].right,v);
        maintain(p,v>=SBT[p].data);
    }
}

int Delete(int &p,int v)
{
    SBT[p].size--;
    int k=SBT[p].data;
    if (v==k||(v<k&&!SBT[p].left)||(v>k&&!SBT[p].right))
    {
        if (!SBT[p].left||!SBT[p].right) p=SBT[p].left+SBT[p].right;
        else SBT[p].data=Delete(SBT[p].left,v+1);
        return k;
    }
    else
    {
        if (v<k) return Delete(SBT[p].left,v);
        else return Delete(SBT[p].right,v);
    }
}

inline int Find_Kth(int k)
{
    int p=root;
    while (SBT[SBT[p].left].size+1!=k)
    {
        if (SBT[SBT[p].left].size+1<k) k-=SBT[SBT[p].left].size+1,p=SBT[p].right;
        else p=SBT[p].left;
    }
    return SBT[p].data;
}

inline int64 work(A *a,int n)
{
    pn=root=elen=0;
    for (int i=1;i<=n;i++)
    {
        eve[++elen]=B(a[i].l,a[i].R,CHARU);
        eve[++elen]=B(a[i].r,a[i].R,SHANCHU);
    }
    sort(eve+1,eve+elen+1);
    int64 res=0;
    int last=eve[1].p;
    int l=1,r=1;
    while (l<=elen)
    {
        while (r<=elen&&eve[r].p==eve[l].p) r++;
        if (SBT[root].size>=lim)
        {
            int64 x=Find_Kth(SBT[root].size-lim+1);
            res+=x*x*(eve[l].p-last);
        }
        for (int i=l;i<r;i++)
        {
            if (eve[i].f==CHARU) Insert(root,eve[i].r);
            else Delete(root,eve[i].r);
        }
        last=eve[l].p;
        l=r;
    }
    return res;
}

int main()
{
    //freopen("xiaoqiao.in","r",stdin);
    //freopen("xiaoqiao.out","w",stdout);
    scanf("%d%d%d",&n,&m,&lim);
    for (int i=1;i<=n;i++)
    {
        int R,l,r;
        scanf("%d%d%d",&R,&l,&r);
        if (l==m) l=-m;
        if (r==-m) r=m;
        if (l==r) continue;
        if (l<=0&&r<=0)
        {
            if (l<r) a[++na]=A(l,r,R);
            else if (l>r)
            {
                if (l!=0) a[++na]=A(l,0,R);
                if (-m!=r) a[++na]=A(-m,r,R);
                if (0!=m) b[++nb]=A(0,m,R);
            }
        }
        else if (l>=0&&r>=0)
        {
            if (l<r) b[++nb]=A(l,r,R);
            else if (l>r)
            {
                if (l!=m) b[++nb]=A(l,m,R);
                if (0!=r) b[++nb]=A(0,r,R);
                if (-m!=0) a[++na]=A(-m,0,R);
            }
        }
        else if (l<=0&&r>=0)
        {
            if (l!=0) a[++na]=A(l,0,R);
            if (0!=r) b[++nb]=A(0,r,R);
        }
        else if (l>=0&&r<=0)
        {
            b[++nb]=A(l,m,R);
            a[++na]=A(-m,r,R);
        }
    }
    printf("%lld\n",work(a,na)+work(b,nb));
    return 0;
}

最后編輯于：2018.11.01 16:23:41

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末发绢，一起剝皮案震驚了整個(gè)濱河市硬耍，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌朴摊，老刑警劉巖默垄，帶你破解...
沈念sama閱讀 219,490評(píng)論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異甚纲，居然都是意外死亡口锭，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,581評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)介杆，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)鹃操，“玉大人，你說(shuō)我怎么就攤上這事春哨【０” “怎么了？”我有些...
開(kāi)封第一講書(shū)人閱讀 165,830評(píng)論 0贊 356
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵赴背，是天一觀的道長(zhǎng)椰拒。經(jīng)常有香客問(wèn)我，道長(zhǎng)凰荚，這世上最難降的妖魔是什么燃观？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,957評(píng)論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮便瑟，結(jié)果婚禮上缆毁，老公的妹妹穿的比我還像新娘。我一直安慰自己，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,974評(píng)論 6贊 393
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布搔扁。她就那樣靜靜地躺著，像睡著了一般浇雹。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上屿讽，一...
開(kāi)封第一講書(shū)人閱讀 51,754評(píng)論 1贊 307
城市分裂傳說(shuō)
那天箫爷，我揣著相機(jī)與錄音，去河邊找鬼聂儒。笑死虎锚，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的衩婚。我是一名探鬼主播窜护，決...
沈念sama閱讀 40,464評(píng)論 3贊 420
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼非春！你這毒婦竟也來(lái)了柱徙？” 一聲冷哼從身側(cè)響起缓屠，我...
開(kāi)封第一講書(shū)人閱讀 39,357評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎护侮，沒(méi)想到半個(gè)月后敌完，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,847評(píng)論 1贊 317
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡羊初，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,995評(píng)論 3贊 338
?白月光啟示錄
正文我和宋清朗相戀三年滨溉，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片长赞。...
茶點(diǎn)故事閱讀 40,137評(píng)論 1贊 351
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡晦攒，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出得哆，到底是詐尸還是另有隱情脯颜，我是刑警寧澤，帶...
沈念sama閱讀 35,819評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布贩据，位于F島的核電站栋操，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏饱亮。R本人自食惡果不足惜讼庇，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,482評(píng)論 3贊 331
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望近尚。院中可真熱鬧，春花似錦场勤、人聲如沸戈锻。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 32,023評(píng)論 0贊 22
一樁弒父案和媳，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)格遭。三九已至，卻和暖如春留瞳，著一層夾襖步出監(jiān)牢的瞬間拒迅，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 33,149評(píng)論 1贊 272
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工她倘，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留璧微，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,409評(píng)論 3贊 373
代替公主和親
正文我出身青樓硬梁，卻偏偏與公主長(zhǎng)得像前硫，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子荧止，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,086評(píng)論 2贊 355