- Reverse Game 博弈、思维
大意：给定一个01字符串S,两人轮流操作，每次可以选择“10”、“110”、“100”、“1010”进行翻转。不能操作的判输。问谁会获胜？
思路：题目给的东西都不是随便给的，观察上面给出的几个字符串我们就会发现，最终不能继续进行操作的时候一定是前半部分全部是0后半部分全部是1。因为一旦1后面有0，那么必然可以翻转将0往前面翻，直到翻到前面不再有1为止。每次只翻转10的次数是把每个1后面0的个数加起来。然后我们观察发现，每次翻转，最少少1个、最多少2个“10”。“1010”翻转少了三个，但是变成“0101”又多了一个，所以还是少2个，所以相当于取石子的问题，把 “10” 看成石子，3是关键数字，所以只要不是3的倍数先手必胜。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string s;
cin>>s;
LL cnt=0,k=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='0')cnt+=i-k,k++;
}
if(cnt%3)cout<<"Alice\n";
else cout<<"Bob\n";
return 0;
}
总结：题目给定的信息都是设计好的，既然给了，就肯定会有特别的意义。
- Divisible by 3 思维、dp
大意：给定一个序列 a,定义区间[l,r]的权重为 1 < = i < j < = r 1<=i<j<=r 1<=i<j<=r b i b j b_ib_j bibj乘积之和，问一共有多少个权重%3为0的区间。
思路：我们之前做过简单的区间和%3为的区间个数。那个题的做法是求出前缀和%3的，对于区间满足sum[l,r]%3为0即是sum[r]-sum[l-1]=0。
也就是说对于遍历到当前位置r时，我们需要找前面有多少个 l 是和 sum[r]相等的，我们可以开个一维数组， 从前往后扫一遍边更新计数就行了。对于这道题完全可以类比过去，唯一不同的就求和方式不同。赛时没推出式子。没写出。
对于简单区间和的时后我们只需要开个一维的数组就行了。但是对于此题，经过我们一系列的推导，最终推出的式子为
w [ i ] = w [ i − 1 ] + a [ i ] ∗ s u m [ i − 1 ] w[i]=w[i-1]+a[i]*sum[i-1] w[i]=w[i−1]+a[i]∗sum[i−1]
w [ l , r ] = w [ r ] − w [ l − 1 ] − s u m [ l − 1 ] ∗ ( s u m [ r ] − s u m [ l − 1 ] ) w[l,r]=w[r]-w[l-1]-sum[l-1]*(sum[r]-sum[l-1]) w[l,r]=w[r]−w[l−1]−sum[l−1]∗(sum[r]−sum[l−1])。我们需要同时知道w,sum。所以开个二维数组来计数，w,sum值只有0，1，2直接枚举就行了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N=500010;
typedef long long LL;
int n;
LL a[N],cnt[3][3],w[N],sum[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
LL ans=0;
cnt[0][0]=1;
for(int i=1;i<=n;i++)
{
w[i]=(w[i-1]+a[i]*sum[i-1])%3;
sum[i]=(sum[i-1]+a[i])%3;
for(int j=0;j<3;j++)
{
for(int k=0;k<3;k++)
{
int t=((w[i]-j-(sum[i]-k)*k)%3+3)%3;
if(!t)ans+=cnt[j][k];
}
}
cnt[w[i]][sum[i]]++;
}
cout<<ans<<"\n";
return 0;
}
总结：对于相似的问题，不妨从简单的入手，然后慢慢地类比。
- Mistake 签到、直接用map 就行了
- Modulo Permutations 思维、dp
大意：给定一个 n 的排列，问能构造出多少种方案使得 p i m o d p i + 1 < = 2 p_i\mod\ p_{i+1}<=2 pimod pi+1<=2。 p n + 1 = p 1 , n < = 1 e 6 p_{n+1}=p_1,n<=1e6 pn+1=p1,n<=1e6 结果对1e9+7 取模
思路：首先我们得明白给定 p n + 1 = p 1 p_{n+1}=p_1 pn+1=p1 的用意，实际上就是个环，对于环我们一般是拆成链写。对于其中1、2两个数是非常特殊的。
除了这两个数，其他的数必须得递减排序，否则构不成 p i m o d p i + 1 < = 2 p_i\mod\ p_{i+1}<=2 pimod pi+1<=2 。我们通过 1或2把环拆成一条链。对于一条链也可以根据1、2分成两段递减的排列。经过一系列转化我们就将问题变成了将 3-n 的数字分成两段递减的排列，并且满足上述条件。因为构成的是一个环，最终的方案数再乘n。接下来就是怎么求同时考虑两段的方案数。显然两段是等价的，我们只需要对其中一段考虑完所有的可能就好了。我们用dp来写，从大到下枚举x。我们用f(x,i,j)表示现在用到的数为x,第一段的数末尾为i,第二段的数末尾为 j,显然i,j必有一个为 x，因为两段实际上是等价的，我们对其中的一段考虑完所有情况就行了，所以不妨把第一段的末尾当成x即 f(x,j)。接着向后转移，我们先不考虑合不合法，x-1放第一段或者第二段，对于 f(x-1,j), f(x,x-1)。对于第一个转移必然是合法的，相当于直接让f(x-1,j)=f(x,j)。省掉第一维之后可以直接忽略。对于第二个转移，j=k*(x-1)+r, 0<=r<=2，但是对于第二个转移实际上是f(x,x-1)，我们要省去第一维的话要保证第一维是一致的，所以改成f(x-1,x)，也就是所我们用的是x-1,但是dp更新的是x，这样两种转移就都可以都省掉第一维。对于第二个转移就是枚举倍数，枚举倍数k=0,r=0时，则值为0，相当于不加数，也是一种方案，所以得有dp[0]=1，枚举倍数是调和级数，时间复杂度logn。总的时间复杂度就是 O ( n l o g n ) O(nlogn) O(nlogn)。因为1，2两个数放在一段的开头是两种情况，所以别忘了乘2。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e9+7;
typedef long long LL;
LL f[N];
int n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
if(n<=2)
{
cout<<n<<"\n";
return 0;
}
f[0]=1;
for(int i=n-1;i>2;i--)
{
LL v=0;
for(int j=0;j<=n;j+=i)
for(int k=0;k<3&&j+k<=n;k++)
v+=f[j+k];
f[i+1]=v%M;
}
LL ans=0;
for(int i=0;i<=n;i++)ans=(ans+f[i])%M;
cout<<ans*2*n%M<<"\n";
return 0;
}
总结：纪录方案数直接排列组合不好求的时候考虑dp来写。