首页 > 其他分享 >CF105

CF105

时间:2024-11-09 15:19:43浏览次数:1  
标签:int double long mp cnt1 CF105 leqslant

吐槽:好长的题目啊啊啊啊啊
我这套题选的不够好,基本上就把时间浪费在理解题意上了。

A.Transmigration

CF原题链接

题目大意:

给定n个能力的名称与能力值,在下一轮这些能力值会乘一个系数\(k\)(向下取整),若能力值在下一轮小于\(100\),会失去这个能力。此外,在下一轮会重新拥有m个能力,这些能力的能力值默认为0。求第二轮拥有能力的数量,以及所有能力名称与它的能力值(按字典序输出)。\((1\leqslant n,m\leqslant 20,0.01\leqslant k\leqslant0.99)\)

解题思路:

map直接搞定。但在浮点数转整数的时候要注意精度问题(\(double\)怒挂不知道多少分)

代码
#incIude <bits/stdc++.h>
#define int long long
using namespace std;
const int N=25;
double n,m;
double k;
map <string,float> mp;
int cnt;

signed main()
{
	cin>>n>>m>>k;
	for (int i=1;i<=n;i++)
	{
		string str;
		int x;
		cin>>str>>x;
		mp[str]=x*k;
		if (mp[str]<100) {mp[str]=-1;cnt--;}
		cnt++;
	}
	for (int i=1;i<=m;i++)
	{
		string str;
		cin>>str;
		if (mp[str]>0) continue;
		mp[str]=0;
		cnt++;
	}
	cout<<cnt<<endl;
	map <string,float> ::iterator it=mp.begin();
	for (;it!=mp.end();it++)
	{
		if ((int)(it->second)==-1) continue;
		else cout<<it->first<<" "<<(int)(it->second)<<endl;
	}
	return 0;
}

B.Dark Assembly

CF原题链接

题目大意:

共有n个人,每个人分别有两个属性:\(b_{i},l_{i}\)。对于第\(i\)个人,他投出赞成票的概率为\(\frac{l_{i}}{100}\)。

共有\(k\)次机会给任意人的 \(l_{i}\) 加 \(10\)。若投出赞成票的人数严格过半,那么此次投票成功;若人数不过半,那么有\(\frac{A}{A+B}\)的概率可以使此次投票成功。其中\(B\)表示对于所有未投出赞成票的人\(i\),\(B=\Sigma b_{i}\)

求在\(k\)次改变\(l_{i}\)方案最优的情况下,最后投票成功的概率。(\(1\leqslant n,k\leqslant 8,1\leqslant A\leqslant 9999\))

解题思路:

第一眼:好难好难

第二眼:这个数据范围?搜索启动!

因为\(1\leqslant n\leqslant 8\),所以我们大可以直接\(dfs\)枚举所有情况。先\(dfs\)一遍,枚举\(k\)次改变 \(l_{i}\) 的情况,对于每种情况,再\(dfs\)求出概率,最后取概率最大值即可。

代码
#incIude <bits/stdc++.h>
#define int long long
using namespace std;
const int N=10;
int n,k;
long double A;
int b[N],l[N];
long double ans,anss; 

void calc(int cnt1,int cnt2,long double dt,long double B)
{
	if (cnt1>n)//个数
	{
		if (cnt2>n/2) ans+=1.0*dt;//投票成功
		else ans+=1.0*dt*(A/(A+B));//投票失败
		return ;
	}
	calc(cnt1+1,cnt2+1,1.0*dt*l[cnt1]/10,B);//该次投赞成票
	calc(cnt1+1,cnt2,1.0*dt*(100-l[cnt1])/10,B+b[cnt1]);//该次不投赞成票
}
void dfs(int m,int cnt)
{
	if (m>k)//k次机会已用完
	{
		ans=0;
		calc(1,0,1,0);
		anss=max(anss,ans/pow(10,n));
		return ;
	}
	for (int i=cnt;i<=n;i++)
	{
		if (l[i]==100) continue;
		l[i]+=10;
		dfs(m+1,i);
		l[i]-=10;
	}
}
signed main()
{
	cin>>n>>k>>A;
	for (int i=1;i<=n;i++) cin>>b[i]>>l[i];
	dfs(1,0);
	cout<<fixed<<setprecision(10)<<anss;
	return 0;
}

C.Item World

CF原题链接

题目大意:

难以翻译。

题目给出 \(n (3\leqslant n\leqslant 100)\) 个武器的名称\(name\),种类\(class\),攻击值\(atk\),防御值\(def\),法力值\(res\),容量\(size\);给出 \(k(1\leqslant k\leqslant 1000)\) 个强化装备的名称\(name\),种类\(type\),数值\(bonus\),原来位置\(home\)。

\(n\)个武器,分别有攻击、防御、法力三种种类\(class\),所有武器都有相应的攻击\(atk\)、防御\(def\)、法力值\(res\)。每个武器有相应的容量\(size\),表示该武器上最多放\(size\)个强化装备。有\(k\)种强化装备,每个强化装备可以对相应种类\(type\)武器的相应值增加\(bonus\)。强化装备必须都放在武器上。

要求给出一种方案,使得移动强化装备后,有最高攻击力的攻击武器;若攻击力相同,要求有最高防御力的防御武器;若防御武器相同,要求有最高法力值的法器。输出该方案三种武器的名称、强化装备数量与强化装备名称。

解题思路:

贪心模拟,直接做做完了


标签:int,double,long,mp,cnt1,CF105,leqslant
From: https://www.cnblogs.com/Myyy-L/p/18536836

相关文章

  • CF1051F题解
    传送门:https://codeforces.com/problemset/problem/1051/F注意到\(m-n\le20\),求一个连通图中任意两点间最短路,我们不难想到将问题转换到树上。先求出树的任意一颗生成树,此时倍增或者树刨能轻松算出仅含树边的最小路径。而对于非树边,从边的角度显然很难做到,我们不妨从点的角度思......
  • CF1051F题解
    TheShortestStatement算法:树链剖分,最小生成树,最短路。先讲一下题意:有一个\(n\)点\(m\)边的无向连通图,\(q\)次询问,每次询问\(a\)到\(b\)的最短路长度。数据范围\(1\len,m\le10^5,m-n\le20\)。首先发现给了一个很奇怪的限制:\(m-n\le20\),考虑他有什么用。我们在......
  • CF1051C Vasya and Big Integers 题解
    Problem-1051E-CodeforcesVasyaandBigIntegers-洛谷感谢女队提交记录推荐给我的一道题\(Orz\)首先\(O(n^2)\)的\(dp\)是simple的,如果你没看出来你可能是像我一样把题目看错了设\(dp_i\)表示考虑前\(i\)个的方案数,转移枚举长度后比较字典序。虽然看......
  • CF1055F Tree and XOR
    这道题代码虽然比较短,但花了我整整一天才过,太菜了这是CF241B的加强版,但是有点不同,因为CF241B后半部分求前\(k\)大的和没法优化了,而这道题能把前面的求第\(k\)小时间复杂度优化到单log,但是需要注意这道题开trie完全开不下,所以肯定没法trie上二分做到单log对于某些......
  • [题解] CF1051F The Shortest Statement
    TheShortestStatement给一张\(n\)个点\(m\)条边的无向连通图,保证\(m-n\le20\),\(q\)次询问求两个点间的最短路。\(n,m,q\le10^5\)。由于边数只比点数多20,所以如果我们建出这张图的一棵生成树,那么非树边至多有21条。那么现在两点之间的最短路就转化成了不......
  • CF1054D Changing Array
    题意给定\(n\)个小于\(2^k\)的数。可以任意让若干数\(xor\)\(2^k-1\)。问使得最终区间\(xor\)不为\(0\)的最大个数。Sol考虑前缀异或和。记异或和的数组为\(s\)。现在一个区间的贡献变为\(s_r\opluss_{l-1}\)。考虑何时该贡献为\(0\)。显然当\(s......
  • CF1051G Distinctification
    Day\(3^3\)。未卡常拿到了最优解/cy。(2023/10/2)观察到\(3\)个比较关键的性质:操作具有可逆性,即一串操作序列可以立即撤销。当新插入一个\((a_i,b_i)\)时,必须连续对\(i\)进行\(1\)操作使得不存在\(j\neqi,a_j=a_i\)。当存在\(a_i=a_j+1\)时,可以花费\(b_j-b_i\)......
  • CF1053E-Euler Tour题解
    前言还是一道神仙题很难想题面luogu上copy的样例解释懒得翻,我觉得应该都看得懂样例吧。题面翻译现有一棵\(n\)个点的形态未知的树,给定其长度为\(2n-1\)的欧拉序的一部分请根据给出的残缺的欧拉序还原出一个完整的欧拉序或判断不存在这样的树输入中用非零数字表示欧拉......
  • CF1051G Distinctification题解
    link首先可以发现,题目给定的两种操作为我们提供了“反悔机制”,所以有:结论\(1\):即任何一个可以到达的局面都能到达最优解。利用这个结论,首先我们先去重。继续提炼性质,与相差不到\(1\)的数为基准\(+1\)与\(-1\)操作,将这个数的变化范围限制在了一个区间,并且这个区间的数能......
  • [刷题笔记] CF1059B Forgery
    ProblemSolution搜索染色类。我们发现染色是不可逆的,也就是染成了#后不得染回“.”,所以对于每次染色我们都要尽可能向std上靠拢。我们可以观察一下std,发现需要尽可能从std上的“.”向四周染色(因为3*3染色中间的"."不染)。每次染色前需要判断染完这一部分是否和std一致,如果一......