A、AOE还是单体？
题意
牛可乐准备和i个怪物厮杀。已知第 i个怪物的血量为 a[i] 。牛可乐有两个技能：
第一个技能是蛮牛冲撞，消耗1mp，可以对任意单体怪物造成1点伤害。
第二个技能是蛮牛践踏，消耗xmp，可以对全体怪物造成x点伤害。
牛可乐想知道，将这些怪物全部击杀，消耗mp的最小值的多少？
输入描述
第一行两个正整数n和x，分别代表怪物的数量、每次蛮牛践踏消耗的x值。
第二行i个正整数a[i]，分别代表每个怪物的血量。
输出描述
一个正整数，代表消耗mp的最小值。
解析
很明显的贪心，显而易见我们在x>=n的时候使用单体更为合适，所以我们在x < n的时候通过不断地调整使得x和n相等，然后剩下的进行单体就好了，那么怎么进行调整呢，我们直接先看下题目给的样例5 2 2 4 5 6 3
我们先对他进行排序
2 3 4 5 6
已知每一次aoe消耗xmp，如果我们一次aoe消灭的血量之和没有超过x，就应该选择单体更为合适，这里我们一次aoe消耗2点，所以我们最少一次要消灭血量之和为3（2的话也行，我们这里还是用3），这里可以看到前两次aoe每次都可以造成5点，第三次只能造成4点，第四次只能三点，再进行下去就只有两点一点了，所以我们到第四次的时候就可以停止了，这里我们推到出 为我们aoe的次数。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 7;
ll aoe[MAXN];
int main(void){
ll x,n,ans=0;
cin>>n>>x;
for(int i=0;i<n;++i){
cin>>aoe[i];
ans+=aoe[i];
}
if(x>=n){
cout<<ans<<endl;
}
else{
sort(aoe,aoe+n);
ll ans1=0;
ans1+=(aoe[n-x-1]*x);
for(int i=n-x;i<n;++i)
ans1+=(aoe[i]-aoe[n-x-1]);
cout<<ans1<<endl;
}
return 0;
}B、k-size字符串
题意
牛妹最近在研究k-size字符串。一个字符串为k-size指，字符串的连续段共有k个。所谓连续段指尽可能多的相同连续字母组成的子串。
例如：aabbbccc为3-size，因为（'aa' 'bb' 'ccc'），ababaab为6-size，因为 （'a' 'b' 'a' 'b' 'aa' 'b'）。
牛妹想知道，由n个 'a' 字符，m个 'b' 字符，组成长度为n+m的k-size字符串，共有多少种组成方式？由于该数可能过大，请对1e9+7取模。
输入描述
三个正整数n,m和k，用空格隔开
输出描述
一个正整数，为方案数对1e9+7取模的结果
解析
题目不难理解，如果我们现在把所有的相邻的相同的字母都缩成一个字母，也就是说把aaabbbaa缩成aba，这么来看所有的排列都是一样的，只有ababab和bababa两种情况，反过来，我们要做的就是先从n，m中拿出k/2个a和k/2个b，组成这两种串，然后再向串中添加字母，
举个例子就是我现在有3个a2个b要组成k=4的串，首先我们先拿两个a两个b组成abab或者baba，这样之后我们再向两种串中a后面添加多出来的一个a，就有aabab，abaab，baaba，babaa，这四种情况，
这个怎么算呢，这个可以看成先向篮子里放苹果，篮子里可以为空的组合数问题这么一来问题就解决了。
代码
#include<bits/stdc++.h>
typedef long long ll;
const int maxn=2e5+9;
const int mod=1e9+7;
#define mk make_pair
using namespace std;
ll fac[maxn],inv[maxn];
ll kpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans;
}
void init()
{
fac[0]=1;
for(int i=1;i<maxn;i++)fac[i]=fac[i-1]*i%mod;
}
ll Cc(ll x,ll y)
{
return fac[x]*kpow(fac[y]*fac[x-y]%mod,mod-2)%mod;
}
int main()
{
init();
ll n,m,k;
scanf("%lld%lld%lld",&n,&m,&k);
if(k>n+m)
{
puts("0");return 0;
}
if(k&1)
{
ll cnt1=k/2,cnt2=k/2+1;
ll sum=0;
if(n>=cnt1&&m>=cnt2)sum=Cc(n-1,cnt1-1)*Cc(m-1,cnt2-1)%mod;
if(n>=cnt2&&m>=cnt1)sum=(sum+(Cc(n-1,cnt2-1)*Cc(m-1,cnt1-1)%mod))%mod;
printf("%lld\n",sum);
}
else
{
ll cnt=k/2;
if(n<cnt||m<cnt)
{
puts("0");return 0;
}
printf("%lld\n",Cc(m-1,cnt-1)*Cc(n-1,cnt-1)%mod*2%mod);
}
}C、白魔法师
题意
现在有一颗树，树上的节点被染成了白色和黑色两种，我现在能改变树上一个点的颜色，要求输出改变后最大的白色块的连通块。输入描述
第一行输入一个正整数n，代表树的顶点数量。
第二行输入一个长度为n的、仅由'W'和'B'组成的字符串，第i个点为'W'代表该点为白***'代表该点为黑色。
接下来的n-1行，每行输入两个正整数x和y，代表x点和y点有一条边连接。
输出描述
一个正整数，代表施放魔法后，最大的白色连通块的大小。
解析
很明显这个题，用脑子想一想都知道，只会将黑色块转换为白色块，就是说最理想的情况就是两个白色块之间隔了一个黑色块，然后我将这个黑色块染成白色，这样就让两个白色块连了起来，自然也可能存在整个树上的白色块之间都隔了不止一个黑色块，我们考虑用并查集和DFS来记录每一个白色块的节点个数，然后通过枚举每一个黑色点，直接将黑色点上的白色块直接加起来，然后比较最大的即可。代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans=0,V[100005],S[100005]={0};
char T[100005];
int find(int a)
{
if(V[a]==a)return a;
return V[a]=find(V[a]);
}
vector<int>R[100005];
void DFS(int x,int fa)
{
int i,j,a,b;
for(i=0;i<R[x].size();i++)
{
j=R[x][i];
if(j==fa)continue;
if(T[j]=='W'&&T[x]=='W')
{
a=find(x),b=find(j);
if(a!=b)V[b]=a,S[a]+=S[b],S[b]=0,ans=max(ans,S[a]);
}
DFS(j,x);
}
}
int main()
{
int i,j,k,s,n;
scanf("%d%s",&n,T+1);
for(i=1;i<=n;i++)
{
V[i]=i;
if(T[i]=='W')S[i]=1;
}
for(i=1;i<=n-1;i++)scanf("%d%d",&j,&k),R[j].push_back(k),R[k].push_back(j);
DFS(1,0);
for(i=1;i<=n;i++)
{
if(T[i]=='W')continue;
for(s=j=0;j<R[i].size();j++)
{
k=R[i][j];
if(T[k]=='W')s+=S[find(k)];
}
ans=max(ans,s+1);
}
printf("%d\n",ans);
return 0;
}D、抽卡
题意
抽卡，抽到每种卡的概率相同，有一个或者多个卡池，每一个卡池里有bi张想要的卡，每个卡池抽一下，要求我们能抽到想要的卡的概率是多少，结果对1e9+7取摸。输入描述
第一行输入一个正整数n
。
第二行输入个正整数
。
第三行输入代表第 个卡池的你想要的卡种类数量。
。
输出描述
一个整数，表示该概率在模
意义下的值。
解析
一个数学题，在比赛的时候想的太多了，一上来就觉得很难，实际上并非如此，抽到自己想要的卡的概率=1-每个卡池都抽不到自己想要的卡的概率之积，即ans=1-[(a1-b1)/a1]\times×[(a2-b2)/a2]\times×...\times×[(an-bn)/an]。 然后就是这种用1e9+7代表概率的题目还是挺多的。代码
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int i,n,A[100005],B[100005];
int fastpow(long long a,int b)
{
long long s=1;
for(;b;b>>=1,a=a*a%mod)if(b&1)s=s*a%mod;
return s;
}
int main()
{
long long ans=1;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&A[i]),ans=ans*fastpow(A[i],mod-2)%mod;
for(i=1;i<=n;i++)scanf("%d",&B[i]),ans=ans*(A[i]-B[i])%mod;
printf("%lld\n",(1-ans+mod)%mod);
return 0;
}小声bb几句,这个是估计说的是PCR，良心游戏很可惜我退了，没有肝下去的动力
E、点击消除
题意
题意很简单，输入一个字符串，然后相连的出现了两个相同的就可以消除，然后消除了之后又出现了重复的两个又可以消除。输入描述
一个字符串，仅由小写字母组成。（字符串长度不大于300000）
输出描述
一个字符串，为“点击消除”后的最终形态。若最终的字符串为空串，则输出0。
解析
这个题目很明显一看就是用栈来做，读入一个数据就和栈顶的数据进行比较，相同就删除栈顶的数据，不相同就压入栈，只是这里的字符串有点长，用STL的栈会爆，所以要手写一个栈，这种题目明显用链表来写栈更加的节省空间和时间，但是代码量明显要大于用数组来写，并且写那个更容易出错，所以还是采用用数组来模拟栈，代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=300000+7;
char a[MAXN];
int main(void){
char ch;
int top = 0;
while (cin >> ch) {
if(!top)
a[top++] = ch;
else {
if(ch == a[top - 1])
top--;
else
a[top++] = ch;
}
}
if (!top) {
cout<<"0"<<endl;
}
else
for (int i = 0; i < top; ++i)
cout << a[i];
return 0;
}F、疯狂的自我检索者
题意
题目给出n个人投票，然后其中有m个人的投票隐藏起来了，让我们求最小可能的平均成绩和最大可能的平均成绩。输入描述
第一行输入两个正整数
第二行输入个正整数
代表没有被隐藏的分数
若相等，责第二行为空
输出描述
两个数，用空格隔开，分别代表最小可能平均分数和最大可能平均分数。小数点后保留5位。
解析
这个题是签到题，理解下题意就明白了，最大的平均数就是被隐藏的都为5，最小的就是被隐藏的都为1,首先将没有被隐藏的读入的时候就加起来，然后一个加上
另一个加上
就好了
代码
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(void){
ll n,m,k;
while(cin>>n>>m){
double ans=0,ans1,ans2;
if(n!=m)
for(ll i=0;i<n-m;++i){
cin>>k;
ans+=k;
}
ans1=ans+m*5;
ans1/=n;
ans2=ans+m;
ans2/=n;
printf("%.5f %.5f\n",ans2,ans1);
}
return 0;
}
G、解方程
题意
解方 解方程输入描述
输入三个正整数
输出描述
如果解存在，请输出方程的解x的值，若你和正确答案的误差不超过
,则认为你的答案正确。如果解不存在，则输出-1。
解析
观察这个函数，高中数学我就不多说了吧，左边是单调递增，所以我们直接在一个大范围里直接二分搜，然后就是这个double的精度问题，建议看一下官方题解戳这里代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int maxn = 100005;
template <class T>
inline void read(T &res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
double a,b,c;
int main() {
scanf("%lf %lf %lf", &a, &b, &c);
double l = 1e-5, r = 1e9;
while (l <= r) {
double mid = (r + l) / 2.0;
if(mid - l < 1e-8) break;
if (pow(mid, a) + b * log(mid) >= c) r = mid;
else l = mid;
}
printf("%.10f\n", l);
return 0;
}H、神奇的字母（二）
题意
给出一段字符，输出这一段字符中出现最多的字母输入描述
一段话，仅由英文小写字母和空格组成。这段话可能有很多行。（保证存在出现次数最多的一个字母）
数据范围：所有字符串总长度之和不超过1000。
输出描述
出现次数最多的那个神奇的字母。
解析
这个题目也挺简单的，和前面那个签到题不分伯仲好吧代码
#include<bits/stdc++.h>
using namespace std;
int k[25];
int main(void){
char a;
memset(k,0,sizeof(k));
while(cin>>a){
k[a-'a']++;
}
int max,j;
for(int i=0;i<25;++i){
if(i==0)
j=0,max=k[i];
else
if(k[j]<k[i]){
max=k[j];
j=i;
}
}
printf("%c",'a'+j);
return 0;
}
I、神奇的字母（二）
题意
现在有一个n*m的矩阵，现在要得到这个矩阵每一个数据所在的行列之和，输入描述
第一行有两个正整数n和m，代表方格的行数和列数。
接下来的n行，每行有m个数,代表每个方格的整数。
输出描述
输出n行n列整数，分别代表选择每个位置方格的得分情况。
解析
题意很简单，就是把这个矩阵中每一个点所在的这一行所有的值加起来在加上所在的这一列所有的值再减掉自身（因为重复了一个）,做法有很多，我就贴一下我自己的代码(这个真的不是我想水代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
template <class T>
inline void read(T &res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
ll n,m;
int main(){
read(n),read(m);
ll vis[n+1][m+1];
ll a[n+1]={0},b[m+1]={0};
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) {
read(vis[i][j]);
a[i]+=vis[i][j];
b[j]+=vis[i][j];
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j)
printf("%lld ",a[i]+b[j]-vis[i][j]);
printf("\n");
}
return 0;
}
还有一个标程我也贴一下，很厉害，很好的节约了空间，用一维数组代替二维数组
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[1000010];
ll sr[1000010],sc[1000010];
int main(){
int n,m,i;
cin>>n>>m;
for(i=0;i<n*m;i++)scanf("%lld",&a[i]);
for(i=0;i<n*m;i++){
sr[i/m]+=a[i];
sc[i%m]+=a[i];
}
for(i=0;i<n*m;i++){
printf("%lld ",sr[i/m]+sc[i%m]-a[i]);
if(i%m==m-1)printf("\n");
}
}
J，异或和之和
题意
有一个数组，里面有n个数，现在要求从这个数组里取出三个数来，对他们异或运算，然后把所有存在的取数情况结果加起来，然后取模输入描述
第一行一个正整数
接下来有n个正整数
输出描述
任取三个数、三元组内部位异或后求和对1e9+7取模的值。
解析
典型的算贡献的题，当初学姐讲这种题的时候没有认真听，现在就是后悔，非常后悔，半夜还在补题解 假设有k个二进制第i位为1的数，那么第i位的贡献为：
这个的意思就是要是我要这一位为1，那么三个数对应这个位置应该是100或者111.
然后我们要做的就是把每一位的贡献加起来。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int tot[60];
inline ll C(int x,int y){
if(x<y){
return 0;
}
y=x-y;
ll res=1;
for(int i=y+1;i<=x;++i){
res=(1LL*res*i);
}
for(int i=2;i<=x-y;++i){
res/=i;
}
return res%mod;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i){
ll x;
cin>>x;
for(int j=0;j<=59;++j){
tot[j]+=(x&1);
x>>=1;
}
}
ll ans=0,now=1;
for(int i=0;i<=59;++i){
ll res=(1LL*C(tot[i],1)*C(n-tot[i],2))%mod+C(tot[i],3);
res%=mod;
ans+=(1LL*res*now)%mod;
ans%=mod;
now=(2LL*now)%mod;
}
printf("%d",ans);
return 0;
}完结撒花！！！，清楚姐姐多给我发点牛币好吗，太难了，半夜还在写，写了两天。因为水平有限，有对大佬和官方题解进行参考，大佬题解戳这里
京公网安备 11010502036488号