9/4 经典dp+线性筛求质数+混合背包

今天打了3场比赛，收获挺多，注意补题，感谢队友帮我debug，哈哈哈哈。看到之前很少写过的题目，对能力提升帮助挺大，果然和队友一起训练效果好。
1.今天还在力扣上写出了一道简单dp题，还是蛮开心的。
2.还是可惜csdn上做得太差了，那个D题我竟然没想到可以向上枚举，算一个巨大的失误。
3.百度之星那道欧拉筛的题目一下就写出来了，积累才是最有用的。但是那个统计字符的题没写出来，想的思路太暴力了，导致超时。不然能出两道，感觉就很不错了。
4.感觉很多题目都有种熟悉感，悲哀的是无法ac……痛苦ing
4.之后要多打比赛，尽管打的不好，但这是一个能力提高的过程，然乎就是坚持下来。
5.开学第一天，舍友还是总打游戏，很吵，别呆在宿舍，晚上晚点回。

B. Making Towers

本题其实不像dp，但要记录上一次相同颜色色块所出现的位置。只有相同色块位置差值为奇数时，才可累加高度

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=1e5+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n,a[N],dp[N],h[N];
bool vis[N];

void solve()
{
    cin>>n;
    for(int i=0;i<=n;i++)
        a[i]=dp[i]=h[i]=vis[i]=0;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        if(!vis[a[i]])
        {
            h[a[i]]=1;vis[a[i]]=1;dp[a[i]]=i;
        }
        else
        {
            if((i-dp[a[i]])%2)
            {
                h[a[i]]++;dp[a[i]]=i;
            }
        }
    }
    for(int i=1;i<=n;i++)
        cout<<h[i]<<" ";
    cout<<endl;
}
signed main()
{
    //ios;
    int T;cin>>T;
    while(T--)
        solve();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

阿宁的质数

思路：
1.先使用素数筛预处理出2e5个素数。
2.在使用map记录数组a中出现过的素数，和预处理的数组进行比较，比对得到答案。

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e6+7;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n,q,a[N],p[N],ans[N],cnt;
bool vis[N];
map<int,int>mp;
void is_prime(int n)
{
    for(int i=2;i*i<=n;i++)
        if(!vis[i])
            for(int j=i*2;j<=n;j+=i)
                vis[j]=1;
    for(int i=2;i<=n;i++)
        if(!vis[i]) p[++cnt]=i;
}

void solve()
{
    is_prime(N);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int g=1;
    for(int i=1;i<=n;i++)
    {
        mp[a[i]]=1;
        while(mp[p[g]])
            g++;
        ans[i]=p[g];
    }
    while(q--)
    {
        int x;cin>>x;
        cout<<ans[x]<<endl;
    }
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

6169. 最长优雅子数组

class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int n=nums.size();
        int sum[n+5][35];
        memset(sum,0,sizeof sum);
        for(int i=0;i<n;i++)
        {
            for(int j=31;j>=0;j--)
            {
                if((nums[i]>>j&1)==1)
                    sum[i+1][j]=sum[i][j]+1;
                else sum[i+1][j]=sum[i][j];
            }
        }
        int ans=1,g=0;
        for(int i=1;i<=n;i++)
        {
            while(g<=i)
            {
                bool flag=1;
                if(g==i) 
                    break;
                for(int j=0;j<32;j++)
                {
                    if(sum[i][j]-sum[g][j]>1)
                    {
                        flag=0;break;
                    }
                }
                if(flag) break;
                g++;
            }
            ans=max(ans,i-g);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

混合背包

转化为01背包和完全背包

void solve()
{
    int num=1;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;cin>>v>>w>>s;
        if(s==0)
            a[num]=v,b[num]=w,c[num++]=0;
        else
        {
            if(s==-1) s=1;
            int k=1;
            while(s>=k)
            {
                a[num]=k*v,b[num]=k*w,c[num++]=1;
                s-=k;
                k<<=1;
            }
        }
        if(s)
            a[num]=s*v,b[num]=s*w,c[num++]=1;
    }
    for(int i=1;i<num;i++)
    {
        if(c[i]==0)
        {
            for(int j=a[i];j<=m;j++)
                f[j]=max(f[j-a[i]]+b[i],f[j]);
        }
        else
        {
            for(int j=m;j>=a[i];j--)
                f[j]=max(f[j-a[i]]+b[i],f[j]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

百度之星 03.字符计数

思路：若出现一个’#‘被访问两次，则说明会有一个联通块，即被包围的’*’号

好像百度之星补不了题，先放一篇大佬的ac代码，之后能提交的话再放自己a掉的代码。
https://matiji.net/exam/contest/adddetail?submissionId=1426997&matchId=57