文章目录
正文
1. 【5.5】P3717 [AHOI2017初中组] cover
题目链接：https://www.luogu.com.cn/problem/P3717
【分析】
暴力搜索 + 两点距离公式，时间复杂度：O(m * n ^ 2)。
【AC_Code】
#include <iostream>
#include <cmath>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
bool vis[105][105]; int ans;
void solve()
{
int n, m, r; cin >> n >> m >> r;
while (m --)
{
int x, y; cin >> x >> y;
for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++)
{
double dis = sqrt(pow((i - x), 2) + pow((j - y), 2));
if (dis <= r) vis[i][j] = true;
}
}
for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) if (vis[i][j]) ans ++;
cout << ans << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
2. 【5.6】P1897 电梯里的尴尬
题目链接：https://www.luogu.com.cn/problem/P1897
【分析】
先读懂题目样例，之后按题意模拟即可，具体看代码。
【AC_Code】
#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e5 + 10; int a[N], now, ans;
void solve()
{
int n; cin >> n; for (int i = 0; i < n; i ++) cin >> a[i];
sort(a, a + n);
for (int i = 0; i < n; )
{
int tar = a[i];
if (tar > now) ans += (tar - now) * 6;
else if (tar < now) ans += (now - tar) * 4;
int cnt = 0;
while (i < n && a[i] == tar) cnt ++, i ++;
ans += 5; ans += cnt; now = tar;
} ans += now * 4;
cout << ans << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
3. 【5.7】P2689 东南西北
题目链接：https://www.luogu.com.cn/problem/P2689
【分析】
按题意模拟即可，注意逻辑，属于简单题。
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int ans;
void solve()
{
int x1, y1, x2, y2, T; cin >> x1 >> y1 >> x2 >> y2 >> T;
while (T --)
{
char c; cin >> c;
if (c == 'N' && y1 < y2) y1 ++, ans ++;
else if (c == 'S' && y1 > y2) y1 --, ans ++;
else if (c == 'W' && x1 > x2) x1 --, ans ++;
else if (c == 'E' && x1 < x2) x1 ++, ans ++;
if (x1 == x2 && y1 == y2) { cout << ans << '\n'; return ; }
}
cout << -1 << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
4. 【5.8】P1145 约瑟夫
题目链接：https://www.luogu.com.cn/problem/P1145
【分析】
pos（删除位置）
4 = (0 + 4) % (2 * 3 - 0)
3 = (4 + 4) % (2 * 3 - 1)
3 = (3 + 4) % (2 * 3 - 2)
=> pos = (pos + m - 1) % (2 * k - i)
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
void solve()
{
int k; cin >> k; int m = k + 1;
while (1)
{
int pos = 0; bool flag = true;
for (int i = 0; i < k; i ++)
{
pos = (pos + m - 1) % (2 * k - i);
if (pos < k) { flag = false; break; }
}
if (flag) { cout << m << '\n'; return ; }
m ++;
}
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
5. 【5.9】P1088 [NOIP 2004 普及组] 火星人
题目链接：https://www.luogu.com.cn/problem/P1088
【分析】
相当于一个全排列模版：求输入的整数序列进行 m 次字典序下一个排列的变换。
【AC_Code】
#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e4 + 10; int a[N];
void solve()
{
int n, m; cin >> n >> m;
for (int i = 0; i < n; i ++) cin >> a[i];
for (int i = 0; i < m; i ++) next_permutation(a, a + n);
for (int i = 0; i < n; i ++) cout << a[i] << ' '; cout << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
6. 【5.10】P1164 小A点菜
题目链接：https://www.luogu.com.cn/problem/P1164
【分析】
01背包的变种，构建二维dp矩阵，f[i][j]表示前i个菜品恰好花费j元的方案数，二维可以优化到一维，这里采用二维解法。
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int a[110], f[110][10010];
void solve()
{
int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 0; i <= n; i ++) f[i][0] = 1;
for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++)
{
f[i][j] += f[i - 1][j];
if (j >= a[i]) f[i][j] += f[i - 1][j - a[i]];
}
cout << f[n][m] << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
7. 【5.11】P1019 [NOIP 2000 提高组] 单词接龙
题目链接：https://www.luogu.com.cn/problem/P1019
【分析】
考察搜索＋字符串处理。
【AC_Code】
#include <iostream>
#include <string>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
string s[25]; int n, vis[25], ans;
string check(string s1, string s2)
{
for (int i = 1; i < s1.length() && i < s2.length(); i ++)
{
if (s1.substr(s1.length() - i, i) == s2.substr(0, i))
return (s1.substr(0, s1.length() - i) + s2);
}
return "0";
}
void dfs(string drag)
{
if (drag.size() > ans) ans = drag.size();
for (int i = 0; i < n; i ++)
{
if (vis[i] == 2) continue;
if (check(drag, s[i]) != "0") { vis[i] ++; dfs(check(drag, s[i])); vis[i] --; }
}
}
void solve()
{
cin >> n; for (int i = 0; i < n; i ++) cin >> s[i];
char c; cin >> c;
for (int i = 0; i < n; i ++)
{
if (s[i][0] == c) { vis[i] ++; dfs(s[i]); vis[i] --; }
}
cout << ans << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
结语
感谢您的阅读！期待您的一键三连！欢迎指正！
