AtCoder Beginner Contest 271
A - 484558
题意：把一个数转化为16进制
map<int,char>mp;
int main()
{
mp[10] = 'A';
mp[11] = 'B';
mp[12] = 'C';
mp[13] = 'D';
mp[14] = 'E';
mp[15] = 'F';
vector<int>q;
int x; scanf("%d",&x);
if(x == 0){
cout << "00";
return 0;
}
while(x){
q.pb(x % 16);
x /= 16;
}
reverse(all(q));
string ans = "";
for(auto it : q){
if(it <= 9) ans = ans + (char)(it + '0');
else ans = ans + mp[it];
}
if(sz(ans) < 2) ans = (char)('0') + ans;
cout << ans;
return 0;
}
B - Maintain Multiple Sequences
题意 ： 给你一个二维数组，问你第\(i\)行第\(j\)列的数字是多少。
代码：
int main()
{
read(n);read(q);
for(int i = 1; i <= n; i ++ ){
int x;read(x);
a[i].pb(x);
while(x --){
int y;read(y);
a[i].pb(y);
}
}
while(q -- ){
int x, y;read(x);read(y);
write(a[x][y]);
if(q) puts("");
}
return 0;
}
C - Manga
题意： 给你n本书，每本书有个权值\(a_i\)，你可以进行以下操作任意次：
- 选择任意两本书删除并新增一个任意权值的书
你可以读权值为 $1, 2, 3, 4, ... $的书，（权值从1开始，并且以1为公差递增）。
问你最多可以读多少本书？
思路：二分、前缀和维护答案即可，记得特判\(n = 1\)的情况。
代码：
const int N = 300010;
int n;
int a[N], cnt[N];
int need[N], sum[N], had[N];
bool check(int u){
int qwq = sum[u];//缺少的
int have = had[u];
int sheng = n - had[u];
if(qwq * 2 <= sheng) return true;
return false;
}
int main()
{
read(n);
for(int i = 1; i <= n; i ++ ){
read(a[i]);
if(a[i] <= n) cnt[a[i]] ++;
}
for(int i = 1; i <= n; i ++ ){
if(!cnt[i]) need[i] = 1;
}
for(int i = 1; i <= n; i ++ ){
sum[i] = sum[i - 1] + need[i];
}
for(int i = 1; i <= n; i ++ ){
had[i] = had[i - 1] + (cnt[i] >= 1);
}
if(n == 1){
if(a[1] == 1){
printf("1");
}else{
printf("0");
}
return 0;
}
int l = 1, r = n;
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
printf("%d",l);
return 0;
}
D - Flip and Adjust
题意 ：有\(n\)张卡片，每张卡片有正反两面，每一面都有数字，每张卡片只能使用一个数字作为其权值，问你是否能用这\(n\)张卡片凑出一个数字\(s\)。
思路：先动态规划维护是否能凑出答案，再递归逆推出状态。
\(dp[i][j]\)表示前\(j\)张卡片是否能凑出\(i\)。如果\(dp[s][n] = true\)就是能凑出，否则不能，状态转移见代码。
const int N = 110, M = 10000;
int a[N], b[N];
int sum, n;
bool dp[20010][110];
string ans;
void dfs(int u, int val){m
if(u == 1 && val == a[1]){
ans += 'H';
reverse(all(ans));
cout << ans;
exit(0);
}
if(u == 1 && val == b[1]){
ans += 'T';
reverse(all(ans));
cout << ans;
exit(0);
}
if(val - a[u] >= 0 && dp[val - a[u]][u - 1]){
ans += 'H';
dfs(u - 1,val - a[u]);
if(ans.size())ans.pop_back();
}
if( val - b[u] >= 0 && dp[val - b[u]][u - 1]){
ans += 'T';
dfs(u - 1,val - b[u]);
if(ans.size())ans.pop_back();
}
}
int main()
{
read(n);read(sum);
for(int i = 1; i <= n; i ++ ){
read(a[i]);read(b[i]);
}
dp[a[1]][1] = 1;
dp[b[1]][1] = 1;
for(int i = 2; i <= n; i ++ ){
for(int j = 0; j <= M; j ++ ){
if(j - a[i] >= 0)
if(dp[j - a[i]][i - 1]) dp[j][i] = 1;
if(j - b[i] >= 0)
if(dp[j - b[i]][i - 1]) dp[j][i] = 1;
}
}
if(dp[sum][n]){
puts("Yes");
dfs(n, sum);
}
else printf("No");
return 0;
}
E - Subsequence Path
题意：
有 \(n\)个城镇，\(m\)条道路，有一个集合 \(s\)，集合里面是道路的编号。你需要从节点 \(1\)走到节点\(n\)且选择的道路所形成的集合是所给集合的子集且顺序不能改变。问是否能走到节点\(n\),如果能那么路径最短为多少。
题解：
动态规划维护路径最小值。\(dp[i]\)表示从第一个节点出发按所给集合顺序走到第\(i\)个节点路径最小值。按集合顺序遍历所给的边即可。
代码：
const int N = 200010;
struct Edge{
int a, b, c;
}edges[N];
int n, m, k;
int e[N];
LL dp[N];
int main(){
scanf("%d %d %d",&n, &m, &k);
for(int i = 1; i <= n; i ++ ) dp[i] = 9e18;
for(int i = 1; i <= m; i ++ ){
int a, b, c;
scanf("%d %d %d",&a, &b, &c);
edges[i] = {a, b, c};
}
for(int i = 1; i <= k; i ++ ) scanf("%d",&e[i]);
for(int i = 1; i <= k; i ++ ){
int a = edges[e[i]].a, b = edges[e[i]].b, c = edges[e[i]].c;
//a -> b
if(a == 1){
dp[b] = min(dp[b], (LL)c);
dp[a] = 0;
}
else if(dp[a] < 9e17) dp[b] = min(dp[b], (LL)dp[a] + c);
}
if(dp[n] > 9e17) printf("-1");
else printf("%lld", dp[n]);
return 0;
}
F. - XOR on Grid Path
题意：
给你一个边长为\(n\)的矩阵，你从坐标为\((1,1)\)开始，你可以向下或者向右走，一开始权值为\(a[1][1]\),当你走到\(a[i][j]\),贡献变成\(a[1][1]\) 异或 \(a[i][j]\)，以此类推，问你走到\((n,n)\)时，权值为\(0\)的方案数为多少。
数据范围
\(1 \leq n \leq 20\)
\(1 \leq a_{i,j} \leq 1e9\)
思路：
暴力遍历肯定会寄，采用\(meet \ in \ middle\)，暴力预处理一半，再去找另一半即可。
时间复杂度：
\(O(N * 2 ^ N)\)
代码：
const int N = 25;
int a[N][N];
int n;
vector<int>q[N];//横坐标
map<pair<int,int>,int>mp;
long long ans;
void dfs(int x, int y, int val){
if(x + y == n + 1){
q[x].push_back(val);
return;
}
if(x + 1 <= n) dfs(x + 1, y, val ^ a[x][y]);
if(y + 1 <= n) dfs(x, y + 1, val ^ a[x][y]);
}
void go(int x, int y, int val){
if(x + y == n + 1){
val = val ^ a[x][y];
ans += mp[make_pair(x, val)];
return;
}
if(x - 1 >= 1) go(x - 1, y, (val ^ a[x][y]));
if(y - 1 >= 1) go(x, y - 1, (val ^ a[x][y]));
}
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
scanf("%d",&a[i][j]);
//从上往下搜
dfs(1, 2, a[1][1]);
dfs(2, 1, a[1][1]);
for(int i = 1; i <= n; i ++ ){
for(auto it : q[i]){
mp[{i, it}] ++;
}
}
go(n, n - 1, a[n][n]);
go(n - 1, n, a[n][n]);
printf("%lld",ans);
return 0;
}