SMU Summer 2024 Contest Round 3

A.Hcode OnlineJudge

 先用欧拉筛把质数预处理出来，然后枚举左端点的质数，只需要询问右端点是不是质数并取差值的min就行了

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll; 
typedef pair<int, int> PII; 
const int N = 1e6+10;
int n,m,k;vector<int>pri;
bool su[10005];void get(){for(int i=2;i<=10000;i++){if(!su[i]) pri.push_back(i);for(auto ed:pri){if(i*ed>10005) break;su[ed*i]=1;if(i%ed==0) {break;}}}
}void sovle(){get();while(scanf("%d",&n)!=EOF){int ans1=0,ans2=0,num=1000000;for(auto ed:pri){if(!su[abs(n-ed)]){int vd=abs(n-ed);if(abs(ed-vd)<num){num=abs(ed-vd);ans1=min(ed,vd);ans2=max(ed,vd);}}}cout<<ans1<<" "<<ans2<<endl;}
}signed main()
{	//ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); int t = 1; //cin>>t;while (t --){sovle();}return 0;
}

B.Hcode OnlineJudge

 随便模拟一下就找到规律了（被多组数据狠狠教育了

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll; 
typedef pair<int, int> PII; 
const int N = 1e6+10;
int n,m,k;void sovle(){while(scanf("%d %d",&n,&m)){if(!n&&!m) return;cout<<n+m-2<<endl;}
}signed main()
{	ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); int t = 1; //cin>>t;while (t --){sovle();}return 0;
}

C.Hcode OnlineJudge

 要使疲劳度最小，必然要找k组相邻的最小差值对，考虑n方的dp，i，j表示前i个物品取k对，注意考虑怎么初始化

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll; 
typedef pair<int, int> PII; 
const int N = 1e6+10;
const int inf = 0x3f3f3f3f;
int n,m,k;int f(int x,int y){return (x-y)*(x-y);
}void sovle(){while(cin>>n>>k){int a[n+1];for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);int dp[n+1][k+1];for(int i=0;i<=n;i++){for(int j=0;j<=k;j++){if(i==0||j==0) dp[i][j]=0;else dp[i][j]=inf;}}for(int i=2;i<=n;i++){for(int j=1;j*2<=i&&j<=k;j++){dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+f(a[i-1],a[i]));}}cout<<dp[n][k]<<endl;}
}signed main()
{	ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); int t = 1; //cin>>t;while (t --){sovle();}return 0;
}

D.Hcode OnlineJudge

水题

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll; 
typedef pair<int, int> PII; 
const int N = 1e6+10;
int n,m,k;void sovle(){int sum=0;cin>>n;vector<int>a(n);for(int i=0;i<n;i++) {cin>>a[i];if(a[i]>10) sum+=a[i]-10;}cout<<sum<<endl;
}signed main()
{	ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); int t = 1; //cin>>t;while (t --){sovle();}return 0;
}

F.Hcode OnlineJudge

对于每组，只有取左边或者右边，等同于对左边，取或者不取。数据范围很小，二进制枚举秒了

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll; 
typedef pair<int, int> PII; 
const int N = 1e6+10;
int n,m,k;void sovle(){cin>>n>>m;vector<int>a(m),b(m);for(int i=0;i<m;i++) cin>>a[i]>>b[i];cin>>k;vector<int>c(k),d(k);int max1=-1;for(int i=0;i<k;i++) cin>>c[i]>>d[i];for(int i=0;i<(1<<k);i++){map<int,int>v,x;for(int j=0;j<k;j++){if((i>>j)&1){v[c[j]]=1;}else{v[d[j]]=1;}}int sum=0;for(int i=0;i<m;i++){if(v[a[i]]&&v[b[i]]){sum++;}}max1=max(max1,sum);}cout<<max1<<endl;
}signed main()
{	ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); int t = 1; //cin>>t;while (t --){sovle();}return 0;
}

I.Hcode OnlineJudge

 给一个小于1e18的正整数，询问能否通过删除最少的位数让该数被3整除。类似的，二进制枚举当前位数删或者不删

#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll; 
typedef pair<int, int> PII; 
const int N = 1e6+10;
int n,m,k;void sovle(){string s;cin>>s;int n=s.size();int num=-1;for(int i=0;i<(1<<n);i++){map<int,int>v;for(int j=0;j<n;j++){if((i>>j)&1){v[j]=1;}}int u=0;int x=1;int sum=0;for(int i=n-1;i>=0;i--){if(v[n-1-i]) {sum++;continue;}u+=x*(s[i]-'0');x*=10;}if(u%3==0&&u){if(num==-1) num=sum;else num=min(sum,num);}}cout<<num<<endl;
}signed main()
{	ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); int t = 1; //cin>>t;while (t --){sovle();}return 0;
}