【算法1-1】模拟与高精度
https://www.luogu.com.cn/training/106#problems
P1518 [USACO2.4]两只塔姆沃斯牛 The Tamworth Two
https://www.luogu.com.cn/problem/P1518
原本我是单纯的模拟，没有判断死循环即无解的情况。看了下面的分析，给t设置一个最大值，超过就无解。
“看到题后，我们的第一反应是寻找环判重叠来算次数，但这样也太麻烦了，所以考虑更简洁的直接模拟：
由于只有10x10行的地图，因此牛和农夫最多只有400种情况（每个位置有4次，4方向各一次）由乘法原理可知，无论怎么走，最多都只能出现160000种情况，实际上还要小的多（而且160000也非常小了）”
#include <bits/stdc++.h>
using namespace std;
const int N = 12;
char a[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
int n, sx, sy, ex, ey;
for(int i = 0; i < 10; i++){
for(int j = 0; j < 10; j++) {
cin >> a[i][j];
if(a[i][j] == 'F') sx = i, sy = j;
if(a[i][j] == 'C') ex = i, ey = j;
}
}
int t = 0, d1 = 0, d2 = 0;
while((sx != ex || sy != ey ) && t < 200000){
t++;
//对于F
int x = sx + dx[d1], y = sy + dy[d1];
if(x >= 0 && x < 10 && y >= 0 && y < 10 && a[x][y] != '*') sx = x, sy = y;
else d1 = (d1 + 1) % 4;
//对于C
x = ex + dx[d2], y = ey + dy[d2];
if(x >= 0 && x < 10 && y >= 0 && y < 10 && a[x][y] != '*') ex = x, ey = y;
else d2 = (d2 + 1) % 4;
//printf("sx = %d sy = %d ex = %d ey = %d\n");
}
if(t == 200000) printf("%d\n", 0);
else printf("%d\n", t);
//cout << p[pos].w << endl;
return 0;
}P1098 [NOIP2007 提高组] 字符串的展开
https://www.luogu.com.cn/problem/P1098
难点在于处理各种特殊情况，要仔细。
#include <bits/stdc++.h>
using namespace std;
int main(){
int p1, p2, p3;
cin >> p1 >> p2 >> p3;
string s, ans = "";
cin >> s;
char last;
for(int i = 0; i < s.size(); i++) {
if(s[i] != '-') ans += s[i];
else if((i == 0 || i == s.size() - 1) && s[i] == '-') ans += '-';
else if(s[i]=='-' && (s[i - 1] == '-' || s[i + 1] == '-')) ans += '-';
else if(s[i] == '-'){
if(s[i - 1] >= s[i + 1] || (s[i - 1] < 58 && s[i + 1] > 96)) ans += '-';
else if(s[i + 1] == s[i - 1] + 1) continue;
else{
if(p1 == 3){
for(int j = 1; j <= (s[i+1] - s[i-1] - 1)* p2; j++)ans += '*';
}
else if(s[i+1] <= '9' && s[i+1] >= '0' && s[i-1] <= '9' && s[i-1] >= '0'){
if(p3 == 1){
//数字，顺序
for(int j = s[i-1]+1; j <= s[i+1]-1; j++){
for(int k = 1; k <= p2; k++)
ans = ans + (char)(j);
}
}else if(p3 == 2){
// 数字 ，逆序
for(int j = s[i+1]-1; j >= s[i-1]+1; j--){
for(int k = 1; k <= p2; k++)
ans = ans + (char)(j);
}
}
}
else if(p1 == 1){
if(p3 == 1){
//小写字母，顺序
for(int j = s[i-1]+1; j <= s[i+1]-1; j++){
for(int k = 1; k <= p2; k++)
ans = ans + (char)(j);
}
}else if(p3 == 2){
// 小写字母，逆序
for(int j = s[i+1]-1; j <= s[i-1]+1; j--){
for(int k = 1; k >= p2; k++)
ans = ans + (char)(j);
}
}
}
else if(p1 == 2) {
if(p3 == 1){
//大写字母，顺序
for(int j = s[i-1]+1; j <= s[i+1]-1; j++){
for(int k = 1; k <= p2; k++)
ans = ans + (char)(j - 'a' + 'A');
}
}else if(p3 == 2){
// 大写字母，逆序
for(int j = s[i + 1]-1; j >= s[i-1]+1; j--){
for(int k = 1; k <= p2; k++)
ans = ans + (char)(j - 'a' + 'A');
}
}
}
}
}
}
//printf("%d\n", t);
cout << ans << endl;
return 0;
}P1045 [NOIP2003 普及组] 麦森数
https://www.luogu.com.cn/problem/P1045
【算法1-2】排序
快排
P1177 【模板】快速排序
https://www.luogu.com.cn/problem/P1177
快排应用：第k个数 练习分治算法
P1923 【深基9.例4】求第 k 小的数
https://www.luogu.com.cn/problem/P1923
方法一：
这里用快排，先排序再输出q[k]，不能完全通过，部分会TLE;
方法二：
修改一下快排函数，找到第k个就返回它。
而且这里用cin读入仍然会TLE
换成scanf就AC了。
模板的k是从1开始，这里k是从0开始，所以要quick_sort(a, 0, n-1, k + 1)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5000010;
int n, k;
int a[N];
int quick_sort(int q[], int l, int r, int k){
if(l >= r) return q[l];
int x = q[l + r >> 1];
int i = l - 1, j = r + 1;
while(i < j){
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j){
int tmp = q[i];
q[i] = q[j];
q[j] = tmp;
}
}
if(j - l + 1 >= k) quick_sort(q, l, j, k);
else quick_sort(q, j + 1, r, k - (j - l + 1));
}
int main(){
int n;
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
}
//模板的k是从1开始，这里k是从0开始
printf("%d ", quick_sort(a, 0, n-1, k + 1));
return 0;
}方法三：
nth_element的用法
https://www.cnblogs.com/xenny/p/9424894.html
#include <bits/stdc++.h>
using namespace std;
const int N = 5000010;
int n, k;
int a[N];
int main(){
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
nth_element(a, a + k, a + n); //使第k小整数就位
printf("%d", a[k]); //调用第k小整数
return 0;
}冒泡排序
P1116 车厢重组
https://www.luogu.com.cn/problem/P1116
方法一： 冒泡排序
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n;
int a[N], cnt;
void bubble(){
for(int i = 0; i < n - 1; i++){
for(int j = 0; j < n - 1; j++){
if(a[j] > a[j + 1]){
swap(a[j], a[j + 1]);
cnt++;
}
}
}
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
bubble();
printf("%d\n", cnt);
return 0;
}方法二：题目只是问需要多少次移动，没问排序结果
没有做排序，只是迭代去计算每个数字前有几个数字比它大，这意味着它必须要移动几次。
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int a[N];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
int cnt = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
if(a[j] > a[i]) cnt++;
}
}
printf("%d\n", cnt);
return 0;
}P1012 [NOIP1998 提高组] 拼数
https://www.luogu.com.cn/problem/P1012
原本我的想法是大的数字放在高位，所以直接比较每个字符串大小就行，但是只能75分。
出错的例子为：
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int n;
string a[N];
bool cmp(string a, string b){
return a > b;
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n, cmp);
string ans = "";
for(int i = 0; i < n; i++) {
//cout << a[i] << endl;
ans += a[i];
}
cout << ans << endl;
//printf("%.3lf\n", ans);
return 0;
}所以直接改cmp函数，100分AC
bool cmp(string a, string b){
return a + b > b + a;
}【算法1-3】暴力枚举
P1036 [NOIP2002 普及组] 选数
https://www.luogu.com.cn/problem/P1036
但其实下面代码中的st数组也可以不要，因为dfs每次传入了开始扫描的数组下标b就保证了不会重复访问。
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int n, k;
int a[N], st[N], cnt;
bool isPrime(int x){
for(int i = 2; i <= x / i; i++){
if(x % i == 0) return false;
}
return true;
}
void dfs(int x, int b, int sum){
if(x == k){
if(isPrime(sum)) {
//cout << sum << endl;
cnt++;
}
return ;
}
for(int i = b; i < n; i++){
if(!st[i]){
st[i] = 1;
//cout << "sum = " << sum << "ai = " << a[i] << endl;
dfs(x + 1, i + 1, sum + a[i]);
st[i] = 0;
}
}
}
int main(){
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> a[i];
dfs(0, 0, 0);
cout << cnt << endl;
return 0;
}P1157 组合的输出
都用了dfs，但题目要求的排列不同，所以dfs要相应调整。
P3392 涂国旗
https://www.luogu.com.cn/problem/P3392
先做一下预处理，求出每行每个色块的个数
让后两个嵌套的for循环分别模拟白色行数（顶部）和红色行数（底部）
进而求出用这种方法涂制国旗所需次数，再来个很简单的判断，就可以得出最少次数
#include <bits/stdc++.h>
using namespace std;
const int N = 60;
int n, m;
char a[N][N];
int W[N], B[N], R[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++){
cin >> a[i][j];
if(a[i][j] == 'W') W[i]++;
if(a[i][j] == 'B') B[i]++;
if(a[i][j] == 'R') R[i]++;
}
}
int ans = 2e9;
//最上方变为白的行数
for(int i = 1; i <= n - 2; i++) {
//最下方变为红的行数
for(int j = 1; j <= n - 2; j++) {
int tmp = 0;
if(i + j > n - 1) continue; //剩余蓝行不足1
//变白格子需要的次数
for(int k = 1; k <= i; k++) tmp += B[k] + R[k];
//变蓝格子需要的次数
for(int k = i + 1; k <= n - j; k++) tmp += W[k] + R[k];
//变红格子需要的次数
for(int k = n - j + 1; k <= n; k++) tmp += W[k] + B[k];
ans = min(ans, tmp);
}
}
cout << ans << endl;
return 0;
}P3654 First Step (ファーストステップ)
https://www.luogu.com.cn/problem/P3654
每次达到k，t--而不是直接变为0，类似滑动窗口。
注意k=1的特殊情况，行列会分别算一遍所以要除以2.
P1149 [NOIP2008 提高组] 火柴棒等式
https://www.luogu.com.cn/problem/P1149
关键是要确定数的范围，这里要是不太能确定的话可以保守一点取大一点。我是看了题解，发现他们的数在2000左右。
P3799 妖梦拼木棒
https://www.luogu.com.cn/problem/P3799
参考第一篇题解
https://www.luogu.com.cn/problem/solution/P3799
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, maxl;
int a[N], cnt[N];
//求得从a个数中取出2个数的组合
int C2(int a){
return a * (a - 1) / 2 % mod;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
maxl = max(maxl, a[i]);
cnt[a[i]] ++;
}
int ans = 0;
//枚举a,b
for(int i = 1; i <= maxl; i++) {
for(int j = i; j <= maxl; j++) {
if(i == j) ans = (ans + C2(cnt[i]) * C2(cnt[i + j])) % mod;
else ans = (ans + cnt[i] * cnt[j] % mod * C2(cnt[i + j]) % mod) % mod;
}
}
cout << ans << endl;
return 0;
}【算法1-4】递推与递归
P1255 数楼梯
https://www.luogu.com.cn/problem/P1255
这里要用到高精度，数值比较大。
vector<vector<int> >的各种用法和易错
https://www.cnblogs.com/superjn/p/10730541.html</int>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int> > f;
vector<int> add(vector<int> &a, vector<int> &b){
if(a.size() < b.size()) return add(b, a);
vector<int> c;
int t = 0;
for(int i = 0; i < a.size(); i++){
t += a[i];
if(i < b.size()) t += b[i];
c.push_back(t % 10);
t /= 10;
}
if(t) c.push_back(t);
return c;
}
int main(){
cin >> n;
vector<int> t;
t.push_back(0); f.push_back(t);
t.pop_back(); t.push_back(1); f.push_back(t);
t.pop_back(); t.push_back(2); f.push_back(t);
for(int i = 3; i <= n; i++) {
vector<int> tmp = add(f[i - 1], f[i - 2]);
f.push_back(tmp);
}
for(int i = f[n].size() - 1; i >= 0; i--)
cout << f[n][i];
return 0;
}P1002 [NOIP2002 普及组] 过河卒
https://www.luogu.com.cn/problem/P1002
这里需要知道马是怎么走的，且马能一步走到的地方是不能经过的。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 30;
int n, m, mx, my;
int dx[9] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
int dy[9] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
LL f[N][N];
bool st[N][N]; //是否被马拦住
int main(){
cin >> n >> m >> mx >> my;
n++, m++, mx++, my++;
//标记不能经过的位置
for(int i = 0; i < 9; i++) st[mx + dx[i]][my + dy[i]] = 1;
f[1][1] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if((i != 1 || j != 1) && !st[i][j]) f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
cout << f[n][m] << endl;
return 0;
}P1044 [NOIP2003 普及组] 栈
https://www.luogu.com.cn/problem/P1044
https://www.luogu.com.cn/problem/solution/P1044
有多种方法。
P1928 外星密码
https://www.luogu.com.cn/problem/P1928
这个题解法很神奇，再看看。
P1164 小A点菜
https://www.luogu.com.cn/problem/P1164
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110;
int m, n, cnt, t;
int a[N];
void dfs(int k, int sum){
t++;
if(sum == m) {
cnt++;
return;
}
if(k > n) return;
dfs(k + 1, sum);
dfs(k + 1, sum + a[k]);
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
dfs(1, 0);
cout << cnt << endl;
return 0;
}dfs会部分超时
改用dp，AC
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 10010;
int m, n;
int a[N], f[M];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
f[0] = 1;
for(int i = 1; i <= n; i++){
for(int j = m; j >= a[i]; j--){
f[j] = f[j] + f[j - a[i]];
}
}
cout << f[m] << endl;
return 0;
}P1990 覆盖墙壁
https://www.luogu.com.cn/problem/P1990
再看看
P3612 [USACO17JAN]Secret Cow Code S
重新写写！是参考题解AC的。
P1228 地毯填补问题
https://www.luogu.com.cn/problem/P1228
分治，重新写写！是参考题解AC的。
【算法1-5】贪心
P1803 凌乱的yyy / 线段覆盖
https://www.luogu.com.cn/problem/P1803
本来想的是按开始时间从小到大排，但WA
实际上应该按结束时间从小到大排，越早结束越应该选。
类似问题：
在一个数轴上有n条线段，现要选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少。
最左边的线段放什么最好？
显然放右端点最靠左的线段最好，从左向右放，右端点越小妨碍越少
其他线段放置按右端点排序，贪心放置线段，即能放就放
本来直接用数组排序，每次计算两个数的值，还用到了前缀和
但只通过了一个，仔细思考后发现，把最小的两个相加后的值不一定是当前最小的，而这个题始终要选最小的两个相加。
所以要用小根堆维护，c++里由优先队列实现。
priority_queue<int, vector<int>, greater<int> > heap;</int></int>
P5019 [NOIP2018 提高组] 铺设道路
https://www.luogu.com.cn/problem/P5019
用模拟会超时。用贪心的思路求解。
再写一遍！
【算法1-6】二分查找与二分答案
P1102 A-B 数对
https://www.luogu.com.cn/problem/P1102
自己写的，本来只用了一个简单二分，但是数组可能有重复值，所以要先排序，然后再找出现的第一个位置和最后一个位置。
题解还有更简单的方法可以看看。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 1000010, mod = 10000;
int n, c;
int a[N];
//找等于x的最小的位置
int search1(int x){
int l = 1, r = n;
while(l < r){
int mid = (l + r) / 2;
if(a[mid] >= x) r = mid;
else l = mid + 1;
}
if(a[l] == x) return l;
else return -1;
}
//找等于x的最大的位置
int search2(int x){
int l = 1, r = n;
while(l < r){
int mid = (l + r + 1) / 2;
if(a[mid] <= x) l = mid;
else r = mid - 1;
}
if(a[l] == x) return l;
else return -1;
}
int main(){
cin >> n >> c;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);//用二分数组要有序
LL cnt = 0;
//枚举b，a = b + c
for(int i = 1; i <= n; i++){
if(search2(a[i] + c) != -1 && search1(a[i] + c) != -1 && search2(a[i] + c) != i && search1(a[i] + c) != i)
cnt += search2(a[i] + c) - search1(a[i] + c) + 1;
}
cout << cnt << endl;
return 0;
}P1678 烦恼的高考志愿
https://www.luogu.com.cn/problem/P1678
再看看
P2678 [NOIP2015 提高组] 跳石头
P3853 [TJOI2007]路标设置
P1182 数列分段 Section II
P1163 银行贷款
P3743 kotori的设备
类似思路，思考什么样的问题可以用二分。
【算法1-7】搜索
P2392 kkksc03考前临时抱佛脚
重重重！
P1433 吃奶酪
常规的dfs+剪枝 最后一个测试点会TLE
查看题解
这里我没有像他那样先按距离排序，而是直接在源代码上加了一个超时弹出的条件，最后一个也能AC了。
void dfs(int now, int cnt, double d){
l++;
if(l >= 30000000) {
int t = clock();
if(t >= 940) return;
}
if(d >= ans) return;
if(cnt == n){
ans = min(ans, d);
return;
}
for(int i = 1; i <= n; i++){
if(now != i && !vis[i]){
vis[i] = 1;
//cout << dis[now][i]<< endl;
dfs(i, cnt + 1, d + dis[now][i]);
vis[i] = 0;
}
}
}P1101 单词方阵
和一般的dfs套路不一样，要多一步处理
P1162 填涂颜***r>https://www.luogu.com.cn/problem/P1162
本来用bfs找1围成的形状的上下左右四条边，但是只得了32分。因为围城的图形不是矩形，是不规则的，所以会有在围墙外的0被改为2.
可以转为思考哪些0应该被涂，哪些不应该被涂。
边界上的一定不会被涂，和它相连的也不应该被涂，剩下的就是被1围起来的。
京公网安备 11010502036488号