2023年10月14日
Div.3 Round903 A Don't Try to Count
题目大意
问把一个串拼接多少次，可以让另一个串为拼接串的子串。
题目理解
用find函数，暴力枚举一下。最多次数不超过6次
代码实现
string x, s;
bool check(string k)
{
if(k.find(s) <= k.size() - 1) return true;
else return false;
}
void solve()
{
int n, m;
cin >> n >> m;
cin >> x >> s;
int res = 0;
if(check(x)) cout << res << endl;
else{
bool flag = 0;
for(int i = 1; i <= 6; i++)
{
x += x;
res++;
if(check(x))
{
flag = 1;
break;
}
}
if(flag) cout << res << endl;
else cout << -1 << endl;
}
return;
}
Div.3 Round903 B Three Threadlets
题目大意
给三个整数，可否只切分三次及以下，把所有的整数切分成一样的。
题目理解
那么切割次数最少的结果一定是，三个数的最大公约数。然后我们计算切到最大公约数需要的次数即可
代码实现
ll gcd(ll a, ll b)
{
if(b > 0) return gcd(b, a % b);
return a;
}
void solve()
{
ll a, b, c;
cin >> a >> b >> c;
ll k = gcd(a, b);
k = gcd(k, c);
ll cnt = 0;
cnt += (a / k) - 1;
cnt += (b / k) - 1;
cnt += (c / k) - 1;
if(cnt > 3) cout << "NO" << endl;
else cout << "YES" << endl;
return;
}
Div.3 RoundC Perfect Square
题目大意
要让一个矩形旋转90度后，保持不变，问最小的操作次数。
题目理解
旋转90度不变，及旋转九十度那四个点对应是相等的。那么，把那四个点就需要表示出来。因为要操作次数最小，每次也只能变成下一个字符，所以我们采用贪心策略。
让它们都变成最大的，那么就是四个和最大的做差求和即可。
代码实现
const int N = 1e3 + 10;
string a[N];
void solve()
{
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
ll res = 0;
for(int i = 0; i < n / 2; i++)
{
for(int j = i; j < n - i - 1; j++)
{
int x1 = i, y1 = j; // 当前点的位置
int x2 = j, y2 = (n - 1) - x1; // 90度的位置
int x3 = (n - 1) - x1, y3 = (n - 1) - y1; // 180度的位置
int x4 = (n - 1 - j), y4 = i; // 270 度的位置
char c1 = a[x1][y1], c2 = a[x2][y2], c3 = a[x3][y3], c4 = a[x4][y4];
char m = max(c1, c2);
m = max(m, c3);
m = max(m, c4); // 取得最大值
res += m - c1 + m - c2 + m - c3 + m - c4; //计算差值
}
}
cout << res << endl;
return;
}
Div.3 Round907 D Divide and Equalize
题目大意
把一个数除约数，另一个数乘以刚才除的数字，问所有的数字能否变成一样的数。
题目理解
对每个书进行分解质因数，然后需要让分解出来的质因数的个数是n的倍数即可。
代码实现
void solve()
{
int n;
scanf("%d", &n);
unordered_map<int, int> mp;
vector<int> a(n);
int flag = 0;
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
if(i >= 1 && a[i] != a[i - 1])
flag = 1;
}
if(flag == 0)
{
printf("YES\n");
return;
}
for(int t = 0; t < n; t++)
{
for(int i = 2; i <= a[t] / i; i++)
if(a[t] % i == 0)
{
int s = 0;
while(a[t] % i == 0)
{
a[t] /= i;
s++;
}
if(!mp.count(i)) mp[i] = s;
else mp[i] += s;
}
if(a[t] > 1) mp[a[t]]++;
}
flag = 1;
for(auto p : mp)
{
if(p.y % n != 0)
flag = false;
}
if(flag == 1) printf("YES\n");
else printf("NO\n");
return;
}
Acwing10 有依赖的背包问题
题目理解
代码实现
- 方案一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 110, M = N * 2;
int h[N], ne[M], e[M], idx, w[N], v[N], f[N][N];
int n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
// 分组背包循环物品组，也就是循环u的子节点
for(int i = h[u]; ~i; i = ne[i])
{
int son = e[i]; // 取出子节点的编号
dfs(e[i]); // 继续递归处理子节点
// 开始分组背包的循环
// 首先是体积
for(int j = m - v[u]; j >= 0; j--) // 循环体积，这里是m - v[i]的
for(int k = 0; k <= j; k++) // 循环决策！因为我们的划分依据是体积，而不是选择物品
f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
}
// 因为我们还没有把u的价值算进去, 所以要加上
for(int i = m; i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + w[u];
for(int i = 0; i < v[u]; i++) f[u][i] = 0;
}
void solve()
{
cin >> n >> m;
int root;
for(int i = 1; i <= n; i++)
{
int a;
cin >> v[i] >> w[i] >> a;
if(a == -1) root = i; // 根节点的编号
else add(a, i);
}
// 递归处理树形dp
dfs(root);
cout << f[root][m]; // 根节点必选，且体积不过m时的价值最大值
return;
}
int main()
{
memset(h, -1, sizeof h);
int T = 1;
while(T--) solve();
return 0;
}
- 方案二
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 110, M = N * 2;
int h[N], ne[M], e[M], idx, w[N], v[N], f[N][N];
int n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
for(int i = v[u]; i <= m; i++) f[u][i] = w[u]; // 因为必选所以把他们初始化为w[u]
// 分组背包循环物品组，也就是循环u的子节点
for(int i = h[u]; ~i; i = ne[i])
{
int son = e[i]; // 取出子节点的编号
dfs(e[i]); // 继续递归处理子节点
// 开始分组背包的循环
// 首先是体积
for(int j = m; j >= v[u]; j--) // 循环体积，体积绝不能小于v[u]
for(int k = 0; k <= j - v[u]; k++) // 循环决策！因为我们的划分依据是体积，而不是选择物品
f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
}
}
void solve()
{
cin >> n >> m;
int root;
for(int i = 1; i <= n; i++)
{
int a;
cin >> v[i] >> w[i] >> a;
if(a == -1) root = i; // 根节点的编号
else add(a, i);
}
// 递归处理树形dp
dfs(root);
cout << f[root][m]; // 根节点必选，且体积不过m时的价值最大值
return;
}
int main()
{
memset(h, -1, sizeof h);
int T = 1;
while(T--) solve();
return 0;
}
Acwing11 背包问题求方案数（最优）
题目理解
代码实现
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1010;
int g[N][N], f[N][N], v[N], w[N];
int n, m;
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 0; i <= n; i++) g[i][0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
f[i][j] = f[i - 1][j];
g[i][j] += g[i - 1][j];
g[i][j] %= Mod;
if(j >= v[i])
{
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
if(f[i][j] == f[i - 1][j - v[i]] + w[i]){
g[i][j] += g[i - 1][j - v[i]];
g[i][j] %= Mod;
}
}
}
cout << g[n][m];
return;
}
int main()
{
int T = 1;
while(T--) solve();
return 0;
}
Acwing12 背包问题求具体方案（最优方案）
题目理解
代码实现
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1010;
int g[N][N], v[N], w[N], d[N][N];
int n, m;
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = n; i >= 1; i--)
for(int j = 1; j <= m; j++)
{
d[i][j] = d[i + 1][j];
if(j >= v[i])
d[i][j] = max(d[i][j], d[i + 1][j - v[i]] + w[i]);
}
int j = m;
for(int i = 1; i <= n; i++)
{
if(j >= v[i] && d[i][j] == d[i + 1][j - v[i]] + w[i])
{
cout << i << " ";
j -= v[i];
}
}
return;
}
int main()
{
int T = 1;
while(T--) solve();
return 0;
}