6.30集訓模擬賽4(炸裂的一天qwq)

  • 2020 年 6 月 30 日
  • 筆記

T1澆水：

　　題目描述

  • 　　在一條長n米，寬m米米的長方形草地上放置着k個噴水裝置。假設長方形草地的坐標範圍為[ 0 , 0 ] ~ [ n , m ]，那麼第 i 個噴水裝置的位置為（ai，m/2），也就是說噴水裝置全部位於一條直線上。此外第 i 個噴水裝置能向半徑ri的圓形區域內噴水。

  •       負責管理噴水裝置的園丁老大爺想知道，要想覆蓋整個草地，至少需要開啟多少個噴水裝置。

　　輸入格式

  •       第一行三個正整數 k , n , m 。其中 m 為偶數。
  •       接下來 k 行，每行兩個整數ai 和ri ，代表第 i  個噴水裝置的橫坐標和噴水半徑。

　　輸出格式

  •       一個整數 ans 代表至少需要開啟的噴水裝置數量。若所有裝置都開啟依然不能覆蓋整個草地則輸出-1 。

　　樣例

　　樣例輸入1

9 16 6
0 5
2 5
4 5
6 5
8 5
10 5
12 5
14 5
16 5

　　樣例輸出1

 2

　　樣例輸入2

8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4

　　樣例輸出2

 6

　　數據範圍與提示

  • 樣例1 解釋開啟位於4和12的噴水裝置即可。
  •      30%的數據中：k ≤ 20。
  •      另有20%的數據中：ri均相等。
  •      100%的數據中：m≤20000,ri≤10000，n，k≤100000,ai。

　　分析：

  • 　　噴水裝置在長方形的中線上，如果某個噴水裝置能噴到左上角的地方，那左下角必定能噴到。
  •        如果噴水裝置的噴水半徑小於此裝置無用
  •        所以我們可以預處理出每一個噴水裝置能噴到的左、右最遠的距離，然後對其左邊界進行排序，從左到右，一次枚舉花壇的未噴到的最遠點，在能噴到的裝置中找到右端點最遠的裝置。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int k,n,m;
int a,r;
int cnt;
struct wat{//記錄一個點的左右最遠的覆蓋範圍
    double L;//double！！！
    double R;
}w[N];

bool cmp(wat a,wat b){//按
    return a.L<b.L;
}

int main(){
    scanf("%d%d%d",&k,&n,&m);//輸入
    for(int i=1;i<=k;i++){
        scanf("%d%d",&a,&r);
        if(r*2<=m)continue;//去除一些沒用的噴水裝置
        w[++cnt].L=a-sqrt(r*r-m*m/4.0);//等於也不行（噴一個線有啥用）
        w[cnt].R=a+sqrt(r*r-m*m/4.0);
    }
    sort(w+1,w+1+cnt,cmp);//排序
    double right=0;
    int ans=0;
    while(right<n){//
        ans++;
        double s=right;//用一個s保存right值因為後面的right值要變
        for(int i=1;i<=k&&w[i].L<=s;i++){
            if(right<w[i].R){
                right=w[i].R;//更新覆蓋的最右邊的值
            }
        }
        if(right==s&&s<n){//不滿題意
            printf("-1\n");
            return 0;
        }
    }
    printf("%d\n",ans);
    return 0;
}

T2免費餡餅：

　　題目描述：

  • 最新推出了一種叫做「免費餡餅」的遊戲:
  • 遊戲在一個舞台上進行。舞台的寬度為 w格，天幕的高度為 h格，遊戲者佔一格。
  •        開始時遊戲者站在舞台的正中央，手裡拿着一個托盤。下圖為天幕的高度為 4 格時某一個時刻遊戲者接餡餅的情景。 image
  •       遊戲開始後，從舞台天幕頂端的格子中不斷出現餡餅並垂直下落。遊戲者左右移動去接餡餅。遊戲者每秒可以向左或向右移動一格或兩格，也可以站在原地不動。
  •       餡餅有很多種，遊戲者事先根據自己的口味，對各種餡餅依次打了分。同時，在 電腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格/秒為單位。

  •       當餡餅在某一秒末恰好到達遊戲者所在的格子中，遊戲者就收集到了這塊餡餅。

  •       寫一個程序，幫助我們的遊戲者收集餡餅，使得所收集餡餅的分數之和最大。

　　輸入格式：

  • 　　輸入文件的第一行是用空格隔開的兩個正整數，分別給出了舞台的寬度 w （ 1到 99之間的奇數）和高度 H（ 1到100 之間的整數）。
  •        接下來依餡餅的初始下落時間順序給出了所有餡餅的信息。每一行給出了一塊餡餅的信息。由四個正整數組成，分別表示了餡餅的初始下落時刻（1 到1000 秒），水平位置、下落速度（1  到 100 ）以及分值。遊戲開始時刻為0從 開始自左向右依次對水平方向的每格編號。
  •        輸入文件中同一行相鄰兩項之間用一個或多個空格隔開

　　輸出格式：

  • 輸出文件的第一行給出了一個正整數，表示你的程序所收集的最大分數之和。

　　樣例:

　　樣例輸入:

3 3
0 1 2 5 
0 2 1 3
1 2 1 3
1 3 1 4

　　樣例輸出:

12

　　數據範圍與提示:

  • 0≤餡餅個數 ≤2500。

　　分析：

  • 一道移動DP題。這題初看無從下手，餡餅和人都在移動，但仔細分析可得：定餡餅不動，由人移動去接餡餅。
  • 想好兩點：
    • 　　只有高度可以被下落速度整除時，改餡餅才有被接住的可能。
    •        時間可以當作縱坐標處理，即
  • 設f [ i ] [ j ]，i 表示時刻，j表示x坐標。用k枚舉移動的距離（k只能取-2，-1，0，1，2）。
  • 動態轉移方程為：f [ i ] [ j ] = max（f [ i – 1 ] [ j + k ] + a [ i ] [ j ]）;
#include<bits/stdc++.h>
using namespace std;
const int N=2600;
int w,h;
int cnt;
int T,P,V,W,maxtime;
int t[N],p[N],v[N],val[N];
int f[N][N];
int hehe(int i,int j){
    int ans=0;
    for(int k=-2;k<=2;k++){
        if(j+k<0||j+k>w)continue;
        ans=max(ans,f[i+1][j+k]);
    }
    return ans;
}

int main(){    
    scanf("%d%d",&w,&h);
    h--;//注意減一
    while(scanf("%d%d%d%d",&T,&P,&V,&W)==4){
        if(h%V==0){
            t[++cnt]=T+h/V;//注意+T;
            p[cnt]=P;v[cnt]=V;val[cnt]=W;
            maxtime=max(maxtime,t[cnt]);//找出下落時間最大的值來
        }
    }
    if(cnt==0){//如果都不符合那就結束
        printf("0");
        return 0;
    }
    for(int i=1;i<=cnt;i++){//可能有不同時出發的但同時同地落下的餡餅。累加。
        f[t[i]][p[i]]+=val[i];
    }
    for(int i=maxtime-1;i>=0;i--){//從後往前
        for(int j=w;j>=0;j--){//maxtime注意減一因為轉移有範圍。
            f[i][j]+=hehe(i,j);
        }
    }
    printf("%d",f[0][(w+1)/2]);//f數組定義的是從i秒j地的最大分數
    return 0;
}

 

 

 T3壓縮：dp(★★★★★★★★★★★★★★★★★★★★★★★★★……)

　　呵呵，洛谷紫題，教練拿來當作入門題考，beng……

　　題目描述：

  • 給一個由小寫字母組成的字符串，我們可以用一種簡單的方法來壓縮其中的重複信息。壓縮後的字符串除了小寫字母外還可以（但不是必需）包含大寫字母R 與M ，其中 M 標記重複串的開始， 重複從上一個 R（如果當前位置左邊沒有M ，則從串的開始算起）開始的解壓結果（稱為緩衝串）。
  • bcdcdcdcd可以壓縮為bMcdRR。

　　 輸入格式：

  • 輸入僅一行，包含待壓縮的字符串，僅包含小寫字母，長度為n。

　　輸出格式：

  • 輸出僅一行，即壓縮後字符串的最短長度。

　　樣例：

　　樣例輸入1：

aaaaaaa

　　樣例輸出1：

 5

　　樣例輸入2：

bcdcdcdcdxcdcdcdcd

　　樣例輸出2：

12

　　數據範圍與提示：

　　50%的數據滿足：1≤n≤20。

　　100%的數據滿足：1≤n≤50。

　　分析：

  • 設f[i][j][0]表示i到j的區間沒有M的情況：
    • 如果前半段與後半段相等，f[i][j][0] = min(f[i][j][0],f[i][mid][0]+1);
    • 如果[i~j],但有可能[i~k](i<k<j)可以摺疊，f[i][j][0] = min(f[i][j][0],f[i][k][0]+j-k);
  • f[i][j][1]表示i到j的區間內有M的情況：
    • k枚舉的是M的位置，即在k的後面放一個M：
    • f[i][j][1] = min(f[i][j][1],min(f[i][k][0],f[i][k][1])+min(f[k+1][j][0],f[k+1][j][1]))
    • 對區間[i , k]和[k+1,j]均有兩種選擇，然後加上M這個1。
  • 最後輸出ans = max（f[i][len][0],f[1][len][1]）。

 

#include <bits/stdc++.h>
using namespace std;
const int N=55;
char s[N];
int f[N][N][3];

bool judge(int l,int r){//判斷前一半是否和後一半相等
    if((r-l+1)&1)return false;//長度為奇數
    int mid=(l+r)>>1;
    for(int i=l;i<=mid;i++)
        if(s[i]!=s[i+mid-l+1])return false;
    return true;
}


int main(){
    scanf("%s",s+1);
    int len = strlen(s+1);
    for(int i=1;i<=len;i++)//初始化為沒有摺疊
        for(int j=i;j<=len;j++)
            f[i][j][0]=f[i][j][1]=(j-i+1);
    for(int l=1;l<=len;l++){
        for(int i=1,j;(j=i+l)<=len;i++){//i為區間起點，j為區間終點
            if(judge(i,j))//區間[i,j]正好能摺疊
                f[i][j][0]=min(f[i][(i+j)/2][0]+1,f[i][j][0]);
            for(int k=i;k<j;k++)//枚舉區間的斷點,有可能[i,k]能摺疊
                f[i][j][0]=min(f[i][j][0],f[i][k][0]+j-k);    
            for(int k=i;k<j;k++)//枚舉M的位置,即在k的後面加一個M
                f[i][j][1]=min(f[i][j][1],std::min(f[i][k][0],f[i][k][1])+min(f[k+1][j][0],f[k+1][j][1])+1);
        }
    }
    printf("%d\n",min(f[1][len][1],f[1][len][0]));
    return 0;
}

 

T4槍戰Maf：（思維★★）

　　題目描述：

  • 　　有 n個人，用1～n進行編號，每個人手裡有一把手槍。一開始所有人都選定一個人瞄準（有可能瞄準自己）。然後他們按某個順序開槍，且任意時刻只有一個人開槍。因此，對於不同的開槍順序，最後死的人也不同。

　　輸入格式：

  • 　　輸入n 人數n<1000000
  •        接下來n個數，依次為每個人的aim。

 

　　輸出格式：

  • 　　輸出只有一行，共兩行整數，為最後死亡的最小和最大人數。

 

　　樣例輸出：

8
2 3 2 2 6 7 8 5

　　樣例格式：

3 5

　　分析：

　　設最大存活人數Max，最少存活人數Min 

 

#include<bits/stdc++.h>
using namespace std;
const int N=1000100;
int n;
int aim[N];
int Min,Max;
int q[N],rd[N];
bool die[N],live[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&aim[i]);
        rd[aim[i]]++;//存入度
    }
    for(int i=1;i<=n;i++){
        if(rd[i]==0){
            Min++;//最小必活數+1
            Max++;//隊列維護的是入度為0的點
            q[Max]=i;
        }
    }
    int aa=1;
    while(aa<=Max){//掃描隊列
        int front=q[aa++];//取出隊首並出隊
        if(die[aim[front]])continue;//隊首目標已死(多個入度為0的點指向一個點)
        die[aim[front]]=1;//隊首目標必死
        int faim=aim[aim[front]];//隊首目標的目標可死可不死，看決策
        rd[faim]--;
        live[faim]=1;//可以讓他活，但想死的時候隨時可以讓他死，在環可以最後死
        if(rd[faim]==0){//雖然入度為0，但不一定是必活，所以Min不加
            q[++Max]=faim;
        }
    }//下面處理只剩下環
    for(int i=1;i<=n;i++){
        if(rd[i]&&!die[i]){
            int l=0,flag=0;//l記錄環大小,flag標記環上是否有live的點 
            for(int j=i;!die[j];j=aim[j]){
                l++;
                flag|=live[j];
                die[j]=1;//標記已死，避免其他的再來計算
            }
            if(!flag&&l>1)Min++;//l=1表示自環，必死
            Max+=l/2;
        }
    }
    printf("%d %d",n-Max,n-Min);
    return 0;
}

 

 

 博主在沒有任何編輯器的惡劣情況下成功奪得514高地（敲了一個多小時），點贊關注頂一下唄……@^_^@……

 

VirMach 便宜 VPS

QNews

QNews