6.9总结(省赛排位赛1)
省赛排位赛1
省赛排名赛1 – Virtual Judge (vjudge.net)
思路:
其实就是一个斐波拉契数列,当前项=前两项之和,先将范围内的数全部存起来放进一个数组,再进行累加查询
代码:
#define _CRT_SECURE_NO_WARNINGS 1
#include
using namespace std;
typedef long long ll;
ll f[1100];
int cnt;
int main()
{
f[1] = 1, f[2] = 1;
cnt = 2;
while (f[cnt] <= 1e15)
{
f[cnt + 1] = f[cnt] + f[cnt - 1];
cnt++;
}
ll n;
while (scanf("%lld", &n) != EOF)
{
int flag = 0;
for (int i = 1; i <= cnt; i++)
{
ll sum = 0;
for (int j = i; j n)
{
break;
}
}
}
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
省赛排名赛1 – Virtual Judge (vjudge.net)
思路:
利用并查集和弗洛伊德,对需要传递的对象都进行标记,经过处理后使他们的父亲发生相应的改变,最后对数组进行查询累加即可
代码:
#include
using namespace std;
int fa[100010];
int v[101][101];
int main()
{
int n;
cin >> n;
for (int i = 1; i > t;
while (t != 0)
{
v[i][t] = 1;
cin >> t;
}
}
for (int i = 1; i <= n; i++)
{
fa[i] = i;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (v[i][j] || (v[i][k] && v[k][j]))
v[i][j] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (v[i][j] == 1)
fa[j] = fa[i];
int ans = 0;
for (int i = 1; i <= n; i++)
if (fa[i] == i)
ans++;
cout << ans;
return 0;
}
省赛排名赛1 – Virtual Judge (vjudge.net)
思路:
规律题,单数和复数方向刚好相反(循环里进行特判即可),每个n阶数组有2n-1条线
代码:
#include
using namespace std;
typedef long long ll;
ll a[1010][1010];
int n;
void solve()
{
int m = 1;
for (int k = 1; k = 0; i++, j--)
{
if (k % 2 == 0)
{
a[i][j] = m;
m++;
}
else
{
a[j][i] = m;
m++;
}
}
}
for (int k = n + 1; k < 2 * n; k++)
{
for (int i = n - 1, j = k - 1 - i; j <= n - 1; i--, j++)
{
if (k % 2 == 0)
{
a[j][i] = m;
m++;
}
else
{
a[i][j] = m;
m++;
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << a[i][j] << " ";
}
cout <> n;
solve();
return 0;
}
省赛排名赛1 – Virtual Judge (vjudge.net)
思路:
简单的二分查找题,直接套模板都行
代码:
#include
using namespace std;
int a[1000010];
int n, m, l, r, mid, x;
int main()
{
cin >> n;
for (int i = 1; i > a[i];
}
cin >> m;
while (m--)
{
cin >> x;
if (x < a[1])
{
cout << a[1] < a[n])
{
cout << a[n] << endl;
}
else
{
l = 1;
r = n;
while (l + 1 x)
{
r = mid;
}
else
{
l = mid;
}
}
if (abs(a[l] - x) <= abs(a[r] - x))
{
cout << a[l] << endl;
}
else
{
cout << a[r] << endl;
}
}
}
return 0;
}
省赛排名赛1 – Virtual Judge (vjudge.net)
思路:
当前一个数k在集合m里,由题可知2k+1,3k+1都在集合里,每一个数又可以延伸出两个数到集合里,每判断一个数k时,顺便对2k+1,3k+1也进行判断,当这个数大于我们输入的数时可知是不可能有结果的,因为无论如何k的倍数都是大于k的,而x小于k
代码:
#include
using namespace std;
typedef long long ll;
ll k, x;
int judge(int a)
{
if (a > k >> c >> x;
if (judge(k))
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
return 0;
}
省赛排名赛1 – Virtual Judge (vjudge.net)
思路:
利用vector建图,从第一个点的第一条边进行搜索,对其边相邻的点一直搜索下去
代码:
#include
using namespace std;
vectore[100010];
bool vis[10010];
int ans[10010];
int n, m;
void dfs(int x, int y)
{
vis[y] = false;
ans[x] = max(ans[x], y);
for (auto v : e[y])if (vis[v])dfs(x, v);
}
int main()
{
cin >> n >> m;
for (int i = 1; i > x >> y;
e[x].push_back(y);
}
for (int i = 1; i <= n; i++)
{
memset(vis, true, sizeof(vis));
dfs(i, i);
}
for (int i = 1; i <= n; i++)
{
cout << ans[i] << " ";
}
return 0;
}