A：AOE还是单体？
排个序贪心就行了，关键是怎么实现的时候注意下细节就行了，看看是继续用AOE打所有人划得来还是直接一枪一枪打死所有人划得来。
我的写法是先统计所有人然后一步一步换算成AOE，直到不能换为止，题目数据ai范围1e9，记得开long long。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555;
int a[N];
int main(){
int n=read(),x=read();
ll ans=0,s=0;
for(int i=1;i<=n;i++){
a[i]=read();
ans+=a[i];
}
if(x>=n){
cout<<ans<<endl;
return 0;
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
while(i+x<=n&&s<a[i]){
ans-=(n-x-i+1);
s++;
}
}
cout<<ans<<endl;
return 0;
}B：k-size字符串
首先我们肯定要先把k个字符摆好，如果是奇数有2种情况，aba,bab，偶数的话就是abab,baba答案乘以2即可剩下的就是把剩下的a和剩下的b看看在这些a，b的位子上有多少种放法，也就是n-k/2个物品放到k/2个箱子里有多少种放法。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1555555,mod=1e9+7;
ll a[N]={1},n,m,k;
ll qsm(ll a,ll b){
ll s=1;
while(b){
if(b%2)s=s*a%mod;
a=a*a%mod;b>>=1;
}
return s%mod;
}
ll inv(ll x) {
return qsm(x,mod-2);
}
ll C(ll n,ll m){
if(n<m||n<0||m<0)return 0;
else return a[n]*inv(a[n-m])%mod*inv(a[m])%mod;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=max(n,m);i++){
a[i]=i*a[i-1]%mod;
}
if(k>n+m){
cout<<0<<endl;
}
else{
ll x=k>>1,y=k-x;
cout<<(C(n-1,x-1)*C(m-1,y-1)%mod+C(n-1,y-1)*C(m-1,x-1)%mod)%mod<<endl;
}
return 0;
}C：白魔法师
看到题目提到连通块这个概念很容易想到并查集，并查集就是专门求连通块的，我们先把所有的白色合并，然后从每个黑点起手求相邻的白点的合并数量有多少个即可，每条边最多跑2次，时间复杂度O（n）。
吐槽下题目数据有点水，我同学直接暴搜都过了的，每个黑点直接开始搜旁边有多少白点。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
ll s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555,mod=1e9+7;
char s[N];
vector<int>q[N];
int a[N],num[N];
inline int find(int x){
if(a[x]!=x)a[x]=find(a[x]);
return a[x];
}
int main(){
int n=read(),ans=0;
scanf("%s",s+1);
for(int i=1;i<=n;i++)a[i]=i;
for(int i=1;i<n;i++){
int x=read(),y=read();
q[x].push_back(y);
q[y].push_back(x);
if(s[x]==s[y]){
a[find(x)]=find(y);
}
}
for(int i=1;i<=n;i++){
num[find(i)]++;
}
for(int i=1;i<=n;i++){
if(s[i]=='B'){
int sum=1;
for(int j=0;j<q[i].size();j++){
if(s[q[i][j]]=='W')
sum+=num[find(q[i][j])];
}
ans=max(ans,sum);
}
}
if(ans)
cout<<ans<<endl;
else
cout<<n<<endl;
return 0;
}D：抽卡
这题考点感觉就是有理数取余，概率方面怎么求并不难，不会有理数取余的同学看下https://www.luogu.com.cn/problem/P2613 洛谷有理数取余的模板题，具体证明博主也不会，这东西平时直接记下来怎么用就行了，比赛出去的时候可以把板子带上。
概率就是算减法，算所有卡池都没抽到的概率，然后用1减去这个概率就行了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555,mod=1e9+7;
ll a[N],b[N],x=1,y=1,c,d;
void f(int a,int b){
if(b==0){
c=1,d=0;return ;
}
f(b,a%b);
int lx=c;
c=d,d=lx-a/b*d;
}
int main(){
int n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
b[i]=read();
}
for(int i=1;i<=n;i++){
y=y*a[i]%mod;
x=(x*(a[i]-b[i]))%mod;
}
x=y-x;
f(y,mod);
x=(x%mod+mod)%mod;
cout<<(x*c%mod+mod)%mod<<endl;
return 0;
}E：点击消除
2个相同的字母，并且相邻碰在一起可以合并，这不就是裸的括号匹配吗，[]左括号和右括号对应，只是这里改成了字母，所以一个栈就可以解决问题了。
判断栈顶和新加的字母是不是相同，相同消去即可，最后剩下的栈是空栈就输出0.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555;
char a[N],b[N];
bool vis[N];
bool check(char a[],int n){
stack<char>q;
for(int i=0;i<n;i++){
if(!q.empty()&&q.top()==a[i])
q.pop();
else
q.push(a[i]);
}
bool flag=false;
int now=0;
while(!q.empty()){
flag=true;
b[now++]=q.top();q.pop();
}
b[now]='\0';
return flag;
}
int main(){
scanf("%s",&a);
int n=strlen(a);
if(check(a,n)){
n=strlen(b);
for(int i=n-1;i>=0;i--){
printf("%c",b[i]);
}
}
else
printf("0");
return 0;
}F：疯狂的自我检索者
签到题，贪心，因为剩下的人的分数是你想要多少就多少，所以尽可能高或者尽可能低即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555;
double sum=0;
int main(){
int n=read(),m=read();
for(int i=1;i<=n-m;i++){
sum+=read();
}
printf("%.5lf %.5lf",(sum+m)/n,(sum+m*5)/n);
return 0;
}G：解方程
很明显的二分，但是比赛时博主脑子抽风硬是想用数学方法写，然后没写出来。
log(x)以e为底的log函数在math库里面。
二分个200次以后误差应该已经很小了，不放心的话还可以再多几次，反正judge一次耗费的时间比较少。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
ll s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555,mod=1e9+7;
double ans=1;
double a,b,c;
bool judge(double x){
return pow(x,a)+b*log(x)<c;
}
int main(){
cin>>a>>b>>c;
double l=0,r=1e9+7;
for(int i=1;i<=200;i++){
double mid=(l+r)/2;
if(judge(mid)){
l=mid;
ans=l;
}
else{
r=mid;
}
}
printf("%.8lf\n",ans);
return 0;
}H：神奇的字母（二）
同样是签到题，用个多组输入再用个桶记录下每个字母出现多少次即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555;
char a[N];
int vis[15555],maxn;
char ans;
int main(){
while(scanf("%s",&a)!=EOF){
int n=strlen(a);
for(int i=0;i<n;i++){
vis[a[i]]++;
if(maxn<vis[a[i]]){
maxn=vis[a[i]];ans=a[i];
}
}
}
printf("%c",ans);
return 0;
}I：十字爆破
题目是说n * m<=1e6所以估计会特意卡开2维数组的1000 * 1000的，所以我们只需要用个一维数组统计下标就行了，(i-1)*m+j表示a[i][j],再把该行该列所有值加起来的数算出来减去这个点的坐标即可，题目数据比较大，记得开long long。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555;
ll h[N],l[N],a[N];
int main(){
int n=read(),m=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ll x=read();
a[(i-1)*m+j]=x;
h[i]+=x;
l[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]);
}
printf("\n");
}
return 0;
}J：异或和之和
又双叒叕是一道位运算题目，好像小白月赛每次都有这种题
这种题，不管他怎么减少的时间复杂度，首先肯定是把每个数的位数上有多少个1求出来，这个肯定是套路了。
这题是求任意3个数组成的，那么组成方式就是Cn3但是我们只需要有效的，也就是该位上出现了1个1或者3个1的情况，也就是在1的个数中取1个和0中取2个和1中取3个统计有多少种取法，再乘以该位的权值，算出来就是答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
ll s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<1)+(s<<3)+(c^48);c=getchar();
}
return f*s;
}
const int N=1555555,mod=1e9+7;
int a[66];
ll ans;
int main(){
int n=read();
for(int i=1;i<=n;i++){
ll x=read();
for(int j=0;j<=63;j++){
if((ll)1<<j&x){
a[j]++;
}
}
}
for(int i=0;i<64;i++){
ll x=n-a[i],y=a[i];//记得开long long不然会溢出
ans=(ans+((ll)1<<i)%mod*((y*(y-1)*(y-2)/6+x*(x-1)*y/2)%mod))%mod;
}
cout<<(ans+mod)%mod<<endl;
return 0;
}
京公网安备 11010502036488号