長樂國慶集訓Day4

来源:https://www.cnblogs.com/I-Love-You-520/archive/2019/10/04/11623277.html
-Advertisement-
Play Games

T1 一道數論神題 題目 【題目描述】 LYK有一張無向圖G={V,E},這張無向圖有n個點m條邊組成。並且這是一張帶權圖,只有點權。 LYK想把這個圖刪乾凈,它的方法是這樣的。每次選擇一個點,將它刪掉,但刪這個點是需要代價的。 假設與這個點相連的還沒被刪掉的點是u1,u2,…,uk。LYK將會增加 ...


T1 一道數論神題

題目

【題目描述】

LYK有一張無向圖G={V,E},這張無向圖有n個點m條邊組成。並且這是一張帶權圖,只有點權。

LYK想把這個圖刪乾凈,它的方法是這樣的。每次選擇一個點,將它刪掉,但刪這個點是需要代價的。

假設與這個點相連的還沒被刪掉的點是u1,u2,…,uk。LYK將會增加 a[u1],a[u2],…,a[uk]的疲勞值。

它想將所有點都刪掉,並且刪完後自己的疲勞值之和最小。你能幫幫它嗎?

【輸入格式】

第一行兩個數n,m表示一張n個點m條邊的圖。

第二行n個數ai表示點權。

接下來m行每行三個數u,v,表示有一條連接u,v的邊。數據保證任意兩個點之間最多一條邊相連,並且不存在自環。

【輸出格式】

你需要輸出這個最小疲勞值是多少。

【輸入樣例】

4 3
10 20 30 40
1 4
1 2
2 3

【輸出樣例】

40

【數據規模】

對於30%的數據n≤10。

對於60%的數據n,m≤1000。

對於 100%的數據1≤n,m,ai≤100000。

解析

久違的送分題

貪心思想,將每個點對與其連接的點的貢獻從大到小排序,依次刪除即可。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
inline int read()
{
    int num=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num;
}
const int N=100100;
struct rec{
    int w,num;
}a[N];
int n,m,b[N];
long long ans;
bool v[N];
vector<int> edge[N];
bool cmp(rec x,rec y)
{
    return x.w>y.w;
}
int main()
{
    //freopen("god.in","r",stdin);
    //freopen("god.out","w",stdout);
    memset(v,false,sizeof(v));
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i].w=read(),a[i].num=i,b[i]=a[i].w;
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        edge[x].push_back(y),edge[y].push_back(x);
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        int x=a[i].num;
        v[x]=true;
        for(int j=0;j<edge[x].size();j++)
            if(!v[edge[x][j]]) ans+=b[edge[x][j]];
    }
    cout<<ans;
    return 0;
}
View Code

 

 

 

 

 

T2 數組異或

題目

【題目描述】

xor——異或,和and與or一樣,是一種重要的邏輯運算,他的運算規律是0xor 0=0,1 xor 1=0,1 xor 0=1,0 xor 1=1。

兩個整數之間的異或是將兩個整數轉化成二進位,對他們的每一位分別進行xor操作,例:6(110) xor 13(1101) = 11(1011)

現在我們要介紹一種新的操作——數組異或,將兩個相同大小(假設都為n)的數組A、B異或成一個新數組C,則新數組必滿足:

現在給你數組大小n,和兩個數組A,B

求他們的異或數組C

由於最終答案可能過大,你需要對C的每個元素對109+7取模

【輸入格式】

一共3行。

第一行一個正整數N。

接下來兩行每行N個正整數,表示數組A、B。

【輸出格式】

一共1行,N個正整數,表示數組C。

【輸入樣例】

7
20670 1316 25227 8316 21095 28379 25235
19745 6535 14486 5460 15690 1796 12403

【輸出樣例】

7583 52096 161325 276944 453024 675974 958287

【數據規模】

對於50%的數據,N≤100。

對於全部的數據,N≤105

解析

數論不太懂,以下是出題人的題解。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
inline int read()
{
    int num=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num;
}
const int N=133333,mod=1000000007;
int n,a[N],b[N],aa[33][2],bb[33][2];
int main()
{
    //freopen("xorarray.in","r",stdin);
    //freopen("xorarray.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    for(int i=1;i<=n;i++)
    {
        long long c=0;
        for(int j=0;j<=30;j++)
        {
            aa[j][(a[i]>>j)&1]++,bb[j][(b[i]>>j)&1]++;
            long long cc=((long long)aa[j][0]*bb[j][1]+(long long)aa[j][1]*bb[j][0])%mod*(1<<j)%mod;
            c=(c+cc)%mod;
        }
        cout<<c<<" ";
    }
    return 0;
}
View Code

 

 

 

 

 

T3 偵探游戲

題目

【題目描述】

小W最近沉迷一個偵探游戲,在這個游戲中會不斷出現命案,而小W作為主角,需要不斷地收集各種關鍵證據,只有當所有的關鍵證據都被找到,你才能駁倒所有人錯誤的判斷,找出真正的凶手。

一共有N個關鍵證據以及M條信息,每條信息如下所示 : 如果你已經掌握了證據i,那麼你可以通過k個時間的搜索和推理得到證據j,同樣的,如果你掌握了證據j你也可以通過k個時間得到證據i。

游戲開始時玩家通過初步觀察現場已經得到了證據1,於此同時,每個玩家在游戲開始階段時都能獲得一個特殊技能來加快游戲進度,增加趣味性。小W 選了一個他以前從來沒用過的技能:好運。這是一個被動技能,系統會在游戲開始時選定一對證據(a,b)(a≠b)當小W發現其中一個證據的時候,他會很好運地立即獲得另外一個證據(不計入時間)。

但是這個技能是完全隨機的,小W完全不知道進入游戲後系統會挑選哪一對證據,他希望你能幫助他算出他花在本輪游戲上的時間的期望值,這樣他心裡能有點B數。

提供的信息保證: i不會等於j,每個k值都互不相同,N個證據都能被得到。

【輸入格式】

一共M+1行。

第一行兩個正整數N和M,表示證據數量和信息數量。

接下來M行,每行三個數字i,j,k表示一個信息

【輸出格式】

共1行,1個整數(期望值是實數,但這裡請直接保留2位小數輸出)。

【輸入樣例】

3 3
1 2 3
1 3 2
2 3 5

【輸出樣例】

2.33

【數據規模】

對於20%的數據,N≤100

對於60%的數據,N≤1000

對於全部的數據,N≤20000,M≤105,1≤k≤106

解析

一條邊權為w的邊,如果把MST上所有邊權小於w的邊加入,且該邊加入後聯通的點對數增加了K,那麼路徑上最大邊權為w的點對數即為K。

所以可以用一個並查集,把邊權從小到大加邊,對於邊(u,v,w),答案累加sizeu*sizev*w,再合併u,v兩點所屬聯通塊。(sizei表示點i所屬聯通塊的大小)。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
inline 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;
}
const int N=33333,M=133333;
struct rec{
    int u,v,d;
}edge[M];
int n,m,fa[N],s[N];
long long cnt,sum;
bool cmp(rec x,rec y)
{
    return x.d<y.d;
}
int find(int x)
{
    if(fa[x]==x) return fa[x];
    return fa[x]=find(fa[x]);
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++) edge[i].u=read(),edge[i].v=read(),edge[i].d=read();
    sort(edge+1,edge+m+1,cmp);
    for(int i=1;i<=n;i++) fa[i]=i,s[i]=1;
    for(int i=1;i<=m;i++)
    {
        int x=find(edge[i].u),y=find(edge[i].v);
        if(x==y) continue;
        sum+=edge[i].d,cnt+=(long long)s[x]*s[y]*edge[i].d,s[x]+=s[y],fa[y]=x;
    }
    double ans=sum-2.0*cnt/n/(n-1);
    printf("%.2lf",ans);
    return 0;
}
View Code

 

 

 

 

 

T4 天上掉餡餅

題目

【題目描述】

小G進入了一個神奇的世界,在這個世界,天上會掉下一些餡餅。今天,天上會隨機掉下k個餡餅。

每次天上掉下餡餅,小 G 可以選擇吃或者不吃(必須在下一個餡餅掉 下來之前作出選擇,並且現在決定不吃的話以後也不能吃)。

餡餅有n種不同的餡,根據物理定律,天上掉下這n種餡餅的概率相 同且相互獨立。然而,每一種餡餅i都有一個前提餡餅集合Si。只有當Si中 的餡餅都吃過之後,才能吃第i 種餡餅。比如說,韭菜餡餡餅的S中有白菜豬肉餡餅和鮮蝦餡餅,那麼小G只有在吃過白菜豬肉餡餅和鮮蝦餡餅之後,才能吃韭菜餡的餡餅。

同時,每個餡餅還有一個美味值Pi。今天一天小G的幸福度,等於小G吃到的所有餡餅的美味值之和。註意:Pi 可能是負數。

現在考慮,採用最優策略的前提下,小G這一天期望的幸福度是多少?

【輸入格式】

第一行兩個正整數k和n,表示餡餅的數量和種類。

以下n行,每行若幹個數,描述一種餡餅。其中第一個數代表美味值,隨後的整數表示該餡餅的前提餡餅,以0結尾。

【輸出格式】

輸出一個實數,保留6位小數,即在最優策略下期望的幸福度。

【輸入樣例】

1 2
1 0
2 0

【輸出樣例】

1.500000

【數據規模】

對於20%的數據,所有的餡餅都沒有“前提餡餅”。

對於50%的數據,1≤k≤10,1≤n≤10。

對於100%的數據,1≤k ≤100,1≤ n≤15,美味度為[-106,106]的整數。

解析

n只有15,顯然狀壓DP,令f[i][j]表示在第1輪到第i-1輪內是否取過狀態為j的最大期望得分。

則狀態轉移方程為:(1≤k≤n)

  1. j狀態滿足吃第k種餡餅的條件,則不吃為f[i+1][j],吃則為f[i+1][j|(1<<k-1)]+Pk,取兩者最大值累加f[i][j]即可;
  2. j狀態不滿足吃第k種餡餅的條件,則不能吃,即f[i][j]=f[i+1][j]。

至於期望值,雖然很高端的樣子,但實際上,由於f[i][j]覆蓋了第i輪吃n種餡餅的情況,所以對於每個f[i][j],均除以n即可。

答案即為f[1][0]。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
inline 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;
}
const int N=16,K=120,T=1<<15;
int k,n,v[N],d[N];
double f[K][T];
int main()
{
    k=read(),n=read();
    for(int i=1;i<=n;i++)
    {
        v[i]=read();
        int x=read();
        while(x) d[i]+=1<<(x-1),x=read();
    }
    for(int i=k;i>=1;i--)
        for(int j=0;j<1<<n;j++)
        {
            for(int p=1;p<=n;p++)
                if((j&d[p])==d[p]) f[i][j]+=max(f[i+1][j],f[i+1][j|(1<<(p-1))]+v[p]);
                else f[i][j]+=f[i+1][j];
            f[i][j]/=n;
        }
    printf("%.6f",f[1][0]);
    return 0;
}
View Code

 


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

-Advertisement-
Play Games
更多相關文章
  • 本文主要講解Spring Boot 整合Jwt 認證的示例,詳細內容,詳見文末源碼。 ...
  • time模塊 作用:列印日期,做時間轉換。 import timeimport datetime #示例一:sleep()print("start to sleep.....")time.sleep(5) #讓程式停止5秒print("wake up...") #示例二:時間戳print(time. ...
  • 高強度訓練第二十天總結:Mybatis面試題 什麼是Mybatis? 1. Mybatis 是一個半 ORM(對象關係映射)框架,它內部封裝了 JDBC,開發時 只需要關註 SQL 語句本身,不需要花費精力去處理載入驅動、創建連接、創建 statement 等繁雜的過程。程式員直接編寫原生態 sql ...
  • CAP定理與BASE理論 CAP定理 2000 年 7 月,加州大學伯克利分校的 Eric Brewer 教授在 ACM PODC 會議上提出 CAP 猜想。2年後,麻省理工學院的 Seth Gilbert 和 Nancy Lynch 從理論上證明瞭 CAP。之後,CAP 理論正式成為分散式計算領域 ...
  • 概述 優點 第一 ,它解決了複雜問題。它把可能會變得龐大的單體應用程式分解成一套服務。雖然功能數量不變,但是應用程式已經被分解成可管理的塊或者服務。每個服務都有一個明確定義邊界的方式,如遠程過程調用(RPC)驅動或消息驅動 API。微服務架構模式強制一定程度的模塊化,實際上,使用單體代碼來實現是極其 ...
  • [TOC] 題目 "P1080 國王游戲" 思路 貪心+高精度。按$a \times b$從小到大排序就可以了、 $Code$ cpp include define MAXN 1001 define rr register using namespace std; const int Big_B = ...
  • 上一篇主要說的是開啟http basic認證,從安全形度來講,基於base64編碼,容易被抓包後破解,在公網中很不安全,本文詳談如何在eureka server和eureka client中開啟https。 公共依賴pom文件 1、eureka server工程 1.1、eureka server工 ...
  • [TOC] 題目 "P1079 Vigenère 密碼" 思路 字元串+模擬。仔細讀題,然後仔細敲代碼(說了和沒說一樣)。。。 $Code$ cpp include include include include include define MAXN 1001 using namespace st ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 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 ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...