CCF-NOIP-2018 提高組(複賽) 模擬試題(七)

来源:https://www.cnblogs.com/Chen574118090/archive/2018/11/03/9900951.html
-Advertisement-
Play Games

T1 Adjoin 【問題描述】 定義一種合法的$0 1$串：串中任何一個數字都與$1$相鄰。例如長度為$ 3 的 0 1 $串中，$101$是非法的，因為兩邊的$1$沒有相鄰的$1，011$是合法的，因為三個數都有$1$相鄰。現在問，長度為$N$的$0 1$中有多少是合法的。 【輸入格式】 一行， ...


T1 Adjoin

【問題描述】

定義一種合法的\(0-1\)串：串中任何一個數字都與\(1\)相鄰。例如長度為$ 3 的 0-1 $串中，\(101\)是非法的，因為兩邊的\(1\)沒有相鄰的\(1，011\)是合法的，因為三個數都有\(1\)相鄰。現在問，長度為\(N\)的\(0-1\)中有多少是合法的。

【輸入格式】

一行，一個整數\(N\)

【輸出格式】

一行，合法\(0-1\)串的個數，答案對\(1000000007\)取模。

【樣例1】

樣例輸入
3
樣例輸出
3

樣例說明

\(110、111、011\)是所有長度為\(3\)的合法\(0-1\)串

數據規模與約定

所有測試點的數據規模與約定如下：
\(30\%\)輸入數據，保證\(n<=50。\)
\(60\%\)輸入數據，保證$ n<=5000$
\(80\%\)輸入數據，保證$ n<=1000000$
\(100\%\)輸入數據，保證$ 1<=n<=10^{18}$

題解

一道很經典的需要反向優化的題目。我們首先考慮暴搜得到較小範圍內每一個\(n\)所對應的答案，如下所示
|i|f[i]|
|-|-
|1|0
|2|1
|3|3
|4|4
|5|5
|6|9
|7|16
|8|25
|9|29
|10|54
然而直接觀察數據似乎沒有什麼明顯的規律。於是我們選擇將奇偶數分開判斷。經過一段時間的觀察，似乎所有的數滿足這樣一個規律：\[f[i]=\begin{cases} 0 & i=1\\ 1 & i=2\\ f[i-1]+f[i-2] & i\%2=0\\ f[i-1]+f[i-2]+(flag=1)?-2:2 & i\%2=1\\ \end{cases} \]
其中我們將flag的初值賦為1，在每碰到一個奇數時為其取反即可。

#include<bits/stdc++.h>
#define maxn 1000005
const long long mod = 1000000007;
using namespace std;
long long n;
long long dp[maxn];
bool flag=1;
int main(){
    //freopen("adjoin.in","r",stdin);
    //freopen("adjoin.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    dp[1]=0;
    dp[2]=1;
    for(register long long i=3;i<=n;i++){
        if(i%2==0)dp[i]=dp[i-1]+dp[i-2];
        else{
            if(flag){
                dp[i]=dp[i-1]+dp[i-2]+2;
                flag=0;
            }
            else{
                dp[i]=dp[i-1]+dp[i-2]-2;
                flag=1;
            }
        }
        //cout<<dp[i]<<endl;
        dp[i]%=mod;
    }
    //for(register long long i=3;i<=n;i++)cout<<dp[i]<<endl;
    cout<<dp[n]%mod<<endl;
    return 0;
}

這時我們就擁有了85分的總分。最大數據範圍為\(n\le 10^{18}\)，早已超出了\(O(n)\)的複雜度能到達的極限。此時，我們思考所有和動態規劃有關的優化。經過一番思索後，我們會發現只有矩陣優化稍微與目前的\(dp\)有點聯繫。然而矩陣優化要求使用通項公式，而我們當前只有一個遞推式。那麼我們現在考慮將方程式反向優化，從一維方程變為三維方程，使整個式子具有通項公式，再使用矩陣優化來降低整體的複雜度。想到了這一點後，實現起來應該並不難。

#include <bits/stdc++.h>
#define RG register
using namespace std;
typedef long long ll;
const int maxn = 1000010;
const int mod = 1e9+7;
const int P = 1e9+7;
ll n;
struct Matrix {
    ll val[4][4];
} A, I, ans;
Matrix operator*(const Matrix &A,const Matrix &B){
    Matrix C;
    for(int i = 0;i < 4;i++)
        for(int j = 0;j < 4;j++){
            C.val[i][j] = 0;
            for(int k = 0;k < 4;k++)
                C.val[i][j] = (1ll * A.val[i][k] * B.val[k][j] + C.val[i][j]) % P;
        }
    return C;
}
Matrix fpm(Matrix x, long long y){
    Matrix ret = I;
    while(y){
        if(y & 1) ret = ret * x;
        x = x*x;
        y >>= 1;
    }
    return ret;
}

int main(){
    freopen("adjoin.in","r",stdin);
    freopen("adjoin.out","w",stdout);
    scanf("%lld",&n);
    if(n == 1){
        puts("0");
        return 0;
    }
    for(int i = 0;i < 4;i++){
        for(int j = 0;j < 4;j++){
            I.val[i][j] = (i == j ? 1 : 0);
            A.val[i][j] = 0;
        }
    }
    ans.val[0][0] = 0;
    ans.val[0][1] = 1;
    ans.val[0][2] = 0;
    ans.val[0][3] = 1;
    A.val[2][0] = A.val[0][1] = A.val[2][1] = A.val[3][2] = A.val[1][3] = A.val[3][3] = 1;
    A = fpm(A,n-2);
    ans = ans * A;
    ll ansss = (ans.val[0][2] + ans.val[0][3]) % mod;
    printf("%lld",ansss);
    return 0;
}

T2 Sorting

【問題描述】

小F不喜歡遞減，他會想盡一切辦法將看到的一切東西排序！
現在小F得到了一個數列，他當然要將這個數列排序了，但他太累了，以至於最多只能交換其中兩個元素，如果這樣不能使得這個數列不遞減，他就要先睡覺了。你能告訴他是否可行嗎？

【輸入格式】

第一行：一個整數N表示小F的數列中數的個數。
第二行，N個正整數，描述小F的數列。

【輸出格式】

一行，YES或NO，表示通過一次“最多交換其中兩個元素（可以不交換）”的操作，是否可使得小F的數列不遞減。

【樣例1】

樣例輸入
3
1 3 1
樣例輸出
YES

數據規模與約定

\(30\%的數據，N ≤ 10^2 。\)
\(60\%的數據，N ≤ 10^4 。\)
\(100\%的數據，N ≤ 10^5 ，所有數為正整數且在longint範圍內。\)

題解

是的，本蒟蒻又一次和AC插肩而過。拿到這道題時，大多數人都會聯想到逆序對和最長不降子序列問題，然而幾組充分設置的樣例就可以卡掉這兩種思路，使得其得分甚至不如60分的暴力。
附六十分的暴力寫法

#include<bits/stdc++.h>
using namespace std;
int main(){
    puts("YES");
    return 0;
}

對於LIS來說，改變一個數有時可以導致多對大小關係的改變；對於逆序對來說，逆序對個數不一定可以決定最終大小關係。對兩種思路最好的反駁樣例如下：
|5 3 2
|-
在排除了這樣的思路後，蒟蒻的我開始思考自己的做法。我們直接從頭往後尋找第一對不滿足條件的組合\(a_i,a_{i-1}\)。此時我們取出\(a_i\)，從頭往後將其與第一個大於他的值交換。此時我們再重新在原串中查找是否存在不合法情況，若存在則輸出NO，否則輸出YES。

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
inline char get(){
    static char buf[30],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline long long read(){
    register char c=get();register long long f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
long long n;
long long a[maxn];
long long ans=0;
bool cd=1;
int main(){
    //freopen("sorting.in","r",stdin);
    //freopen("sorting.out","w",stdout);
    n=read();
    for(register long long i=1;i<=n;i++)a[i]=read();
    for(register long long i=2;i<=n;i++){
        if(a[i]<a[i-1]){
            for(register long long j=1;j<=n;j++){
                if(a[j]>a[i]){
                    swap(a[i],a[j]);
                    goto next;
                }
            }
        }
    }
    next:;
    for(register long long i=2;i<=n;i++){
        if(a[i]<a[i-1]){
            puts("NO");
            return 0;
        }
    }
    puts("YES");
    return 0;
}

為什麼我們選擇了這樣一個奇怪的演算法呢？事實上，在比賽中選擇演算法的第一原則是能否證明其錯誤性。在這道題中，蒟蒻無法證明該演算法是錯誤的，於是就這麼得到了85分的安慰分。
其實題目已經提示得很明顯了。Sorting，就是在暗示我們進行一次排序操作。我們只需要比較排序前後的兩個兩個序列，若其中同一位置不一樣的元素的個數在兩個以內（一次交換最多導致4對大小關係發生改變），則輸出YES，否則就記其為非法情況，輸出NO。

#include <bits/stdc++.h>
using namespace std;
int b[2111111],a[2111111];
int n;
int main(){
    freopen("sorting.in","r",stdin);
    freopen("sorting.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+n);
    int len=0;
    for(int i=1;i<=n;i++){
        if(a[i]!=b[i])len++;
        if(len>2){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

T3 Editor

【問題描述】

小\(F\)有一個夢想：為數列寫一個最強大的編輯器！
一開始，數列為空，游標在開頭位置，小F的編輯器要對這個數列作如下五種操作：
I x：在游標的後面插入一個數字x，並將游標移到這個新加入的\(x\)後。
D：刪除游標前的最後一個數字（保證存在），游標位置不變。
L：游標左移一位，如果已經在開頭則不做任何事。
R：游標右移一位，如果已經在結尾則不做任何事。
Q k：編輯器需要給出\(A_1,A_2 ··· A_k\)的最大首碼和（首碼長度不能為0），保證\(1 ≤ k ≤ N\)，其中\(N\)為當
前游標前的數字個數。

【輸入格式】

第一行，一個整數\(Q\)，表示操作的總次數。
後\(Q\)行，每行是上列五種操作中的一種。

【輸出格式】

對每個\(Q\)操作，輸出一行一個整數，表示答案。

【樣例輸入1】

8
I 2
I -1
I 1
Q 3
L
D
R
Q 2

【樣例輸出1】

樣例輸出
2
3

【數據規模與約定】

$ 1\le q \le 1000000，-1000 \le m \le 1000 $

【題解】

模擬題，註意一下優化就好。本蒟蒻的代碼風格太醜因此在此不予貼出。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • PHP數據類型
    PHP 支持 9 種原始數據類型。詳細講述了其中基本數據類型的用法與註意事項。 ...
  • c++模板參數——數值類型推斷
    模板類中，或模板函數中，若限定模板參數為數值類型，可以使用如下方式進行判斷. 以上代碼節選自muduo. 其中主要推斷方式是通過調用std::is_arithmetic<T>. 若 T 為算術類型（即整數類型或浮點類型）或其修飾類型(添加註入const等)，則提供等於 true 的成員常量 valu ...
  • PHP變數
    變數來源於數學，是電腦語言中能儲存計算結果或能表示值抽象概念。變數可以通過變數名訪問。 ...
  • 使用 Lombok 優雅編碼
    一、介紹和使用 Lombok 是一個 java 庫，能以簡單的註解形式來簡化 java 代碼，提高開發人員的開發效率。 常見使用在開發過程中需要寫的 javabean，往往開發需要花時間去添加相應的 getter/setter，也許還要去寫構造器、equals等方法，而且需要維護，當屬性多時會出現大 ...
  • 第一章：正則表達式
    目錄 一. 正則表達式 二. 特殊的元字元 三. python3的re模塊方法 四. python3的re模塊練習 五. 第一章課後練習題 六. re模塊綜合應用之計算器 一. 正則表達式 正則表達式是由一堆字元和特殊符號組成的字元串。它可以為我們提供高級的文本搜索，匹配，替換功能。當然，正則表達式 ...
  • netty源碼分析之服務端啟動
    ServerBootstrap與Bootstrap分別是netty中服務端與客戶端的引導類，主要負責服務端與客戶端初始化、配置及啟動引導等工作，接下來我們就通過netty源碼中的示例對ServerBootstrap與Bootstrap的源碼進行一個簡單的分析。首先我們知道這兩個類都繼承自Abstra ...
  • Java開發筆記（十八）上下求索的while迴圈
    迴圈是流程式控制制的又一重要結構，“白天-黑夜-白天-黑夜”屬於時間上的迴圈，古人“年復一年、日復一日”的“日出而作、日落而息”便是每天周而複始的生活。電腦程式處理迴圈結構時，給定一段每次都要執行的代碼塊，然後分別指定迴圈的開始條件和結束條件，就形成了常見的迴圈語句。最簡單的迴圈結構只需一個while ...
  • PHP核心技術與最佳實踐
    《PHP核心技術與最佳實踐》是一本致力於為希望成為中高級PHP程式員的讀者提供高效而有針對性指導的經典著作。系統歸納和深刻解讀了PHP開發中的編程思想、底層原理、核心技術、開發技巧、編碼規範和最佳實踐。全書分為5個部分：第一部分（1～2章）從不同的角度闡述了面向對象軟體設計思想的核心概念、技術和原則 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類