赛前集训DAY2

342->500
有参照标程的以下都直接放标程

T1

埃式筛

#include<bits/stdc++.h>
using namespace std;
int pre[100005],t[100005],n;
bool vis[100005],mpp[100005];
inline void prime(int n){
    int p=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            pre[p]=i;
            mpp[i]=true;
            p++;
            for(int j=1;j<=n/i;j++){
                vis[j*i]=true;
                int q=i*j;
                while(q%i==0){
                    t[i*j]++;
                    q/=i;
                }
            }
        }
        else{
            continue;
        }
    }
}
int main(){
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    prime(100000);
    for(int i=4;i<=n;i++){
        if(mpp[t[i]]==true){
            cout<<i<<endl;
        }
    }
    return 0;
}

T2

签到题，然而没看到字符限制导致乱码
以下标程

#include <cstdio>
#include <cstring>
using namespace std;
char s[210];
int n;

bool check(int x)
{
    if (x == 1 || x == n || s[x] != &#039;-&#039;) return 0;
    if (s[x - 1] >= &#039;a&#039; && s[x - 1] <= &#039;z&#039; && s[x + 1] >= &#039;a&#039; && s[x + 1] <= &#039;z&#039; && s[x - 1] < s[x + 1]) return 1;
    if (s[x - 1] >= &#039;0&#039; && s[x - 1] <= &#039;9&#039; && s[x + 1] >= &#039;0&#039; && s[x + 1] <= &#039;9&#039; && s[x - 1] < s[x + 1]) return 1;
    return 0;
}

int main()
{
    freopen("expand.in", "r", stdin);
    freopen("expand.out", "w", stdout);
    scanf("%s", s + 1); n = strlen(s + 1);
    for(int i = 1; i <= n; i++)
        if (check(i))
            for(int j = s[i - 1] + 1; j < s[i + 1]; j++) putchar(j);
        else putchar(s[i]);
    puts("");
    return 0;
}

T3

优先队列，记得scanf或者快读优化

#include<bits/stdc++.h>
using namespace std;
#define ll int
struct cmp{
    bool operator()(const ll &a,const ll &b){
        return a>b;
    }
};
priority_queue<ll,vector<ll>,cmp> q;
int main(){
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    ll n,k;
    char s[5];
    scanf("%d",&n);
    for(ll i=1;i<=n;i++){
        scanf("%s",s);
        if(s[0]==&#039;i&#039;){
            scanf("%d",&k);
            q.push(k);
        }
        else{
            printf("%d\n",q.top());
            q.pop();
        }
    }
    return 0;
}

T4

二维前缀和
以下标程

#include<bits/stdc++.h>
using namespace std;
int n,m,a[305][305],ans;
int main()
{
    freopen("paint.in","r",stdin);
    freopen("paint.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            a[i][j]+=a[i][j-1]+(a[i-1][j]-a[i-1][j-1]);
        }
    }
    for(int k=2;k<=min(n,m);k++){
        int c=k*k;
        for(int i=0;i<=n-k;i++){
            for(int j=0;j<=m-k;j++){
                if(abs(2*(a[i+k][j+k]-a[i+k][j]-a[i][j+k]+a[i][j])-c)<=1){
                    ans++;
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

T5

区间DP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[35],dp[35][35],b[35],n,m,maxx,ans;
ll pw(ll p,ll q){
    ll re=1;
    while(q){
        if(q&1) re*=p;
        q>>=1;
        p*=p;
    }
    return re;
}
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    b[0]=1;
    for(ll i=1;i<=m;i++){
        b[i]=2*b[i-1];
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>a[j];
        }
        maxx=-1;
        for(ll j=1;j<=m;j++){
            for(ll k=m;k>=j;k--){
                dp[j][k]=max(dp[j][k+1]+a[k+1]*b[m-k+j-1],dp[j-1][k]+a[j-1]*b[m-k+j-1]);
            }
            dp[j][j]+=a[j]*b[m];
            maxx=max(maxx,dp[j][j]);
        }
        ans+=maxx;
    }
    cout<<ans;
    return 0;
}

总结

如果CSP-J也这么简单……