D - Flip and Adjust
一共有 \(N\) 张牌，每一面都写着一个整数。卡 \(i(1 \le i \le N)\) 前面写着整数 \(a_i\)，后面写着整数 \(b_i\)。你可以选择是否放置每张卡片的正面或背面可见。
确定是否可以将卡片放置到可见整数的和完全等于 \(S\) 的位置，如果可能的话，找到卡片的位置来实现这一点。
数据范围：$ 1 \le N \le 100,1 \le S \le 10^4$。
经典小背包方案，不想说了，嗯，就是这样。
Code.
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=1e4+10;
int n,s,a[N],b[N],ans,f[N][M],yl[N],t[N][M];
int main()
{
scanf("%d%d",&n,&s); for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
f[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=s;j>=a[i];j--) {f[i][j]|=f[i-1][j-a[i]]; if(f[i-1][j-a[i]]) t[i][j]=1;}
for(int j=s;j>=b[i];j--) {f[i][j]|=f[i-1][j-b[i]]; if(f[i-1][j-b[i]]) t[i][j]=2;}
}
if(! f[n][s]) return puts("No"),0;
puts("Yes"); int p=s;
for(int i=n;i;i--) {yl[i]=t[i][p]; if(yl[i] == 1) p-=a[i]; else p-=b[i];}
for(int i=1;i<=n;i++) if(yl[i] == 1) printf("H"); else printf("T"); puts("");
return 0;
}
E - Subsequence Path
有 \(N\) 个编号为 \(1,...,N\) 的城镇和 \(M\) 条编号为 \(1,...,M\) 的道路。每条路都有方向; \(i\) 路\((1 \le i \le M)\) 从 \(A_i\) 镇到 \(B_i\) 镇。路 \(i\) 的长度是 \(C_i\)。
给定长度为 \(K\) 的序列 \(E=(E1,...,EK)\)，由 \(1\) 到 \(m\) 之间的整数组成。从城镇$ 1$ 到城镇 \(N\) 的道路称为好路径，如果：按照路径中使用的顺序排列的道路的数字序列是 \(E\) 的子序列。
注意，序列的子序列是通过从原始序列中删除 \(0\) 个或多个元素并在不改变顺序的情况下连接其余元素而获得的序列。求一条好路所用道路长度的最小总和。
数据范围：\(2 \le N \le 2 \times 10^5,1 \le C_i \le 10^9\)。
难度诈骗题，简单的思考，如果当前的路 \(i\) 能用，仅当之前有一条路可以走到这条路的起点，且 \(i\) 会影响它到达的终点 \(v\)，所以只需要标记这条路的起点是否出现过，如果出现过就更新到达点的答案就可以了。
Code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6e5+10;
int w[N<<1],d[N],st[N],idx,n,m,k;
struct nod {int u,v,c;} pl[N];
signed main()
{
memset(d,0x7f,sizeof d); cin>>n>>m>>k; int tmp=d[1];
for(int i=1,u,v,c;i<=m;i++) {cin>>u>>v>>c; pl[i]={u,v,c};}
st[1]=1; d[1]=0;
while(k -- )
{
int id; cin>>id;
if(! st[pl[id].u]) continue ;
else
{
st[pl[id].v]=1; int u=pl[id].v;
d[u]=min(d[pl[id].u]+pl[id].c,d[u]);
}
}
if(tmp == d[n]) puts("-1"); else cout<<d[n];
return 0;
}
F - XOR on Grid Path
有一个有 \(N\) 行 \(N\) 列的网格。我们用 \((i,j)\) 表示第 \(i\) 行 \((1 \le i \le N)\) 和第 \(j\) 列\((1 \le j \le N)\) 交点处的数值。点 \((i,j)\) 上面写着一个非负整数 \(a_{i j}\)。
当你在点 \((i,j)\) 处时，你可以移动到点 \((i+1,j)\) 或点 \((i,j+1)\)，你不允许走出网格。
求出从点 \((1,1)\) 到点 \((N,N)\) 的路径个数，使所访问的路径上的异或和为 \(0\)。
数据范围：\(2 \le N \le 20\)。
数据范围很小，考虑个暴力，但又不是很暴力的东西，折半搜索。思路很简单，把询问沿对角线拆开，针对上一半的所有路径拿一个二维的哈希表吧到分割点时的异或值全都存下来，一条路径异或和为零，可以理解为上下两半异或值相等，所以下一半从终点向对角线跑，到分割点时加上哈希表已经存储的答案就可以了。
Code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=30;
int n,a[N][N],res; unordered_map<int,int> ma[N][N];
void dfs1(int x,int y,int now)
{
if(x + y == n) return ma[x][y][now]++,void();
else if(x + y < n) dfs1(x+1,y,now^a[x+1][y]),dfs1(x,y+1,now^a[x][y+1]);
}
void dfs2(int x,int y,int now)
{
if(x + y == n) return res+=ma[x][y][now^a[x][y]],void();
else if(x + y > n) dfs2(x-1,y,now^a[x-1][y]),dfs2(x,y-1,now^a[x][y-1]);
}
signed main()
{
scanf("%lld",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%lld",&a[i][j]);
dfs1(1,1,a[1][1]); dfs2(n,n,a[n][n]);
printf("%lld",res);
return 0;
}