洛谷100题计划(20/100)
P1147 连续自然数和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意就是找一段连续的区间,使得区间和为\(M\),很容易发现,其实这个区间就是一个等差数列,所以\(区间和 = \frac{(首项+末项)\times 项数}{2}\),假设首项为\(L\),末项为\(R\),那么可以得出\(\frac{(L+R)\times (R-L+1)}{2}=M\),全部展开再化简可以得到\(R^2+R+(2M-L^2+L)=0\),我们可以去枚举\(L\),通过解方程求出\(R\),首先肯定要有解,即\(b^2-4ac>0\),又易知一元二次方程解\(x = \frac{-b\pm \sqrt{b^2-4ac}}{2a}\),小于\(L\)的直接就不看了,对于大于\(L\)的\(R\),我们只要看它是不是整数即可
#include<bits/stdc++.h>
using i64 = long long;
using namespace std;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
double M;
cin >> M;
vector<PII> v;
for (i64 L = 1; L < M; L ++) {
if (1 - 4 * (L - 2 * M - L * L) >= 0) {
double R = (-1 + sqrt(1 - 4 * (L - 2 * M - L * L))) / 2.0;
if (R == (int)R && R > L) {
cout << L << ' ' << R << '\n';
}
}
}
return 0;
}
P1125 [NOIP2008 提高组] 笨小猴 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
按照题意模拟即可(原来做过就直接上代码了
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int mod = 47;
char s1[N], s2[N];
int n, a, b, c, ss[N];
bool perim(int x)
{
if (x < 2) return false;
for (int i = 2; i <= sqrt(x); i++)
if (x % i == 0) return false;
return true;
}
int main()
{
cin >> s1;
for (int i = 0; i < strlen(s1); i++)
ss[s1[i] - 'a'] ++;
int maxn = -1, minn = N ;
for (int i = 0; i < 26; i++)
{
if (ss[i] == 0) continue;
maxn = max(maxn, ss[i]);
minn = min(minn, ss[i]);
}
if (perim(maxn - minn))
cout << "Lucky Word\n" << maxn - minn << endl;
else
cout << "No Answer\n" << 0 << endl;
return 0;
}
P1605 迷宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目数据很小,随便搜应该都能过(
按我以前的思路来看就是先把障碍点标记,然后从起点上下左右地去搜
#include<bits/stdc++.h>
using namespace std;
int maap[6][6], n, m, t, sx, sy, fx, fy, zx, zy, ans;
bool hehe[6][6] = {0};
int v[] = {1, 0, -1, 0}, u[] = {0, 1, 0, -1};
void dfs(int sx, int sy, int fx, int fy)
{
if (sx == fx && sy == fy)
{
ans++;
return ;
}
else
{
for (int i = 0; i < 4; i++)
{
int x, y;
x = sx + v[i];
y = sy + u[i];
if ((hehe[x][y] == 0) && (maap[x][y] == 1))
{
hehe[sx][sy] = 1;
dfs(x, y, fx, fy);
hehe[sx][sy] = 0;
}
}
}
return ;
}
int main()
{
cin >> n >> m >> t >> sx >> sy >> fx >> fy;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
maap[i][j] = 1;
for (int i = 1; i <= t; i++)
{
cin >> zx >> zy;
maap[zx][zy] = 0;
}
dfs(sx, sy, fx, fy);
cout << ans;
return 0;
}
P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
很经典的一道题,一道优先队列的入门题,就是将全部果子都放进优先队列里,每次取堆顶的两个合并然后又放进去,直到剩一个为止
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int main() {
int n, m;
priority_queue<int, vector<int>, greater<int>> Q;
cin >> n;
for (int i = 0; i < n; i ++) {
cin >> m;
Q.push(m);
}
int ans = 0;
while (Q.size() > 1) {
int u = Q.top();
Q.pop();
int v = Q.top();
Q.pop();
ans += u + v;
Q.push(u + v);
}
cout << ans << endl;
return 0;
}
P1037 [NOIP2002 普及组] 产生数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这题感觉坑点有点小多,首先你如果没用高精度的话就要用\(int128\),因为最后结果可能会爆long long,其次不能直接用字符串去递归,会爆\(MLE\)(亲身经历,好的方法其实是去递归每次能更换哪些数字,按题中例子来看\(234\),\(2\)可以换成\(2,5\),可更换\(2\)种,\(3\)可以换成\(3,6\),也可更换\(2\)种,除此之外没了,所以答案就是\(2\times 2=4\),所以我们直接去遍历每个数字,看每个数字能更换多少种,然后全部乘起来即可,复杂度\(\mathcal{O}(n2^k)\)
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
inline void print(__int128 x)
{
if(x<0){
putchar('-');
x=-x;
}
if(x>9) print(x/10);
putchar(x%10+'0');
}//int128不能直接输出,需要用快写,网上一搜就有了
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
int k;
cin >> s >> k;
vector<int> x(20), y(20);
vector<bool> v(20, false);
for (int i = 0; i < k; i ++) {
cin >> x[i] >> y[i];
}
int n = s.size();
auto dfs = [&](auto self, int si) {
if (v[si]) return ;
v[si] = true;
for (int i = 0; i < k; i ++) {
if (x[i] == si)
self(self, y[i]);
}
return ;
};
__int128 ans = 1;
for (int i = 0; i < n; i ++) {
dfs(dfs, s[i] - '0');
int num = 0;
for (int i = 0; i <= 9; i++)
num += v[i], v[i] = false;
ans *= num;
}
print(ans);
return 0;
}