Educational Codeforces Round 155 (Rated for Div. 2)

A.

最优直接用第一个人的力量值即可，比他小的数都不用思考，力量值比他大的如果耐力值也比他大于等于那就一定-1，否则输出第一个人的力量值即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
 
int n,m;
PII a[N];
void solve(){
    cin>>n;
    map<PII,int> mp;
    for(int i=1;i<=n;i++){
        cin>>a[i].first>>a[i].second;
        mp[{a[i].first,a[i].second}]++;
    }
    int c=a[1].first,d=a[1].second;
    if(mp[{a[1].first,a[1].second}]>1){
        cout<<"-1\n";
        return ;
    }
    sort(a+1,a+1+n,[&](const auto&p,const auto&q){
        return p.first<q.first; 
    });
    int mx=0;
    int idx;
    for(int i=1;i<=n;i++){
        if(a[i].first==c&&a[i].second==d){
            idx=i;
            break;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(i==idx) continue;
        if(a[i].first>=c) mx=max(mx,a[i].second);
    }
    if(mx>=d){
        cout<<-1<<"\n";
        return ;
    }
    cout<<c<<"\n";
    
}
 
signed main(){
    cin.tie(0);ios::sync_with_stdio(0);
    int t=1;
    cin>>t;
    while(t--) solve();
}

B.

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
 
int n,m;
int a[N],b[N];
void solve(){
    cin>>n;
    //4 6 3
    //7 6 6
    //4 3 3
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    int mn=*min_element(a+1,a+1+n);
    int mn1=*min_element(b+1,b+1+n);
    int res1=0,res2=0;
    for(int i=1;i<=n;i++) res1+=(mn+b[i]);
    for(int i=1;i<=n;i++)
    res2+=(mn1+a[i]);
    cout<<min(res1,res2)<<"\n";
    
}
 
signed main(){
    cin.tie(0);ios::sync_with_stdio(0);
    int t=1;
    cin>>t;
    while(t--) solve();
}

C.

理性分析：要么开头是0，要么开头1开始，所以可以枚举是1开头还是0开头

然后发现其实没必要，直接以字符串第一个字符开头就行，

我们先把每段连续的缩点

每个点里面只选一个数出来，其他点都要删

所以最小次数就是每个点的总和-点的总数

方案数就是要删除的个数的阶乘  * 每个点选择哪一个点出来当合法的0/1

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
 
int n,m;
string s;
int fact[N];
void init(){
    fact[0]=1;
    for(int i=1;i<N;i++){
        fact[i]=(LL)fact[i-1]*i%mod;
    }
}
// PII get1()
// {
//     int cnt=1,now=0;
//     int res=0;
//     vector<PII> a;
//     a.push_back({(s[1]-'0'),0});
//     for(int i=1;i<=n;i++)
//     {
//         int x=s[i]-'0';
//         if(a.back().first==x) a.back().second++;
//         else a.push_back({x,1});
//     }
 
// PII get2(){
//     int cnt=0,now=1;
//     int res=0;
//     vector<PII> a;
//     a.push_back({(s[1]-'0'),0});
    
//     for(int i=1;i<=n;i++)
//     {
//         int x=s[i]-'0';
//         if(a.back().first==x) a.back().second++;
//         else a.push_back({x,1});
//     }
//     ///000000
    
//     for(auto [x,v]:a)
//     {
//         cnt+=v;
//         if(x==now)
//         {
//             now^=1;
//             res+=v-1;
//         }
//         else
//         {
//             res+=v;
//         }
//     }
//     return {res,fact[cnt]};
// }
 
void solve(){
 
    cin>>s;
    n=s.size();
    s="?"+s;
    
    vector<PII> a;
    a.push_back({(s[1]-'0'),0});
    for(int i=1;i<=n;i++)
    {
        int x=(s[i]-'0');
        if(a.back().first==x) a.back().second++;
        else a.push_back({x,1});
    }
    
    int cnt=1,res=0;
    for(auto [x,v]:a)
    {
        res+=v-1;
        cnt=cnt*v%mod;
    }
    cout<<res<<" "<<cnt*fact[res]%mod<<"\n";
}
 
signed main(){
    cin.tie(0);ios::sync_with_stdio(0);
    int t=1;
    init();
    cin>>t;
    while(t--) solve();
}

D：异或和考虑每个二进制进行思考

先进行前缀异或和，变成选两个数(s【r】^s[l-1])*(r-l+1)

如果第i下标的某个二进制当前位是1，那么我只要前面的数二进制当前位是0的数，否则答案是0不用考虑

考虑r-l+1

统计前面有多少个数异或和为0的个数，和异或和为0下标总和

然后（r-l+1）=个数*r-下标总和即可，（因为是s[l-1]，所以那个+1已经考虑进去了）

#include<bits/stdc++.h>
using namespace std;
const int N =3e5+10,mod= 998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
 
int n,m;
int a[N];
int s[N];
int cnt[2][35];
int d[2][35];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int res=0;
    //1 2 3 3
    for(int i=1;i<=n;i++)
    s[i]=a[i]^s[i-1];
 
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=30;j++)
        {
            int now=0;
            if(s[i]>>j&1) now=0,d[1][j]=(d[1][j]+i)%mod;
            else now=1,d[0][j]=(d[0][j]+i)%mod;
    res+=(1<<j)%mod*(cnt[now][j]*i%mod-d[now][j])%mod;
    res=(res%mod+mod)%mod;
            cnt[now^1][j]++;
        }
    }
    cout<<(res%mod+mod)%mod;
}
 
signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
    
   // cin>>t;
    while(t--) solve();
}