首先声明一下我现在正在订正上周的题。。。

这是赛后订正的于是没有任何反思总结。。

听说这次的前四题都很水、。。

然而丁思源爸爸照样AK虐全场%%%%

T1：

不得不说，真滴水。。。

考虑贪心，首先是最多人，那么就是每只XX(复制不了？？)每次都只看见一个人，答案即为a+b

最少人的话就是每只XX都看见两个人，也就是max(a,b)

code:

#include<bits/stdc++.h>
using namespace std;
int a,b;
int main(){
    scanf("%d%d",&a,&b);
    printf("%d %d",max(a,b),a+b);
    return 0;
}

顺便说一下，以后我的代码会去掉freopen，以减少码量。。（懒死啦）

T2：

开个三个前缀和sa,sb,sc分别表示前i个数中ABC的数量，然后n^2枚举区间[l,r]判断

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll sa[1010],sb[1010],sc[1010],ans;
char s[1010];
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;i++){
        sa[i]=sa[i-1]+(s[i]=='A');
        sb[i]=sb[i-1]+(s[i]=='B');
        sc[i]=sc[i-1]+(s[i]=='C');
    }
    for(int l=1;l<=n;l++)
        for(int r=l;r<=n;r++)
            if(sa[r]-sa[l-1]==sb[r]-sb[l-1]&&sa[r]-sa[l-1]==sc[r]-sc[l-1]) ans++;
    printf("%lld",ans);
    return 0;
}

T3：

首先用筛法求出范围内的素数

接着枚举每个数，然后判断他的前后是否都是质数就好了

code:

#include<bits/stdc++.h>
using namespace std;
int p[1000010],l,r,ans;
void init(){
    p[0]=1;
    p[1]=1;
    for(int i=1;i<=sqrt(1000000);i++)
        if(!p[i]) for(int j=i*i;j<=1000000;j+=i) p[j]=1;
    return;
}
bool check(int x){
    for(int i=10;i<=1000000;i*=10)if((!p[x%i])&&(!p[x/i])) return true;
    return false;
}
int main(){
    scanf("%d%d",&l,&r);
    init();
    for(int i=l;i<=r;i++)if(check(i)) ans++;
    printf("%d",ans);
    return 0;
}

T4:

并查集的模板题，其实就是判断亲缘关系。。。

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a,b,fa[100010],n,m,k;
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        int fx=getfa(a),fy=getfa(b);
        fa[fx]=fy;
    }
    for(int i=1;i<=k;i++){
        scanf("%d%d",&a,&b);
        int fx=getfa(a),fy=getfa(b);
        if(fx==fy) puts("I am SB!")    ;
        else puts("Sweet!");
    }
    return 0;
}

T5:

设f[i][j]表示i阶sam数的末尾为j的方案数，然后就可以把所有的f[k][i]加起来就可以得到答案了。。

注意判断前导0。。。

貌似标算需要矩阵乘法。。。

然后还有DSY爸爸的玄学倍增。。。

code:

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll ans,f[1000010][10],k;
int main(){
    scanf("%lld",&k);
    for(int i=1;i<=9;i++)f[1][i]=1;
    if(k==1){puts("10");return 0;}
    for(ll i=2;i<=k;i++)
        for(int j=0;j<=9;j++)
            for(int ij=-2;ij<=2;ij++){
                if(j+ij<0) continue;
                if(j+ij>9) continue;
                f[i][j]=(f[i][j]+f[i-1][j+ij])%mod;
            }
    for(int i=0;i<=9;i++)ans=(f[k][i]+ans)%mod;
    printf("%lld",ans);
    return 0;
}

T6:

这题只打了60分的暴力。。。

设s[i][j]表示矩阵[1,1][i,j]的数值和，然后暴力枚举一切、、

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,b,a,d,c,x;
ll s[1010][1010],ans;
ll solve(int x1,int y1,int x2,int y2){
    ll ans=s[x2][y2];
    ans-=s[x2][y1-1];
    ans-=s[x1-1][y2];
    ans+=s[x1-1][y1-1];
    return ans;
}
int main(){
    scanf("%d%d%d%d%d%d",&m,&n,&b,&a,&d,&c);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d",&x);
            s[i][j]=s[i-1][j]+s[i][j-1]+x-s[i-1][j-1];
        }
    for(int x1=1;x1+a-1<=n;x1++)
        for(int y1=1;y1+b-1<=m;y1++){
            ll cnt=solve(x1,y1,x1+a-1,y1+b-1);
            for(int x2=x1+1;x2+c<x1+a;x2++)
                for(int y2=y1+1;y2+d<y1+b;y2++){
                    ll tot=solve(x2,y2,x2+c-1,y2+d-1);
                    ans=max(ans,cnt-tot);
                }
        }
    printf("%lld",ans);
    return 0;
}