Solution A(数组操作):

​ 有长度为n的数组，m次操作，操作分为两种，对区间每个数开根和区间求和。考虑到n和m均小于3* 10^3，对于两种操作，我们直接遍历区间[l,r]，暴力sqrt()开根修改和挨个求和，时间复杂度O(n^{2})

std:

#include<bits/stdc++.h>
#define N 100005
using namespace std ;
int a[N],c[N],n,m ;
int main() {
    cin>>n>>m ;
    for(int i=1;i<=n;++i) cin>>a[i] ;
    while(m--)
    {
        int opt,l,r ;
        cin>>opt>>l>>r ;
        if(opt==1)
        {
            for(int i=l;i<=r;++i) a[i]=floor(sqrt(a[i])) ;
        }
        else 
        {
            long long ans=0 ;
            for(int i=l;i<=r;++i) ans+=a[i] ;
            cout<<ans<<endl ;
            for(int i=1;i<=n;++i) c[i]=0 ;
        }
    }
    return 0 ;
}

Solution B(斐波那契数列):

​ 给出递推式
f(n)=A × f(n-1)+B × f(n-2)+C
求
f(n) \mod (10^9+7)
。直接从i=3枚举到i=n，每层套公式算，即可得到f(n)，但本题要注意开long long，不然在递推中f(n)的计算会爆long long，时间复杂度O(n)

std:

#include<bits/stdc++.h>
#define N 1000005
#define mod 1000000007
#define LL long long
using namespace std ;
int main() {
    LL a,b,c,n ;
    cin>>a>>b>>c>>n ;
    LL f[N] ;
    f[1]=1 ; f[2]=1 ;
    for(int i=3;i<=n;++i)
        f[i]=(a*f[i-1]+b*f[i-2]+c)%mod ;
    cout<<f[n]<<endl ;
    return 0 ;
}

Solution C(两世之约):

​ n*n的格子，每次可以翻转某一行或者某一列，问是否可以通过翻转得到“真理的答案”，如果无解输出-1

​ 首先题目中”真理的答案“的定义：可以从某个白色格子出发，在只经过白色格子且每个 白色格子必须经过且仅经过一次的情况下走完所有白色格子，这本质上是求网格图上仅考虑白色格子的情况下是否存在一条哈密顿路径，判断哈密顿路径是否存在目前是np完全问题，只能暴力dfs，但是随机情况下表现不差，我们这一块不做考虑，我们重点考虑如何进行行/列的翻转操作。

​ 通过观察可以发现，某一行/列翻转偶数次等于没有翻转，翻转奇数次等于翻转一次，所以如果答案存在，这个答案不会超过n*n。

​ 考虑到数据n<=7，所以我们打算通过bfs(广度优先搜索)来实现，bfs的优势是搜到答案即可退出搜索过程，这个答案一定是最小的之一。

​ 剩下的就是bfs的记忆化问题，也就是我们如何判断当前状态是否已经搜索过。记忆化的方式不唯一，可以用hash函数或者状态压缩来实现，题解采用了状态压缩的方式实现。

​ 我们考虑用一个14位二进制数来表示当前的翻转状态，1-7位分别对应1-7行，8-14位分别对应1-7列，如果该二进制数当前位是1，则代表该行/列已经翻转过，反之则没有被翻转过，我们开一个vis[i]数组代表二进制数i是否已经被搜索过，每个二进制数入队时我们令它的vis为1，如果vis[i]=1，我们直接不对其进行搜索(当前待搜索队列已经有二进制数i)

​ 至此，本题bfs中最多有2^{2n}个状态，我们搜到答案直接输出并结束程序，bfs结束没有搜到答案则输出-1，在数据随机情况下可以通过本题。

std:

#include<bits/stdc++.h>
#define N 9
using namespace std ;
int n,s[N][N],t[N][N] ;
char c[N][N] ;
bool vis[1<<(N*2)],lst[N][N],is[1<<N] ;
struct node { int x,d ; } ;
int dx[4]={-1,1,0,0},
    dy[4]={0,0,-1,1};
inline bool check(int x,int y)
{
    return x>0&&y>0&&x<=n&&y<=n ;
}
bool dfs(int x,int y,int cnt,int id)
{
    if(cnt==0) return 1 ;
    lst[x][y]=1 ;
    for(int i=0;i<4;++i)
    {
        int px=x+dx[i],py=y+dy[i] ;
        if(check(px,py)&&t[px][py]==0&&!lst[px][py]&&dfs(px,py,cnt-1,id))
            return 1 ;
    }
    lst[x][y]=0 ;
    return 0 ;
}
int main()
{
    scanf("%d",&n) ;
    for(int i=1;i<=n;++i) scanf("%s",c[i]+1) ;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;j++)
            s[i][j]=c[i][j]-'0' ;
    queue<node> q ;
    q.push((node){0,0}) ; vis[0]=1 ;
    while(!q.empty())
    {
        node p=q.front() ; q.pop() ;
        memcpy(t,s,sizeof(t)) ;
        int num=0,X=p.x ;
        for(int i=0;i<n;++i)
        {
            num++ ;
            if(X&1) 
            {
                for(int i=1;i<=n;++i)
                    t[num][i]^=1 ;
            }
            X>>=1 ;
        }
        num=0 ; 
        for(int i=0;i<n;++i)
        {
            num++ ;
            if(X&1)
            {
                for(int i=1;i<=n;++i)
                    t[i][num]^=1 ;
            }
            X>>=1 ;
        }
        int res=0 ;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;j++)
                if(t[i][j]==0) res++ ;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;j++)
                if(t[i][j]==0)
                {
                    if(dfs(i,j,res-1,p.x))
                    return printf("%d\n",p.d),0 ;
                }
        for(int i=0;i<n*2;++i)
            if(!(p.x&(1<<i))&&!vis[p.x|(1<<i)])
                q.push((node){p.x|(1<<i),p.d+1}),vis[p.x|(1<<i)]=1 ;
    }
    printf("-1\n") ;
    return 0 ;
}

Solution D(Raksasa的酒):

根据题意推导可得
2个瓶盖=一瓶酒+1个瓶盖
所以1个瓶盖=一瓶酒(不算最后一个瓶盖)
所以最终答案为2*n-1;

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll n;
        scanf("%lld",&n);
        printf("%lld\n",n+n-1);
    }
    return 0;
}

Solution E(Raksasa的木材):

可以考虑到一整段完整的木材，要劈 木材长度-1 刀
所以现在有几段，说明已经劈了 段数-1 刀
最终答案为(n-1)-(cnt-1)=n-cnt;

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n,cnt;
    scanf("%lld%lld",&n,&cnt);
    ll l,r;
    for(int i=0;i<cnt;i++) scanf("%lld%lld",&l,&r);
    printf("%lld\n",n-cnt);
    return 0;
}

Solution F(最长子序列):

我们采用贪心的思路，将每个字符按照字典序为第一关键字、下标为第二关键字进行排序。由于字典序的特性，在字符相等的情况下，我们取下标靠前的为首个字符。之后按照排序后的序列，从首个字符向后，取下标在上一个字符后面的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
bool cmp(pair<char,int> a,pair<char,int>  b){
    if(a.first==b.first) return a.second<b.second;
    return a.first>b.first;
}
int main() {
    int T;
    cin>>T;
    while(T--){

        string s;
        cin>>s;
        vector<pair<char,int>> ve;
        for(int i=0;i<s.size();i++){
            ve.push_back({s[i],i});
        }
        sort(ve.begin(),ve.end(),cmp);
        string re="";
        re+=ve[0].first;
        int i=1;
        int num=ve[0].second;
        while(i!=ve.size()){
            if(ve[i].second>num){
                num=ve[i].second;
                re+=ve[i].first;
            }
            i++;
        }
        cout<<re<<endl;
    }
    return 0;
}

Solution G(Raksasa的二进制):

直接算就行，题目说什么就写什么就行

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        char c[2][32];
        char op;
        scanf(" %c",&op);
        scanf("%s",c[0]);
        scanf("%s",c[1]);
        if(op=='&') for(int i=0;i<32;i++) printf("%c",((c[0][i]-'0')&(c[1][i]-'0'))+'0');
        else if(op=='|') for(int i=0;i<32;i++) printf("%c",((c[0][i]-'0')|(c[1][i]-'0'))+'0');
        else for(int i=0;i<32;i++) printf("%c",((c[0][i]-'0')^(c[1][i]-'0'))+'0');
        printf("\n");
    }
    return 0;
}