泉州一中2023SCP第二轮模拟赛

A.幸运数(lucky)

考试暴力80pts

• 正解：
  线性筛

#include
using namespace std;
int n;
int prime[100001];
bool visit[100001];
int dp[100001];
void Prime() {
    visit[1]=visit[0]=1;
    for (int i=2; i<=100001; i++) {
        if (!visit[i]) {
            prime[++prime[0]] = i;
        }
        for (int j=1; j<=prime[0] && i*prime[j]<=100001; j++) {
            visit[i*prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}
void pprime() {
    dp[1]=dp[0]=1;
    for (int i=2; i<=100001; i++) {
        if(!visit[i])
            dp[i]=1;
        for (int j=1; j<=prime[0] && i*prime[j]>n;
    Prime();
    pprime();
    for(int i=4;i<=n;i++)
    if(!visit[dp[i]])
    cout<<i<<"\n";
    return 0;
}

---

B.字符串展开(expand)

没有从0开始，80pts

• 正解：

模拟

#include
using namespace std;
int m;
string s;
inline void work(char a,char b) {
    for(char c=a; c>s;
    m=s.size();
    int i=0;
    while(i=m-2)
            cout<<s[i];
        else

            if(s[i+1]!='-')
                cout<<s[i];
            else {
                if('0'<=s[i+2] && s[i+2]<='9' && '0'<=s[i] && s[i]<='9' && s[i]<s[i+2]) {
                    work(s[i],s[i+2]);
                    i++;
                } else {
                    if('a'<=s[i+2] && s[i+2]<='z' && 'a'<=s[i] && s[i]<='z' && s[i]<s[i+2]) {
                        work(s[i],s[i+2]);
                        i++;
                    } else
                        cout<<s[i];
                }
            }
        i++;
    }
    return 0;
}

---

C.懒羊羊吃草(number)

优先队列模板
100pts

#include
using namespace std;
int n;
char a;
long long k;
priority_queue<long long,vector,greater > q;
int main() {
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    while(n--) {
        cin>>a;
        if(a=='i') {
            cin>>k;
            q.push(k);
        } else {
            cout<<q.top()<<"\n";
            q.pop();
        }
    }
    return 0;
}

---

D.方格稿纸(paint)

考试写错一行，5pts

• 正解:
  前缀和

#include
using namespace std;
int n,m;
int mp[301][301];
int sum[301][301];
int ans;
int main() {
    freopen("paint.in","r",stdin);
    freopen("paint.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            scanf("%d",&mp[i][j]);
    for(int i=1; i<=n; i++)
        for(int j=1; j=2; k--)
        for(int i=1; i+k-1<=n; i++)
            for(int j=1; j+k-1<=m; j++)
                if(abs((sum[i+k-1][j+k-1]-sum[i+k-1][j-1]-sum[i-1][j+k-1]+sum[i-1][j-1])-k*k+(sum[i+k-1][j+k-1]-sum[i+k-1][j-1]-sum[i-1][j+k-1]+sum[i-1][j-1]))<=1)
                    ans++;
    printf("%d",ans);
    return 0;
}

---

E.矩阵取数游戏(game)

广搜67pts

• 正解：
  区间dp

#include
using namespace std;
long long n,m,dp[101][101],Max,b[101],a[1001],Ans;
int main(){
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    cin>>n>>m;
    b[0]=1;
    for(int i=1;i<=m;i++){
        b[i]=b[i-1]*2;
    }
    while(n--){
        for(int i=1;i>a[i];
        Max=0;
        for(int i=1;i=i;j--){
                dp[i][j]=max(dp[i][j+1]+a[j+1]*b[m-j+i-1],dp[i-1][j]+a[i-1]*b[m-j+i-1]);
            }
            dp[i][i]+=a[i]*b[m];
            if(dp[i][i]>Max)Max=dp[i][i];
        }
        Ans+=Max;
    }cout<<Ans;
    return 0;
}