D - 刻录光盘
https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P2835
思路：
利用并查集和弗洛伊德，对需要传递的对象都进行标记，经过处理后使他们的父亲发生相应的改变，最后对数组进行查询累加即可
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define mod 100003
#define inf 1e9+7
typedef long long ll;
ll n, m, t, cnt = 1, ans, sum1, sum2, num;
ll x, y, z;
ll a[N], b[N], c[N], times[N], dp[N];
ll dis[205][205], head[N];
bool vis[N];
typedef pair<int, int>pii;
priority_queue<pii, vector<pii>, greater<pii>>q;
struct node {
ll a, b, c;
}f[N];
map<int, int>mp;
set<int>s;
vector<int>v;
ll gcd(ll a, ll b) {
return b > 0 ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
return a * b / gcd(a, b);
}
int find(int x)
{
if (times[x] == x)
return x;
return times[x] = find(times[x]);
}
int main()
{
cin >> t;
for (int i = 1; i <= t; i++) {
times[i] = i;
}
/*for (int i = 1; i <= t; i++) {
for (int j = 1; j <= t; j++) {
dis[i][j] = 0;
}
}*/
for (int i = 1; i <= t;i++) {
while (cin >> n && n != 0) {
dis[i][n] = 1;
}
}
for (int k = 1; k <= t; k++) {
for (int i = 1; i <= t; i++) {
for (int j = 1; j <= t; j++) {
if (dis[i][k]&&dis[k][j]) {
dis[i][j] = 1;
}
}
}
}
for (int i = 1; i <= t; i++) {
for (int j = 1; j <= t; j++) {
if (dis[i][j]) {
times[j] = times[i];
}
}
}
ans = 0;
for (int i = 1; i <= t; i++) {
if (times[i] == i)
ans++;
}
cout << ans << endl;
return 0;
}F - 蛇形填充数组https://vjudge.net/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-T1143
思路：
规律题，单数和复数方向刚好相反（循环里进行特判即可），每个n阶数组有2n-1条线
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 2000005
#define mod 100003
#define inf 1e9+7
typedef long long ll;
ll n, m, t, cnt = 1, ans, sum, num,minn;
ll x, y, z;
ll dp[15][15];
struct node {
ll a, b, c;
}f[N];
map<ll, ll>mp;
set<int>s;
vector<int>v;
ll gcd(ll a, ll b) {
return b > 0 ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
return a * b / gcd(a, b);
}
int main()
{
cin >> n;
ans = sum = 0;
for (int i = 2; i <= 2*n; i++) {
sum++;
if (sum % 2 == 0) {
for (int k = i - 1; k >= 1; k--) {
if (i - k <=n&& k <= n) {
dp[i - k][k] = ++ans;
}
}
}
else {
for (int k = 1; k <=i - 1; k++) {
if (i - k <= n&&k<=n) {
dp[i - k][k] = ++ans;
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << dp[i][j] << " ";
}
cout << endl;
}
return 0;
}
J - 判断元素是否存在https://vjudge.net/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-T1184
思路：
当前一个数k在集合m里，由题可知2k+1,3k+1都在集合里，每一个数又可以延伸出两个数到集合里，每判断一个数k时，顺便对2k+1,3k+1也进行判断，当这个数大于我们输入的数时可知是不可能有结果的，因为无论如何k的倍数都是大于k的，而x小于k
代码：
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define mod 100003
#define inf 1e9+7
typedef long long ll;
ll n, m, t, cnt = 1, ans, sum, num,minn;
ll x, y, z;
ll dp[N];
struct node {
ll a, b, c;
}f[N];
map<ll, ll>mp;
set<ll>s;
vector<ll>G[N];
ll gcd(ll a, ll b) {
return b > 0 ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
return a * b / gcd(a, b);
}
bool dfs(ll n) {
if (n > y)
return 0;
if (n == y)
return 1;
if (n < y)
return dfs(2 * n + 1) || dfs(3 * n + 1);
}
int main()
{
cin >> x;
getchar();
cin >> y;
if (dfs(x))
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
