2022牛客寒假算法基础集训营3

当天去走亲戚了，后来自己vp了一下，只能说逃过一劫，这场真阴间（呜呜呜，被智乃哥哥杀爆了），赛中6赛后8，估算rank在450名左右，打了估计掉分

A：签中签，0

B：背包，6（1）

C：dp（补）

D：签到，2

E：模拟，175（6）

G：数据结构（补）

I：尺取，107（5）

L：stl+模拟，30

 这题本质就是一个分组背包，每种物品三个操作：选，不选，选一半，其实就是一组里面三个物品，0，整个，半个。至于我为什么wa1，哈哈，忘了取模，棹，前两场每场都因为这个wa过，呜呜呜，就是不长记性。

#include 
using namespace std;
#define int long long
#define ll long long
#define mod (ll)(1e9+7)
int a[1010];
int dp[1010][1010];
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=a[i]){
                dp[i][j]+=dp[i-1][j-a[i]];
            }
            if(j>=a[i]/2){
                dp[i][j]+=dp[i-1][j-a[i]/2];
            }
            dp[i][j]%=mod;
        }
        dp[i][a[i]]++;
        dp[i][a[i]/2]++;
    }
    for(int i=1;i<=m;i++){
        cout< 
E：智乃的数字积木(easy version) 
 
 这题就是一个模拟，带一点点思维，和上一场的F有点类似，首先题目中说可以交换任意的两个连续的同色区间的数，那我们就每次遍历的时候对每一个连续的同色区间进行排序即可，但是注意要新拷贝一个，不能直接在原数组上修改，那为什么我wa6呢？因为我是fw(，我一开始想到并查集去了，但是这题直接循环修改就行，不涉及迭代修改的问题，呜呜呜。
 
#include 
using namespace std;
#define fast ios::sync_with_stdio(0), cin.tie(0)
#define int long long
#define ll long long
#define mod (int)(1e9+7)

int x[100001];
int y[100001];
int z[100001];
int ou=0;
signed main(){
    fast;
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        char a;
        cin>>a;
        x[i]=a-'0';
    }
    for(int i=1;i<=n;i++){
        cin>>y[i];
    }
    int flag=1;
    k++;
    while(k--){
        if(flag!=1){
            int a,b;
            cin>>a>>b;
            for(int i=0;i<=n;i++){
                if(y[i]==a){
                    y[i]=b;
                }
            }
        }
        flag=0;
        memcpy(z,x,sizeof(x));
        int l=1,r=2;
        for(int i=2;i<=n;i++){
            if(y[i]==y[i-1]){
                r++;
                continue;
            }else{
                sort(z+l,z+r,greater());
                l=r;
                r++;
            }
        }
        if(l!=r){
            sort(z+l,z+r,greater());
        }
        ou=0;
        for(int i=1;i<=n;i++){
            ou*=10;
            ou+=z[i];
            ou%=mod;
        }
        ou%=mod;
        cout< 
 
G：智乃的树旋转(easy version) 
 
 
 
 
 
 
哎，贼长的题面，其实就是树的平衡旋转，不懂的可以回去学学数据结构，算是acmer入门必学吧，那你为什么没做出来？，对此我的评价是：我是没入门的fw，主要是vp到最后不想打了，看到队里的爹都下机了，没动力了，呜呜呜。
 
思路：由于题目说保证一定存在k<=1的解，所以无非就下面两种情况：
 
 
 智乃哥哥牛逼（超大声），一目了然，看不懂的去b站听听智乃哥哥的讲解吧，easy version还是不难的，但是hard version我就不补了,12人题我拿头补（。
 
#include 
using namespace std;
#define fast ios::sync_with_stdio(0), cin.tie(0)
#define int long long
#define ll long long
mapol;
mapne;
signed main(){
    fast;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
    	int a,b;
    	cin>>a>>b;
    	ol[a]=i;
    	ol[b]=i;
	}
	for(int i=1;i<=n;i++){
		int a,b;
		cin>>a>>b;
		ne[a]=i;
		ne[b]=i;
	}
    if(ne==ol){
        cout<<0< 
 
I：智乃的密码 
 这题本质是个尺取（好多人说叫双指针，我感觉可能尺取更顺口一点？），尺取的特点就是我在一串数中维护某一段，而这一段随着左右端点的变化其答案的变化是有规律的，例如：我可以不必每次移动左端点时都将右端点回溯到左端点的右边第一个，而是可以直接通过规律找到直接计算答案增量的办法，这题就很典型，为什么wa5：tnnd，看错题目了，题目说至少3种，我以为必须三种，而且这样理解样例居然也是对的，我不管，样例的锅。。。。。
 
尺取思路：首先，我这个区间的长度肯定要符合题意，所以我左端点先不动，右端点右移，一旦我找到了一个至少包含种3个符号的区间时，我的右端点还有没有必要向后继续移动呢？肯定是不需要的，因为后面的区间一定满足至少包含3种符号这个条件，直接计算即可，那我的左端点下一步难道要向右移动一位再把右端点拉回来吗？也不用，我们每次移动左端点时检测至少三种符号这个条件是否成立如果仍然成立依旧可以套用公式直接计算，这样就做到了右端点不回退，O(n)解决。
 
#include 
using namespace std;
#define int long long
#define ll long long

int fun(int a,int b,int c,int d){
    int cnt=0;
    if(a!=0){
        cnt++;
    }
    if(b!=0){
        cnt++;
    }
    if(c!=0){
        cnt++;
    }
    if(d!=0){
        cnt++;
    }
    return cnt;
}

signed main(){
    int n,l,r;
    cin>>n>>l>>r;
    string a;
    cin>>a;
    int cnt1=0,cnt2=0,cnt3=0,cnt4=0;
    int le=0,re=-1;
    int ans=0;
    for(int i=0;i='A'&&a[i]<='Z'){
            cnt1++;
        }else if(a[i]>='a'&&a[i]<='z'){
            cnt2++;
        }else if(a[i]>='0'&&a[i]<='9'){
            cnt3++;
        }else{
            cnt4++;
        }
        re++;
        while(fun(cnt1,cnt2,cnt3,cnt4)>=3&&re-le+1>=l){
            if(fun(cnt1,cnt2,cnt3,cnt4)>=3&&re-le+1>=l&&re-le+1<=r){
                ans+=min(n-re,r-(re-le));
            }
            if(a[le]>='A'&&a[le]<='Z'){
                cnt1--;
            }else if(a[le]>='a'&&a[le]<='z'){
                cnt2--;
            }else if(a[le]>='0'&&a[le]<='9'){
                cnt3--;
            }else{
                cnt4--;
            }
            le++;
        }
    }
    while(re-le+1>=l){
        if(a[le]>='A'&&a[le]<='Z'){
            cnt1--;
        }else if(a[le]>='a'&&a[le]<='z'){
            cnt2--;
        }else if(a[le]>='0'&&a[le]<='9'){
            cnt3--;
        }else{
            cnt4--;
        }
        le++;
        if(fun(cnt1,cnt2,cnt3,cnt4)>=3&&re-le+1>=l&&re-le+1<=r){
            ans+=min(n-re,r-(re-le));
        }
    }
    cout<
 
 
L：智乃的数据库 
 
 
 
 这题面又贼长，其实就是给你介绍这个group by语句，没学过数据库的可能要理解一会，其实group by就是把后面跟着的字段拼起来作为一整个关键字进行统计，算出每个关键字对应的记录条数，知道这个这题就是个水题了，我们直接照做就行，把关键字拼起来其实就是搞一个vector作为key值，然后用map统计数量就可以了，只是字符串处理可能对小白来说有点困难（说实话我第一个想到的居然是用正则表达式。。。。）
 
#include 
using namespace std;
#define visit _visit
#define pb push_back
#define int long long
#define ll long long

int x[1010][1010];
mappos;
map,int>ans;
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i>a;
        pos[a]=i;
    }
    for(int i=0;i>x[i][j];
        }
    }
    getchar();
    string a;
    getline(cin,a);
    a=a.substr(36);
    string tem="";
    vectorp;
    for(int i=0;it;
    for(int i=0;i 
总结：这把难度有所提高，比较考验阅读理解能力，还是老问题，wa得太多了，春节期间要特训一下一次过的能力了，呜呜呜，下一场就在年后了，这期间该cf上上分了，芜湖。