AtCoder-arc059 題解

来源:https://www.cnblogs.com/C-W-K/archive/2019/11/29/11960282.html
-Advertisement-
Play Games

A いっしょ / Be Together (結論/暴力) "題目鏈接" 題目大意: 有 $n$ 個數字,要將它們變成相等,對每一個數字最多操作一次,如將 $a \to b$ 的代價為 $(a b)^2$ ,求出最小的代價。 大致思路: 根據不等式的知識可以知道,假設最後數字變為 $x$,那麼 $x$ ...


A - いっしょ / Be Together (結論/暴力)

題目鏈接

題目大意:

\(n\) 個數字,要將它們變成相等,對每一個數字最多操作一次,如將 \(a \to b\) 的代價為 \((a-b)^2\) ,求出最小的代價。

大致思路:

根據不等式的知識可以知道,假設最後數字變為 \(x\),那麼 \(x\)\(\sum{a_i}\) 平均數的代價最小,由於要為整數,就取最接近 \(x\) 兩個整數做為結果,取其中最小的代價就行了。

代碼:

#include<bits/stdc++.h>
using namespace std;
int n;
int a[200];
int main()
{
    //freopen("H:\\c++1\\in.txt","r",stdin);
    //freopen("H:\\c++1\\out.txt","w",stdout);
    scanf("%d",&n);
    int ans1=0,ans2=0,sum=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    int t1=sum/n,t2=(sum+n-1)/n;
    for(int i=1;i<=n;i++){
        ans1+=(t1-a[i])*(t1-a[i]);
        ans2+=(t2-a[i])*(t2-a[i]);
    }
    printf("%d\n",min(ans1,ans2));
    return 0;
}

B - アンバランス / Unbalanced (思維)

題目鏈接

題目大意:

給定一個字元串 \(s\) ,問其中是否存在“不平衡”的連續子串,“不平衡”的字元串被定義為長度大於等於 \(2\) ,且其中一個字母出現次數過半。有的話任意輸出一個。

大致思路:

一開始,想到要大於半數,那麼必須存在兩個相鄰的字母相同,交上去 \(wa\) 了,後來發現其實還有一種可能就是 \(3\) 個字母,頭尾相同,如 \(aba\) ,把兩種情況都枚舉一下,就行了。

代碼:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char s[N];
int main()
{
    //freopen("H:\\c++1\\in.txt","r",stdin);
    //freopen("H:\\c++1\\out.txt","w",stdout);
    scanf("%s",s+1);
    int len=strlen(s+1);
    if(len==2&&s[1]==s[2]){ // 特判
        printf("1 2\n");
        return 0;
    }
    int l=-1,r=-1;
    for(int i=1;i<len-1;i++){
        if(s[i]==s[i+1]||s[i]==s[i+2]||s[i+1]==s[i+2]){
            l=i,r=i+2;
            break;
        }
    }
    printf("%d %d\n",l,r);
    return 0;
}

C - キャンディーとN人の子供 / Children and Candie (dp+計算貢獻)

題目鏈接

題目大意:

\(n\) 個人, \(C\) 個糖果,將 \(C\) 個糖果分配給 \(n\) 個人,每一個人有 \(c_i\) 個,可以為 \(0\) 個,每一個人有一個活躍度 \(x_i\) ,那麼這次分配的價值為 \(\prod{x_i^{c_i}}\) ,將一個值用 \(f(x_1,x_2,...,x_n)\) 表示,現在給你兩個數字 \(A[n],B[n]\) ,要求求出下式。

img

大致思路:

雖然這題過了,但是還是有很多細節的部分沒用弄懂,一開始根本沒有想到 \(dp\) 來解,後來看了題解才知道,當 \(A_i=B_i\) 的情形比較好想,設 \(dp[i] [j]\) 表示分給前i個人,使用 \(j\) 個糖果的價值數,那麼可以寫出方程,\(dp[i][j]+=dp[i-1][j-k]*(A_i^k)\)\(k\) 其實就是枚舉分給第 \(i\) 個人的糖果,但是當 \(A_i != B_i\) 的時候,我對於為什麼可以將求和號提出來有些疑惑,就是為什麼可以單獨計算某一個對總體的貢獻。具體的解法就是,將上述方程改成 \(dp[i] [j] += dp[i-1] [j-k] * (\sum_{t=A[i]}^{B[i]}{t^k})\),然後通過預處理就可以 \(O(n^3)\) 的過了。

(之後還得在思考思考)

代碼:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=500;
const int mod=1e9+7;
ll ksm(ll a,ll b){ // 快速冪
    ll res=1,t=a;
    while(b){
        if(b&1)res=(res*t)%mod;
        t=(t*t)%mod;
        b>>=1;
    }
    return res;
}
ll dp[N][N];
ll n,c;
ll a[N],b[N];
ll p[N][N];
ll sum[N][N];
void init(){ // 預處理
    for(int i=1;i<N;i++)
    for(int j=0;j<N;j++)p[i][j]=ksm(i,j);
    for(int k=0;k<N;k++){
        for(int i=1;i<N;i++)sum[i][k]=(sum[i-1][k]+p[i][k])%mod;
    }
}
int main()
{
    //freopen("H:\\c++1\\in.txt","r",stdin);
    //freopen("H:\\c++1\\out.txt","w",stdout);
    init();
    scanf("%lld%lld",&n,&c);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    for(int j=0;j<=c;j++){
        for(int k=0;k<=j;k++){ //枚舉第i個人拿的糖果數
            dp[i][j]=(dp[i][j]+(dp[i-1][j-k]*(sum[b[i]][k]-sum[a[i]-1][k]+mod)%mod))%mod;
        }
    }
    printf("%lld\n",dp[n][c]);
    return 0;
}

D - バイナリハック / Unhappy Hacking (dp計數)

題目鏈接

題目大意:

\(3\) 個按鍵,分別是 \(,,0,1,backspace\) 鍵,按下 \(0\) 或者 \(1\) ,就會在最右邊出現 \(0\) 或者 \(1\) ,按下 \(backspace\) 鍵就會將最右邊的數字刪去,如果沒有數字就無事發生。現在告訴你一串數字,並且按了 \(n\) 次鍵,問有幾種按法。

大致思路:

這題一開始想分類討論,後來發現刪除的數字若是連在一起又可以改變刪除的順序就不會做了,看了題解,原來就是我一開始寫的 \(dp\) ,但是當時不懂怎麼轉移。用 \(dp[i][j]\) 表示按了 \(i\) 下,數字長度為 \(j\) 的方案數,我們考慮當前按下的是數字,那麼必然是和給定串的對應位相同,若按下的是刪除鍵,那麼就這位刪除的可以是 \(0\) 也可以是 \(1\) 就有兩種可能,按照這個轉移一下即可。

代碼:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5010;
const int mod=1e9+7;
ll dp[N][N];
char s[N];
int n;
int main()
{
    //freopen("H:\\c++1\\in.txt","r",stdin);
    //freopen("H:\\c++1\\out.txt","w",stdout);
    dp[0][0]=1;
    scanf("%d",&n);
    scanf("%s",s+1);
    int len=strlen(s+1);
    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++){
        if(j==0)dp[i+1][j]=(dp[i][j]+dp[i+1][j])%mod;//特判
        else{
            dp[i+1][j-1]=(dp[i][j]*2+dp[i+1][j-1])%mod;//按backspace
        }
        dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j])%mod;//按數字鍵
    }
    printf("%lld\n",dp[n][len]);
    return 0;
}

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

-Advertisement-
Play Games
更多相關文章
  • 2.1、anaconda的安裝 ​ 1 、安裝可執行程式 ​ 2 、配置環境變數 ​ 根據環境變數的 去查找可執行程式文件,如果查找到就執行,如果查找不到就報錯。 ​ 3 、python的多版本相容問題 ​ 修改可執行程式的文件名,再配置環境變數 ​ 4 、hash案例 2.2、requests模塊 ...
  • 生活中,當你閑暇之餘瀏覽資訊的時候,當你搜索資料但繁雜信息夾雜時候,你就會想,如何更為準確的定位需求信息。今天就為你帶來: 分頁查詢 需求分析:在列表頁面中,顯示指定條數的數據,通過翻頁按鈕完成首頁/上一頁/下一頁/尾頁的查詢 數據分析: 通過觀察,頁面上需要顯示下麵的幾個數據:當前頁:curren ...
  • 安裝 SQLAlchemy 報錯 安裝命令 報錯截圖 編碼錯誤,這裡我們需要改下源碼 解決方案 重新安裝,安裝成功 參數文章: ...
  • 在python3.7 環境下 函數聲明時能在參數後加冒號,如圖: 可能有疑問,python不是動態類型語言 ,難不成還能指定參數類型? 來看一下列印結果: 但同時也確實能傳其他類型的值 如:f("test",123) 那結果如何呢? 如下: 當然會報錯了啊,返回值是一個字元串,int型不能參與字元串 ...
  • student類 package cn.itheima.Manag;/** * *標準類 * **/public class Student { //學號 private String id; //姓名 private String name; //年齡 private String age; // ...
  • 伺服器的監控通過安裝一些常用的監控軟體之外,有時也需要運行一些shell或Python腳本;shell下可以使用系統自帶的ps/free/top/df等shell命令,Python可以調用subprocess等模塊來運行shell命令,不過這麼做就比較麻煩。這裡有一個比較好用的第三方模塊:psuti ...
  • 1.在一個文件夾名為www.html3.com的web項目來實現,首先到nginx的配置文件nginx.conf做如下配置 python和html混合編寫的文件,我以文件尾碼為.phtml,通過伺服器配置讓它重定向到 /rewrite/ 2.進去項目目錄下的static/html/ 編寫一個1.ph ...
  • 函數1 函數2 函數3 —————————————————————————————————————————————————————————————————— 1調用2,將變數a的地址做實參,傳給2的指針變數b。形如&a —》 *b。 2調用3,若仍以&b —》*c,則在指針變數c中,存入的是b的地址 ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...