1.珠心算测验
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e4+39+7;
int mp[N],n,a[N],ans=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i]!=a[j]){
mp[a[i]+a[j]]=1;
}
}
}
for(int i=1;i<=n;i++){
if(mp[a[i]]){
ans++;
}
}
cout<<ans;
return 0;
}
解题思路：
用一个哈希表统计和即可
2.比例简化
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int gcd(int a,int b){
if(!b)return a;
return gcd(b,a%b);
}
int a,b,l,ans1,ans2;
int main(){
cin>>a>>b>>l;
ans1=l;
ans2=1;
for(int i=1;i<=l;i++){
for(int j=1;j<=l;j++){
if(gcd(i,j)==1){
if(i*b>=a*j&&ans1*j>=ans2*i){
ans1=i;
ans2=j;
}
}
}
}
cout<<ans1<<' '<<ans2;
return 0;
}
解题思路：
判断i，j是否互质，且比值大于等于a/b即可
注意事项：
1.由于c++中实数操作可能会丢失精度，所以要把a/b>c/d换成a*d>b*c
3.螺旋矩阵
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,x,y;
int dfs(int n,int x,int y){
if(x==1)return y;
if(y==n)return n+x-1;
if(y==1)return 4*n-2-x;
if(x==n)return 3*n-y-1;
return dfs(n-2,x-1,y-1)+4*(n-1);
}
int main(){
cin>>n>>x>>y;
cout<<dfs(n,x,y);
return 0;
}
解题思路：
由矩阵可以看出，分5种情况：第一种，x=1，直接返回y
第二种，x=n，可以找到规律，是3n-y-1
第三种，y=1，可以找到规律，是4n-x-2
第四种，y=n，可以找到规律，是n+x-1
第五种,在中心，返回dfs(n-2,x-1,y-1)+4(n+1)，向内递进一层
最终可以得出答案
4.子矩阵
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 39+7;
int n,m,r,c,a[N],num[N][N],sol=1e9,w[N],g[N][N],dp[N][N];
void init(){
for(int i=1;i<=m;i++){
w[i]=0;
for(int j=1;j<r;j++)w[i]+=abs(num[a[j]][i]-num[a[j+1]][i]);
}
for(int i=1;i<=m;i++){
for(int j=i+1;j<=m;j++){
g[i][j]=0;
for(int k=1;k<=r;k++){
g[i][j]+=abs(num[a[k]][i]-num[a[k]][j]);
}
}
}
}
int dpp(){
memset(dp,0x7f,sizeof(dp));
dp[0][0]=0;
for(int k=1;k<=c;k++){
for(int i=k;i<=m;i++){
for(int j=k-1;j<i;j++){
dp[i][k]=min(dp[i][k],dp[j][k-1]+w[i]+g[j][i]);
}
}
}
int ans=dp[c][c];
for(int i=c+1;i<=m;i++)ans=min(ans,dp[i][c]);
return ans;
}
void dfs(int tr){
if(tr>r){
init();
sol=min(sol,dpp());
return;
}
for(int i=a[tr-1]+1;i<=n;i++){
a[tr]=i;
dfs(tr+1);
}
}
int main(){
cin>>n>>m>>r>>c;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>num[i][j];
}
}
dfs(1);
cout<<sol;
return 0;
}
解题思路：
暴力枚举行的组合是C(n,r)，在使用dp去计算列的最小值，每次取最小值即可,时间复杂度是O(C(n,r)*m3)