题解 | #雾之湖的冰精#
A.
C.
D.
E.
F.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
if(a+b<=9)
printf("Yes\n");
else
printf("No\n");
}
B.
二分查找小于x的最大位置
#include<bits/stdc++.h>
using namespace std;
int find(int *a,int start,int end,int tar)
{
if(start>end)
return -1;
int mid=(start+end)/2;
if(a[mid]<=tar)
return max(mid,find(a,mid+1,end,tar));
else
return find(a,start,mid-1,tar);
}
int main()
{
int n,x;
cin>>n>>x;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
int ans=find(a,0,n-1,x);
cout<<ans+1<<" ";
int use=ans==-1?0:a[ans];
cout<<x-use<<endl;
}
C.
如果结果一位，x*10取模和结果求和取模为0，如果结果2位，x*10取模和结果求和取模为0.结果至多三位。
#include<bits/stdc++.h>
using namespace std;
long long f(int len,long long x)
{
for(int i=0;i<len;i++)
{
x=(x*10)%495;
}
int t=(495-x)%495;
if(len==1)
{
if(t>=0&&t<=9)
return t;
else
return -1;
}
else if(len==2)
{
if(t>=10&&t<=99)
return t;
else
return -1;
}
else
return t;
}
int main()
{
long long x;
cin>>x;
x%=495;
if(x==0)
cout<<"-1\n";
else
{
int ans;
for(int i=1;i<10;i++)
{
if(f(i,x)!=-1)
{
ans=f(i,x);
break;
}
}
cout<<ans<<endl;
}
}
输出首位字符较大者。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
string s;
cin>>s;
if(s[0]>=s[n-1])
cout<<s[0]<<endl;
else
cout<<s[n-1]<<endl;
}
bfs求最短路，只是给每一个位置加上方向
#include<bits/stdc++.h>
using namespace std;
struct Node{
int x,y,f;
Node(int xx,int yy,int ff)
{
x=xx;
y=yy;
f=ff;
}
};
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
string s[n];
for(int i=0;i<n;i++)
cin>>s[i];
int x1,y1,x2,y2;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(s[i][j]=='S')
{
x1=i;
y1=j;
}
if(s[i][j]=='T')
{
x2=i;
y2=j;
}
}
}
int get[n][m][4]; //0,1,2,3 上下左右
memset(get,-1,sizeof get);
queue<Node> qu;
for(int i=0;i<4;i++)
{
get[x1][y1][i]=0;
qu.push(Node(x1,y1,i));
}
while(!qu.empty())
{
int x=qu.front().x;
int y=qu.front().y;
int f=qu.front().f;
//printf("%d %d %d\n",x,y,f);
qu.pop();
if(s[x][y]=='*')
{
if(f==0)
{
if(x&&s[x-1][y]!='#'&&(get[x-1][y][f]==-1||get[x-1][y][f]>get[x][y][f]+1))
{
qu.push(Node(x-1,y,f));
get[x-1][y][f]=get[x][y][f]+1;
}
if(y&&s[x][y-1]!='#'&&(get[x][y-1][2]==-1||get[x][y-1][2]>get[x][y][f]+1))
{
qu.push(Node(x,y-1,2));
get[x][y-1][2]=get[x][y][f]+1;
}
if(y+1<m&&s[x][y+1]!='#'&&(get[x][y+1][3]==-1||get[x][y+1][3]>get[x][y][f]+1))
{
qu.push(Node(x,y+1,3));
get[x][y+1][3]=get[x][y][f]+1;
}
}
else if(f==1)
{
if(x+1<n&&s[x+1][y]!='#'&&(get[x+1][y][f]==-1||get[x+1][y][f]>get[x][y][f]+1))
{
qu.push(Node(x+1,y,f));
get[x+1][y][f]=get[x][y][f]+1;
}
if(y&&s[x][y-1]!='#'&&(get[x][y-1][2]==-1||get[x][y-1][2]>get[x][y][f]+1))
{
qu.push(Node(x,y-1,2));
get[x][y-1][2]=get[x][y][f]+1;
}
if(y+1<m&&s[x][y+1]!='#'&&(get[x][y+1][3]==-1||get[x][y+1][3]>get[x][y][f]+1))
{
qu.push(Node(x,y+1,3));
get[x][y+1][3]=get[x][y][f]+1;
}
}
else if(f==2)
{
if(x&&s[x-1][y]!='#'&&(get[x-1][y][0]==-1||get[x-1][y][0]>get[x][y][f]+1))
{
qu.push(Node(x-1,y,0));
get[x-1][y][0]=get[x][y][f]+1;
}
if(x+1<n&&s[x+1][y]!='#'&&(get[x+1][y][1]==-1||get[x+1][y][1]>get[x][y][f]+1))
{
qu.push(Node(x+1,y,1));
get[x+1][y][1]=get[x][y][f]+1;
}
if(y&&s[x][y-1]!='#'&&(get[x][y-1][2]==-1||get[x][y-1][2]>get[x][y][f]+1))
{
qu.push(Node(x,y-1,2));
get[x][y-1][2]=get[x][y][f]+1;
}
}
else
{
if(x&&s[x-1][y]!='#'&&(get[x-1][y][0]==-1||get[x-1][y][0]>get[x][y][f]+1))
{
qu.push(Node(x-1,y,0));
get[x-1][y][0]=get[x][y][f]+1;
}
if(x+1<n&&s[x+1][y]!='#'&&(get[x+1][y][1]==-1||get[x+1][y][1]>get[x][y][f]+1))
{
qu.push(Node(x+1,y,1));
get[x+1][y][1]=get[x][y][f]+1;
}
if(y+1<m&&s[x][y+1]!='#'&&(get[x][y+1][f]==-1||get[x][y+1][f]>get[x][y][f]+1))
{
qu.push(Node(x,y+1,f));
get[x][y+1][f]=get[x][y][f]+1;
}
}
}
else
{
if(f==0)
{
if(x&&s[x-1][y]!='#'&&(get[x-1][y][f]==-1||get[x-1][y][f]>get[x][y][f]+1))
{
qu.push(Node(x-1,y,f));
get[x-1][y][f]=get[x][y][f]+1;
}
}
else if(f==1)
{
if(x+1<n&&s[x+1][y]!='#'&&(get[x+1][y][f]==-1||get[x+1][y][f]>get[x][y][f]+1))
{
qu.push(Node(x+1,y,f));
get[x+1][y][f]=get[x][y][f]+1;
}
}
else if(f==2)
{
if(y&&s[x][y-1]!='#'&&(get[x][y-1][f]==-1||get[x][y-1][f]>get[x][y][f]+1))
{
qu.push(Node(x,y-1,f));
get[x][y-1][f]=get[x][y][f]+1;
}
}
else
{
if(y+1<m&&s[x][y+1]!='#'&&(get[x][y+1][f]==-1||get[x][y+1][f]>get[x][y][f]+1))
{
qu.push(Node(x,y+1,f));
get[x][y+1][f]=get[x][y][f]+1;
}
}
}
}
/*
printf("0:\n");
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
printf("%d ",get[i][j][0]);
printf("\n");
}
printf("1:\n");
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
printf("%d ",get[i][j][1]);
printf("\n");
}
printf("2:\n");
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
printf("%d ",get[i][j][2]);
printf("\n");
}
printf("3:\n");
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
printf("%d ",get[i][j][3]);
printf("\n");
}
*/
int ans=1e9;
for(int i=0;i<4;i++)
{
if(get[x2][y2][i]!=-1)
ans=min(ans,get[x2][y2][i]);
}
ans=ans==1e9?-1:ans;
cout<<ans<<endl;
}
}
F.
抛弃最多就是用最少的灵魂位与结果为0，记dp[ i ] [ j ]表示考虑第i个灵魂，位与结果位j，需要用到的最少灵魂数量。 则dp[ i ] [ j &a[ i ] ] =min(dp[ i - 1 ] [ j & a[ i ] ] , dp[ i - 1 ] [ j ]+1)。初始化dp[ 0 ] [ i ] =n*2, dp[ 0 ] [255] = 0 。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int ans[256],last[256];
for(int i=0;i<256;i++)
last[i]=n*2;
last[255]=0;
for(int i=0;i<n;i++)
{
memcpy(ans,last,sizeof ans);
for(int j=0;j<256;j++)
{
if(last[j]!=n*2)
{
int x=(j&a[i]);
ans[x]=min(ans[x],last[j]+1);
}
}
//printf("--%d",ans[0]);
memcpy(last,ans,sizeof ans);
}
if(ans[0]==n*2)
printf("-1\n");
else
printf("%d\n",n-ans[0]);
}
}
查看6道真题和解析
投递金山WPS等公司10个岗位 >
