T1 連珠風暴
題目
【題目描述】
給定M種顏色的珠子，每種顏色珠子的個數均不限，將這些珠子做成長度為N的項鏈，
問能做成多少種不重復的項鏈，兩條項鏈相同，當且僅當兩條項鏈通過旋轉或是翻轉后能重合在一起，且對應珠子的顏色相同，
【輸入格式】
一行兩個整數分別表示M,N，
【輸出格式】
一行一個整數表示答案，
【輸入樣例】
2 5
【輸出樣例】
8
【資料規模】
對于30%的資料，n,m≤4；
對于60%的資料，n,m≤5；
對于100%的資料，nm≤32，
決議
nm≤32，可以直接暴力AC，
正解貌似是Polya定理，
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int m,n,ans; int gcd(int x,int y) { if(y==0) return x; return gcd(y,x%y); } int main() { //freopen("necklace.in","r",stdin); //freopen("necklace.out","w",stdout); cin>>m>>n; for(int i=1;i<=n;i++) ans+=pow(m,gcd(n,i)); if(n&1) ans+=n*pow(m,(n+1)/2); else ans+=(n/2)*pow(m,(n+2)/2)+(n/2)*pow(m,n/2); cout<<ans/(n*2); return 0; }View Code
T2 種樹
題目
【題目描述】
Fanvree很聰明，解決難題時他總會把問題簡單化，例如，他就整天喜歡把圖轉化為樹，但是他不會碩訓，那他怎么轉化呢？
這是一個有n個點m條雙向邊的圖，Fanvree會選定一個節點，然后刪掉這個節點和這個點連出去的邊，如果變成了一棵樹，那么這個節點便是可行的，什么是樹呢？樹也即無簡單環的無向連通圖，
告訴Fanvree可能的節點是什么，
【輸入格式】
第一行兩個正整數n,m，表示有n個點m條邊，保證n≥2，
接下來m行，每行兩個整數v,u，表示v和u之間有一條無向邊1≤v,u≤n，保證沒有重邊和自環，
【輸出格式】
第一行一個正整數 ns，表示這個圖中有 ns 個結點可選，
接下來一行，共 ns 個整數，每個整數表示一個可選結點的編號，請按編號從小到大的順序輸出，
資料保證圖中至少存在一個可選的結點，
【輸入樣例】
6 6 1 2 1 3 2 4 2 5 4 6 5 6
【輸出樣例】
3 4 5 6
【資料規模】
對于40%的資料，n,m≤1000；
另存在10%的資料，m=n-1；
另存在20%的資料，m=n；
對于100%的資料，n,m≤100000，
決議
可選的點必然不是割點，
選好點后，如果圖是連通的，且剩余邊數剛好為n-2，那么這個點就是可選的，
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <queue> using namespace std; const int N=100010; int n,m,head[N],ver[N<<1],Next[N<<1],tot,deg[N],ans,dfn[N],low[N],cnt,anss[N],cut[N]; void add(int x,int y) { ver[++tot]=y; Next[tot]=head[x],head[x]=tot; } void tarjan(int x) { int child=0; dfn[x]=++cnt,low[x]=cnt; for(int i=head[x];i;i=Next[i]) { int y=ver[i]; if(!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]&&x!=1) cut[x]=1; if(x==1) child++; } low[x]=min(low[x],dfn[y]); } if(child>=2) cut[x]=1; } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; add(x,y),add(y,x); deg[x]++,deg[y]++; } tarjan(1); for(int i=1;i<=n;i++) if(!cut[i]&°[i]==m-n+2) { ans++; anss[ans]=i; } if(ans==0) { cout<<-1; return 0; } cout<<ans<<endl; for(int i=1;i<=ans;i++) cout<<anss[i]<<" "; return 0; }View Code
T3 序列
題目
【題目描述】
Fiugou想要在一個長度為N的序列A中找到不同位置的三個數，以這三個數為三邊長來構成一個三角形，但是它希望在滿足條件下，這三個數的位置盡量靠前，
具體地，設這三個數的為Ai,Aj,Ak(i<j<k)，Fiugou希望k盡量小；當k相等時，滿足j盡量小；當k，j均相等時，滿足i盡量小，
但是這個序列中的數可能會發生變化，所以Fiugou給出了M個操作，形式如下：
1 x y：將Ax改為y；
2：查詢最優的合法解，從小到大給出這三個數(而不是位置)，
【輸入格式】
第一行一個整數N，代表序列的長度，
第二行有N個整數，代表初始序列，
第三行一個整數M，代表操作的個數，
接下來M行操作，兩種操作格式如上所述，
【輸出格式】
共M行，每行三個數，從小到大給出，如果不存在，輸出-1，
【輸入樣例】
6 7 1 3 4 5 1 3 2 1 3 5 2
【輸出樣例】
3 5 7 4 5 7
【資料規模】
對于10%的資料，N≤10，M≤5；
對于30%的資料，N≤100，M≤25；
對于50%的資料，N≤1000，M≤1000；
對于100%的資料，N≤100000，M≤1000，1≤Ai≤2×109，1≤x≤N，1≤y≤2×109，
決議
直接暴力模擬即可，注意三角形三邊的關系判斷與i,j,k的關系判斷，
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; inline long long 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; } int n,m; long long a[100100]; int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); m=read(); for(int t=1;t<=m;t++) { int r=read(); if(r==1) { int x=read(); long long y=read(); a[x]=y; } else { bool ok=false; for(int k=3;k<=n;k++) if(!ok) for(int j=2;j<k;j++) if(!ok) for(int i=1;i<j;i++) if(a[i]+a[j]>a[k]&&a[i]+a[k]>a[j]&&a[j]+a[k]>a[i]) { if(a[i]<a[j]) { if(a[i]<a[k]) { cout<<a[i]<<" "; if(a[j]<a[k]) cout<<a[j]<<" "<<a[k]<<endl; else cout<<a[k]<<" "<<a[j]<<endl; } else cout<<a[k]<<" "<<a[i]<<" "<<a[j]<<endl; } else { if(a[i]<a[k]) cout<<a[j]<<" "<<a[i]<<" "<<a[k]<<endl; else { if(a[j]<a[k]) cout<<a[j]<<" "<<a[k]<<" "; else cout<<a[k]<<" "<<a[j]<<" "; cout<<a[i]<<endl; } } ok=true; break; } if(!ok) cout<<"-1"<<endl; } } return 0; }View Code
T4 禮物
題目
【題目描述】
夏川的生日就要到了，作為夏川形式上的男朋友，季堂打算給夏川買一些生日禮物，
商店里一共有N種禮物，夏川每得到一種禮物，就會獲得相應喜悅值Wi（每種禮物的喜悅值不能重復獲得），
每次，店員會按照一定的概率Pi（或者不拿出禮物），將第i種禮物拿出來，
季堂每次都會將店員拿出來的禮物買下來，沒有拿出來視為什么都沒有買到，也算一次購買，
季堂希望最后夏川的喜悅值盡可能地高，
求夏川最后最大的喜悅值是多少，并求出使夏川得到這個喜悅值，季堂的期望購買次數，
【輸入格式】
第一行，一個整數N，表示有N種禮物，
接下來N行，每行一個實數Pi和正整數Wi，表示第i種禮物被拿出來的概率和可以獲得喜悅值，
【輸出格式】
第一行，一個整數表示可以獲得的最大喜悅值，
第二行，一個實數表示獲得這個喜悅值的期望購買次數，保留3位小數，
【輸入樣例】
3 0.1 2 0.2 5 0.3 7
【輸出樣例】
14 12.167
【資料規模】
對于10%的資料，N=1；
對于30%的資料，N≤5；
對于100%的資料，N ≤ 20，0<Wi≤109，0<Pi≤1且ΣPi≤1，
決議
期望值是什么鬼？
N只有20，可以考慮用狀壓DP：
設fs表示已經購買的禮物集合為s時的期望購買次數，則轉移方程為：
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; const int N=(1<<20)+5; double p[N],f[N]; int n,w[N]; long long ans; int main() { cin>>n; for(int i=0;i<n;i++) cin>>p[i]>>w[i],ans+=w[i]; int temp=1<<n; for(int i=1;i<temp;i++) { double pp=0,ff=1; for(int j=0;j<n;j++) if(1<<j&i) ff+=f[1<<j^i]*p[j],pp+=p[j]; f[i]=ff/pp; } cout<<ans<<endl; printf("%.3f",f[temp-1]); return 0; }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/100188.html
標籤：C++
下一篇：長樂國慶集訓Day3