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
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類