AtCoder Beginner Contest 221（A~E）

略

#include 
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define debug(x) cout<<"> "<< x< PII;
const int N =10 + 1e5, mod = 1e9 + 7;

void solve()
{    
    string s,t;
    cin>>s>>t;
    if(s == t){
        cout<< "Yesn";
        return;
    }
    for(int i=0;i 
C 
题目 
 
 
给一个整数，可以把它的每一位重新组合，并把它分割为两个数字，求分开的这两个数的乘积的最大值
 
 
思路 
数据范围较小，直接遍历所有的排列，遍历每种排列的分割方案即可。
 
AC代码 
#include 
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define debug(x) cout<<"> "<< x< PII;
const int N =10 + 1e5, mod = 1e9 + 7;
ll get_ans(int *a,int n)
{
    int tmp[15];
    for(int i=0;i  "<>n;
   int len=0;
   while(n){
       a[len++] = n%10;
       n/=10;
   }
   sort(a,a+len);
   ll res = get_ans(a,len);
   while(next_permutation(a,a+len)){
       res = max(get_ans(a,len),res);
   }
   cout << res<< endl;
}
signed main()
{
    ios::sync_with_stdio();cin.tie();cout.tie();

    solve();

    return 0;
}
 
D 
题目 
 
 
给出n个人上线天数的区间，求由i个人同时在线的天数。
 
 
思路 
key point:明确一个人上线对在线人数的贡献为1，一个人下线对在线人数的贡献为-1
 
我们可以把所有人的上下线时间点放在一个时间轴上，上线和下线的时间点会把这个时间轴划分为若干个小段，我们对每一个小段进行分析。
显然，我们现在的疑惑就是对于每一个小段提供的天数，我们到底把它放在同时在线人数为几的答案上。
 由key point，我们可以实时更新这个在线人数，每有人上线+1，反之减一。这样就可以正确确定答案的索引。
 
AC代码 
#include 
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define debug(x) cout<<"> "<< x< PII;
const int N =10 + 2e5, mod = 1e9 + 7;
int n;
PII a[N];
void solve()
{    
    cin>>n;
    for(int i=0;i>a[i].first>>a[i].second;
    sort(a,a+n);

    vectortmp;
    for(int i=0;i 
E 
题目 
 
 
给定一个序列，找出所有满足末尾元素大于等于首元素的子串（子串不必连续）。
 
 
思路 
key point：维护涉及一个序列前缀和某元素相对大小关系的时候，树状数组很好用，典型样例是用树状数组求逆序对的数量
 
排列组合很容易推出，如果我们选
     
      
       
        
         
          a
         
         
          j
         
        
       
       
        a_j
       
      
     aj​做尾端，对于前面任意一个不比它大的元素
     
      
       
        
         
          a
         
         
          i
         
        
       
       
        a_i
       
      
     ai​还说，可以选择的方案数为
     
      
       
        
         
          2
         
         
          
           j
          
          
           −
          
          
           i
          
          
           −
          
          
           1
          
         
        
       
       
        2^{j-i-1}
       
      
     2j−i−1，因此我们只要遍历尾端，把所有方案找到再加一起就行，因为有
     
      
       
        
         i
        
       
       
        i
       
      
     i和
     
      
       
        
         j
        
       
       
        j
       
      
     j两个变量这是
     
      
       
        
         O
        
        
         (
        
        
         
          n
         
         
          2
         
        
        
         )
        
       
       
        O(n^2)
       
      
     O(n2)的算法。显然会T掉。
进一步，我们可以先对原数据进行离散化后用树状数组进行优化，考虑方案计算公式
     
      
       
        
         
          2
         
         
          
           j
          
          
           −
          
          
           i
          
          
           −
          
          
           1
          
         
        
       
       
        2^{j-i-1}
       
      
     2j−i−1，它可以变为
     
      
       
        
         
          
           2
          
          
           
            j
           
           
            −
           
           
            1
           
          
         
         
          
           2
          
          
           i
          
         
        
       
       
        frac {2^{j-1}}{2^i}
       
      
     2i2j−1​,进一步的，以
     
      
       
        
         
          a
         
         
          j
         
        
       
       
        a_j
       
      
     aj​为结尾的情况下，总的方案数是
     
      
       
        
         
          2
         
         
          
           j
          
          
           −
          
          
           1
          
         
        
        
         ∗
        
        
         (
        
        
         
          
           1
          
          
           
            2
           
           
            
             
              i
             
             
              1
             
            
            
             −
            
            
             1
            
           
          
         
        
        
         +
        
        
         
          
           1
          
          
           
            2
           
           
            
             
              i
             
             
              2
             
            
            
             −
            
            
             1
            
           
          
         
        
        
         +
        
        
         
          
           1
          
          
           
            2
           
           
            
             
              i
             
             
              3
             
            
            
             −
            
            
             1
            
           
          
         
        
        
         +
        
        
         ⋅
        
        
         ⋅
        
        
         ⋅
        
        
         ⋅
        
        
         ⋅
        
        
         ⋅
        
        
         )
        
       
       
        2^{j-1}*(dfrac{1}{2^{i_1-1} }+ dfrac{1}{2^{i_2-1}} +dfrac{1}{2^{i_3-1}}+······)
       
      
     2j−1∗(2i1​−11​+2i2​−11​+2i3​−11​+⋅⋅⋅⋅⋅⋅),对于后半部分，每一个小部分都由一个
     
      
       
        
         
          a
         
         
          i
         
        
       
       
        a_i
       
      
     ai​提供，将其存在树状数组中，即可在
     
      
       
        
         O
        
        
         (
        
        
         l
        
        
         o
        
        
         g
        
        
         n
        
        
         )
        
       
       
        O(logn)
       
      
     O(logn)的时间内得到这个和。
 
AC代码 
时间复杂度：
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        l
       
       
        o
       
       
        g
       
       
        n
       
       
        )
       
      
      
       O(nlogn)
      
     
    O(nlogn)
 
#include 
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define debug(x) cout<<"> "<< x< PII;
const int N =10 + 3e5, mod = 998244353;
int n;
int a[N] ,b[N];
int tr[N];
void add(int p,int v){
    for(int i=p;i<=n;i+=lowbit(i)) (tr[i]+=v)%=mod;
}
int getsum(int p){
    int res =0;
    for(int i=p;i>0;i-=lowbit(i)) (res+=tr[i])%=mod;
    return res;
}
int ksm(int a,int b){
    int res =1;
    while(b){
        if(b&1) res = 1ll*res*a%mod;
        a = 1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
void solve()
{    
    cin>> n;
    for(int i=1;i<=n;i++) cin>>a[i],b[i] = a[i];
    sort(b+1,b+1+n);
    int len = unique(b+1,b+1+n) - b - 1;
    for(int i=1;i<=n;i++) a[i] = lower_bound(b+1,b+1+len,a[i])- b;

    ll res = 0;
    ll pw = 1;
    for(int i=1;i<=n;i++){
        (res+=pw*getsum(a[i]))%=mod;
        (pw<<=1)%=mod;
        
        add(a[i],ksm(pw,mod-2));
    }
    cout << res << endl;

}
signed main()
{
    ios::sync_with_stdio();cin.tie();cout.tie();

    solve();

    return 0;
}