复兴提高班暑假作业
2025-08-15 12:32:07
发布于：上海
32阅读
0回复
0点赞
T1逃离迷宫2
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,fx,fy,p=INT_MAX;
int mp[15][15];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool vis[15][15];
void dfs(int x,int y,int s){
if(x==fx&&y==fy){
p=min(p,s);
return;
}
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<1||nx>n||ny<1||ny>m) continue;
if(vis[nx][ny]==1) continue;
if(mp[nx][ny]==1) continue;
vis[nx][ny]=true;
dfs(nx,ny,s+1);
vis[nx][ny]=false;
}
}
int main(){
cin>>n>>m;
sx=1; sy=1;
fx=n; fy=m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c;
cin>>c;
if(i==1&&j==1||i==n&&j==m){
if(c=='#'){
cout<<-1<<endl;
return 0;
}
}
if(c=='#') mp[i][j]=1;
}
}
vis[sx][sy]=true;
dfs(sx,sy,0);
if(p==INT_MAX) cout<<-1<<endl;
else cout<<p<<endl;
return 0;
}
T2细胞
#include<bits/stdc++.h>
#define N 1009
using namespace std;
char g[N][N];
bool vis[N][N];
int n,m;
int dx[4]={-1, 1, 0, 0};
int dy[4]={0, 0, -1, 1};
void dfs(int x,int y){
if(x<0||x>=n||y<0||y>=m||g[x][y]=='0'||vis[x][y]){
return;
}
vis[x][y]=true;
for(int i=0;i<4;i++){
dfs(x+dx[i],y+dy[i]);
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>g[i][j];
}
}
int cnt=0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] != '0' && !vis[i][j]) {
dfs(i,j);
cnt++;
}
}
}
cout<<cnt<<endl;
return 0;
}
T3充满希望的拼接质数2
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int x){
if(x<2) return 0;
for(int i=2;i*i<=x;i++){
if(x%i==0) return 0;
}
return 1;
}
int n,a[19],cnt=0;
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
for(int k=1;k<(1<<n);k++){
int sum=0;
bool flag=0;
for(int i=0;i<n;i++){
if(k&(1<<i)){
if(i>0&&a[i]==a[i-1]&&!(k&(1<<(i-1)))){
flag=1;
break;
}
sum+=a[i];
}
}
if(!flag&&isPrime(sum)) cnt++;
}
cout<<cnt<<endl;
return 0;
}
T4充满希望的拼接质数1
#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
int nums[20];
bool isPrime(int x){
if(x==0 or x==1) return false;
for(int i=2;i<=sqrt(x);i++){
if(x%i==0) return false;
}
return true;
}
void dfs(int level,int energy){
if(level==n){
if(isPrime(energy)) ans++;
return;
}
dfs(level+1,energy+nums[level+1]);
dfs(level+1,energy);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>nums[i];
}
sort(nums+1,nums+n+1);
dfs(0,0);
cout<<ans;
}
T5海战
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt=0;
char Map[5001][5001];
bool vis[5001][5001];
int x_move[4]={1,0,-1,0},y_move[4]={0,1,0,-1};
struct node{
int x,y;
};
bool check(node next){
return next.x>=1&&next.x<=n&&next.y>=1&&next.y<=m;
}
void bfs(node s){
queue<node> q;
q.push(s);
vis[s.x][s.y]=1;
while(!q.empty()){
node f=q.front();
q.pop();
for(int i=0;i<4;i++){
node next;
next.x=f.x+x_move[i],next.y=f.y+y_move[i];
if(check(next)&&!vis[next.x][next.y]&&Map[next.x][next.y]!='0'){
q.push(next);
vis[next.x][next.y]=1;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>Map[i][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(Map[i][j]!='0'&&!vis[i][j]){
bfs({i,j});
cnt++;
}
}
}
cout<<cnt;
return 0;
}
T6迷路的小猫
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
bool st[N];
int d[N];
void bfs(int sx,int sy){
queue<int>q;
q.push(sx);
st[sx] = true;
d[sx] = 0;
while(q.size()){
int u = q.front();
q.pop();
int t = u + 1;
if(t <= N && !st[t]){
q.push(t);
d[t] = d[u] + 1;
st[t] = true;
}
t = u - 1;
if(t >= 1 && !st[t]){
q.push(t);
d[t] = d[u] + 1;
st[t] = true;
}
t = u * 2;
if(t <= N && !st[t]){
q.push(t);
d[t] = d[u] + 1;
st[t] = true;
}
}
cout << d[sy];
}
int a,b;
int main() {
cin >> a >> b;
if(a > b){
cout << a - b;
return 0;
}
bfs(a,b);
return 0;
}
T7卡牌
#include <bits/stdc++.h>
using namespace std;
int n, a[200005], b[200005];
long long m;
bool check(int mid){
long long ans = 0;
for(int i = 1; i <= n; i ++){
if(mid - a[i] <= b[i]){
ans += max(mid - a[i], 0);
}else{
return 0;
}
}
return ans <= m;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++) cin >> b[i];
long long l = 1, r = 4e5 + 5, ans = 0;
while(l <= r){
long long mid = l + r >> 1;
if(check(mid)){
l = mid + 1;
ans = mid;
}else{
r = mid - 1;
}
}
cout << ans;
return 0;
}
T8小试牛刀
#include <bits/stdc++.h>
using namespace std;
vector<int> g[150];
int main(){
int n,m,x;
cin>>n>>m;
while(m--){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
cin>>x;
vector<int> dist(n+1,-1);
queue<int> q;
dist[x]=0;
q.push(x);
while(!q.empty()){
auto u=q.front();
q.pop();
for(auto v:g[u]){
if(dist[v]==-1){
dist[v]=dist[u]+1;
q.push(v);
}
}
}
for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
return 0;
}
T9鱼缸
#include <bits/stdc++.h>
using namespace std;
long long n, m, a[200005], l = 1, r, mid, sum, ans, ll = 0;
bool check(int mid){
for(int i = 1; i <= n; i ++) sum += max(ll, mid - a[i]);
return sum <= m;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) { cin >> a[i]; r = max(a[i], r); }
r += m;
while(l <= r){
mid = l + r >> 1;
sum = 0;
if(check(mid)){
ans = mid;
l = mid + 1;
}else{
r = mid - 1;
}
}
cout << ans;
return 0;
}
T10神庙迷宫1
#include <bits/stdc++.h>
using namespace std;
int n, m, dirx[4] = {1, -1, 0, 0}, diry[4] = {0, 0, 1, -1}, vis[45][45];
char a[45][45], p;
void dfs(int x, int y){
if(x == n && y == m){
p = 1;
return;
}
for(int i = 0; i < 4; i ++){
int xx = x + dirx[i], yy = y + diry[i];
if(xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy] || a[xx][yy] == '#') continue;
vis[xx][yy] = 1;
dfs(xx, yy);
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
cin >> a[i][j];
vis[1][1] = 1;
dfs(1, 1);
if(p) cout << "YES";
else cout << "NO";
return 0;
}
T11逆序对
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+7;
long long ans;
int n;
int b[N],a[N];
void mergesort(int l,int r){
if(l==r) return ;
int mid=(l+r)>>1;
mergesort(l,mid);
mergesort(mid+1,r);
int i=l,j=mid+1,cnt=0;
while(i<=mid&&j<=r){
if(a[i]<=a[j]) b[cnt++]=a[i++];
else b[cnt++]=a[j++],ans+=(mid-i+1);
}
while(i<=mid) b[cnt++]=a[i++];
while(j<=r) b[cnt++]=a[j++];
for(int i=l,j=0;i<=r;i++,j++) a[i]=b[j];
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
mergesort(0,n-1);
cout<<ans<<endl;
return 0;
}
T12网络连接
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
typedef long long ll;
struct op{
int k;
ll c;
vector<int>v;
};
int f[N];
int find(int x){
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
bool cmp(op i,op j){
return i.c<j.c;
}
int main(){
int n,m;
cin>>n>>m;
vector<op>ops(m);
for(int i=0;i<m;i++){
cin>>ops[i].k>>ops[i].c;
ops[i].v.resize(ops[i].k);
for(int j=0;j<ops[i].k;j++)
cin>>ops[i].v[j];
}
sort(ops.begin(),ops.end(),cmp);
for(int i=1;i<=n;i++)f[i]=i;
ll tot=0;
int cnt=0;
for(auto o:ops){
if(cnt==n-1)break;
int firstRoot=find(o.v[0]);
for(int j=1;j<o.k;j++){
int cur=find(o.v[j]);
if(firstRoot!=cur){
f[cur]=firstRoot;
tot+=o.c;
cnt++;
if(cnt==n-1)break;
}
}
}
if(cnt!=n-1)cout<<-1<<endl;
else cout<<tot<<endl;
return 0;
}
T13程序自动分析
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
struct node{
int i,j,e;
}s[N];
int f[N];
bool cmp(node a,node b){
return a.e>b.e;
}
int find(int x){
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void solve(){
int n;
cin>>n;
map<int,int> mp;
int l=0;
for(int i=1;i<=n;i++){
int x,y,z;
cin>>x>>y>>z;
if(!mp.count(x)) mp[x]=++l;
if(!mp.count(y)) mp[y]=++l;
s[i]={mp[x],mp[y],z};
}
sort(s****+n+1,cmp);
for(int i=1;i<=l;i++) f[i]=i;
for(int i=1;i<=n;i++){
if(s[i].e==1) f[find(s[i].i)]=find(s[i].j);
else if(find(s[i].i)==find(s[i].j)){
cout<<"NO\n";
return;
}
}
cout<<"YES\n";
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
T14修学分
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+5;
typedef long long ll;
ll n,p,l,t;
ll d;
bool check(ll mid){
ll sum=min(2*mid,d)*t+mid*l;
return sum>=p;
}
int main(){
cin>>n>>p>>l>>t;
d=(n+6)/7;
ll x=1,y=n,ans=0;
while(x<=y){
ll mid=x+y>>1;
if(check(mid)){
ans=mid;
y=mid-1;
}else{
x=mid+1;
}
}
cout<<n-ans;
return 0;
}
T15跳石头
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+7;
typedef long long ll;
ll L,n,m;
ll a[N];
bool check(ll x){
ll cnt=0;
int j=0;
for(int i=1;i<=n+1;i++){
if(a[i]-j<x)cnt++;
else j=a[i];
}
return cnt<=m;
}
int main(){
cin>>L>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
a[n+1]=L;
ll l=2e9+7,r=L;
for(ll i=1;i<=n+1;i++){
l=min(l,a[i]-a[i-1]);
}
while(l+1<r){
ll mid =l+(r-l)/2;
if(check(mid)){
l=mid;
}else{
r=mid;
}
}
cout<<l<<endl;
return 0;
}
T16暴躁的病人
#include <bits/stdc++.h>
using namespace std;
int n, m, a[1000005], l = 1, r, mid, ans;
bool check(int mid){
int x = a[1], sum = 1;
for(int i = 2; i <= m; i ++){
int y = lower_bound(a + 1, a + n + 1, x + mid) - a;
if(y <= n) sum ++;
else break;
x = a[y];
}
return sum >= m;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + n + 1); r = a[n] - a[1];
while(l <= r){
mid = l + r >> 1;
if(check(mid)){
ans = mid;
l = mid + 1;
}else r = mid - 1;
}
cout << ans;
return 0;
}
T17礼物盒子
#include<bits/stdc++.h>
using namespace std;
int n,ans;
bool check(int x){
int k=x;
while(x>=3){
k+=x/3;
int a=x/3;
x=x%3+a;
}
return k>=n;
}
int main(){
cin>>n;
int l=0,r=n;
int mid;
while(l<=r){
mid=(l+r)/2;
if(check(mid)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
cout<<ans;
return 0;
}
T18逃离迷宫计数
#include <bits/stdc++.h>
using namespace std;
int n, m;
int maze[10][10];
bool visited[10][10];
int paths;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
void dfs(int x, int y) {
if (x == n-1 && y == m-1) {
paths++;
return;
}
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !maze[nx][ny] && !visited[nx][ny]) {
dfs(nx, ny);
}
}
visited[x][y] = false;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c;
cin >> c;
maze[i][j] = (c == '#');
}
}
dfs(0, 0);
cout << paths;
return 0;
}
T19桥
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>graph;
vector<int>dfn,low;
vector<bool>vis;
int n,m,u,v,ans,timer;
void dfs(int u,int pa=0) {
vis[u]=1;
dfn[u]=low[u]=++timer;
for (auto v:graph[u]) {
if(v!=pa){
if(vis[v])low[u]=min(low[u],dfn[v]);
else{
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])ans++;
}
}
}
}
int main() {
cin>>n>>m;
graph.resize(n+1);
dfn.resize(n+1);
low.resize(n+1);
vis.resize(n+1,0);
while(m--){
cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
}
for(int i=1;i<=n;i++)if(!vis[i])dfs(i);
cout<<ans;
return 0;
}
T20朋友 1
#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[200009];
int s[200009];
int get(int x){
if(f[x]==x)return x;
return f[x]=get(f[x]);
}
void merge(int x,int y){
f[get(x)]=get(y);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=1,a,b;i<=m;i++){
cin>>a>>b;
merge(a,b);
}
for(int i=1;i<=n;i++){
s[get(i)]++;
}
int mx=-1e9;
for(int i=1;i<=n;i++){
mx=max(mx,s[i]);
}
cout<<mx;
return 0;
}
有帮助，赞一个