前面的碎碎念：
啊啊啊，差点就AK了好可惜啊，数学题忘了小球放盒子怎么快速求方法数了，对不起高中数学老师...
题解部分：
A-AOE还是单体？
比较简单的贪心题目。若怪兽数目大于x，那么释放一个AOE技能对所有怪物造成1伤害，肯定比一个一个放个单体技能对所有怪物造成1伤害赚；若怪兽数目等于x，两者等价；若怪兽数目小于x，单体技能比AOE技能更赚。所以我们先用AOE技能把怪杀到只剩x-1个，再用单体技能把剩下的怪物全部杀死即可。
时间复杂度：O(nlog(n))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int a[200005];
int main()
{
int i,n,x;
long long ans=0;
scanf("%d%d",&n,&x);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+1+n);
if(n<=x)for(i=1;i<=n;i++)ans+=a[i];
else
{
ans=x*a[n-x];
for(i=n-x+1;i<=n;i++)ans+=a[i]-a[n-x];
}
printf("%lld\n",ans);
return 0;
}B-k-size字符串
我们先按照abab...或者baba...这样排成k个，然后把剩下的a字符和b字符再插入到排好的a字符和b字符的位置。假设排成k个的字符中有m个a字符，剩下了n个a字符，那么插入的问题就等价于n个相同的小球放入m个盒子，允许盒子为空，这个方法数是C(n+m-1,m-1)。同理可以求出b字符的方法数，ab两字符的方法数相乘，加到ans上即可。而组合数可以通过预处理阶乘和阶乘的逆元，之后直接快速求解。
时间复杂度：O(max(n,m))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long fac[100005],inv[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 Cal(int m,int n)
{
return fac[m]*inv[n]%mod*inv[m-n]%mod;
}
int main()
{
//A和B分别表示一开始k个字符中，'a'字符和'b'字符的个数
//a和b分别表示剩余的'a'字符和'b'字符的个数
int n,m,k,A,B,a,b;
long long i,j,ans=0;
scanf("%d%d%d",&n,&m,&k);
for(fac[0]=i=1;i<=1e5;i++)fac[i]=fac[i-1]*i%mod;
inv[100000]=fastpow(fac[100000],mod-2);
for(i=99999;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
A=k/2,B=k/2+k%2,a=n-A,b=m-B;
//剩余的'a'字符和'b'字符个数应该非负，否则就是非法的
if(a>=0&&b>=0)
{
i=Cal(a+A-1,A-1),j=Cal(b+B-1,B-1);
ans=(ans+i*j%mod)%mod;
}
A=k/2+k%2,B=k/2,a=n-A,b=m-B;
if(a>=0&&b>=0)
{
i=Cal(a+A-1,A-1),j=Cal(b+B-1,B-1);
ans=(ans+i*j%mod)%mod;
}
printf("%lld\n",ans);
return 0;
}C-白魔法师
我们先利用并查集，DFS求出所有白色连通块及其对应的结点个数，将ans初始化为最大的白色连通块的结点个数。之后枚举黑色结点，将所有和它直接相连的白色连通块的节点个数全部加起来，设其为s，则令ans=max(s+1,ans)，最后输出ans即可。
时间复杂度：O(n)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
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-抽卡
简单的数学题，抽到自己想要的卡的概率=1-每个卡池都抽不到自己想要的卡的概率之积，即ans=1-[(a1-b1)/a1][(a2-b2)/a2]
...
[(an-bn)/an]。
时间复杂度：O(nlog(n))。
代码部分：
#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;
}E-点击消除
栈的简单应用。从左到右遍历一遍字符串，若栈为空，直接把字符入栈；若栈不为空，判断栈顶元素和当前字符是否一样，若一样栈顶元素出栈，若不一样把该字符入栈。最后判断栈是否为空，若为空输出0，否则从栈底到栈顶输出栈内剩余元素。
时间复杂度：O(n)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
char R[300005],S[300005];
int main()
{
int i,t=-1;
scanf("%s",R);
for(i=0;R[i]!='\0';i++)
{
if(t==-1)S[++t]=R[i];
else
{
if(R[i]==S[t])t--;
else S[++t]=R[i];
}
}
if(t==-1)printf("0\n");
else S[++t]='\0',printf("%s\n",S);
return 0;
}F-疯狂的自我检索者
签到题。先统计未被隐藏的分数之和，对于被隐藏的分数，全部令其为最大值5，加起来再除以打分人数，即可得到最大可能平均分；全部令其为最小值1，加起来再除以打分人数，即可得到最小可能平均分。
时间复杂度：O(n)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,n,m;
double ans1=0,ans2=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n-m;i++)
{
scanf("%d",&j);
ans1+=j,ans2+=j;
}
while(m--)ans1+=1,ans2+=5;
printf("%.5lf %.5lf\n",ans1/n,ans2/n);
return 0;
}G-解方程
设f(x)=x^a+bln(x)，很显然f(x)是个单调递增函数，对于最小的c=1，总有x=1能使其成立，故这个方程不存在无解的情况。那么我们可以利用三分法来找到这个x，注意设置一个计数变量防止无限循环卡死的情况。
时间复杂度：O(log(c))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int t=0,a,b,c;
double F(double x)
{
return pow(x,a)+b*log(x);
}
int main()
{
double i,j,l=1,r=1e9;
scanf("%d%d%d",&a,&b,&c);
while(r-l>0.0000001)
{
t++,i=(l+r)/2,j=(i+r)/2;
if(t>1000)break;
if(F(i)<c)l=i;
else r=j;
}
printf("%.14lf\n",i);
return 0;
}H-神奇的字母（二）
签到题。直接利用读到文件尾的while循环统计各个字母的出现个数，最后再把出现次数最多的字母输出即可。
时间复杂度：O(n)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,ans,V[26]={0};
char c;
while(~scanf("%c",&c))if(c>='a'&&c<='z')V[c-'a']++;
for(i=j=0;i<26;i++)if(V[i]>j)ans=i,j=V[i];
printf("%c\n",ans+'a');
return 0;
}I-十字爆破
设原数组为R，H[i]为第i行数字之和，L[j]为第j列数字之和，那么ans[i][j]=H[i]+L[j]-R[i][j]。至于R数组无法直接开出来的情况，我们可以利用vector容器动态分配内存，当然把二维数组压缩成一维数组也行。
时间复杂度：O(nm)。
代码部分：
#include<bits/stdc++.h>
using namespace std;
vector<long long>R[1000005];
long long H[1000005]={0},L[1000005]={0};
int main()
{
int i,j,k,n,m;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
scanf("%d",&k);
R[i].push_back(k);
H[i]+=k,L[j]+=k;
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)printf("%lld ",H[i]+L[j]-R[i][j]);
printf("\n");
}
return 0;
}J-异或和之和
经典按位考虑算贡献。从左到右遍历一遍，若ai的第j位是1，若要该位有贡献，那么只能是100或者111的情况，设从i+1到n，第j位是1的个数为one，第j位是0的个数为zero，那么贡献=(1<<j)C(one,2)+(1<<j)
C(zero,2)；若ai的第j位是0，若要该位有贡献，那么只能是010或者001的情况，设从i+1到n，第j位是1的个数为one，第j位是0的个数为zero，那么贡献=(1<<j)
one
zero，以上的C(m,n)是组合数。至于快速计算i+1到n，第j位0与1的个数，我们可以利用前缀和数组预处理出来。
时间复杂度：O(nlog(max(ai)))。
代码部分：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long a[200005];
int S[60][200005]={0};
int main()
{
int i,j,n,s0,s1,ans=0;
__int128 one=1;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
for(j=0;j<60;j++)
{
S[j][i]=S[j][i-1];
if((one<<j)&a[i])S[j][i]++;
}
}
for(i=1;i<n-1;i++)
{
for(j=0;j<60;j++)
{
s1=S[j][n]-S[j][i],s0=n-i-s1;
if((one<<j)&a[i])
{
ans=(ans+(one<<j)*s1*(s1-1)/2)%mod;
ans=(ans+(one<<j)*s0*(s0-1)/2)%mod;
}
else ans=(ans+(one<<j)*s1*s0)%mod;
}
}
printf("%d\n",ans);
return 0;
}完结撒花，若有不足之处，还望大佬轻喷~
京公网安备 11010502036488号