A
模拟，签到
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define db double
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a, b;
cin >> a >> b;
if (a + b > 9)
cout << "No" << endl;
else
cout << "Yes" << endl;
// system("pause");
return 0;
}
B
显然贪心，将数组 从小到大排序，找到手里有的
无法使得巫女
开心的位置，就投
的钱，满足
位巫女。
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define db double
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
int arr[maxn];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, x;
cin >> n >> x;
for (int i = 1; i <= n; i++)
cin >> arr[i];
sort(arr + 1, arr + 1 + n);
for (int i = 1; i <= n; i++) {
if (x < arr[i]) {
x -= arr[i - 1];
cout << i - 1 << " " << x << endl;
return 0;
}
}
cout << n << " " << x - arr[n] << endl;
// system("pause");
return 0;
}
C
这个C很有意思，有一种数位dp的感觉，想起来数位dp里面有一道题也是类似的思路。
思路是爆搜，枚举往后面填的数字，然后495的倍数，就维护取余495的余数。
核心是每填一位数，相当于前面的余数乘10，再加上现在填的数字， 再剪枝一下。
#define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define db double
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
string ans = "100000000000000";
void dfs(int yu, string now) {
if (yu == 0) {
if (now.length() < ans.length()) {
ans = now;
}
return;
}
if (now.length() > ans.length())
return;
for (int i = 0; i <= 9; i++) {
dfs((yu * 10 + i) % 495, now + (char)('0' + i));
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
n %= 495;
if (n == 0) {
cout << -1 << endl;
return 0;
}
dfs(n, "");
cout << ans << endl;
// system("pause");
return 0;
}
D
猜结论，结论是：输出字符串的首尾中较大的那个字母
首先，由于其中一个人目的是字典序最小，所以最后字符串肯定只剩下一个字母。先手一定可以通过一次删到只剩首或者尾，就结束游戏。所以答案的下界一定能取到，首尾中较大的字母。
然后假设中间有更大的字母，先手得删两次才能只剩它，但是后手可以删掉它，所以先手取不到中间那个更大的字母。（差不多这个意思），于是直接猜一下这个结论就过了。（严谨证明可以等其他人）
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define db double
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
string str;
cin >> str;
cout << max(str.back(), str.front()) << endl;
// system("pause");
return 0;
}
E
BFS典题
跟普通的走迷宫相比，多了转向，蘑菇也是用来转向的。所以直接考虑在普通的bfs基础上，给距离数组加上方向设定， 表示位于点
且当前朝向是
的最短距离，然后就正常跑bfs，维护一下方向即可。复杂度
忽然发现方向0到3，必须保证是连续的，我写的时候没注意，恰好写出来顺序就是连着的，转向才不会出现掉头的情况
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define db double
using namespace std;
const int maxn = 1e3 + 10;
const int mod = 998244353;
int vis[maxn][maxn][4];
int dis[maxn][maxn][4];
char ch[maxn][maxn];
struct Node {
int x, y, dir;
};
void solve() {
int n, m;
cin >> n >> m;
pii s, t;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> ch[i][j];
if (ch[i][j] == 'S')
s = pii(i, j);
if (ch[i][j] == 'T')
t = pii(i, j);
for (int k = 0; k < 4; k++)
vis[i][j][k] = 0, dis[i][j][k] = inf;
}
queue<Node> q;
for (int i = 0; i < 4; i++) {
auto [x, y] = s;
vis[x][y][i] = 1;
dis[x][y][i] = 0;
q.push(Node{x, y, i});
}
while (!q.empty()) {
auto [x, y, dir] = q.front();
q.pop();
if (pii(x, y) == t) {
continue;
}
int u, v;
if (dir == 0) {
u = 1;
v = 0;
} else if (dir == 1) {
u = 0;
v = 1;
} else if (dir == 2) {
u = -1;
v = 0;
} else {
u = 0;
v = -1;
}
int xx = x + u, yy = y + v;
if (xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy][dir] ||
ch[xx][yy] == '#' || dis[xx][yy][dir] < dis[x][y][dir] + 1)
continue;
dis[xx][yy][dir] = dis[x][y][dir] + 1;
vis[xx][yy][dir] = 1;
q.push(Node{xx, yy, dir});
if (ch[xx][yy] == '*') {
int d1 = (dir - 1 + 4) % 4, d2 = (dir + 1) % 4;
if (vis[xx][yy][d1] == 0) {
vis[xx][yy][d1] = 1;
dis[xx][yy][d1] = dis[x][y][dir] + 1;
q.push(Node{xx, yy, d1});
}
if (vis[xx][yy][d2] == 0) {
vis[xx][yy][d2] = 1;
dis[xx][yy][d2] = dis[x][y][dir] + 1;
q.push(Node{xx, yy, d2});
}
}
}
int ans = inf;
for (int i = 0; i < 4; i++)
ans = min(ans, dis[t.first][t.second][i]);
if (ans == inf)
ans = -1;
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
// system("pause");
return 0;
}
F
状压dp
值域很小，很容易发现，对于相等的值，只需要留一个即可，所以长度 直接可以缩到
。然后观察题意，需要保证剩下的数与起来为0。
涉及到位运算，就会考虑按位思考。与起来为0，即对于每个位，剩下来的数都至少要有一个数，该位是0。又因为值域200，位只有8位，就容易考虑用状压dp。（不知道状压dp的可以先去补一下）
设 对于
中所有是1的位，表示选中的数中，这些存在0的最少选中数量，最后答案就是
即8个位都是1，即选中的数中，这8个位都存在0的最少数量。
转移过程就是 枚举状态，再
枚举所有可选数字, 设当前枚举到的数字是
，则构造一个数字
，使得
中是0的位，
中该位是
，（应该也能直接用波浪号取反操作得到，但是没调出来，就直接暴力构造），然后对于当前枚举到的状态
，有如下表达式：
初始化所有dp值正无穷，dp[0]=0，最后输出即可。
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define db double
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 998244353;
int arr[maxn];
int dp[1 << 8];
void solve() {
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
sort(arr + 1, arr + 1 + n);
int len = unique(arr + 1, arr + 1 + n) - arr - 1;
for (int i = 0; i < (1 << 8); i++) {
for (int j = 1; j <= len; j++) {
int x = arr[j];
int y = 0;
for (int j = 0; j < 8; j++)
if ((((x >> j) & 1) == 0))
y |= 1 << j;
dp[i | y] = min(dp[i | y], dp[i] + 1);
}
}
if (dp[(1 << 8) - 1] == inf)
dp[(1 << 8) - 1] = n + 1;
cout << n - dp[(1 << 8) - 1] << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
// system("pause");
return 0;
}
京公网安备 11010502036488号