1 Ygg分苹果

#include <iostream>
using namespace std;

int main() {
   int n;
   cin>>n;
   cout<<(1+n)*n/2;
}

2 最大公约数

#include<bits/stdc++.h>
using namespace std;
#define int long long 
signed  main() {
  int x,y,z;
  cin>>x>>y>>z;
  cout<<gcd(gcd(x,y),z)<<"\n";
}

3 软软的国旗

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n,m;
    cin>>n>>m;
    int flag=1;
    int last=-1;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        s=" "+s;
        int lflag=-1;
        for(int j=1;j<=m;j++){
            int tem=s[j]-'0';
            if(lflag==-1){
                lflag=tem;
            }else if(lflag!=tem){
                flag=0;
            }
        }
        if(last!=-1&&last==lflag){
                flag=0;
        }
        last=lflag;
    }
    if(flag){
        cout<<"YES"<<"\n";
    }else{
        cout<<"NO"<<"\n";
    }
}

4 79元能买什么

背包

#include<bits/stdc++.h>
using namespace std;
#define int long long

signed  main() {
   int n;
   cin>>n;
   vector<int> dp(79+10);
   for(int i=1;i<=n;i++){
    int v,w;
    cin>>v>>w;
    for(int j=79;j>=v;j--){
        dp[j]=max(dp[j-v]+w,dp[j]);
    }
   }
   cout<<dp[79]<<"\n";

}

5 a+b?


#include<bits/stdc++.h>

using namespace std;
#define int long long
signed main(){
    int a,b;
    cin>>a>>b;
    int maxx=0;
    auto ex=[&](int x){
        int res=0;
        while(x){
            res=max(res,x%10);
            x/=10;
        }
        return res;
    };
    maxx=max(ex(a),ex(b))+1;
    string ta=to_string(a),tb=to_string(b);
    reverse(ta.begin(),ta.end());
    reverse(tb.begin(),tb.end());
    int y=0;
    for(int i=0;i<max(ta.length(),tb.length());i++){
            int na=((i>=ta.length())?0:(ta[i]-'0')),nb=((i>=tb.length())?0:(tb[i]-'0'));
            int tem=y+na+nb;
            y=tem/maxx;
    }
    int len=max(ta.length(),tb.length());
    if(y){
        len++;
    }
    cout<<len<<"\n";
}

6 卓卓子的特殊癖好

双指针

#include<bits/stdc++.h>

using namespace std;
#define int long long
signed main(){
   int n,m;
   cin>>n>>m;
   string s;
   cin>>s;
   s=" "+s;
   int res=0;
   int ans=0;
   for(int l=1,r=0;l<=n;l++){
       r=max(l-1,r);
       while(res<m&&r<=n){
           r++;
           res+=(s[r]=='*');
       }
       if(r>n) {
           break;
       }
       ans+=min(n-l+1,n-r+1);
       if(r>=l){
           res-=(s[l]=='*');
       }

   }
   if(ans==0){
       cout<<"This is really a regrettable thing."<<"\n";
   }else{
       cout<<ans<<"\n";
   }
}

7 软院三大恶霸

bfs

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    map<vector<string>,int> k;
    map<vector<string>,int> cnt;
    vector<string> f(3);
    for(int i=0;i<3;i++){
            cin>>f[i];
    }
    k[f]=1;cnt[f]=0;
    vector<string>ini(3);
    ini[0]="lsh";
    ini[1]="l*w";
    ini[2]="qyq";
    queue<vector<string>> q;
    q.push(f);
    int dx[]={1,-1,0,0};
    int dy[]={0,0,1,-1};
    int ans=0;
    while(!q.empty()){
        auto nw=q.front();
        q.pop();
        if(nw==ini){
            ans=cnt[nw];
            break;
        }
        int nx,ny;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(nw[i][j]=='*'){
                    nx=i,ny=j;
                    break;
                }
            }
        }
        for(int i=0;i<4;i++){
            auto lx=nx+dx[i],ly=ny+dy[i];
            auto lw=nw;
            if(lx<0||lx>2||ly<0||ly>2){
                continue;
            }
            swap(lw[nx][ny],lw[lx][ly]);
            if(k[lw]){
                continue;
            }
            k[lw]=1;
            cnt[lw]=cnt[nw]+1;
            q.push(lw);
        }
    }

    cout<<ans<<"\n";

}

8 去漫展咯

前缀和

注意该题数据有点问题,实际上没有保证l和r小于n;

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n,m;
    cin>>n>>m;
    vector<int> f(n+1000000);
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        f[l]++,f[r+1]--;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        f[i]+=f[i-1];
        ans=max(f[i],ans);
    }
    cout<<ans<<"\n";

}

9 分割数字

简单dp

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n;
    cin>>n;
   string s;
   cin>>s;
   s=" "+s;

   vector<vector<int>> f(n+10,vector<int>(n+10,-1));
   f[0][0]=0;
   for(int i=1;i<=n;i++){
       int p=1;
       int num=0;
       for(int j=i-1;~j;j--){
            num+=(s[(j+1)]-'0')*p;
            p*=10;
            for(int r=j;~r;r--){
                if(r==0&&j!=0){
                    continue;
                }
                if((~f[j][r])&&f[j][r]<=num){
                    if(!(~f[i][r+1])){
                        f[i][r+1]=num;
                    }else{
                        f[i][r+1]=min(num,f[i][r+1]);
                    }
                }
            }
       }
   }
   for(int i=n;i;i--){
       if(~f[n][i]){
           cout<<i<<"\n";
           return 0;
       }
   }

}
}