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）
- 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
