A~E题解

A

签到题。2^n就是1<<n，正常比大小就可以了。

	int n;
    cin >> n;
    if ((1 << n) > n * n * n)cout << "B" << endl;
    else cout << "A" << endl;

B

 不重不漏枚举起点，长度一定所以终点一定，对于每个这样的字串判断是否符合条件。

#include<iostream>
using namespace std;
int main(){
    string s;
    cin>>s;
    int ans=0;
    for(int i=0; i<s.size(); ++i){
        if(i+4>=s.size())break;
        if(s[i]==s[i+2] && s[i+2]==s[i+4] && s[i]!=s[i+1] && s[i+1]==s[i+3])ans++;
    }
    cout<<ans<<endl;
    return 0;
}

C

根据题意，我们知道的基本事实是：

只要放置了一个路径上的障碍，那么两个人在此障碍到终点这一段地图会变成同一路径。所以不可能有两个障碍
一个“有效障碍”会让distance+2

1,2=>两个障碍的间距是二

进一步发现这两个人只能符合：

(x,y),(x+1,y+1)
(x,y)(x,y)

第一种情况要注意在第二行留一个空位放障碍。所以x+1,y+1这个点不能在n-1和n列。

#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int x1, y1, x2, y2;
    cin>>x1>>y1>>x2>>y2;
    
    bool ans=false;
    ans=ans|(x1+y1==x2+y2);
    ans=ans|(x1-x2==1 && y1-y2==1 && y1!=n && y1!=n-1);
    ans=ans|(x1-x2==-1 && y1-y2==-1 && y2!=n && y2!=n-1);
    if(ans)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

D

假设处理后的数组是以第二个数字作为基底的，那么移开a[1]需要1个代价，那么肯定不如累加在a[2]上，那么此操作应该与a[2]加到a[1]上等价。

发现基本事实是把前k-1个最大的数直接堆在a[1]上。如果有许多这样相同的数，那么优先累加最靠近数组尾部的数。把这个命题反向思考易得。

搓了一个唐唐的代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+100;
struct node{
    int i;
    long long e;
    bool color=0;
}a[N];
bool cmp(node a, node b){
    return a.e>b.e || (a.e==b.e && a.i>b.i);
}
bool cmp2(node a, node b){
    return a.i<b.i;
}
void solve(){
    int n, k;
    cin>>n>>k;
    for(int i=1; i<=n; ++i){
        cin>>a[i].e;
        a[i].i=i;
        a[i].color=0;
    }
    sort(a+2, a+n+1, cmp);
    for(int i=2, u=1; u<=k; ++i, ++u){
        a[1].e+=a[i].e;
        a[i].color=1;
    }
    sort(a+2, a+n+1, cmp2);
    for(int i=1; i<=n; ++i){
        if(a[i].color==0)cout<<a[i].e<<' ';
    }
    cout<<endl;
    return;
}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

E

使用mex分类。

mex=0的时候集合内数字必然全部相等，计数方式为sum:c(i,t), i∈[1,n],这个式子等价于2 的t次方-1

mex!=0的时候集合内的数字必然只能存在[0, mex-1]区间的数字。以每个数字可以产生的方案数为元素进行乘原理即可。

#include<iostream>
using namespace std;
const int mod=1e9+7;
const int N=1e6+1000;
long long net[N];
int a[N];
//cite:https://oiwiki.com/math/binary-exponentiation/
long long qmi(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
int cal(int x){
    return qmi(2, x, mod)-1;
}
int main(){
    int n;
    cin>>n;
    int maxn=0;
    for(int i=1; i<=n; ++i){
        cin>>a[i];
        net[a[i]]++;
        maxn=max(maxn, a[i]);
    }

    for(int i=0; i<=maxn; ++i)net[i]=cal(net[i]);
    long long ans=0;
    for(int i=1; i<=maxn; ++i){
        ans+=net[i];
        ans%=mod;
    }
        
    for(int i=1; i<=n; ++i){
        net[i]*=net[i-1];
        net[i]%=mod;
    }
    
    for(int i=0; i<=maxn; ++i){
        ans+=net[i];
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}