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

思维题练习

本文选取题目源于此处,以及一些平时的好的思维题。

大体按照主观难度排序。

[FJCPC 2025] 构造大师贝贝

注意到 \(T\leq1000\),但是 \(n\leq10^{12}\)。那么从时间复杂度的角度考虑,应当为一个类似于 \(\mathcal O(T\log n)\) 的复杂度。

但是这道题的思维难度也就在这里了,将 \(n\) 变为完全平方数,每次加上约数 \(x\),很不好想到有什么带 log 的做法。

本题为 Special Judge,只需要输出任意一种构造方案。经过一些胡乱尝试猜测,想到也许可以想办法将 \(n\) 构造为形如 \(x^{2k}\) 的完全平方数。

那么考虑将其构造为 \(2^{2k}\),每次只需要加上 \(\operatorname{lowbit}(n)\) 即可,\(\operatorname{lowbit}(n)\) 定义同树状数组。

参考代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
ll lowbit(ll n){return n&-n;
}
bool check(ll n){ll x=sqrt(n);return x*x==n;
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){ll n;cin>>n;vector<ll>ans;while(!check(n)){ans.push_back(lowbit(n));n+=lowbit(n);}cout<<ans.size()<<'\n';for(ll i:ans){cout<<i<<' ';}if(ans.size()){cout<<'\n';}}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}

[GDCPC 2024] 图

从原图中找出 \(k=\left\lceil\dfrac m{n-1}\right\rceil\) 条两点之间的边不相交路径。

考虑将原图划分为 \(k\) 张图 \(T_1,T_2,\cdots,T_k\),每一张图维护一条路径。\(k\) 的值可以启发我们维护一棵类似于树的图,实际上 \(T_i\) 中有环是不优的,可以放到其他图上产生新的路径。

最终答案即找 \(u\sim v\) 的路径,使得 \(T_1,T_2,\cdots,T_k\) 中均连通。维护前缀连通,在 \(T_k\) 中随便找两个连通的点,在 \(T_1\sim T_{k-1}\) 中暴力 DFS 找即可。

但其实 \(T_i\) 应当是一棵森林。

详细题解参见此处。

参考代码
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=2e5,M=2e5,K=M;
int n,m;
//vector<int>g[N+1];
vector<vector<vector<int> > >tree;
int k;
struct dsu{vector<int>f,size;
//	int f[N+1],size[N+1];int find(int x){if(f[x]==x){return x;}return f[x]=find(f[x]);}void build(int n){f.resize(n+1);size.resize(n+1);for(int i=1;i<=n;i++){f[i]=i;size[i]=1;}}void merge(int x,int y){x=find(x),y=find(y);if(size[x]<size[y]){f[x]=y;size[y]+=size[x];}else{f[y]=x;size[x]+=size[y];}}
};
vector<dsu>dsu;
void resize(int n,int k){dsu.resize(k+1);for(int i=1;i<=k;i++){dsu[i].build(n+1);}tree.resize(k+1);for(int id=1;id<=k;id++){ tree[id].resize(n+1);for(int i=1;i<=n;i++){tree[id][i].resize(0);}}
}
void addEdge(int u,int v){/*for(int i=1;i<=k;i++){if(dsu[i].find(u)!=dsu[i].find(v)){tree[i][u].push_back(v);tree[i][v].push_back(u);dsu[i].merge(u,v);break;}}*/int l=1,r=k,ans=-1;while(l<=r){int mid=l+r>>1;if(dsu[mid].find(u)!=dsu[mid].find(v)){ans=mid;r=mid-1;}else{l=mid+1;}}if(ans!=-1){tree[ans][u].push_back(v);tree[ans][v].push_back(u);dsu[ans].merge(u,v);}
}
bool dfs(int x,int fx,int to,int id,vector<int>&ans){ans.push_back(x);if(x==to){return true;}for(int i:tree[id][x]){if(i==fx){continue;}if(dfs(i,x,to,id,ans)){return true;}}ans.pop_back();return false;
}
namespace debug{void dfs1(int x,int fx,int id){cerr<<x<<" ";for(int i:tree[id][x]){if(i==fx){continue;}dfs1(i,x,id);}}
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){cin>>n>>m;k=(m+n-2)/(n-1);resize(n,k);while(m--){int u,v;cin>>u>>v;addEdge(u,v);}bool flag=true; for(int i=1;flag&&i<=n;i++){for(int j:tree[k][i]){flag=false;cout<<i<<' '<<j<<'\n';for(int id=1;id<=k;id++){vector<int>ans;dfs(i,0,j,id,ans);cout<<ans.size()<<' ';for(int x:ans){cout<<x<<' ';}cout<<'\n';}break;}}if(flag){cout<<"-1\n";}}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}
/*
1
3 1
1 31 3
2 1 3
*/
/*
1
4 7
1 2
2 3
3 4
4 1
1 3
2 4
1 41 4
4 1 2 3 4
2 1 4
2 1 4
*/
/*
3
3 1
1 3
4 7
1 2
2 3
3 4
4 1
1 3
2 4
1 4
5 5
1 2
2 3
3 4
4 5
3 51 3
2 1 3
1 4
4 1 2 3 4
2 1 4
2 1 4
3 5
3 3 4 5
2 3 5
*/
http://www.hskmm.com/?act=detail&tid=18910

相关文章:

  • NXP - 用MCUXpresso IDE导入lpcopen_2_10_lpcxpresso_nxp_lpcxpresso_1769.zip中的工程 - 教程
  • spatial项目的主要领导者斯坦福大学ppl实验室的 Kunle Olukotun 教授和 Christos Kozyrakis 教授
  • 程序语言杂谈:概述
  • 字符串基础
  • 在CodeBolcks下wxSmith的C++编程教程——使用 wxGrid
  • 题解:P12479 [集训队互测 2024] 长野原龙势流星群
  • linux下nginx
  • 9.27
  • OI 笑传 #12
  • spatial芯片设计语言 学习笔记
  • 【C++】23. C++11(上) - 教程
  • kali2025搭建ARL灯塔系统
  • 实用指南:AI 术语通俗词典:LLM(大语言模型)
  • java学习 2025-9-27
  • 题解:P11667 [USACO25JAN] Astral Superposition B
  • 北极通讯网络题解(做题记录)
  • elasticsearch安装插件 - 实践
  • 个人学习——前端react项目框架
  • 软件基础第一次作业
  • LGP9755 [CSP-S 2023] 种树 学习笔记
  • 7、revision 是 Maven 3.5+ 引入的现代版本管理机制 - 实践
  • P1731 生日蛋糕 做题记录
  • 如何有效提升代码覆盖率:从单元测试到集成测试的实践指南
  • Spring知识点(2)
  • 超越实习期的AI自动化工具:播客工作流与Slack导出器实战
  • 调度器的各项指标以及计算方式
  • 浅谈dsu on tree
  • JavaDay10
  • 昇腾多机推理极速上手:10倍简化的 DeepSeek R1 超大规模模型部署
  • python开始exe应用程序初级教程