C 70%

#include<bits/stdc++.h>
using namespace std;
int fj(int x)//数位分解
{
while(x!=0)
{
int t=x%10;
if(t==7) return 0;
x/=10;
}
return 1;
}
int p(int x)//判断x这个数能不能报
{
if(fj(x)==0) return 0;//含不含有7
else//如果不含7的话 它是不是含7的数的倍数
{
for(int i=1; i*i<=x; i++)//分解因数
{
if(x%i==0)// i是x的因数 那么x/i也是x的因数
{
if(fj(i)==0||fj(x/i)==0)
{
return 0;
}
}

}
}
return 1;
}
int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
{
int a;
cin>>a;
if(p(a)==0) cout<<-1<<endl;
else
{
while(1)
{
a++;
if(p(a)==1)
{
cout<<a<<endl;
break;
}
}
}
}
return 0;
}

C 100%

#include<bits/stdc++.h>
using namespace std;
int book[10000010];//book[i]=0表示这个数字合法 否则不合法
int ans[10000010];//ans[i]表示i之后第一个满足条件的数
bool check(int x)//x这个数中有7时 返回1 否则返回0
{
while(x!=0)
{
if(x%10==7) return 1;
x/=10;
}
return 0;//如果到最后也没找到7 才会return 0
}
int main()
{
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
for(int i=1;i<=10000000;i++)
{
if(book[i]) continue;//如果i已经被标记过了 就不用再标记它的倍数
if(check(i))//如果i里含有7
{
for(int j=1;i*j<=10000000;j++)//枚举i的倍数
{
book[i*j]=1;
//标记i的倍数为不合法
}
}
}
int last=10000001;//10000001满足条件 所以答案最多为它
for(int i=10000000;i>=1;i--)//预处理i之后第一个满足条件的数
{
ans[i]=last;
if(book[i]==0) last=i;
}
int t;
cin>>t;
while(t--)
{
int x;
scanf("%d",&x);
if(book[x]) printf("-1\n");
else printf("%d\n",ans[x]);
}
return 0;
}
/*
思路：
从 1 开始枚举到 10^7，判断其是否合法
若不合法，筛除它从 1 到 10^7间的所有倍数
若它已被标记（筛除）直接跳过 不用再去找它的倍数
因为如果一个数被枚举到时已经被标记 就说明有更小的含7的数字是它的因数
那么它的倍数也一定是更小的数字的倍数 已经被筛过了
接下来还需要处理每个数字下一个满足条件的数 如果现场去book数组中找会超时
处理时 从后往前枚举 记录last为离它最近的满足条件的数即可
*/

D

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int a[110][110],minn[110][110];
//a数组记录每个格子的颜色
//minn记录当前搜索到的到达这个格子需要花费的最少金币
void dfs(int x,int y,int cost,int ma)
//cost记录当前花费的金币数量 ma记录现在能否用魔法 因为不能连续用
{
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int tx,ty;
if(cost>=minn[x][y]) return;//如果走到这个格子时花费的金币比以前搜到的还多 直接返回
if(cost<minn[x][y]) minn[x][y]=cost;
if(x==n&&y==n) return;//走到了终点 直接返回
for(int i=0;i<=3;i++)
{
tx=x+dx[i]; ty=y+dy[i];
if(tx<1||ty<1||tx>n||ty>n) continue;//如果下一步越界
if(a[tx][ty]==a[x][y]) dfs(tx,ty,cost,1);//如果两个格子颜色相同 不需要花费金币
else if(a[tx][ty]==0&&ma)//如果下一个格子无色 且魔法可以用
{
a[tx][ty]=a[x][y];//如果要变颜色 肯定是变成和当前格子一样的颜色收益最大
//因为如果变成不同的颜色 走到那个格子去还要一个金币
dfs(tx,ty,cost+2,0);//ma=0表示此时魔法不能用了
a[tx][ty]=0;//回溯之后要把更改的格子颜色重新变回无色
}
else if(a[tx][ty]!=0) dfs(tx,ty,cost+1,1);
//注意不能直接写else 因为如果下一个格子无色且ma=0 就不能走
//这里表示下一个格子颜色不同的情况
}
}
/*
总结下来 走到下一个格子有三种情况
1：下一个格子和这个格子颜色相同 cost不变
2：下一个格子和这个格子颜色不同 cost+1
3：下一个格子无色 如果此时能用魔法 就把颜色改变为和当前格子相同 cost+2
*/

int main()
{
freopen("chess.in","r",stdin);
freopen("chess.out","w",stdout);
scanf("%d%d",&n,&m);
//在搜索前 把到每个结点的最小花费置为极大值
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) minn[i][j]=99999999;
for(int i=1;i<=m;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
if(c==0) a[x][y]=2;//红色用2表示 无色用0表示
else a[x][y]=1;//黄色用1表示
}
dfs(1,1,0,1);
if(minn[n][n]==99999999) printf("-1");
//如果不能走到n n这个点 最小花费就还是极大值
else printf("%d",minn[n][n]);
return 0;
}