B 枚举 贪心
想不到比我的思路简单多了 其实只需要按照给定的n c d 将题目要求的矩阵枚举出来就行了 枚举出来后 再将这些数字排个序
然后再将 题目里给的 $n^2$ 个数 排好序后 与我们枚举的数比较 如果完全一样 那就能组成要求的矩阵 反之就不能组成
这道题的关键点是啥呢
就是题目给出的元素行和列的关系式 使得我们排列出来的矩阵具有唯一性
只要将矩阵左上角的元素(也就是矩阵内最小的元素)从输入的数里面sort出来后 那根据给的c和d 排列出来的矩阵肯定是唯一的
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 3e5;
int b[N][N]; //存我们利用输入的公式 找出的正确矩阵
int a[M]; //题目里给的构成矩阵的n^2个数
int n, c, d;
int T;
vector<int> q;
void solve()
{
scanf("%d%d%d", &n, &c, &d);
q.clear();
memset(b, 0, sizeof b);
for (int i = 1; i <= n * n; i ++ ) scanf("%d", &a[i]);
sort(a + 1, a + n * n + 1); //先将给的数排序
int minn = a[1]; //找到给的数里面最小的数 将其作为矩阵的左上角开始枚举 左上角一定是矩阵内最小的数
b[1][1] = minn;
//先枚举第一列上所有元素
for (int i = 2; i <= n; i ++ )
{
b[i][1] = b[i - 1][1] + c;
}
//有了第一列的所有元素 那我们只需要对每一行进行枚举就行了 最终肯定满足每一行的元素上下关系都是符合公式要求的 是合法矩阵 感觉这个思路可以用在dfs 下午试试
for (int i = 1; i <= n; i ++ )
{
for (int j = 2; j <= n; j ++ )
{
b[i][j] = b[i][j - 1] + d;
}
}
//将其放进数组内
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= n; j ++ )
{
q.push_back(b[i][j]);
}
}
sort(q.begin(), q.end()); //装我们算出的合法矩阵的数组从前到后排序
//比较合法矩阵和题目给的数组是否完全相同 都已经sort排序过了
for (int i = 1; i <= n * n; i ++ )
{
if(q[i - 1] != a[i]) //注意q是从0开始存的合法矩阵
{
puts("NO");
return;
}
}
puts("YES");
return;
}
int main()
{
scanf("%d", &T);
while (T -- )
{
solve();
}
return 0;
}
贪心的思路和枚举差不多
其实不管你一道题用什么方法去解决 解题思想都是一致的
放在左上角的一定是 a 中最小的那一个元素,我们以这个最小的元素按题意构造,如果能跟原数组一致,那么就输出Yes。
#include <bits/stdc++.h>
using namespace std;
int n, c, d;
int T;
vector<int> q;
void solve()
{
scanf("%d%d%d", &n, &c, &d);
q.clear();
vector<int> a(n * n); //这里必须在括号内写上范围
for (int i = 0; i < n * n; i ++ ) cin >> a[i];
sort(a.begin(), a.end()); //先将给的数排序
int minn = a[0]; //找到给的数里面最小的数 将其作为矩阵的左上角开始枚举 左上角一定是矩阵内最小的数
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < n; j ++ )
{
q.push_back(minn + i * c + j * d); //简直精妙 比枚举方便多了 这一步操作就可以直接将合法矩阵所有数全部求出 并且存进数组
}
}
sort(q.begin(), q.end()); //装我们算出的合法矩阵的数组从前到后排序
//将其与原数组比较 由于这次都是从数组头节点开始放的数 可以直接比较 方便
if (a == q) puts("YES");
else puts("NO");
return;
}
int main()
{
scanf("%d", &T);
while (T -- )
{
solve();
}
return 0;
}
用深搜 无非就是我们将给定的元素排好序 一个一个搜索 看是否能满足题目给的横向和纵向的公式 但是不好处理一个元素会搜两次不好用st[][]标记的问题
下面是考试写的代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5;
int T;
int a[N];
bool st[N];
int n, c, d;
string s[10010];
bool dfs(int x, int y, int z)
{
if (z > n * n)
{
if (x == n && y == n)
{
return true;
}
else return false;
}
for (int i = 1; i <= n * n; i ++ )
{
if (!st[i])
{
if ((a[x] + c == a[i] ) && x < n)
{
//st[i] = true;
dfs(x + 1, y, z + 1);
}
else if ((a[x] + d == a[i] ) && y < n)
{
//st[i] = true;
dfs(x, y + 1, z + 1);
}
}
}
}
int main()
{
scanf("%d", &T);
for (int i = 1; i <= T; i ++ )
{
memset(a, 0, sizeof a);
memset(st, 0, sizeof st);
scanf("%d%d%d", &n, &c, &d);
for (int i = 1; i <= n * n; i ++ )
{
scanf("%d", &a[i]);
}
sort(a + 1, a + n * n + 1);
if (dfs(1, 1, 1)) s[i] = "YES";
else s[i] = "NO";
}
for (int i = 1; i <= T; i ++ ) cout << s[i] << endl;
return 0;
}
C 枚举 + 剪枝优化
做的时候写出来了暴力代码 但没时间优化了
其实优化思路是对的 就是分别对队列的头部和尾部进行处理
海怪总共要攻击k次 那么就会在头部攻击 $(k + 1) / 2$ 次 尾部攻击 $k / 2$ 次
注意 头部的分子加1的原因是 海怪先攻击队列头部 所以是向上取整
那问题就很简单了 我们对这个队列正反都遍历一遍即可 因为海怪不管头船有没有被打掉 都会去打尾船 所以攻击头部和尾部不会互相影响
正着打$(k + 1) / 2$ 看有多少船被打掉
反着打$k / 2$ 看有多少船被打掉
最后相加即可
考虑特殊情况 如果总 船只耐久度 小于等于 k,那么所有船能够全部被击没 直接返回船只数目
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
int n;
int T;
int a[N];
int ans[10010];
LL k;
LL sum;
int main()
{
scanf("%d", &T);
for (int i = 1; i <= T; i ++ )
{
int cnt = 0;
sum = 0;
memset(a, 0, sizeof a);
scanf("%d%lld", &n, &k);
for (int j = 1; j <= n; j ++ )
{
scanf("%d", &a[j]);
sum += a[j];
}
if (k >= sum) //攻击次数大于所有船只耐久度总和
{
ans[i] = n;
}
else
{
//先枚举攻击船只头部
int x = (k + 1) / 2;
for (int m = 1; m <= n; m ++ )
{
if (a[m] <= x)
{
x -= a[m];
cnt ++ ;
}
else break; //不能击沉当前船只 直接退出 因为必须先击败当前头部船只 才能攻击下一个船只
}
//枚举攻击船的尾部
x = k / 2;
for (int m = n; m >= 1; m -- )
{
if (a[m] <= x)
{
x -= a[m];
cnt ++ ;
//cout << x << endl;
}
else break;
}
ans[i] = cnt;
}
}
for (int i = 1; i <= T; i ++ ) printf("%d\n", ans[i]);
return 0;
}
像这种测试用例的题 每次T的for循环就要占用一个i 导致后面读入a[]就只能用a[j] 很容易写错 我也得去学学写在solve()函数内
比赛的时候写的暴力代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
int n;
int T;
int a[N];
int ans[10010];
LL k;
deque<int> q;
int main()
{
scanf("%d", &T);
for (int i = 1; i <= T; i ++ )
{
int cnt = 0;
q.clear();
memset(a, 0, sizeof a);
scanf("%d%lld", &n, &k);
for (int j = 1; j <= n; j ++ )
{
scanf("%d", &a[j]);
q.push_back(a[j]);
}
while (q.size() >= 2)
{
int t = q.front();
q.pop_front();
int l = q.back();
q.pop_back();
//cout << l << endl;
if (k)
{
t --;
k --;
q.push_front(t);
if (!t)
{
//cout << k << endl;
cnt ++ ;
q.pop_front();
}
if (k)
{
l -- ;
q.push_back(l);
//cout << l << endl;
k -- ;
if (!l)
{
cnt ++ ;
q.pop_back();
}
}
else break;
}
else break;
}
if (q.size())
{
int t = q.front();
if (k >= t) cnt ++ ;
}
ans[i] = cnt;
}
for (int i = 1; i <= T; i ++ ) printf("%d\n", ans[i]);
return 0;
}
D 双指针
刚开始题意都理解错了
实际上是要找在a数组内找和b数组一样长的子序列c 要求是c序列满足至少有k个元素跟b的一样
关键点就是c序列要跟b数组一样长 这个最开始理解错了
那我们其实可以用滑动窗口的思想
假设 b数组长度为m 那我们就可以在a数组内从前向后去维护一段长为m的子序列c 利用双指针维护这段子序列的头节点 和 尾节点
我们只需要记录b数组内含有的元素及其个数 再看序列c内包不包含b数组内含有的元素 包含一个贡献度加1 当贡献度达到k时就可以记录为一个合法的字段
当右指针移动到长度m+1时左指针 就要右移
特殊情况 比如b数组内有两个2 当前c序列新滑入的元素也是2 但c序列本身就有两个2了
此时 新加入的2就不能产生贡献度 即使他与b数组元素2相符合
所以我们在判断能否产生贡献度时 就要加入当前b数组和c数组元素个数的比较
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int T, a, m, k;
int arr[N], brr[N];
void solve()
{
scanf("%d%d%d", &a, &m, &k);
map<int, int> mp; //开一个map存b中的重复元素 因为我们最终是找b数组中的元素的值 与其顺序无关 因为可以重新排列 只要有这个数就行
for (int i = 1; i <= a; i ++ ) scanf("%d", &arr[i]);
for (int i = 1; i <= m; i ++ )
{
scanf("%d", &brr[i]);
mp[brr[i]] ++ ; //将b数组这个位置存的数拎出来 在map里记录其值和对应的数量
}
map<int, int> temp; //开一个map存我们长度为m的区间里的数字和其个数
int res = 0;
int cnt = 0;
//开始用左右指针l r 维护区间长度
for (int l = 1, r = 1; r <= a; r ++ )
{
temp[arr[r]] ++ ; //右端点指针向右移动一位 会让当前指针指向的元素 在我们所维护的区间内个数加一
//关键点 如果此时右移所产生的新元素及其个数 在b数组内是可以放得下的 那我们就将贡献度加1 比如说b数组里有2个2 原本a数组有1个2 因为这次循环区间右移一位又加了个2进来 一共2个2了 但b区间本来也有两个2 本次新加的2也会产生一个贡献度
if (temp[arr[r]] <= mp[arr[r]]) cnt ++ ; //注意mp和temp里一定都是判断的当前指针指向的arr[r] 刚开始写成brr[r]debug半天
//如果右端点此时比m大了 那我们初始的窗口就已经形成 此后需要开始滑动这个长度为m的窗口 也就是右指针右移一位 左指针也需要右移一位
if (r > m)
{
temp[arr[l]] -- ; //该元素在维护区间内的数量-1
//滑出窗口也要判断滑出的元素是否会影响现有数组内的贡献度 如果b数组有2个2 但此时a数组有3个2 位于头节点的2滑出就不会影响贡献度 反之则会影响
if (temp[arr[l]] < mp[arr[l]]) cnt -- ; //记住这里是严格小于 因为我们上一句话就把要滑出的元素数量给减了 现在是判断剩余的区间内剩余的元素个数
//cout << cnt << endl;
l ++ ; //左指针右移一位
}
if (r > m && cnt >= k) //当维护的区间已经开始滑动
{
res ++ ; //当区间长度等于m且贡献度已经够了 合法子序列数量加一
//cout << r << endl;
}
//特判一下起始区间符不符合合法子序列的情况
if (r == m && cnt >= k) res ++ ;
}
printf("%d\n", res);
return;
}
int main()
{
scanf("%d", &T);
while (T -- )
{
solve();
}
return 0;
}