長樂培訓Day3

来源:https://www.cnblogs.com/I-Love-You-520/archive/2019/07/24/11239720.html
-Advertisement-
Play Games

T1 奶牛曬衣服 題目 【題目描述】 在熊大媽英明的帶領下，時針和他的同伴生下了許多牛寶寶。熊大媽決定給每個寶寶都穿上可愛的嬰兒裝。於是，為牛寶寶洗曬衣服就成了很不爽的事情。 聖人王擔負起了這個重任。洗完衣服後，你就要弄乾衣服。衣服在自然條件下用1的時間可以曬乾A點濕度。摳門的熊大媽買了1台烘衣機。 ...


T1 奶牛曬衣服

題目

【題目描述】

在熊大媽英明的帶領下，時針和他的同伴生下了許多牛寶寶。熊大媽決定給每個寶寶都穿上可愛的嬰兒裝。於是，為牛寶寶洗曬衣服就成了很不爽的事情。

聖人王擔負起了這個重任。洗完衣服後，你就要弄乾衣服。衣服在自然條件下用1的時間可以曬乾A點濕度。摳門的熊大媽買了1台烘衣機。

使用烘衣機可以讓你用1的時間使1件衣服除開自然曬乾的A點濕度外，還可烘乾B點濕度，但在1的時間內只能對1件衣服使用。

N件的衣服因為種種原因而不一樣濕，現在告訴你每件衣服的濕度，要你求出弄乾所有衣服的最少時間（濕度為0為乾）。

【輸入格式】

第一行N，A，B，接下來N行，每行一個數，表示衣服的濕度。

【輸出格式】

一行，最少時間。

【數據規模】

1<=濕度,A,B<=500000,1<=N<=500000。

解析

第一題依舊是送分的（安慰一下其他題爆零的情緒QAQ）。

直接二分即可，每次迴圈中只需要判斷s[i]（濕度）與a*mid（mid為天數）的大小就可以了。

最後的答案即為l。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
int n,a,b,s[500100];
long long l,r,mid;
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    //freopen("dry.in","r",stdin);
    //freopen("dry.out","w",stdout);
    n=read(),a=read(),b=read();
    for(int i=1;i<=n;i++)
    {
        s[i]+=read();
        r+=s[i];
    }
    while(l<=r)
    {
        long long ans=0;
        mid=(l+r)>>1;
        for(int i=1;i<=n;i++)
            if(s[i]-a*mid>0)
            {
                if((s[i]-a*mid)%b==0) ans+=(s[i]-a*mid)/b;
                else ans+=(s[i]-a*mid)/b+1;
            }
        if(ans<=mid) r=mid-1;
        else l=mid+1;
    }
    cout<<l;
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}
View Code

 

 

 

 

 

T2 解密文件

題目

【題目描述】

 已知英語中26個字母出現的概率p[0],p[1]……,p[25]（它們的和為1），分別表示’a’, ‘b’,‘c’……出現的概率（大寫字母和小寫字母被認為是一樣的）。

現在有一個加密過的文件，加密方法是將原文件中的每一個字母進行相同的變換，其他的字元不變，變換的方法如下：

如果將a到z編號為0到25，那麼字母i將被替換成(i+k) mod 26，0<=k<26。原來是大寫的字母，仍然是大寫，原來是小寫的字母仍然是小寫。

但是你並不知道k的值，所以只好枚舉。因為知道26個字母出現的頻率，所以你可以選擇一個儘量好的k，使得頻率的方差和最小，方差和定義如下：

假設你枚舉的k還原出來的原文件中的26個字母出現的概率為x[0], x[1], ……, x[25]，那麼方差和為：(p[0]-x[0])^2 + (p[1]-x[1])^2 + …… + (p[25]-x[25])^2。

如果有兩個相同的k一樣好，那麼選較小的k。

最後輸出解密出的原文件。

【輸入格式】

前26行分別是26個字母出現的概率。

接下來是一個只含有26個大小寫字母和空格，換行符，標點符號，阿拉伯數字等的文本。

【輸出格式】

解密過的文本。

【數據規模】

輸入文件不超過10k。

解析

這題直接模擬即可，非常噁心有趣。

先預處理出a數組（每個數字所對應的字母，0-25表示a-z，26-51表示A-Z）。

處理文本我用的是string，直接while迴圈getline(cin,s[++temp])，這裡有兩個細節：

1、輸入時要先輸入一個“\n”（我也不知道為什麼，反正它會讀入一個換行）；

2、由於++temp，所以即使沒有讀入了還是會自加一次，所以要-1或者輸出時把<=改成<。

關於每個字母的頻率，本蒟蒻是在枚舉k時每次都計算，實際上並不用那麼麻煩，

因為每個字母都是由初始字母一一對應轉換來的，所以只需要計算初始字母的頻率就行了（輸入時明明給了的說）。

然後取方差和最小的即可。輸出時如果是字母要分大寫和小寫處理，

小寫輸出a[(int)((s[i][j]-'a'+kk)%26)]，大寫輸出a[(int)((s[i][j]-'A'+kk)%26+26)]（預處理a數組是大寫字母實在小寫字母基礎上+26的）。

如果不是字母直接輸出原來的文本就好了。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int temp=0,sum[55],kk;
double p[26],x[26],ans,minn=1000000.0;
char a[55];
string s[10001];
int main()
{
    //freopen("decode.in","r",stdin);
    //freopen("decode.out","w",stdout);
    for(int i=0;i<26;i++) a[i]=char('a'+i);
    for(int i=26;i<52;i++) a[i]=char('A'+i-26);
    for(int i=0;i<26;i++) cin>>p[i];
    scanf("\n");
    while(getline(cin,s[++temp])) ;
    for(int k=0;k<26;k++)
    {
        memset(sum,0,sizeof(sum));
        ans=0.0;
        for(int i=1;i<=temp;i++)
            for(int j=0;j<s[i].size();j++)
            {
                if(s[i][j]>='a'&&s[i][j]<='z') sum[(s[i][j]-'a'+k)%26]++;
                if(s[i][j]>='A'&&s[i][j]<='Z') sum[(s[i][j]-'A'+k)%26]++;
            }
        for(int i=0;i<26;i++)
        {
            x[i]=(double)(sum[i]*0.03846153846);
            ans+=(p[i]-x[i])*(p[i]-x[i]);
        }
        if(ans<minn)
        {
            minn=ans;
            kk=k;
        }
    }
    for(int i=1;i<temp;i++)
    {
        for(int j=0;j<s[i].size();j++)
        {
            if(s[i][j]>='a'&&s[i][j]<='z') cout<<a[(int)((s[i][j]-'a'+kk)%26)];
            else if(s[i][j]>='A'&&s[i][j]<='Z') cout<<a[(int)((s[i][j]-'A'+kk)%26+26)];
            else cout<<s[i][j];
        }
        cout<<endl;
    }
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}
View Code

 

 

 

 

 

T3 休息

題目

【題目描述】

休息的時候，可以放鬆放鬆渾身的肌肉，打掃打掃衛生，感覺很舒服。在某一天，某LMZ開始整理他那書架。

已知他的書有n本，從左到右按順序排列。他想把書從矮到高排好序，而每一本書都有一個獨一無二的高度Hi。

他排序的方法是：每一次將所有的書劃分為儘量少的連續部分，使得每一部分的書的高度都是單調下降，然後將其中所有不少於2本書的區間全部翻轉。

重覆執行以上操作，最後使得書的高度全部單調上升。可是畢竟是休息時間，LMZ不想花太多時間在給書排序這種事上面。

因此他劃分並翻轉完第一次書之後，他想計算，他一共執行了多少次翻轉操作才能把所有的書排好序。

LMZ驚奇地發現，第一次排序之前，他第一次劃分出來的所有區間的長度都是偶數。

【輸入格式】

第一行一個正整數n, 為書的總數。

接下來n行，每行僅一個正整數Hi，為第i本書的高度。

【輸出格式】

僅一個整數，為LMZ需要做的翻轉操作的次數。

【數據規模】

對於10%的數據：n<=50

對於40%的數據：n<=3000

對於100%的數據：1<=n<=100000, 1<=Hi<=n

解析

其實這題就是在求逆序對，所以用歸併排序來做。

在歸併的過程中，如果a[i]>a[j]，即逆序對，則ans+=mid-i+1，具體原因模擬一遍就知道了。

程式中運用到的reverse函數是<algorithm>里的，作用是翻轉，在給p[cnt].r賦值的時候,賦的是i-1，所以在翻轉時，得在最後+1。

答案是在n2/2的，很顯然int是不夠的，記得開long long。

Code

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e5 + 10;
int c[N], a[N], n;
long long ans;
void msort(int l, int r) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    msort(l, mid), msort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r) {
        if(a[i] <= a[j]) 
            c[k++] = a[i++];
        else {
            ans += mid - i + 1;
            c[k++] = a[j++];
        }
    }
    while(i <= mid) c[k++] = a[i++];
    while(j <= r) c[k++] = a[j++];
    for(int t = l; t <= r; t++)
        a[t] = c[t];
}
struct rec {
    int l, r;
}p[N];
int main() {
    //freopen("rest.in", "r", stdin);
    //freopen("rest.out", "w", stdout);
    int cnt = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        if(a[i] > a[i - 1]) {
            p[cnt].r = i - 1;
            p[++cnt].l = i;
        }
    }
    p[cnt].r = n;
    for(int i = 1; i <= cnt; i++) 
        reverse(a + p[i].l, a + p[i].r + 1), ans++;
    msort(1, n);
    cout<<ans;
    return 0;
}
View Code

 

 

 

 

 

T4 矩陣取數游戲

題目

【題目描述】

帥帥經常跟同學玩一個矩陣取數游戲：對於一個給定的n*m的矩陣，矩陣中的每個元素aij均為非負整數。游戲規則如下：

1.每次取數時須從每行各取走一個元素，共n個。m次後取完矩陣所有的元素；
2.每次取走的各個元素只能是該元素所在行的行首或行尾；
3.每次取數都一個得分值，為每行取數的得分之和；每行取數的得分=被取走的元素值*2i，其中i表示第i次取數(從1開始編號)；
4.游戲結束總得分為m次取數得分之和。

帥帥想請你幫忙寫一個程式，對於任意矩陣，可以求出取數後的最大得分。

【輸入格式】

輸入文件包括n+1行：

第一行為兩個用空格隔開的整數n和m。

第2~n+1行為n*m矩陣，其中每行m個用單個空格隔開。

【輸出格式】

輸出文件僅包含1行，為一個整數，即輸入矩陣取數後的最大的分。

【數據規模】

60%的數據滿足：1<=n, m<=30，答案不超過1016

100%的數據滿足：1<=n, m<=80，0<=aij<=1000

解析

這題實際上一眼就可以看出是區間DP。

令f[i][j]表示第k行取數取成了[i,j]的區間的得分。

由於只能從左右兩端取，所以狀態轉移方程顯而易見：

f[i][j]=max(f[i-1][j]+a[i-1][j]*2m-j+i-1,f[i][j+1]+a[i][j+1]*2m-j+i-1)

由於本蒟蒻的代碼i和j都是從0開始迴圈的所以2的次方並不是m-j+i-1，而是i+j（個人更推薦上面的寫法，更通俗易懂）。

好了，這題就是這樣。

才怪，

如果單單隻是這樣的話，這題就太簡單了，

但是！！！！！

註意看數據範圍，m最大為80，那麼2的80次方是多少？1208925819614629174706176！

這麼大的數int不行，long long也不行，哪怕是unsigned long long也不夠，那怎麼辦呢？

答案是：高精！

高精才是這道題真正噁心的地方，需要用到的有：

高精+高精、高精*單精、max(高精,高精)。

所以本蒟蒻來講一下高精如何實現......才怪。

由於本蒟蒻不會高精，所以下麵代碼中的高精是直接從標程“借鑒”來的（手動滑稽）。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
int n,m,a[85][85];
struct sb{
    int c[16];
    friend inline sb operator * (const sb &a, const int &b)
    {
        sb c;
        for(int i = 1; i <= 15; i ++)
            c.c[i] = 0;
        c.c[0] = a.c[0];
        int p = 0;
        for(int i = 1; i <= a.c[0]; i ++)
        {
            c.c[i] = a.c[i] * b + p;
            p = c.c[i] / 10000;
            c.c[i] %= 10000;
        }
        int &len = c.c[0];
        while (p)
        {
            c.c[++len] = p % 10000;
            p /= 10000;
        }
        return c;
    }
    friend inline sb operator * (const sb &a, const sb &b)
    {
        sb c;
        for(int i = 1; i <= 15; i ++)
            c.c[i] = 0;
        c.c[0] = a.c[0] + b.c[0] - 1;
        for(int i = 1; i <= a.c[0]; i ++)
        {
            int p = 0;
            for(int j = 1; j <= b.c[0]; j ++)
            {
                c.c[i + j - 1] += a.c[i] * b.c[j] + p;
                p = c.c[i + j - 1] / 10000;
                c.c[i + j - 1] %= 10000;
            }
            c.c[i + b.c[0]] += p;
        }
        if (c.c[c.c[0] + 1]) c.c[0] ++;
        return c;
    }
    friend inline sb operator + (const sb &a, const sb &b)
    {
        sb c;
        int &len = c.c[0];
        c.c[0] = max(a.c[0], b.c[0]);
        for(int i = 1; i <= 15; i ++)
            c.c[i] = 0;
        int p = 0;
        for(int i = 1; i <= len; i ++)
        {
            c.c[i] = a.c[i] + b.c[i] + p;
            p = c.c[i] / 10000;
            c.c[i] %= 10000;
        }
        if (p) len ++, c.c[len] = p;
        return c;
    }
    inline sb operator = (const sb &b)
    {
        c[0] = b.c[0];
        for(int i = 1; i <= 15; i ++)
            c[i] = 0;
        for(int i = 1; i <= b.c[0]; i ++)
            c[i] = b.c[i];
        return *this;
    }
    inline void print()
    {
        cout << c[c[0]];
        for(int i = c[0] - 1; i >= 1; i --)
            printf("%04d", c[i]);
        cout << endl;
    }
};
inline sb Max(const sb &a, const sb &b)
{
    if (a.c[0] > b.c[0]) return a;
    else if (a.c[0] < b.c[0]) return b;
    else if (a.c[0] == b.c[0])
    {
        for(int i = a.c[0]; i >= 1; i --)
            if (a.c[i] > b.c[i]) return a;
            else if (a.c[i] < b.c[i]) return b;
    }
    return a;
}
sb f[85][85],cf[85],tot,ans;
int main()
{
    //freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) a[i][j]=read();
    cf[0].c[0]=1;cf[0].c[1]=1;
    for(int i=1;i<=m;i++) cf[i]=cf[i-1]*2;
    for(int k=1;k<=n;k++)
    {
        for(int i=0;i<=m;i++)
            for(int j=0;j<=m;j++) memset(f[i][j].c,0,sizeof(f[i][j].c));
        f[m][m].c[0]=1;
        memset(tot.c,0,sizeof(tot.c));
        tot.c[0]=1;
        for(int i=0;i<=m;i++)
            for(int j=0;j<=m-i;j++)
            {
                if(i==0&&j==0) continue;
                if(i) f[i][j]=Max(f[i][j],f[i-1][j]+cf[i+j]*a[k][i]);
                if(j) f[i][j]=Max(f[i][j],f[i][j-1]+cf[i+j]*a[k][m-j+1]);
                tot=Max(tot,f[i][j]);
            }
        ans=ans+tot;
    }
    ans.print();
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
View Code

 


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

-Advertisement-
Play Games
更多相關文章
  • Smarty內置函數之capture
    capture的作用是： 捕獲模板輸出的數據並將其存儲到一個變數，而不是把它們輸出到頁面，任何在 {capture name="foo"}和{/capture}之間的數據將被存儲到變數$foo中，該變數由name屬性指定，在模板中通過 $smarty.capture.foo 訪問該變數，{captu ...
  • python函數知識七 閉包、裝飾器一（入門）
    21.閉包 1. 閉包：在嵌套函數內，使用非全局變數(且不使用本層變數) 2. 閉包的作用：1.保證數據的安全性（純潔度）。2.裝飾器使用 3. ._\_closure\_\_判斷是否是閉包 22.裝飾器一（入門） 1.一個裝飾器裝飾多個函數 開放封閉原則：擴展是開放的（增加新功能），源碼是封閉的（ ...
  • [Java 開發利器Lombok] 常用註解演示
    在以往的對象模型編碼時，我們需要寫一大堆的get/set以及不同的構造函數等。Lombok為我們提供了一個非常好的插件形式。 在大多數的項目中，只需要使用到以下集中Annotation就足夠了，如果需要查看更多的選項，請參考： "傳送門" 1. 2. 3. 4. 生成final 欄位的構造函數 5. ...
  • GCD&&素篩&&快速冪 --A - Pseudoprime numbers
    Fermat's theorem states that for any prime number p and for any integer a > 1, ap = a (mod p). That is, if we raise a to the pth power and divide by p ...
  • 學習shiro第一天
    shiro是一個強大而且易用的安全框架(主要包括認證和授權)，它比spring security更加簡單，而且它不依賴於任何容器，可以和許多框架集成。 shiro的核心是安全管理器（SecurityManagement），它主要包括四個模塊： 1.Authentication:認證模塊，主要用於驗證 ...
  • Flink 從0到1學習—— Flink 不可以連續 Split(分流)？
    前言 今天上午被 Flink 的一個運算元困惑了下，具體問題是什麼呢？ 我有這麼個需求：有不同種類型的告警數據流(包含恢複數據)，然後我要將這些數據流做一個拆分，拆分後的話，每種告警裡面的數據又想將告警數據和恢複數據拆分出來。 結果，這個需求用 Flink 的 Split 運算符出現了問題。 分析 需 ...
  • 如何優雅關閉 Spring Boot 應用
    如何優雅關閉 Spring Boot 應用 如何優雅關閉 Spring Boot 應用前言定製 Tomcat Connector 行為內嵌 Tomcat 添加 Connector 回調開啟 Shutdown Endpoint模擬測試實現自動化總結參考 如何優雅關閉 Spring Boot 應用前言定 ...
  • Python 也會傳文件，再也不用看某某網盤的臉色了！
    在我們的日常生活和工作中，難免會碰到要給別人傳文件的時候。可能這對現在的你來說不是一件很難的事情，估計相當多的一部分人說我可以直接把文件拖進微信或者 qq 里發給別人，但這個只適用於文件較少的時候，文件較多的時候用聊天工具來進行文件傳輸就又變成了一件很麻煩的事情。 這時候你可能又會說，那我可以傳到某 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類