wwh

$\color{red}nb$

T1

欧拉筛+一点DP
\color{white}cyh没写出来

#include <bits/stdc++.h>
using namespace std;
int prime[100001],cnt=0,st[100001];
int num[100001];
int main()
{
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    int n;
    cin >> n;
    st[0]=st[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) 
        {
            prime[++cnt]=i;
            num[i]=1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
        {
            st[i*prime[j]]=1;
            num[i*prime[j]]=num[i]+num[prime[j]];
            if(i % prime[j] == 0) break;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(st[num[i]] == 0)
        {
            printf("%d\n",i);
        }
    }
    return 0;
}

T2

水模拟

T3

优先队列，常州的时候打过来

T4

nmd n,m打炸了！
二维前缀和

#include <bits/stdc++.h>
using namespace std;
int n,m,a[501][501];
int black[501][501],white[501][501];
int main()
{
    freopen("paint.in","r",stdin);
    freopen("paint.out","w",stdout);
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin >> a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            black[i][j]+=black[i-1][j]+black[i][j-1]-black[i-1][j-1];
            if(a[i][j] == 1) black[i][j] += 1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            white[i][j]+=white[i-1][j]+white[i][j-1]-white[i-1][j-1];
            if(a[i][j] == 0) white[i][j] += 1;
        }
    }
    int cnt=0;
    for(int i=1;i<=max(n,m);i++)
    {
        for(int j=1;j<=max(n,m);j++)
        {
            for(int a=1;a<=max(n,m);a++)
            {
                int x1=i,y1=j;
                int x2=i+a,y2=j+a;
                if(x2 <= n&&y2 <= m)
                {
                    int b=black[x2][y2]-black[x2][y1-1]-black[x1-1][y2]+black[x1-1][y1-1];
                    int w=white[x2][y2]-white[x2][y1-1]-white[x1-1][y2]+white[x1-1][y1-1];
                    //cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << b << " " << w << endl;
                    if(abs(b-w) <= 1) cnt++;
                }
            }
        }
    }
    cout << cnt;
    return 0;
}

T5

区间DP
每一行分开处理
dp[i][j]为i-j这个区间中可以得到的最大分数

#include <bits/stdc++.h>
using namespace std;
long long n,m,a[50][50],p[50];
long long dp[50][50];
long long ans;
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin >> a[i][j];
        }
    }
    p[1]=2;
    for(int i=2;i<=m;i++) p[i]=p[i-1]*2;
    for(int k=1;k<=n;k++)
    {
        long long maxn=0;
        memset(dp,0,sizeof dp);
        for(int i=1;i<=m;i++)
        {
            for(int j=m;j>=i;j--)
            {
                dp[i][j]=max(dp[i-1][j]+a[k][i-1]*p[m-j+i-1],dp[i][j+1]+a[k][j+1]*p[m-j+i-1]);
            }
            dp[i][i]+=a[k][i]*p[m];
            maxn=max(maxn,dp[i][i]);
        }
        ans+=maxn;
    }
    cout << ans;
    return 0;
}