黑龍江農墾科技職業學院喜迎寒假多校聯賽2（快樂ak場）

快樂ak場 （沒做可以做一下 - > 本次比賽鏈接

• 前言
  這次比賽難嗎，我認為挺容易的（每道題都挺容易的），
  我后面一個半小時都在玩，我感覺我就是個撒比，這種難度都做不來（A 和 D 沒做），還不好好看題，我感覺自己真的挺無語的，重點是考的都是我已經學過的，沒有盲區，害，萌新直接去世，腦子瓦特，
  希望大家一起加油，好好努力，發現不足，及時補進

• 第一題 陣列截取

思想：雙指標 + 快速讀取

• 快速讀取模板

inline int read() {
		char c = getchar(); int n = 0;
		while (c < '0' || c > '9') { c = getchar(); }
		while (c >= '0' && c <= '9') { n = (n << 1) + (n << 3) + (c & 15); c = getchar(); }
		return n;
 	}                 ///快讀模板

這個直接背就行了，不需要什么思想，

• 快寫模板

void write(int x)
	{
		if(x<0)	putchar('-'),x=-x;
		if(x>9)	write(x/10);
		putchar(x%10+'0');
	}           ///快寫模板

好了正式開始，講雙指標，
傳送門 - > 題目A，點擊這里

• 決議

  雙指標思想就是用兩個指標，指向一個區間，主要分兩種
  第一種：同時指向開頭 （這題）
  第二種：分別指向開頭和結尾

  
  舉個例子，讓 i 和 j 兩個指標同時指向 【3，3，1，1，1，0，0，0，3，3】這個區間開頭
  讓 j 這個指標不斷右移，直到找到 j 到 i 的區間里面之和大于 k (例題就是 3)
  
  這里的 i 和 j 這個范圍區間為6，我們就讓 i 這個指標右移
  
  這樣就區間就之和 就不大于 3（也就是k） 然后進行判斷區間是否等于 k ，如果等于就記錄距離，
  以此類推，輸出我們找到最大的距離

• 注意事項

  1 題目資料很大（超過了題目規定的范圍），所以開大點陣列
  2 快讀
  3 long long 型別

代碼如下

#include<iostream>
//全開longlong，保險
using namespace std;
inline long long read() {
		char c = getchar(); long long n = 0;
		while (c < '0' || c > '9') { c = getchar(); }
		while (c >= '0' && c <= '9') { n = (n << 1) + (n << 3) + (c & 15); c = getchar(); }
		return n;
 	}
long long a[20000010];
int main(){
    long long  n,m,ans=0,sum=-1;
    n=read(),m=read();//快讀
    for(long long i=0,j=0;i<n;i++){
        a[i]=read();//快讀
        ans+=a[i];//累加區間和
        while(ans>m) ans-=a[j++];// 當ans>m時，j 指標右移
        if(ans==m) sum=max(sum,i-j+1); //等于記錄距離
    }
    cout<<sum;//輸出最大距離
    return 0;//收工
}

想練一道雙指標的題嗎？
練習題 傳送門 - > 快去完成吧

第二題 群友們在排列數字

• 主要思想：DFS

這 - > 題目

這題本來要用DFS的，可是這屬于全排列的范疇，也可以用STL里的全排列神器

next_permutation 不是很了解的 傳送門 -> next_permutation詳細用法

這道題如果使用神器的話就太簡單了，把區間里的數全累加起來取模就行，判斷次數

• 第一種題解 STL的做法

#include<iostream>
#include<algorithm>
using namespace std;
int n,k;
long long a[15];
int main(){
    int ans=0;
    cin>>n>>k;
    for(int i=0;i<n;i++) a[i]=i;
    do{
        long long sum=0;
        for(int i=0;i<n;i++){
            sum=sum*10+a[i];
        }
        if(sum%k==0) ans++;
    }while(next_permutation(a,a+n));
    if(ans) cout<<ans;
    else cout<<-1;
    return 0;
}

再說一下DFS的做法（學過的同學可以看一下，沒學過的，學完再看吧，可以看第一種解法）
這題是DFS入門題沒啥子好講（真的就是入門題，DFS新手村的題目）

• 沒有注意事項

代碼

#include<iostream>

using namespace std;

const int N=15;
int p[N];
bool s[N];
int n,k;
long long ans;
void dfs(int u){
    if(u==n){
        long long sum=0;
        for(int i=0;i<n;i++){
            sum=sum*10+p[i];
        }
        if(sum%k==0&&sum) ans++;
        return ;
    }
    for(int i=0;i<n;i++){
        if(!s[i]){
            p[u]=i;
            s[i]=true;
            dfs(u+1);
            s[i]=false;
        }
    }
}
int main(){
    cin>>n>>k;
    dfs(0);
    if(ans) cout<<ans;
    else cout<<-1;
    return 0;
}

歡迎看看我的DFS博客 傳送門 - > DFS講解
DFS這題 原型傳送門 - > 排序問題

第三題 gg查成績

主要思想：前綴和

這題又是前綴和新手村的題目（入門題，學了前綴和就會）
如果用列舉，會超時的喲

• 簡單講一下 前綴和

有兩個陣列 a[ N ]和s[ N ]；
a[ N ]是資料，s[ N ]是a[0]到 a[N] 的區間和
公式 s[ i ]=s[ i-1 ]+a[ i ]
求一段區間 [ l , r ] 和 ans = s[ r ] - s [ l - 1];
這種求法時間復雜度是O（1）的（非常快）

• 前綴和公式

S[i] = a[1] + a[2] + ... a[i]    //s[i] 陣列
a[l] + ... + a[r] = S[r] - S[l - 1]  //求區間和

代碼如下

#include<iostream>

using namespace std;
const int N=1e6+10;
int n,m;
long long a[1000005]; //這里我只開了區間和陣列，也就是s[N],因為這題不需要用到a[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){     // i 要從1開始避免特判  i=0, i-1=-1,這就錯誤了 a[0]=0;
        long long x;
        scanf("%lld",&x);
        a[i]=a[i-1]+x;   //累加，得前綴和陣列
    }
    for(;m;m--){    
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%lld\n",a[r]-a[l-1]); 
    }
    return 0;
}

本題原型 趕緊秒了他 - > 前綴和入門題

第四題 issue與lifehappy給學生分組

主要思想： 二分答案

題目 這里

這題二分有點不好寫，D和E算是這里水平還可以的題目了
二分我就不多介紹了，就是 對半取

• 決議

就是用答案證結論 看是大還是小了 然后就相當應縮短區間

主要是怎么取很重要

比方說我們有一個大小為 mid 最大值

比 mid 大的區間就不成立 我們就要再給一組 ，看我們最終的組和題目給我們的組數的大小，來縮短查找區間

如果mid為9，我們就這么劃磁區間，我只能講到這里，具體看代碼吧，說的比較抽象

代碼

#include<iostream>

using namespace std;
const int N=2e6+10;
long long n,m;
long long a[N];
bool f(long long x){
    long long ans=0,len=0;//len是組數
    for(int i=0;i<n;i++){
        if(ans+a[i]<=x) ans+=a[i];  
        else len++,ans=a[i]; //再劃分一個區間
    }
    if(ans) len++; //沒劃分的數的再劃分一個區間
    return len>m;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++) scanf("%lld",&a[i]);
    long long l=0,r=1e11+1;
    while(l<r){
        long long mid=l+r>>1;//二分
        if(f(mid)) l=mid+1; //組多了 就增大最大值
        else r=mid; //否則縮小最大值
    }
    cout<<l;
    return 0;
}

這里我們一定要處理好臨界情況，整數二分最難搞的就是臨界情況

給大家一個二分題，練練手吧 - > 整數二分
再來個浮點二分 - > 浮點二分

模板放下面 自己看

• 整數二分

bool check(int x) {/* ... */} // 檢查x是否滿足某種性質
// 區間[l, r]被劃分成[l, mid]和[mid + 1, r]時使用：
int bsearch_1(int l, int r)
{
    while (l+1 < r)
    {
        int mid = (l + r) 1;
        if (check(mid)) r = mid;    // check()判斷mid是否滿足性質
        else l = mid ;
    }
    return l;
}
// 區間[l, r]被劃分成[l, mid - 1]和[mid, r]時使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = (l + r + 1)1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

• 浮點二分

bool check(double x) {/* ... */} // 檢查x是否滿足某種性質

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取決于題目對精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

這里有STL里有關于二分的函式 分別是 lower_bound( ) 和 upper_bound( ) ，這兩個只能用在有序陣列里，切記

關于lower_bound( )和upper_bound( )的常見用法

好了下午再補充，我先休息了，嘻嘻

第五題 刪刪刪越小越好

題目

主要思想：單調堆疊

肯定有人說，這怎么可以是單調堆疊呢？其實他是字符的單調堆疊，并非數字，原理是一模一樣的，

1 怎么樣得到最小值

因為我們有k次洗掉機會，但我們不管怎么刪，數的位數是不會變的，
所以我們只需要把高位的數盡可能的小就行了
這時就要用到單調堆疊思想了

2 啥是單調堆疊

其實很簡單，就是我們要得到一個單調遞增的區間，把搗亂的資料洗掉，

例如 如圖

我們有十次機會洗掉 我們要讓前面的位數呈單調遞增，這樣高位就是最小的，
12345897 到 7 時 不呈單調遞增，所以我們把 7 前面的 8和 9 刪掉

就變成了123477了，我們現在還有8次洗掉權限，后面讀入1，就變成了1234771，又不呈現單調了，現在我們就要把2，3，4，7，7刪了

**就變成了11了，現在我們有三次權限，我們再讀入1187，這時把 8刪了，我們還有2次洗掉機會，
以此類推，直至呈現單調遞增或洗掉權限沒有了，為止，

這個例題得到的數為 1114164979 因為洗掉權限用完了，所以我們就輸出**

挺簡單的，但要想到單調堆疊的思想很難，

代碼如下

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e7+10;
long long k,tt,hh=1;
char a[N],b[N];//這里位數太大，必須用字符來輸入
int main(){
    scanf("%s%lld",a,&k);
    for(int i=0;a[i];i++){
        while(k&&tt&&b[tt]>a[i]) k--,tt--; //k用完或前面沒有字符，我們就不進行洗掉
        b[++tt]=a[i]; //滿足單調性質，就讀入
    }
    while(b[hh]=='0'&&hh<tt) hh++; //消除前導零,hh為開頭第一個非零的字符
    for(int i=hh;i<=tt-k;i++) cout<<b[i]; //若已經呈單調，但k沒有用完
	   return 0;						//我們就輸出前hh到tt-k    
}							                       

題目還是要練一下的 - > 單調堆疊

第六題 happy的異或運算

思想：懂異或，就能做出來了，很簡單的思維題

啥是異或？

異或符號為 ^，這個在計算機的主要功能很多，你們自己可以去看，我這里講簡單點，
了解一下這三個運算
1 ^ 0 = 1
0 ^ 0 = 0
1 ^ 1 = 0

知道這三個運算就夠了，因為計算機是二進制存盤的，所以只有0 和 1 的運算
這題要求最大值 我們只要讓所有二進制位都為一就是最大值了
因為 1 到 n 一定可以找到 兩個數 1 和 0 互補，使所有位置上都為一，這就是這題思想

例如 4 = 100（二進制）， 最大值就為 7 = 111（二進制）

代碼如下，提供兩種寫法

第一種是我寫的

#include<iostream>
  
using namespace std;
long long n,sz=0; 
int main(){
    cin>>n;
    if(n==1){
    	cout<<0;   //因為1的異或最大值為0，所有特判一下，1^1=0 
    	return 0;
    }
    while(sz<=n) sz=(sz*2+1);
    cout<<sz<<endl;  
    return 0;
}

第二種是位運算

#include<iostream>
  
using namespace std;
long long n;
int main(){
    cin>>n;
    long long b=1;
    while(b<=n) b<<=1; //使用右移運算子
    cout<<b-1;
    return 0;
}

思維題就沒啥可推薦的，一抓一大把，0.0

第七題 Alan%%%
題目

思維：他要求啥，就做啥

這題沒啥可講的，就講幾個string庫的小知識吧

1 find函式 找到你想要的字串位置
例如 字串 string str = “abcd”
str.find（“cd”），他就會回傳cd字串的位置，位置為2.

2 getline函式
gets沒啥區別,作用是讀入一行字串，包括空格，直到碰到回車為止

3 因為c++的string多載了+運算子

   string a = "123"
   string b = "456"
 	string c = a+b
   c=="123456"

代碼如下

#include<iostream>

using namespace std;
string a;
int n,ans;
int main(){
    cin>>n;
    cin.ignore();//吃掉回車，防止getline吃了上一行的回車
    for(;n;n--){  
        string b;
        bool flag=false;
        int sum=0;
        getline(cin,a); //讀入
        for(int i=0;i<a.size();i++){
            if(a[i]!=' ') b+=a[i]; //將空格屏蔽
            if(a[i]=='%') sum++;	//數 % 個數
        }
        if(b.find("Alan")<b.size()) flag=true; //用find函式找一下Alan，如果不在這個范圍，就說明沒有
        if(flag) ans+=sum;
    }
    cout<<ans;
    return 0;
}

代碼題沒啥可講

第八，九題 cg寫專案

思維：要求排序

這里我們要介紹sort的自定義寫法

就是自己定義比較規則
第一種 STLsort的自定義

#include<iostream>
#include<algorithm>
using namespace std;
struct ss{
    string t,m,x,h;    //用戶名t，密碼m，性別x，電話h
    int id;
}s[100005];
int n;
bool cmp(ss a,ss b){            //這里我們定義了比較的規則
    if(a.t.size()!=b.t.size()) return a.t.size()<b.t.size();  // t的大小不同，這t的大小 小的在前
    if(a.t!=b.t) return a.t<b.t;    //t的大小相同則比較t，t小的在前
    return a.id<b.id;          //若都相同，這id小的在前
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) s[i].id=i,cin>>s[i].t>>s[i].m>>s[i].x>>s[i].h;
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++) cout<<s[i].t<<" "<<s[i].m<<" "<<s[i].x<<" "<<s[i].h<<endl;
    return 0;
}

第二種 多載 < 運算子（高手都是第二種，大家搖身變大佬，哈哈 ）

#include<iostream>
#include<algorithm>
using namespace std;
struct ss{
    string t,m,x,h;
    int id;
    bool operator < (const ss &a)const{  
        if(t.size()!=a.t.size()) return t.size()<a.t.size();
        if(t!=a.t) return t < a.t;
        return  id<a.id;
    }
}s[100005];
int n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++) s[i].id=i,cin>>s[i].t>>s[i].m>>s[i].x>>s[i].h;
    sort(s,s+n);
    for(int i=0;i<n;i++) cout<<s[i].t<<" "<<s[i].m<<" "<<s[i].x<<" "<<s[i].h<<endl;
    return 0;
}

也可以用快排和歸排，但是好麻煩，所有自己可以去試，只有把<多載了就行了
這里有一道要求排序題 - > 建議使用多載<去做排序

最后一道簽到題
不講了，這都講，那太沒無語了

#include<iostream>
 
using namespace std;
const int N=1e6+10;
int n,m=0x3f3f3f3f;
int main(){
    int t,x;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(m>x)  m=x,t=i;
    }
    cout<<t<<endl;
    return 0;
}

感謝大家的觀看，我花了好久打完了，希望能幫到大家
完結撒花
點點贊，辛苦死我了/(ㄒoㄒ)/~~