A - Lacked Number

Code

void solve()
{
    string s;	cin >> s;
    for (int i = 0; i < s.length(); i++)    st[s[i] - '0']++;
    	
    for (int i = 0; i < 10; i++)
    	if (!st[i])
    	{
    		cout << i;
    		return 0;
    	}
}

B - Slimes

Code

void solve()
{
    int a, b, k;	cin >> a >> b >> k;
    
    int res = 0;
    while (a < b)
    {
    	a *= k;
    	res++;
    }
    
    cout << res << endl;
}

C - Dice Sum(背包方案数)

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 55, M = N * N, mod = 998244353;

int n, m, k, f[N][M];  // f[i][j]表示选择i个数字总和为sum的方案数

int main()
{
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++)	f[1][i] = 1;  // 初始化
	
	for (int i = 1; i < n; i++)
		for (int j = 0; j < k; j++)
			for (int k = 1; k <= m; k++)
				f[i + 1][j + k] = (f[i + 1][j + k] + f[i][j]) % mod;
	
	int res = 0;
	for (int i = 0; i <= k; i++)	res = (res + f[n][i]) % mod;
	
	cout << res << endl;
	return 0;
}

D - Range Count Query(容器\二分)

题目大意

给定一个数组$a$和$l, r, x$查询区间[l, r]内等于$x$的数的个数

解题思路

对于每个数存储它的坐标,对于每个查询进行l, r位置的二分查找

void solve()
{
    int n;	cin >> n;
	vector<vector<int>> pos(n + 1);
	
	for (int i = 1; i <= n; i++)  // 坐标从0开始
	{
		int x;	cin >> x;
		pos[x].push_back(i);
	}
	
	int q;	cin >> q;
	while (q--)
	{
		int l, r, x;	cin >> l >> r >> x;
		cout << lower_bound(pos[x].begin(), pos[x].end(), r + 1) - lower_bound(pos[x].begin(), pos[x].end(), l) << endl;
	}	
}

E - K-colinear Line

题目描述

给定$N$个二维坐标和$K$,问能形成多少个经过$K$个或$K$个以上点的直线

解题思路

当$k = 1$:经过一点可以形成无数条直线
当$k > 1$:可以先确定两个点, 然后对两个点之后的每个点进行枚举,
如果斜率一致,表明在一条直线上。

假设有$3$个点, $P(x, y), A(x_0, y_0), B(x_1, y_1)$
如果三个点在一条直线上, 则满足$(y_1 - y)/(x_1 - x) = (y_0 - y)/(x_0 - x)$
本公式可以转化为$(y_1 - y) * (x_0 - x) = (y_0 - y) * (x_1 - x)$来避免除法

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
using namespace std;
const int N = 330;
typedef pair<int, int> PII;
 
int n, k, flag[N][N];
vector<int> now;
PII p[N];
 
bool check(int a, int b, int c)  // 判断是否在一直线
{
	int v1 = (p[b].y - p[a].y)*(p[c].x - p[a].x);
	int v2 = (p[b].x - p[a].x)*(p[c].y - p[a].y);
	return (v1 == v2);
}
 
signed main()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++)	cin >> p[i].x >> p[i].y;
	
	if (k == 1)	
	{
		cout << "Infinity" << endl;
		return 0;
	} 
	
	memset(flag, true, sizeof flag);
	
	int res = 0, cnt;
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (flag[i][j])
			{
				cnt = 2;
				now.clear();
				now.push_back(i);
				now.push_back(j);
				for (int k = j + 1; k < n; k++)  // 向后枚举每个点是否符合
					if (check(i, j, k))
					{
						cnt++;
						now.push_back(k);
					}
				for (int k = 0; k < cnt; k++)
					for (int l = k + 1; l < cnt; l++)
						flag[now[k]][now[l]] = false;  // 对于符合条件的点所构成的直线标记为使用过。避免重复
				
				if (cnt >= k)	res++;
			}
 
	cout << res << endl;
	return 0;
} 
上一篇 下一篇