6.9总结（省赛排位赛1）

省赛排位赛1
省赛排名赛1 - Virtual Judge (vjudge.net)

思路：

其实就是一个斐波拉契数列，当前项=前两项之和，先将范围内的数全部存起来放进一个数组，再进行累加查询

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
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 <= cnt; j++){sum += f[j];if (sum == n){flag = 1;}else if (sum > n){break;}}}if (flag)cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}

省赛排名赛1 - Virtual Judge (vjudge.net)

思路：

利用并查集和弗洛伊德，对需要传递的对象都进行标记，经过处理后使他们的父亲发生相应的改变，最后对数组进行查询累加即可

代码：

#include<bits/stdc++.h>
using namespace std;
int fa[100010];
int v[101][101];
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){int t;cin >> 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<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1010][1010];
int n;
void solve()
{int m = 1;for (int k = 1; k <= n; k++){for (int i = 0, j = k - 1; j >= 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 << endl;}
}
int main()
{cin >> n;solve();return 0;
}

省赛排名赛1 - Virtual Judge (vjudge.net)

思路：

简单的二分查找题，直接套模板都行

代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int n, m, l, r, mid, x;
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}cin >> m;while (m--){cin >> x;if (x < a[1]){cout << a[1] << endl;}else if (x > a[n]){cout << a[n] << endl;}else{l = 1;r = n;while (l + 1 < r){mid = (l + r) / 2;if (a[mid] > 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<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll k, x;
int judge(int a)
{if (a < k){return 0;}else if (a == k){return 1;}else{return judge(k * 2 + 1) || judge(k * 3 + 1);}
}
int main()
{char c;cin >> k >> c >> x;if (judge(k)){cout << "YES" << endl;}else{cout << "NO" << endl;}return 0;
}

省赛排名赛1 - Virtual Judge (vjudge.net)

思路：

利用vector建图，从第一个点的第一条边进行搜索，对其边相邻的点一直搜索下去

代码：

#include<bits/stdc++.h>
using namespace std;
vector<int>e[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 <= m; i++){int x, y;cin >> 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;
}