一.闲话
本来打的挺开心的，A题速度挺快的。然后。。。G题被疯狂卡精度。。。（绝望），罚时一大堆qwq。我好菜啊qwq
由于打比赛的时候，打的比较快，很多代码都比较粗糙，还请见谅~
二.题解
A.AOE还是单体？
明显是个单峰函数求极值问题（应该可以直接推式子，但是懒）~
我们三分群体攻击次数，然后计算求极值即可~
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+1;
int a[N],n,T;
inline int calc(int x){
int res=0;
for(int i=1;i<=n;++i){
res+=max(0LL,a[i]-x);
}
return res+x*T;
}
signed main(){
scanf("%lld%lld",&n,&T);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
int l=0,r=1e9,res=0;
while(l<=r){
int lc=l+(r-l)/3,rc=r-(r-l)/3;
int L=calc(lc),R=calc(rc);
if(L<=R){
r=rc-1;res=L;
}else{
l=lc+1;res=R;
}
}
printf("%lld",res);
return 0;
} B.k-size字符串
这题一开始式子推错了
首先，我们来考虑下最终字符串的大概形态：
1.abab...(其中a,b由若干个(>=1)'A''B'组成)
2.baba...
那么， 我们就把这两种情况的方案数分别计算出来
我们为了保证合法，先给每个位置的a放一个'A',每个位置的b放一个'B'
然后，我们再把剩下的'A'和'B'放入任意一个a,b里面即可
统计方案:
假设我们现在还剩x个'A',有y个a可以选择，那么方案数为：（'B'直接类比即可）
因为每个'A'是等价的，所以，我们这里用隔板法来计算
我们在x个'A'中插入y+1个隔板(假装开头和末尾有一个)，相邻两个隔板之间即为一个区间，第i个区间的'A'的个数就是我们放进第i个a的'A'的个数。由于可以放0个进去，所以区间长度可以为0。
那么，方案就是，我们把所有隔板放入后（不考虑开头和末尾），共x+y-1个空，每个空填'A'或者隔板，那么，方案数即为C(x+y-1,y-1)
把两个情况的答案统计一遍，再求和即可（注意判断是否有足够的'A'/'B'）
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e5+1;
int s[N];
inline int ksm(int x,int y){
int ans=1;
while(y){
if(y&1){
ans=(1LL*ans*x)%mod;
}
x=(1LL*x*x)%mod;
y>>=1;
}
return ans;
}
inline int C(int y,int x){
int res=1;
for(int i=y+1;i<=x;++i){
res=(1LL*res*i)%mod;
}
for(int i=(x-y);i;--i){
res=(1LL*res*s[i])%mod;
}
return res;
}
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
s[0]=s[1]=1;
for(int i=2;i<=max(n,m);++i){
s[i]=ksm(i,mod-2);
}
//选k个然后依次插入即可
int ans=0;
//先a后b
int mid1=(k+1)/2,mid2=k/2;
if(n>=mid1&&m>=mid2){
int A=n-mid1,B=m-mid2,res=1;
res=(1LL*res*C(mid1-1,n-1))%mod;
res=(1LL*res*C(mid2-1,m-1))%mod;
ans=(ans+res)%mod;
}
if(n>=mid2&&m>=mid1){
int A=n-mid2,B=m-mid1,res=1;
res=(1LL*res*C(mid1-1,m-1))%mod;
res=(1LL*res*C(mid2-1,n-1))%mod;
ans=(ans+res)%mod;
}
printf("%d",ans);
return 0;
} C.白魔法师
明显的一道树形dp问题。
我们设dp[i][0],dp[i][1],dp[i][2]
分别表示以i为根的子树中，没有修改/i修改/子树中有一个修改
那么，我们有转移方程：
前两个很好递推，第三个怎么求？我们注意到，因为1和2一共最多取一个（因为最多修改1次），所以，我们先算出所有儿子中j=0的和，再从j=1/2减去j=0的差值中取最大加上去就好了
最后的答案就是
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
struct node{
int v,nex;
}t[N<<1];
int len,las[N];
bool a[N];
int dp[N][3];
inline void add(int u,int v){
t[++len]=(node){v,las[u]},las[u]=len;
}
inline void dfs(int now,int fa){
dp[now][0]=dp[now][2]=a[now];dp[now][1]=1;
int maxe=0;
for(int i=las[now];i;i=t[i].nex){
int v=t[i].v;
if(v!=fa){
dfs(v,now);
if(a[now]){
dp[now][0]+=dp[v][0];dp[now][2]+=dp[v][0];
maxe=max(maxe,max(dp[v][1],dp[v][2])-dp[v][0]);
}
dp[now][1]+=dp[v][0];
}
}
dp[now][2]+=maxe;
}
int main(){
int n;
scanf("%d",&n);
string x;
cin>>x;
for(int i=1;i<=n;++i){
a[i]=(x[i-1]=='W');
}
for(int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs(1,1);
int ans=0;
for(int i=1;i<=n;++i){
ans=max(ans,max(dp[i][0],dp[i][1]));
ans=max(ans,dp[i][2]);
}
printf("%d",ans);
return 0;
} D.抽卡
简单概率。
因为正着算很麻烦，所以我们直接算反面，即抽不到想要的卡的概率。然后用1-抽不到的概率即为抽得到的概率了。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1,mod=1e9+7;
inline int ksm(int x,int y){
int ans=1;
while(y){
if(y&1){
ans=(1LL*ans*x)%mod;
}
x=(1LL*x*x)%mod;
y>>=1;
}
return ans;
}
int a[N],b[N];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
int ans=1;
for(int i=1;i<=n;++i){
scanf("%d",&b[i]);
b[i]=a[i]-b[i];
ans=(1LL*ans*b[i])%mod;
ans=(1LL*ans*ksm(a[i],mod-2))%mod;
}
ans=1-ans;
ans=(ans%mod+mod)%mod;
printf("%d",ans);
return 0;
} E.点击消除
估计正解应该是删去字符串中的所有回文串，不过太懒了，就直接模拟了一遍。。。
代码:
#include<bits/stdc++.h>
using namespace std;
int flag[300001];
int main(){
string x;
cin>>x;
int tim=0;
while(true){
++tim;int len=x.size();bool f=0;
for(int i=1;i<len;++i){
if(x[i]==x[i-1]){
flag[i]=flag[i-1]=tim;f=1;++i;
}
}
if(!f){
break;
}
string y="";
for(int i=0;i<len;++i){
if(flag[i]!=tim){
y+=x[i];
}
}
x=y;
}
if(x.size()==0){
puts("0");
return 0;
}
cout<<x;
return 0;
} update:补充一个正解，类似括号匹配问题，把合法的匹配删掉即可~
update2:应大佬要求，来补充下。qwq
我们注意到，我们删除的串一定是这样的:
ABC....TT....CBA【间隔若干个字符】UVW...ZZ...WVU【间隔若干个字符】...
（每个大写字母代表一个字符，不同大写字母代表的字符可能一样，大写字母的数量也可能不一样，只是为了方便说明qwq）
也即是说，我们一定是删除若干个回文串（长度为偶数），那么如果我们把这些字母换成我们常见的括号会怎么样呢？
([{...}])
我们会发现，我们每次删除的，其实就是一个合法的括号的匹配
那么，我们直接类似括号匹配问题，开一个栈，每成功匹配了，就把匹配成功的删去，那么栈里面剩下的就是我们删除之后的字符串辣！
代码：
#include<bits/stdc++.h>
using namespace std;
char sta[300001];int top;
int main(){
string x;
cin>>x;
int len=x.size();
for(int i=0;i<len;++i){
if(top&&x[i]==sta[top]){
--top;
continue;
}
sta[++top]=x[i];
}
if(!top){
puts("0");
return 0;
}
for(int i=1;i<=top;++i){
cout<<sta[i];
}
return 0;
} F.疯狂的自我检索者
最小情况就是剩余m个人都只给1分，最大情况就是剩余m个人都给5分。
分别计算即可
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
scanf("%d%d",&n,&m);
int sum=0;
for(int i=1;i<=n-m;++i){
int x;
scanf("%d",&x);
sum+=x;
}
double ming=sum+m,maxe=sum+5*m;
ming/=double(n),maxe/=double(n);
printf("%.5lf %.5lf",ming,maxe);
return 0;
} G.解方程
这题精度把我整惨了qwq（不知道各位大佬怎么弄得（感觉是我人丑所以代码丑））
观察后不难发现，该式是明显的一个递增函数，而且x趋近0的时候，值趋近0，c>=1,所以必有解，直接二分就好了。
然而，二分会挂（应该是我自己的锅qwq）
所以，我们考虑玄学的做法：
我们把整数部分和小数部分分开二分做，这样，就不怕精度了qwq（别跟我说long double,我long double也出锅了qwq，气死）
代码:
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-10;
int a,b,c;
inline double power(double x,int y){
double res=1;
while(y--){
res*=x;
}
return res;
}
int main(){
scanf("%d%d%d",&a,&b,&c);
int L=0,R=1e9,po=0;
while(L<=R){
int mid=(L+R)>>1;
double res=power(mid,a)+b*log(mid)-c;
if(res<=0){
L=mid+1;
}else{
R=mid-1;
}
}
po=min(L,R);
double l=eps,r=1;
while(r-l>=eps){
double mid=(l+r)/2.0;
double res=power(mid+po,a)+b*log(mid+po)-c;
if(res>=0){
r=mid;
}else{
l=mid;
}
}
printf("%.14lf",l+po);
return 0;
} H.神奇的字母（二）
直接读入，然后统计个数即可
代码：
#include<bits/stdc++.h>
using namespace std;
int tim[26];
int main(){
string x;
while(cin>>x){
int len=x.size();
for(int i=0;i<len;++i){
++tim[x[i]-'a'];
}
}
int maxe=0,id=0;
for(int i=0;i<26;++i){
if(tim[i]>maxe){
maxe=tim[i];id=i;
}
}
cout<<char(id+'a');
return 0;
} I.十字爆破
一个很简单的统计问题
我们设l[i]表示第i列的所有数的和,h[i]表示第i行所有数的和，a[i]表示第i个数（编号后）的值，那么第i行和第j列的所有数的和即为
维护好数组后，按公式输出即可
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
#define int long long
int l[N],h[N],a[N];
signed main(){
int n,m;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
int x;
scanf("%lld",&x);h[i]+=x,l[j]+=x;
a[(i-1)*m+j]=x;
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
printf("%lld ",h[i]+l[j]-a[(i-1)*m+j]);
}
puts("");
}
return 0;
} J.异或和之和
还是上套路：按位统计
假设有k个二进制第i位为1的数，那么第i位的贡献为：
直接每位都统计下贡献，再加起来即可
代码:
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int tot[60];
inline long long C(int x,int y){
if(x<y){
return 0;
}
y=x-y;
long long 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){
long long x;
cin>>x;
for(int j=0;j<=59;++j){
tot[j]+=(x&1);
x>>=1;
}
}
long long ans=0,now=1;
for(int i=0;i<=59;++i){
//1个1 or 3个1
long long 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号