T1 game
题目大意
两个 \(2 × 2\) 的方格，问方格一能否通过将滑动操作变成方格二，X 代表空格
样例
AB
XC
AC
BX
NO
题目分析
数据范围很小，我们可以进行暴力搜索，对于有 X 的点就让它移动向两个方向移动一下，对于每一个 dfs 最多搜十次，时空复杂度 \(O(2^{10})\)
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
#define ck a[i][j] == 'X'
using namespace std;
const int N = 5;
const int MAX = 10;
int n = 2;
char a[N][N], b[N][N], c[N][N];
bool kk;
void dfs(int cnt)
{
//cout << cnt << endl;
if (cnt >= MAX) return ;
/*if (cnt == 1)
{
cout << a[1][1] << a[1][2] << endl;
cout << a[2][1] << a[2][2] << endl;
return ;
}*/
bool flag = 0;
for (rint i = 1; i <= n; i++)
{
for (rint j = 1; j <= n; j++)
{
if (a[i][j] != b[i][j])
{
flag = 1;
}
}
}
//if (cnt == 1) return ;
if (flag == 0)
{
kk = 1;
return ;
}
for (rint i = 1; i <= n; i++)
{
for (rint j = 1; j <= n; j++)
{
if (ck && i == 1 && j == 1)
{
a[1][1] = a[1][2]; a[1][2] = 'X';
dfs(++cnt);
cnt--;
a[1][2] = a[1][1]; a[1][1] = 'X';
a[1][1] = a[2][1]; a[2][1] = 'X';
dfs(++cnt);
cnt--;
a[2][1] = a[1][1]; a[1][1] = 'X';
}
else if (ck && i == 1 && j == 2)
{
a[1][2] = a[1][1]; a[1][1] = 'X';
dfs(++cnt);
cnt--;
a[1][1] = a[1][2]; a[1][2] = 'X';
a[1][2] = a[2][2]; a[2][2] = 'X';
dfs(++cnt);
cnt--;
a[2][2] = a[1][2]; a[1][2] = 'X';
}
else if (ck && i == 2 && j == 1)
{
a[2][1] = a[1][1]; a[1][1] = 'X';
dfs(++cnt);
cnt--;
a[1][1] = a[2][1]; a[2][1] = 'X';
a[2][1] = a[2][2]; a[2][2] = 'X';
dfs(++cnt);
cnt--;
a[2][2] = a[2][1]; a[2][1] = 'X';
}
else if (ck && i == 2 && j == 2)
{
a[2][2] = a[1][2]; a[1][2] = 'X';
dfs(++cnt);
cnt--;
a[1][2] = a[2][2]; a[2][2] = 'X';
a[2][2] = a[2][1]; a[2][1] = 'X';
dfs(++cnt);
cnt--;
a[2][1] = a[2][2]; a[2][2] = 'X';
}
}
}
}
signed main()
{
for (rint i = 1; i <= n; i++)
{
for (rint j = 1; j <= n; j++)
{
cin >> c[i][j];
a[i][j] = c[i][j];
}
}
for (rint i = 1; i <= n; i++)
{
for (rint j = 1; j <= n; j++)
{
cin >> b[i][j];
}
}
dfs(0);
if (kk == 1) cout << "YES";
else cout << "NO";
return 0;
}
T2 price
题目大意
\(n\) 个人买东西，每个人有理想价格，如果定价高过理想价格他们就会买，求利润最大值
输入 \(n\)，第二行 \(n\) 个数表示理想价格
输出最大利润及对应定价，如果有多组解，输出定价最低的那个
\(n < 10^5, a_i < 10^6\)
样例
4
1 6 4 6
题目分析
排序，然后遍历一遍，二分查找当前点所在序列位置，计算答案，更新答案：
代码
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
using namespace std;
const int N = 4e5 + 5;
const int inf = 1e8;
int n;
int a[N], ans = 0, minn = inf;
int c[N], s[N];
signed main()
{
cin >> n;
for (rint i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a + 1, a + n + 1);
int len = a[n];
int j = 0;
for (rint i = 1; i <= a[n]; i++)
{
j = lower_bound(a + 1, a + n + 1, i) - a - 1;
//cout << (n - j) * i << endl;
if (ans < (n - j) * i)
{
ans = (n - j) * i;
minn = i;
}
}
cout << ans << " " << minn << endl;
return 0;
}
T3 wait
题目分析
资历程度不同的 cow 吃草顺序不同
所以用优先队列维护即可
赛时智慧的我直接插入数组，导致出现莫名 WA，挂掉 90pts
10pts 代码
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
#define time time__
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e18;
int n;
int maxx = 0;
int time = 0;
struct node
{
int age;
int a, time;
}f[N];
bool cmp(node a, node b)
{
if (a.a != b.a)
{
return a.a < b.a;
}
if (a.a == b.a)
{
return a.age > b.age;
}
}
bool cmp1(node a, node b)
{
return a.age > b.age;
}
signed main()
{
cin >> n;
f[n + 1].a = inf;
for (rint i = 1; i <= n; i++)
{
cin >> f[i].a >> f[i].time;
f[i].age = n - i + 1;
}
sort(f + 1, f + n + 1, cmp);
time = f[1].a + f[1].time;
for (rint i = 2; i <= n;)
{
//cout << i << " " << time << endl;
if (f[i].a <= time)
{
int k = i;
while (1)
{
if (f[k].a <= time) k++;
else break;
}
k--;
sort(f + i, f + k + 1, cmp1);
for (rint j = i; j <= k; j++)
{
//cout << f[j].a << " " << time << endl;;
maxx = max(maxx, time - f[j].a);
time += f[j].time;
}
i = k + 1;
}
else
{
time = f[i].a;
//i++;
}
}
cout << maxx << endl;
return 0;
}
赛后 100pts 代码
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
#define time time__
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e9;
int n;
int time = 0;
int maxx = 0;
struct cow
{
int a, time, age;
}f[N];
priority_queue<cow> q;
bool operator < (cow x, cow y)
{
return x.age > y.age;
}
bool cmp(cow x, cow y)
{
return x.a < y.a;
}
signed main()
{
cin >> n;
for (rint i = 1; i <= n; i++)
{
cin >> f[i].a >> f[i].time;
f[i].age = i;
}
sort(f + 1, f + n + 1, cmp);
auto s = f[1];
q.push(s);
time = f[1].a;
for (rint i = 2; i <= n; )
{
if (q.empty())
{
q.push(f[i]);
time = f[i].a;
i++;
}
auto x = q.top();
maxx = max(maxx, time - x.a);
time += x.time;
q.pop();
while (f[i].a <= time && i <= n)
{
q.push(f[i]);
i++;
}
}
cout << maxx << endl;
return 0;
}
T4 func
题目大意
查询 \(q\) 个 \(f(a)\) 的值
\(f(a)=\max_{0<b<a}\gcd(a\oplus b,a\ \&\ b)\)
数据范围：\(1\le q\le 10^3\)，\(2\le a_i\le 2^{25}-1\)
题目分析
通过打表，发现结论是有规律的 他一定为 \(2^k-1\)，对于 \(n=2^k-1\) ，结果单独另算，可以打表求出
代码
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 5;
int T;
int f[N] = {0, 0, 1, 1, 5, 1, 21, 1, 85, 73, 341, 89, 1365, 1, 5461, 4681, 21845, 1, 87381, 1, 349525, 299593, 1398101, 178481, 5592405, 1082401};
signed main()
{
cin >> T;
while (T--)
{
int n;
cin >> n;
int x = log2(n + 1) + 1;
if (!(n & (n + 1)))
{
cout << f[x - 1] << endl;
}
else
{
cout << (1 << x) - 1 << endl;
}
}
return 0;
}