当前位置: 首页 > news >正文

2025 --【J+S 二十连测】-- 第二套 总结

总结

T1 T2 T3

很快就写出来了,没什么大问题。

T4 T5

没有写出来,下来有个非常巧妙的思路。

题解

T1

我们只需要横纵坐标最小的,最大的那些点。然后把它们全部照在一起,那就可以了。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
signed main()
{freopen("lab.in","r",stdin);freopen("lab.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n;cin>>n;int maxx=-inf,maxy=-inf,minx=inf,miny=inf;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;maxx=max(maxx,x),maxy=max(maxy,y);minx=min(minx,x),miny=min(miny,y);}cout<<minx-1<<' '<<miny-1<<endl<<maxx+1<<' '<<maxy+1;return 0;
}

T2

直接照题意模拟即可。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=105;
char a[maxn][maxn];
string s;
int n,m,ans=0,vis[maxn][maxn];
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
// 下 右 上 左 右下 左下 右上 左上
bool in(int x,int y)
{return x>=1&&x<=n&&y>=1&&y<=m;
}
void dfs(int x,int y,int step,int f,int lf)
{vis[x][y]=1;if(step==(int)s.size()-1){ans++;vis[x][y]=0;return;}for(int i=0;i<8;i++){int tx=x+dx[i],ty=y+dy[i];if(f==-1||i==f){if(in(tx,ty)&&s[step+1]==a[tx][ty]&&!vis[tx][ty]) dfs(tx,ty,step+1,i,lf);}else if(lf!=-1) continue;else if(s[step+1]==a[tx][ty]&&!vis[tx][ty]){f++,i++;if(f==1&&(i==2||i==4)) dfs(tx,ty,step+1,i-1,f-1);if(f==2&&(i==1||i==3)) dfs(tx,ty,step+1,i-1,f-1);if(f==3&&(i==2||i==4)) dfs(tx,ty,step+1,i-1,f-1);if(f==4&&(i==1||i==3)) dfs(tx,ty,step+1,i-1,f-1);if(f==5&&(i==6||i==7)) dfs(tx,ty,step+1,i-1,f-1);if(f==6&&(i==5||i==8)) dfs(tx,ty,step+1,i-1,f-1);if(f==7&&(i==5||i==8)) dfs(tx,ty,step+1,i-1,f-1);if(f==8&&(i==6||i==7)) dfs(tx,ty,step+1,i-1,f-1);f--,i--;}}vis[x][y]=0;
}
signed main()
{freopen("treasure.in","r",stdin);freopen("treasure.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>s>>n>>m;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]==s[0]) dfs(i,j,0,-1,-1);cout<<ans;return 0;
}

T3

不难发现是一个周期问题先发掘他是在第几位,然后去一个一个找即可。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=2e5+5;
char a[maxn];
int b[maxn],cnt;
signed main()
{freopen("song.in","r",stdin);freopen("song.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);string s;cin>>s;int x;cin>>x;x++;for(int i=0;i<s.size();i++){a[++cnt]=s[i];while(isdigit(s[i+1])) i++,b[cnt]=b[cnt]*10+(s[i]-'0');b[cnt]+=b[cnt-1];}int sy=(x-1)%b[cnt]+1;for(int i=1;i<=cnt;i++){if(b[i]>=sy){cout<<a[i];return 0;}}return 0;
}

T4

不难发现,我们。把B从大到小排序,这样子做一定是最优的。

排完序之后,我们考虑DP。

\(dp_{i,j}\) 表示前 \(i\) 个人。其中一个已经分过去的人的 \(a\) 和是 \(j\) 时,答案是几

那么方程为:

\[dp_{i,j}=\min(\max(j+b_i,f_{i-1,j}),\max(s_i-j+b_i,f_{i-1,j})) \]

转移即可

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=500005;
int dp[maxn];
struct node
{int a,b;
}a[maxn];
bool cmp(node a,node b)
{return a.b>b.b;
}
signed main()
{freopen("meal.in","r",stdin);freopen("meal.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,sum=0;cin>>n;for(int i=1;i<=n;i++) cin>>a[i].a>>a[i].b;sort(a+1,a+1+n,cmp);memset(dp,0x3f,sizeof(dp));dp[0]=0;for(int i=1;i<=n;i++){sum+=a[i].a;for(int j=sum;j>=0;j--){dp[j]=max(dp[j],sum-j+a[i].b);if(j>=a[i].a) dp[j]=min(dp[j],max(j+a[i].b,dp[j-a[i].a]));}}int ans=inf;for(int i=0;i<=sum;i++) ans=min(ans,dp[i]);cout<<ans;return 0;
}

T5

不难发觉,在二进制上的某一位有一个一的情况下,那么这些在这一位唯一的数肯定不能在同一个集合。

但是这样并不好转移,所以我们考虑正难则反假设他们必须在同一个集合。

而对于集合里面的东西,我们可以用并查集来维护。答案就是 \(2^{并查集联通块个数}\)

最后利用容器把答案累加即可。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=500+5,mod=998244353;
struct UFS
{int fa[maxn],n;void init(int len){n=len;for(int i=1;i<=n;i++) fa[i]=i;}int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]); }void merge(int u,int v){u=get(u),v=get(v);if(u!=v) fa[v]=u;}
}ufs;
int kasumi(int a,int b)
{int ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}
int a[maxn];
signed main()
{freopen("partition.in","r",stdin);freopen("partition.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,d = 0,ans=0;cin>>n;for(int i=1;i<=n;i++) cin>>a[i],d|=a[i];for(int j=0;j<(1<<15);j++){if((d&j)!=j) continue;ufs.init(n);for(int i=0;i<=14;i++){if(!(j&(1<<i))) continue;int now=0;for(int k=1;k<=n;k++){if(a[k]&(1<<i)){if(!now) now=k;ufs.merge(k,now);}}}int sum=0;for(int i=1;i<=n;i++) if(ufs.fa[i]==i) sum++;if(__builtin_popcount(j)%2==0) ans=(ans+kasumi(2,sum))%mod;else ans=(ans-kasumi(2,sum)+mod)%mod;}cout<<ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=25075

相关文章:

  • 2025 蒸发器厂家最新企业品牌推荐排行榜,江苏纵横携手知名品牌,彰显蒸发器公司行业影响力
  • 题解:Luogu P11976 [KTSC 2021] 通信网络 / communication
  • 弦振动方程
  • 理论构建尝试整理
  • 2025聚合硫酸铁厂家最新企业品牌推荐排行榜,工业聚合硫酸铁,混凝剂聚合硫酸铁,固态聚合硫酸铁,粉末聚合硫酸铁,硫酸亚铁公司推荐!
  • 2025成型机厂家最新企业品牌推荐排行榜,冷弯成型机,卷帘门成型机,卷闸门成型机,彩钢瓦成型机,货架成型机推荐!
  • 2025 年 PP 管厂家最新推荐榜:甄选 pp 风管,PP 喷淋塔,pp 洗涤塔,pp 通风管道优质公司!
  • 解密并下载受DRM保护的MPD(DASH流媒体)加密视频 - 教程
  • 在PyCharm中运行 wandb.login();
  • 机器学习科学家分享技术写作艺术
  • AT VP 记录
  • rpm安装
  • 关于主体性介枚枚介的讨究
  • 2025索道厂家最新企业品牌推荐排行榜,城市交通索道,旅游索道,滑雪索道,单人固定抱索器拖牵索道,固定抱索器吊篮式索道公司推荐
  • 无向图三元环计数 小记
  • Python语法基础篇(含有类型转换、拷贝、可变对象/不可变对象,函数,拆包,异常,模块,闭包,装饰器)
  • 2025 年探伤仪厂家最新企业品牌推荐排行榜,涡流探伤仪,超声波探伤仪,管材探伤仪,焊缝探伤仪,无损探伤仪推荐这十家公司!
  • 2025 年建筑工程施工总包最新推荐排行榜,以严格质量管控彰显行业实力推荐这十家公司!
  • 与斐波那契数列相关的对换题目 CF553B Kyoya and Permutation
  • wpf .net 8 使用mvvm指南
  • office办公软件
  • 2025.10.4训练记录
  • st表 + 变形的djs (好题
  • 2025年微信小程序开发:AR/VR与电商的最新案例 - 指南
  • 10.5
  • 在wpf .net 8项目中使用materialDesign 4 以上版本的的注意事项
  • 学习STC51单片机26(芯片为STC89C52RCRC) - 实践
  • 洛谷P14120 题解 - lemon
  • cf41d
  • 33 ACwing 294 Count The Repetitions 题解