B题，很简单的一道思维题，但是当时读错题导致看了好久，审题还应该仔细啊；
J题，给一个数，让找另外一个数和给的数相乘不是某个数的平方的倍数，根据题意这个数是几个素数的乘积，我们只要找到这些素数，在找另外一个不和这些素数相同的素数就可以；
代码：
#include<bits/stdc++.h> using namespace std; vector<int>p; int isp(int n) { int l=sqrt(n); if(n==2||n==1)return 1; for(int i=2;i<=l;i++) { if(n%i==0)return 0; } return 1; } int a[100005]; int find(int n) { int l=p.size(); if(l==0)return 0; for(int i=0;i<l;i++) { if(p[i]==n)return 1; } return 0; } int main() { for(int i=2;i<100002;i++) { a[i]=isp(i); } int n; cin>>n; int l=sqrt(n); for(int i=2;i<=l;i++) { if(n%i==0){ p.push_back(i); p.push_back(n/i); } } for(int i=2;i<n;i++) { if(a[i]==1&&find(i)==0) { cout<<i; break; } } }
E题，给一个数字，让找最小的钱数，钱的面值是由10的倍数（包括一）组成的，问最少可以交换多少张钱币数，
有两种方式找钱，一种是直接给比如5元就给5个1元的，还有就是给比它大一面值的在找钱，比如8，给一张10元的，找2张1元的；
当时一个队友说了思路我写出来但是过不了qwq，找了好多例子都可以但是还是不行就放弃了，
#include<bits/stdc++.h> using namespace std; int main() { string s; cin>>s; int ans=0; int l=s.length(); int flag=0; for(int i=0;i<l;i++) { if(s[i]-‘0‘<5) { if(flag==1)ans++; ans+=s[i]-‘0‘; flag=0; } else { // if(flag==0&&s[i]==‘5‘&&s[i-1]!=‘5‘)flag=0; // else flag=1; if(i==l-1||s[i+1]<‘5‘) { ans+=10-s[i]+‘0‘; // cout<<ans<<endl; } else ans+=10-s[i]+‘0‘-1; } } if(flag==1)ans++; cout<<ans; }
看题解是用dp做的，找递推式 dp[i+1][0]=min(dp[i][0]+s[i]-‘0‘,dp[i][1]+10-s[i]+‘0‘) dp[i+1][1]=min(dp[i][0]+s[i]-‘0‘+1,dp[i][1]+10-s[i]+‘0‘-1)
说实话当时根本没想到这题可以用dp做，也没想用dp；
代码：
#include<iostream> #include<cstring> using namespace std; int dp[10005][2]; int main(){ char s[10005]; scanf("%s",s); dp[0][1]=1; dp[0][0]=0; for(int i=0;i<strlen(s);i++){ dp[i+1][0]=min(dp[i][0]+s[i]-‘0‘,dp[i][1]+10-s[i]+‘0‘); dp[i+1][1]=min(dp[i][0]+s[i]-‘0‘+1,dp[i][1]+10-s[i]+‘0‘-1); } printf("%d",dp[strlen(s)][0]); return 0; }
Benelux Algorithm Programming Contest 2019 解题与补题报告
原文：https://www.cnblogs.com/Kingstar1/p/12573537.html