网站开发商城app,鄂州第一网官方网站,盐山网站,宁波比较好的网站公司1.两只塔姆沃斯牛#xff08;模拟#xff09; 思路#xff1a;人和牛都记录三个数据#xff0c;当前坐标和走的方向#xff0c;如果人和牛的坐标和方向走重复了#xff0c;那就说明一直在绕圈圈#xff0c;无解
#includeiostream
using namespace std;
const i…1.两只塔姆沃斯牛模拟 思路人和牛都记录三个数据当前坐标和走的方向如果人和牛的坐标和方向走重复了那就说明一直在绕圈圈无解
#includeiostream
using namespace std;
const int N 15;
char g[N][N];
int b[N][N][N][N][N][N];
int tx, ty, ex, ey;
struct Point{int x, y, fang;
}peo, cow;
int ok;int dx[] {-1, 0, 1, 0};
int dy[] {0, 1, 0, -1};void ff(){int px peo.x dx[peo.fang];int py peo.y dy[peo.fang];int cx cow.x dx[cow.fang];int cy cow.y dy[cow.fang];if(g[px][py] ! *){peo.x px;peo.y py;}else{peo.fang (peo.fang 1) % 4;}if(g[cx][cy] ! *){cow.x cx;cow.y cy;}else{cow.fang (cow.fang 1) % 4;}
}int main(){for(int i 0; i 11; i){for(int j 0; j 11; j){g[i][j] *;}}for(int i 1; i 10; i){for(int j 1; j 10; j){cing[i][j];if(g[i][j] F){tx i;ty j;}if(g[i][j] C){ex i;ey j;}}}
// for(int i 0; i 11; i){
// for(int j 0; j 11; j){
// coutg[i][j];
// }
// coutendl;
// }peo {tx, ty, 0};cow {ex, ey, 0};int cnt 0, ok1 0, ok2 0;while(!(peo.x cow.x peo.y cow.y)){cnt;ff();if(b[peo.x][peo.y][peo.fang][cow.x][cow.y][cow.fang] 1){ok 1;break;}b[peo.x][peo.y][peo.fang][cow.x][cow.y][cow.fang] 1;}if(ok 1) cout0;else coutcnt;return 0;
}2.宇宙总统排序 思路自定义排序按照从大到小升序排序
#includeiostream
#includealgorithm
using namespace std;
const int N 25;
pairstring, int q[N];
int n;bool cmp(const pairstring, int pp, const pairstring, int qq){if(pp.first.size() ! qq.first.size()) return pp.first.size() qq.first.size();else{int m pp.first.size();for(int i 0; i m; i){if(pp.first[i] ! qq.first[i]){return pp.first[i] qq.first[i];}}}
}int main(){cinn;string x;for(int i 1; i n; i){cinx;q[i] {x, i};}sort(q 1, q n 1, cmp);coutq[1].secondendl;coutq[1].first;return 0;
}3.回文质数回文数、质数 思路先判断回文数再判断质数最大的回文质数是 9989899
#includeiostream
#includecstring
using namespace std;
int a, b;// 检查是否回文
int check1(int x){int res 0, t x;while(t){res res * 10 t % 10;t / 10;}return res x;
}// 检查是否质数
int check2(int x){if(x 2) return 0;for(int i 2; i x / i; i){if(x % i 0){return 0;}}return 1;
}int main(){cinab;for(int i a; i b; i){// 最大的回文质数是 9989899 if(i 10000000) break;if(check1(i)){//coutiendl;if(check2(i)){coutiendl;}}}return 0;
}4.海底高铁前缀和、差分 思路如上差分标记两个起始地点然后前缀和求出每个地方需要走多少次贪心求出买票还是买卡划算
#includeiostream
#includecstring
using namespace std;
const int N 1e5 10;
int p[N], s[N];
int n, m;int main(){cinnm;for(int i 0; i m; i){cinp[i];if(i 0){if(p[i] p[i - 1]){s[p[i - 1]];s[p[i]]--;}else{s[p[i]];s[p[i - 1]]--;}}}// 差分数组累加前缀和for(int i 1; i n; i){s[i] s[i - 1];}int a, b, c;long long sum 0;for(int i 1; i n; i){cinabc;sum min(1ll * a * s[i], 1ll * b * s[i] c);}if(m 2) cout0;else coutsum;return 0;
}5.KMPkmp #includeiostream
#includecstring
using namespace std;
const int N 1e6 10;
int ne[N], f[N];
char s[N], p[N];
int n, m;void kmp(){ne[1] 0;int j 0;for(int i 2; i m; i){while(j 0 p[i] ! p[j 1]) j ne[j];if(p[i] p[j 1]) j;ne[i] j;}j 0;for(int i 1; i n; i){while(j 0 s[i] ! p[j 1]) j ne[j];if(s[i] p[j 1]) j;f[i] j;}for(int i 1; i n; i){if(f[i] m){cout(i - m 1)endl;}}for(int i 1; i m; i){coutne[i] ;}
}int main(){cin(s 1)(p 1);n strlen(s 1);m strlen(p 1);kmp();return 0;
}6.直播获奖桶排序 #includeiostream
using namespace std;
const int N 610;
int t[N];
int n, w;int main(){cinnw;int x;for(int i 1; i n; i){cinx;t[x];int sum 0;for(int j 600; j 0; j--){sum t[j];if(sum max(1, i * w / 100)){coutj ;break;}}}return 0;
}7.最大子段和递推 思路从开头一直累加如果小于 0那就重新开始累加取最大值
#includeiostream
#includealgorithm
using namespace std;
const int N 2e5 10;
int a[N];
int n; int main(){cinn;int x, res 0, ans -1e9;for(int i 0; i n; i){cinx;res x;ans max(ans, res);if(res 0) res 0;}coutans;return 0;
}8.采药01背包 思路每个物品只能使用一次时间就是体积
#includeiostream
#includealgorithm
using namespace std;
const int N 1000 10;
int f[N], v[N], w[N];
int n, m; int main(){cinmn;for(int i 1; i n; i){cinv[i]w[i];}for(int i 1; i n; i){for(int j m; j v[i]; j--){f[j] max(f[j], f[j - v[i]] w[i]);} }coutf[m];return 0;
}
9.疯狂的采药完全背包 思路时间就是体积完全背包注意数据范围背包体积 1e7最大价值是 1e7 * 1e4 1e11
#includeiostream
#includealgorithm
using namespace std;
const int N 1e7 10;
long long f[N], v[N], w[N];
int n, m; int main(){cinmn;for(int i 1; i n; i){cinv[i]w[i];}for(int i 1; i n; i){for(int j v[i]; j m; j){f[j] max(f[j], f[j - v[i]] w[i]);} }coutf[m];return 0;
}10.最大食物链计数拓扑排序 思路求的是路径条数只有出度为 0 的时候才累加答案
#includeiostream
#includealgorithm
#includevector
#includequeue
using namespace std;
const int N 5e3 10, mod 80112002;
vectorint g[N];
int ru[N], chu[N];
int siz[N];
int n, m;
int cnt;void ff(){queueint q;for(int i 1; i n; i){if(ru[i] 0){siz[i] 1;q.push(i);} }while(q.size()){int it q.front();q.pop();for(int i : g[it]){siz[i] (siz[i] siz[it]) % mod;ru[i]--;if(ru[i] 0){if(chu[i] 0){cnt (cnt siz[i]) % mod;}else{q.push(i);}}}}
}int main(){cinnm;int a, b;for(int i 1; i m; i){cinab;g[a].push_back(b);chu[a];ru[b];}ff();coutcnt;return 0;
}11.装箱问题01背包 思路01 背包求最大能装下的体积体积也是价值
#includeiostream
using namespace std;
const int N 2e4 10;
int f[N], v[N];
int n, m;int main(){cinmn;for(int i 1; i n; i){cinv[i];}for(int i 1; i n; i){for(int j m; j v[i]; j--){f[j] max(f[j], f[j - v[i]] v[i]);}}cout(m - f[m]);return 0;
}12.高维正方体快速幂、逆元 思路f[i][j]i 维立方体中 j 维元素个数
#includeiostream
using namespace std;
const int N 1e5 10, mod 1e9 7;
int f[N];int qm(int a, int b){int res 1 % mod;while(b){if(b 1) res 1ll * res * a % mod;a 1ll * a * a % mod;b 1;}return res;
}int main(){int a, b;cinab;f[0] qm(2, a);for(int j 1; j b; j){f[j] ((1ll * f[j - 1] * (a 1 - j)) % mod * qm(2 * j, mod - 2) % mod) % mod;}coutf[b];return 0;
}13.编码计算组合数 #includeiostream
using namespace std;
const int N 30;
int f[N][N];void init(){for(int i 1; i N; i){for(int j 0; j i; j){if(j 0) f[i][j] 1;else f[i][j] f[i - 1][j] f[i - 1][j - 1];}}
}int main(){init();string s;cins;int n s.size();for(int i 0; i n - 1; i){if(s[i] s[i 1]){cout0;return 0;}}int ans 0;// 加上位数比当前小的 for(int i 1; i n; i) ans f[26][i];//枚举当前每一位可以有多少种情况 for(int i 0; i n; i){int m s[i] - a;for(int j 1; j m; j){ans f[26 - j][n - i - 1];}} // 加上自身 ans;coutans;return 0;
}14.高低位交换位运算 思路无符号整型 unsigned int 是 32 位整型越界就等于取模了
#includeiostream
using namespace std;int main(){unsigned int n;cinn;unsigned int res (n 16) (n 16);coutres;return 0;
}15.合并果子贪心 思路每次取出两个最小的果子合并
#includeiostream
#includequeue
using namespace std;
const int N 1e4 10;
priority_queueint, vectorint, greaterint q;
int n;int main(){cinn;int x;for(int i 0; i n; i){cinx;q.push(x);}long long sum 0;while(q.size() 1){int a q.top();q.pop();int b q.top();q.pop();sum a b;q.push(a b);}coutsum;return 0;
}16.陶陶摘苹果升级版贪心 思路按照每个苹果所需要的力气升序排序一个一个摘
#includeiostream
#includealgorithm
using namespace std;
const int N 1e5 10;
pairint, int q[N];
int n, m, a, b;bool cmp(const pairint, int pp, const pairint, int qq){if(pp.second ! qq.second) return pp.second qq.second;else return pp.first qq.first;
}int main(){cinnm;cinab;int x, y;for(int i 1; i n; i){cinxy;q[i] {x, y};}sort(q 1, q n 1, cmp);int cnt 0;for(int i 1; i n; i){if(m - q[i].second 0 a b q[i].first){cnt;m - q[i].second;}}coutcnt;return 0;
}17.一元三次方程求解二分 思路如果有一个区间左右端点相乘小于等于 0那么这个区间存在一个零点
#includeiostream
#includealgorithm
using namespace std;
double a, b, c, d;double check(double x){double sum a * x * x * x b * x * x c * x d;return sum;
}int main(){cinabcd;int f 0;for(int i -100; i 100; i){if(f 3) break;double l i - 0.5, r i 0.5;if(check(l) * check(r) 0){if(check(l) 0){while(l 0.00001 r){double mid (l r) / 2;if(check(mid) 0) l mid;else r mid; }}else if(check(l) 0){while(l 0.00001 r){double mid (l r) / 2;if(check(mid) 0) l mid;else r mid; }}f;printf(%.2lf , r);}}return 0;
}18.八皇后dfs 思路dfs 一个参数维护每行然后三个数组维护每一列、正对角线、斜对角线
#includeiostream
#includequeue
using namespace std;
const int N 30;
int a[N];
int vis1[N], vis2[N], vis3[N];
int n;
int cnt;void dfs(int u){if(u n){cnt;if(cnt 4){for(int i 1; i n; i){couta[i] ;}coutendl;}return;}for(int i 1; i n; i){if(!vis1[i] !vis2[u i] !vis3[i - u n]){vis1[i] vis2[u i] vis3[i - u n] 1;a[u] i;dfs(u 1);vis1[i] vis2[u i] vis3[i - u n] 0;}}
}int main(){cinn;dfs(1);coutcnt;return 0;
}19.单词接龙dfs 思路dfs 维护当前拼接成功的单词用 map 记录每个单词用了几次
#includeiostream
#includemap
using namespace std;
const int N 30;
mapstring, int mp;
string s[N];
int n;
int ans;string check(string s1, string s2){int len s1.size();for(int i 1; i len; i){if(s1.substr(len - i) s2.substr(0, i)){string t s1 s2.substr(i);return t;}}return 加训;
}void dfs(string ss){if(ss.size() ans) ans ss.size();for(int i 1; i n; i){if(mp[s[i]] 2) continue;string t check(ss, s[i]);if(t ! 加训){mp[s[i]];dfs(t);mp[s[i]]--;}}
}int main(){cinn;for(int i 1; i n; i){cins[i];}char c;cinc;for(int i 1; i n; i){if(s[i][0] c){mp[s[i]];dfs(s[i]);mp[s[i]]--;}}coutans;return 0;
}20.约瑟夫问题取模 思路vector 下标从 0 开始每次前进 m - 1 个位置到第 n 个位置取模后会变成 0正好符合条件
#includeiostream
#includevector
using namespace std;
vectorint v;
int n, m;int main(){cinnm;for(int i 1; i n; i) v.push_back(i);int cnt 0;while(v.size()){cnt (cnt m - 1) % v.size();coutv[cnt] ;v.erase(v.begin() cnt);}return 0;
}21.队列安排模拟链表 思路结构体模拟双链表
#includeiostream
#includecstring
using namespace std;
const int N 1e5 10;
int n, m;
struct Point{int l, r; // 左边和右边的同学 int vis; // 标记是否删除
}q[N];void add(int i, int j, int f){// j 插到 i 的右边 if(f 1){q[j].r q[i].r;q[j].l i;q[i].r j;q[q[j].r].l j;}else{// j 插到 i 的左边 q[j].r i;q[j].l q[i].l;q[i].l j;q[q[j].l].r j;}
}void init(){q[0].r 0, q[0].l 0;add(0, 1, 1); // 1 插到 0 的右
}int main(){cinn;int k, p;for(int i 2; i n; i){cinkp;add(k, i, p);}cinm;int x;for(int i 1; i m; i){cinx;q[x].vis 1;}for(int i q[0].r; i 0; i q[i].r){if(!q[i].vis) couti ;}return 0;
}22.验证栈序列模拟栈 思路按入栈顺序入栈如果栈顶和当前 b 数组元素相等那就弹出如果入栈结束栈不为空说明 b 不是出栈序列
#includeiostream
#includestack
using namespace std;
const int N 1e5 10;
int a[N], b[N];
int n, q;int main(){cinq;while(q--){cinn;for(int i 0; i n; i) cina[i];for(int i 0; i n; i) cinb[i];stackint q;int cnt 0;for(int i 0; i n; i){q.push(a[i]);while(q.top() b[cnt]){q.pop();cnt;if(q.empty()) break;}}if(q.empty()) coutYesendl;else coutNoendl;}return 0;
}23.马的遍历bfs #includeiostream
#includecstring
#includequeue
using namespace std;
const int N 410;
int g[N][N], vis[N][N], dis[N][N];
int n, m;int dx[] {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[] {-2, -1, 1, 2, 2, 1, -1, -2};void bfs(int x, int y){queuepairint, int q;vis[x][y] 1;dis[x][y] 0;q.push({x, y});while(q.size()){auto it q.front();q.pop();for(int i 0; i 8; i){int a it.first dx[i], b it.second dy[i];if(a 1 || a n || b 1 || b m) continue;if(vis[a][b]) continue;vis[a][b] 1;dis[a][b] dis[it.first][it.second] 1;q.push({a, b});}}
}int main(){memset(dis, -1, sizeof(dis));int x, y;cinnmxy;bfs(x, y);for(int i 1; i n; i){for(int j 1; j m; j){coutdis[i][j] ;}coutendl;}return 0;
}24.01迷宫dfs 思路记录每个点属于哪个连通块记录每个连通块的点个数
#includeiostream
#includecstring
#includequeue
using namespace std;
const int N 1e3 10, M 1e5 10;
char g[N][N];
int vis[N][N];
int mp[M];
int n, m;
int cnt;int dx[] {0, 0, -1, 1};
int dy[] {-1, 1, 0, 0};void dfs(int x, int y, int z){vis[x][y] z;mp[z];for(int i 0; i 4; i){int a x dx[i], b y dy[i];if(a 1 || a n || b 1 || b n) continue;if(vis[a][b]) continue;if(g[a][b] g[x][y]) continue;dfs(a, b, z);}
}int main(){cinnm;for(int i 1; i n; i){for(int j 1; j n; j){cing[i][j];}}for(int i 1; i m; i){int x, y;cinxy;if(!vis[x][y]){dfs(x, y, i);coutmp[i]endl;vis[x][y] i;}else{coutmp[vis[x][y]]endl;}}return 0;
}25.村村通并查集、dfs 思路把连通的点放在一个集合只需要找多少个不连通的集合需要加的边数就是这个数量减一
// 并查集
#includeiostream
using namespace std;
const int N 1e3 10;
int p[N];
int n, m;int fd(int x){if(x ! p[x]){p[x] fd(p[x]);}return p[x];
}// 合并两个集合
void ff(int x, int y){int t1 fd(x);int t2 fd(y);p[t2] t1;
}int main(){while(cinn n ! 0){cinm;int x, y;for(int i 1; i n; i){p[i] i;}for(int i 0; i m; i){cinxy;ff(x, y);}int cnt 0;for(int i 1; i n; i){if(fd(i) i){cnt;}}cnt--;coutcntendl;}return 0;
}// dfs
#includeiostream
#includecstring
#includevector
using namespace std;
const int N 1e3 10;
vectorint g[N];
int vis[N];
int n, m;void dfs(int x){if(!vis[x]);vis[x] 1;for(int y : g[x]){if(!vis[y]){dfs(y); }}
}int main(){while(cinn n ! 0){memset(vis, 0, sizeof(vis));cinm;int x, y;for(int i 1; i N; i) g[i].clear();for(int i 0; i m; i){cinxy;g[x].push_back(y);g[y].push_back(x);}int ans 0;for(int i 1; i n; i){if(vis[i]) continue;dfs(i);ans;}ans--;coutansendl;}return 0;
}26.两数之和哈希表 class Solution {
public:vectorint twoSum(vectorint nums, int target) {mapint, int mp;int n nums.size();for(int i 0; i n; i){mp[nums[i]] i 1;}for(int i 0; i n; i){int x target - nums[i];if(mp[x] 0 i ! mp[x] - 1){return vectorint {i, mp[x] - 1};}}return vectorint {0, 0};}
};27.盛水最多的容器双指针 class Solution {
public:int maxArea(vectorint height) {int n height.size();int l 0, r n - 1;int ans 0, res 0;while(l r){res min(height[l], height[r]) * (r - l);ans max(ans, res);if(height[l] height[r]) r--;else l;}return ans;}
};28.最长公共前缀模拟 思路枚举第一个字符串的长度如果后面不满足相等那就返回
class Solution {
public:string longestCommonPrefix(vectorstring strs) {if (strs.empty()) return ;string prefix ;for (int i 0; i strs[0].size(); i) {char ch strs[0][i];for (int j 1; j strs.size(); j) {if (i strs[j].size() || strs[j][i] ! ch) {return prefix;}}prefix ch;}return prefix;}
};29.寻找重复数哈希、二分、双指针 双指针思路数组在 [1, n] 之内所以慢指针每次走一步快指针每次走两步如果有环肯定会相遇
// 哈希
class Solution {
public:int findDuplicate(vectorint nums) {mapint, int mp;int n nums.size();for(int i 0; i n; i){mp[nums[i]];if(mp[nums[i]] 2) return nums[i];}return 666;}
};// 二分
class Solution {
public:int findDuplicate(vectorint nums) {int n nums.size();int l 1, r n - 1, ans -1;while (l r) {int mid (l r) 1;int cnt 0;for (int i 0; i n; i) {cnt nums[i] mid;}if (cnt mid) {l mid 1;} else {r mid - 1;ans mid;}}return ans;}
};// 双指针
class Solution {
public:int findDuplicate(vectorint nums) {int slow 0, fast 0;do {slow nums[slow];fast nums[nums[fast]];} while (slow ! fast);slow 0;while (slow ! fast) {slow nums[slow];fast nums[fast];}return slow;}
};30.分割数组的最大值二分答案 思路二分这个最大值
class Solution {
public:int check(vectorint nums, int x, int k){int sum 0;int n nums.size();int cnt 1;for(int i 0; i n; i){if(sum nums[i] x){sum nums[i];}else{sum nums[i];cnt;}}return cnt k;}int splitArray(vectorint nums, int k) {int n nums.size();int sum 0, res 0;for(int i 0; i n; i){sum nums[i];res max(res, nums[i]);}int l res - 1, r sum 1;while(l 1 r){int mid (l r) / 2;if(check(nums, mid, k)) r mid;else l mid;}return r;}
};
