题解

我的博客

A. 小橘编译器

使得代码在找到第一个连续的//停止即可。

void work()
{
    string s ; cin >> s ;
    string no = "" ;
    for(int i = 0 ; i < s.size() ; i++)
    {
        if(s[i] == '/' && i + 1 < s.size() && s[i + 1] == '/' )
        {
            break ;
        }
        no += s[i] ;
    }
    if(no == "")
    {
        no = "null" ;
    }
    cout << no << endl ; 
}

B. 小橙的好序列

考虑a 从 1 -> n 的每一个值都是他前一个值的2 * k + 1(1是不变)倍，递推过去即可(注意边运算便取模)。

void work()
{
    int n , k ; cin >> n >> k ; 
    vi dp(n + 1 , 1) ;
    for(int i = 1 ; i <= n ; i++)
    {
        dp[i] = (dp[i - 1] * (2 * k + 1)) % mod2 ;
    }
    cout << dp[n] << endl ; 
}

C. 小橙的完美序列

由ai = i ^ x可知，x = ai * i , 在了解位运算后，我们采取贪心的做法，找到整个序列中数量最多的对于每一个数的x , 然后用n减去即可。

void work()
{
    int n ; cin >> n ; 
    vi a(n + 1) ;
    unordered_map<int ,  int>mp ;
    int mx = 0 ; 
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i] ; 
        mp[a[i] ^ i]++ ;
        mx = max(mx , mp[a[i] ^ i]) ;
    }
    cout << n - mx << endl ; 
}

D&&E. 小橙的幸运数

前言：为了更好的理解倍增的思想，请移步牛客算法登峰题单(我也是现学的)(划掉) 考虑到实际上每次相加的数都是a中的某一个数。或者说，存在一个循环，使x沿循环移动，看是否能够到达c。

void work()
{
    int m , c , q ; cin >> m >> c >> q ;
    vi a(m) ;
    for(int i = 0 ; i < m ; i++)
    {
        cin >> a[i] ; 
    }
    vii mp(m , vi(35)) ;
    for(int i = 0 ; i < m ; i++)
    {
        mp[i][0] = a[i] ;
    }
    for(int i = 1 ; i < 35 ; i++)
    {
        for(int j = 0 ; j < m ; j++)
        {
            int f = mp[j][i - 1] ;
            int a1 = (j + f) % m ;
            mp[j][i] = f + mp[a1][i - 1] ;
            if(mp[j][i] > c)mp[j][i] = INT_MAX ; 
        }
    }
    while(q--)
    {
        int x ; cin >> x ; 
        if(x > c)
        {
            cout << "No" << endl ; 
            continue ;
        }
        else if(x == c)
        {
            cout << "Yes" << endl ;
            continue ;
        }
        for(int i = 34 ; i >= 0 ; i--)
        {
            int b = x + mp[x % m][i] ;
            if(b <= c)
            {
                x = b ;
            }
        }
        if(x == c)cout << "Yes" << endl ; 
        else cout << "No" << endl ; 
    }
}

F. 小橙的异或和

由于考虑到对于0的修改没有意义，并且0对于结果并没有贡献，并且我们需要在操作过程中删去新出现的0，所以我们需要维护的数据结构具有以下特点

1、可以有序排列数组下标

2、对于每一个l , r能够能很快的找到离他们最近的非0数组元素

3、删除元素的时间复杂度尽可能小

由此我们想到使用set 由于num ^ a ^ a == num , 所以我们可以在读入数据的时候放心的计算异或和，在后续修改的过程中先使用答案异或原来的数组元素，再异或新的数组元素即可

void work()
{
    int n , q ; cin >> n >> q ;
    vi a(n + 1) ;
    int ans = 0 ; 
    set<int>md ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i] ;
        if(a[i] != 0)
        {
            md.in(i) ;
        }
        ans ^= a[i] ;
    }
    while(q--)
    {
        int o ; cin >> o ;
        if(o == 2)
        {
            cout << ans << endl ; 
        }
        else
        {
            int l , r ; cin >> l >> r ; 
            auto idex = md.lower_bound(l + 1) ;    
            while(idex != md.end() && *idex <= r)
            {
                ans ^= a[*idex] ;
                a[*idex] = (a[*idex] / (*idex - l + 1)) ;
                ans ^= a[*idex] ;
                if(a[*idex] == 0)
                {
                    idex = md.erase(idex) ;
                }
                else
                {
                    idex++ ;
                }
            }
        }
    }
}