吐槽:好长的题目啊啊啊啊啊
我这套题选的不够好,基本上就把时间浪费在理解题意上了。
A.Transmigration
题目大意:
给定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
题目大意:
共有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
题目大意:
难以翻译。
题目给出 \(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