遗留问题
2025-07-31 09:45:21
发布于：河北
128阅读
0回复
0点赞
报名指导网站
// 所有同学中选择任意个同学
// n ≤12
// 2^12 = 4096
// 但他希望他最终收到的撤硕使用费用之和是一个质数
// 质数 除了1和他本身以外 不能被其他数整除
#include<bits/stdc++.h>
using namespace std;
// O(sqrt(x))
int a[20],ans,n;
int isprime[12001];
void is_prime(){
//埃氏筛法
// 质数 2 4 6 8 10
isprime[1] = 1;
for(int i=2;i<=12000;i++){
if(isprime[i]==0){
// 2i 3i 4i 5i
for(int j=i+i;j<=12000;j+=i){
isprime[j] = 1;//不是质数
}
}
}
}
// 01枚举 DFS
// u枚举到的同学 sum花费
// 4096 * sqrt(12000)
void dfs(int u,int sum){
if(u == n+1){
if(isprime[sum]==0)ans++;
return;
}
// 不上
dfs(u****um);
// 上
dfs(u****um+a[u]);
}
int main(){
is_prime();
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,0);
cout<<ans;
return 0;
}
连通块
#include<bits/stdc++.h>
using namespace std;
char g[50][50];
bool vis[50][50];//有没有被染色
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int n,m;
struct node{
int x, y;
};
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>g[i][j];
queue<node> q;
vis[1][1] = 1;
q.push({1,1});
while(q.size()){
node u = q.front();//获得队头
q.pop();
//扩散 4 个方向
// u.x u.y
for(int i=0;i<4;i++){
int nx = u.x + dx[i];
int ny = u.y + dy[i];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && g[nx][ny]!='#' && !vis[nx][ny]){
vis[nx][ny] = true;
q.push({nx,ny});
}
}
}
// 是否存在一条从左上角到右下角的可行路径
if(vis[n][m])cout<<"YES";
else cout<<"NO";
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,cat;
int d[100001];//从起点 n 到达 i 这个点的最短路径
int main(){
cin>>n>>cat;
for(int i=1;i<=100000;i++)d[i] = 1e9;
queue<int> q;
q.push(n);
d[n] = 0;
while(q.size()){
int u = q.front();
q.pop();
//+1 -1 *2
if(u+1<=100000 && d[u+1]==1e9){
d[u+1] = d[u] + 1;
q.push(u+1);
}
if(u-1>=0 && d[u-1]==1e9){
d[u-1] = d[u] + 1;
q.push(u-1);
}
if(u*2<=100000 && d[2*u]==1e9){
d[2*u] = d[u] + 1;
q.push(2*u);
}
}
cout<<d[cat];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
char g[1010][1010]; // 1e8
bool vis[1010][1010];
struct node{
int x,y;
};
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int n,m;
bool check(int nx,int ny){
if(nx>=1 && nx<=n && ny>=1 && ny<=m && g[nx][ny]!='0' && !vis[nx][ny])return true;
return false;
}
void bfs(int x,int y){
vis[x][y] = true;
queue<node> q;
q.push({x,y});
while(q.size()){
node u = q.front();
q.pop();
for(int i=0;i<4;i++){
int nx = u.x+dx[i];
int ny = u.y+dy[i];
if(check(nx,ny)){
vis[nx][ny]=true;
q.push({nx,ny});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>g[i][j];
int ans = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!vis[i][j]){
bfs(i,j);
ans++;
}
}
}
cout<<ans;
return 0;
}
八皇后
#include<bits/stdc++.h>
using namespace std;
int n;
bool board[110][110];
vector<int> path;
vector<vector<int> > ans;
bool check(int x,int y){
for(int i=1;i<x;i++){
if(board[i][y]) return false;
if(x-i>=1 && board[x-i][y-i]) return false;
if(x-i>=1 && board[x-i][y+i]) return false;
}
return true;
}
void dfs(int now){
if(now==n+1){
ans.push_back(path);
return ;
}
for(int i=1;i<=n;i++){
if(check(now,i)){
board[now][i]=true;
path.push_back(i);
dfs(now+1);
board[now][i]=false;
path.pop_back();
}
}
}
int main(){
cin>>n;
dfs(1);
for(int i=0;i<3;i++){
for(int j=0;j<ans[i].size();j++){
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
cout<<ans.size();
return 0;
}
第三题
#include <bits/stdc++.h>
using namespace std;
long long a[10010],tot;
// 从0年0月0日 - y年m月d日，总共的天数
long long day(int y,int m,int d){
long long ans = 0;
//年算完了
for(int i=0;i<y;i++){
ans+=tot;
if(i%4==0)ans++;
}
//月算完了
for(int i=1;i<m;i++){
ans+=a[i];
}
ans+=d;
return ans;
}
int main(){
freopen ("ccc.in", "r", stdin);
freopen ("ccc.out", "w", stdout);
int t;
cin >> t;
while (t--){
int n;
cin >> n;
tot = 0;
for(int i=1;i<=n;i++){
cin>>a[i];
tot+=a[i];
}
int yb,mb,db,yc,mc,dc;
cin>>yb>>mb>>db>>yc>>mc>>dc;
long long ans = day(yc,mc,dc) - day(yb,mb,db) + 1;
cout<<ans<<endl;
}
fclose (stdin);
fclose (stdout);
return 0;
}
遗留问题
#include<bits/stdc++.h>
using namespace std;
char a[1105][1105];
struct node{
int x, y;
};
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int main(){
freopen("explore.in", "r", stdin);
freopen("explore.out", "w", stdout);
int t;
cin>>t;
while(t--){
int n,m,k,x,y,d;
cin>>n>>m>>k>>x>>y>>d;//行 列 机器人走路次数 机器人下标(x,y) 机器人初始的方向
//d=0 东 d=1 南 d=2 西 d=3 北
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
int ans = 1;
a[x][y] = '#';
while(k--){
int nx = x + dx[d];
int ny = y + dy[d];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]=='.'){
a[nx][ny] = '#';
x = nx;
y = ny;
ans++;
}else{
d = (d+1)%4;
}
}
cout<<ans<<endl;
}
fclose(stdin);
fclose(stdout);
}
有帮助，赞一个