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; }
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; }
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; }
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; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/601593.html