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）
- j狀態滿足吃第k種餡餅的條件，則不吃為f[i+1][j]，吃則為f[i+1][j|(1<<k-1)]+Pk，取兩者最大值累加f[i][j]即可；
- 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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/100196.html
標籤：C++