每日一题5.29

495684945

2023 ccpc 秦皇岛 区域赛

比赛榜单

第五题 F快银

XinyuLin

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int inf = 0x3f3f3f3f3f3f3f3f;
bool is_prime(int x)
{
    for (int i = 2; i * i <= x; i ++ )
    {
        if (x % i == 0) return false;
    }
    return true;
};

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    vector<vector<int>> dp(n + 1, vector<int>(4, inf));
    dp[1][0] = 0, dp[1][1] = dp[1][2] = dp[1][3] = 1;
    for (int i = 1; i < n; i ++ )
    {
        if (is_prime(a[i] + a[i + 1])) dp[i + 1][0] = min(dp[i + 1][0], dp[i][0]);
        if (is_prime(a[i] + 1)) dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + 1);
        if (a[i] & 1) dp[i + 1][2] = min(dp[i + 1][2], dp[i][0] + 1);
        else dp[i + 1][3] = min(dp[i + 1][3], dp[i][0] + 1);

        // a[i]变为1
        if (is_prime(1 + a[i + 1])) dp[i + 1][0] = min(dp[i + 1][0], dp[i][1]);
        dp[i + 1][2] = min(dp[i + 1][2], dp[i][1] + 1);
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1);

        // a[i]变为偶数
        if (a[i + 1] & 1) dp[i + 1][0] = min(dp[i + 1][0], dp[i][2]);
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][2] + 1);
        dp[i + 1][3] = min(dp[i + 1][3], dp[i][2] + 1);

        // a[i]变为非1奇数
        if (a[i + 1] % 2 == 0) dp[i + 1][0] = min(dp[i + 1][0], dp[i][3]);
        dp[i + 1][2] = min(dp[i + 1][2], dp[i][3] + 1);
    }
    cout << min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]}) << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    
	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

495684945

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;
int is_prime(int x){
	for(int i=2;i<=x/i;i++){
		if(x%i==0)return 0;
	}
	return 1;
}
void solve(){
	int n;
	cin>>n;
	vector f(n+10,vector<int>(5,1e18));//0不修改 1改1 2改偶 3改奇
	vector<int>a(n+10);
	for(int i=1;i<=n;i++)cin>>a[i];
	f[1][1]=f[1][2]=f[1][3]=1,f[1][0]=0;
	if(a[1]==1)f[1][1]=0;//本来就是1还改啥
	for(int i=1;i<=n;i++){
		//对0转移  第i位不修改
		if(a[i]%2==0){//是偶数
			f[i][0]=min(f[i][0],f[i-1][3]);//前面改奇一定存在可以为质数
			if(is_prime(a[i]+a[i-1])){//前面不改看看能不能行
				f[i][0]=min(f[i][0],f[i-1][0]);
			}
			if(is_prime(a[i]+1)){//前面改1看看能不能行
				f[i][0]=min(f[i][0],f[i-1][1]);
			}
		}else{//是奇数
			f[i][0]=min(f[i][0],f[i-1][2]);//前面改偶一定存在可以为质数
			if(is_prime(a[i]+a[i-1])){//前面不改看看能不能行
				f[i][0]=min(f[i][0],f[i-1][0]);
			}
			if(a[i]==1){//当前是1,前面改1,为2没问题
				f[i][0]=min(f[i][0],f[i-1][1]);
			}
		}
		//对1转移  第i位改1 前面可以为1和偶数和不改
		f[i][1]=min(f[i][1],f[i-1][1]+1);//前面为1，后面为1肯定可以
		f[i][1]=min(f[i][1],f[i-1][2]+1);//前面改偶数,一定存在一个改法可以
		if(is_prime(a[i-1]+1)){//当前改1看看能不能行
			f[i][1]=min(f[i][1],f[i-1][0]+1);
		}
		//对2转移 第i位改偶   前面可以为1和奇数和不改
		f[i][2]=min(f[i][2],f[i-1][1]+1);//前面为1，后面改偶一定存在一个改法可以
		f[i][2]=min(f[i][2],f[i-1][3]+1);//前面改奇数,一定存在一个改法可以
		if(a[i-1]%2==1){//前面不改,只有前面为奇数后面改偶才一定存在一个改法
			f[i][2]=min(f[i][2],f[i-1][0]+1);
		}
		//对3转移 第i位改奇 前面可以改偶和不改
		f[i][3]=min(f[i][3],f[i-1][2]+1);//前面改偶数,一定存在一个改法可以
		if(a[i-1]%2==0){//前面不改,只有前面为偶数后面改奇才一定存在一个改法
			f[i][3]=min(f[i][3],f[i-1][0]+1);
		}
	}
	cout<<min({f[n][0],f[n][1],f[n][2],f[n][3]})<<endl;
}

signed main(){
	int t=1;ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//	cin>>t;
	while(t--)solve();
	return 0;
}

Fengyj

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
const int INF = 1e9;
bool isp(int x)
{
    if (x < 2)
        return 0;
    for (int i = 2; i <= x / i; i++)
    {
        if (x % i == 0)
            return 0;
    }
    return 1;
}

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    vector<array<int, 4>> dp(n + 1, {INF, INF, INF, INF});
    dp[1][0] = 0;
    dp[1][1] = 1;
    dp[1][2] = 1;
    dp[1][3] = 1;
    for (int i = 1; i < n; i++){

        // case1
        if (isp(a[i + 1] + a[i]))
        {
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][0]);
        }
        if(isp(a[i+1]+1)){
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][1]);
        }
        if(a[i+1]&1){
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][2]);
        }
        if(a[i+1]%2==0){
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][3]);
        }

        //case2
        if(isp(a[i]+1)){
            dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + 1);
        }
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1);
        dp[i + 1][1] = min(dp[i + 1][1], dp[i][2] + 1);

        //case3
        if(a[i]&1)
            dp[i + 1][2] = min(dp[i + 1][2], dp[i][0] + 1);
        dp[i + 1][2] = min(dp[i + 1][2], dp[i][1] + 1);
        dp[i + 1][2] = min(dp[i + 1][2], dp[i][3] + 1);

        //case4
        if(a[i]%2==0){
            dp[i + 1][3] = min(dp[i + 1][3], dp[i][0] + 1);
        }
        dp[i + 1][3] = min(dp[i + 1][3], dp[i][2] + 1);
    }
    int ans = 1e9;
    for (int i = 0; i < 4;i++){
        ans = min(dp[n][i], ans);
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}