t1 两个年轻人

思路

考虑题目中所说的最优方案是什么。显然，如果只剩一堆，那么将这一堆直接选完就是最优方案。而如果剩下两堆，那么将最少的一堆选到只剩一个就是最优方案。由此，可以发现，是否必胜只与能否在只剩一堆前将其他堆选到只剩下一有关。所以，我们只需要将初始为1的堆处理一下即可。

点击查看代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define ll long long
using namespace std;
template<typename T>inline void in(T &x){
	x=0;int f=0;char c=getchar();
	for(;!isdigit(c);c=getchar())f|=(c=='-');
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x=f?-x:x;
}
template<typename T>inline void out(T x){
	if(x<0)x=~x+1,putchar('-');
	if(x>9)out(x/10);
	putchar(x%10^48);
}
const int N=10005;
int n;
ll a[N],cnt;
int main(){
	int t;
	in(t);
	while(t--){
		in(n);
		cnt=0;
		fo(i,1,n){
			in(a[i]);
			if(a[i]==1)++cnt;
		}
		if(cnt==n){
			if(cnt&1)puts("Yes");
			else puts("No");
		}
		else if(n-cnt&1){
			if(cnt&1)puts("No");
			else puts("Yes");
		}
		else{
			if(cnt&1)puts("No");
			else puts("Yes");
		}
	}
	return 0;
}

t2 搬砖

最初思路（贪心）

可以发现，每次只有两种选择。只拿一块砖或者一次拿两块砖。那我们根据一次拿两块砖的路程与各自拿一次这两块砖差值从大到小排序，计算，得出答案。当然，这样是无法过掉这道题的。

终局思路（状压记忆化搜索）

因为\(n\le20\)我们显然可以想到状压，但直接状压是过不了的。而且比较麻烦，所以这里考虑记忆化搜索。

t3 闪电链

暴力

直接按照题意去构造答案。

点击查看代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define ll long long
using namespace std;
template<typename T>inline void in(T &x){
	x=0;int f=0;char c=getchar();
	for(;!isdigit(c);c=getchar())f|=(c=='-');
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x=f?-x:x;
}
template<typename T>inline void out(T x){
	if(x<0)x=~x+1,putchar('-');
	if(x>9)out(x/10);
	putchar(x%10^48);
}
const int N=100005,mod=998244353;
int n,h;
ll ans;
int a[N],r[N];
inline void work(int x){
	r[x]=r[x-1]+a[r[x-1]];
	int kp=r[x];
	if(r[x]==n)++ans,ans%=mod;
	else if(r[x]>r[x-1]&&r[x]<n)work(x+1);
	r[x]=r[x-1]+r[x-1]-r[x-2];
	if(r[x]==kp)return;
	if(r[x]==n)++ans,ans%=mod;
	else if(r[x]>r[x-1]&&r[x]<n)work(x+1);
}
int main(){
	in(n),in(h);
	fo(i,1,n)in(a[i]);
	r[1]=1;
	r[2]=1+h;
	work(3);
	if(r[2]==1+a[1]){
		out(ans);
		return 0;
	}
	r[2]=1+a[1];
	work(3);
	out(ans);
	return 0;
}

动态规划

对于条件2，我们可以将其理解为在\(A\)序列上跳跃，并且每次跳跃有两种选择:

按照现在所处位置对应的\(a_{i}\)进行跳跃。
按照上次跳跃的距离进行跳跃。

那我们显然可以想到用\(dp\)方程来进行转移。定义\(dp[i][j]\)表示当前处在\(a_{i}\)的位置，上一步跳跃了\(j\)的距离的方案数。那状态转移方程自然也就出来了，不过考虑到\(for\)循环枚举时会有很多无意义的转移，所以我们采用刷表法进行转移。

\[dp[i+a[i]][a[i]]+=dp[i][j]\\dp[i+j][j]+=dp[i][j] \]

这样就得到了一个\(O(n^{2})\)的算法，接下来再进行优化即可。

标签：20221004,cnt,puts,int,include,dp,getchar
From： https://www.cnblogs.com/thanktothelights/p/16755030.html

20221004（匈）

20221004