洛谷100题DAY1

你的名字 2024-03-24 20:53 92阅读 0赞

### 1.P1002 \[NOIP2002 普及组\] 过河卒 ###

对地图整体进行偏移， 使起始点从(0, 0)变为(1, 1)

注：这里是为了dp\[i - 1\]\[j\] 与dp\[i\]\[j - 1\]不会被减成负数

进行dp时注意dp\[1\]\[1\]已经提前有值，故在整体dp时记得跳过

不必将两轴边界进行初始化，因为i - 1 = 0此时dp\[i\]\[j\]一道为0

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1010;
    long long n, m, x2, y2, dp[N][N];
    bool st[N][N];
    int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1}; 
    int main()
    {
    	cin >> n >> m >> x2 >> y2;
    	n ++, m++, x2 ++, y2 ++;
    	st[x2][y2] = true;
    	for(int i = 0; i < 8; i ++)
    	{
    		int a = x2 + dx[i];
    		int b = y2 + dy[i];
    		if(a >= 1 && a <= n && b >= 1 && b <= m)
    		st[a][b] = true;
    	}
    	dp[1][1] = 1;
    	for(int i = 1; i <= n; i ++)
    	{
    		for(int j = 1; j <= m; j ++)
    		{
    			if(i == 1 && j == 1)continue;
    			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    			if(st[i][j])dp[i][j] = 0;
    		}
    	}
    	cout << dp[n][m];
    }

### 2.P1003 \[NOIP2011 提高组\] 铺地毯 ###

简单模拟，只需循环看地毯是否在范围内

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 10;
    int n, a[N], b[N], c[N], d[N], ans, x, y;
    int main()
    {
    	cin >> n;
    	for(int i = 1; i <= n; i ++) 
    	{
    		cin >> a[i] >> b[i] >> c[i] >> d[i];
    	}
    	cin >> x >> y;
    	for(int i = 1; i <= n; i ++)
    	{
    		if(x >= a[i] && x <= a[i] + c[i] && y >= b[i] && y <= b[i] + d[i])
    		{
    			ans = i;
    		}
    	}
    	if(ans == 0)cout << -1;
    	else cout << ans;
    	return 0;
    }

### 3.P1008 \[NOIP1998 普及组\] 三连击 ###

set中的元素是按照一定的顺序进行存储和访问的（默认按照升序排序）

**每个元素只会在set中出现一次！！！一次！！！**

将i的三倍在大于100小于1000的范围进行循环，一定为三位数，统计不重复数字的个数（当然这里不包含0）如果不重复数字的个数等于9故正确

#include<bits/stdc++.h>
    using namespace std;
    bool check(int a, int b, int c)
    {
    	set<int> st;
    	while(a)
    	{
    		st.insert(a % 10);
    		a /= 10;
    	}
    	while(b)
    	{
    		st.insert(b % 10);
    		b /= 10;
    	}
    	while(c)
    	{
    		st.insert(c % 10);
    		c /= 10;
    	}
    	for(auto i : st)if(i == 0)return false;
    	return st.size() == 9;
    }
    int main()
    {
    	for(int i = 100; i * 3 < 1000; i ++)
    	{
    		int j = i * 2, k = i * 3;
    		if(check(i, j, k))cout << i << ' ' << j << ' ' << k << '\n';
    	}
    	return 0;
    }

### 4.P1028 \[NOIP2001 普及组\] 数的计算 ###

**竟然不太会！！！**

**但是第二天（好像）会了（误打误撞）**

用f\[x\]来表示此组合以x开头之后可以组成数的个数，如果有找过x的记录就返回记录值，要不f\[x\]为1，不断一一累加

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 10;
    int n, f[N];
    int dfs(int x)
    {
    	if(f[x])return f[x];
    	f[x] = 1;
    	for(int i = 1; i <= x / 2; i ++)
    	{
    		f[x] += dfs(i); 
    	}
    	return f[x];
    }
    int main()
    {
    	cin >> n;
    	cout << dfs(n);
    	return 0;
    }

### 5.P1029 \[NOIP2001 普及组\] 最大公约数和最小公倍数问题 ###

a与b的值一定在x与y的范围内

![abd1633d6df74f37a4ae244116d4309f.png][]

#include<bits/stdc++.h>
    using namespace std;
    long long gcd(int a, int b)
    {
    	return b == 0 ? a : gcd(b, a % b);
    }
    long long lcm(int a, int b)
    {
    	return a * b / gcd(a, b);
    }
    int x, y, ans;
    int main()
    {
    	cin >> x >> y;
    	for(int i = x; i <= y; i ++)
    	{
    		int j = x * y / i;
    		if(j * i != x * y)continue;
    		if(gcd(i, j) == x && lcm(i, j) == y)ans ++;
    	}
    	cout << ans;
    	return 0;
    }

[abd1633d6df74f37a4ae244116d4309f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/c0c00bd5d24f4309b8ea4df83f81dfce.png