Solution
T1 排列计数
原题链接
简要思路
直接用 next_permutation 枚举全排列计算答案即可。
完整代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,k;
int a[100];
int ans;//可能的答案数量
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++)
a[i]=i;//先记录每个数
do{
bool f=true;
for(int i=2;i<=n;i++)
if(abs(a[i]-a[i-1])==k)//任意相邻两数的差的绝对值不能为 k
f=false;
if(f==1)ans++;//满足条件
}while(next_permutation(a+1,a+n+1));//do-while 循环枚举每一种可能的排列
cout<<ans<<endl;
return 0;
}
T2 向量乘法
原题链接
简要思路
-
No.1 80pts
同 T1，枚举全排列按照题目中给定的计算方式来计算最终的结果，并记录一个桶来计算有几个不同的答案。 -
No.2 100pts
发现题目给定的式子等同于 \((α_{p_1} \times α_{p_2}) \times (α_{p_3} \times α_{p_4}) \times (α_{p_5} \times α_{p_6}) ......\)，也就是说第 \(2k-1\) 和第 \(2k\) 个向量交换顺序不会影响计算结果，那么每对向量放在哪里都不会影响计算结果。按照上述性质和结论，我们此题可以用 DFS。用一个 set 来储存答案，DFS 两个数：当前遍历到了第几对向量以及当前的计算结果。维护一个数组 \(f\)，\(f_i\) 表示是否轮到了第 \(i\) 个向量。如果 \(f_i\) 为 \(0\)，就对其进行 DFS。注意
true和false的变化。
完整代码
- No.1 80pts
#include<bits/stdc++.h>
using namespace std;
map<int,bool> m;//map 储存答案
int p[10];//为每个向量打编号，以来全排列
struct node{
int x;
int y;
}a[105];//向量结构体
int js(node a,node b){//奇数情况下，向量 a * 向量 b 为一个实数 r
node c;
c.x=a.x*b.x;
c.y=a.y*b.y;
int r;
r=c.x+c.y;
return r;
}
node os(int r,node b){//偶数情况下，实数 r * 向量 b 为一个向量 c
node c;
c.x=b.x*r;
c.y=b.y*r;
return c;
}
int f,num,n;
signed main(){
cin>>n;
n*=2;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
for(int i=1;i<=n;i++) p[i]=i;//给每组向量打编号
do{
int ans=0;//计算答案
node k;
k=a[p[1]];//记录当前排列状态下的第一组向量是什么
for(int i=1;i<n;i++){
if(i%2!=0) ans=js(k,a[p[i+1]]);//奇数
if(i%2==0) k=os(ans,a[p[i+1]]);//偶数
}
if(m[ans]!=1)num++;//如果这个答案是第一次出现就将最终答案 num++
m[ans]=1;//标记为已经出现
}while(next_permutation(p+1,p+1+n));
cout<<num<<endl;
return 0;
}
- No.2 100pts
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=25;
bool used[MAXN];
int x[MAXN],y[MAXN];
set<int> s;//存储答案（set 有自动去重的功能）
int n;
void dfs(int i,int now){//dfs 到了第 i 个向量，且之前向量的计算结果为 now
while(i<2*n&&used[i])//轮到了 i
i++;
if(i==2*n){//结算完毕
s.insert(now);//插入结果
return;
}
used[i]=true;//标记轮到了
for(int j=i+1;j<2*n;j++)//枚举后面每一种可能的向量
if (!used[j]){//如果没轮到
used[j]=true;//轮到 true
dfs(i,now*(x[i]*x[j]+y[i]*y[j]));
//此处 i 不用加一，因为上面的 while 循环已经对 i 进行了更新
//通过给定的向量乘法的公式更新 now
used[j]=false;//dfs 完后更新为 false，以为了下一组 dfs
}
used[i]=false;//注意更新为 false
}
signed main(){
cin>>n;
for(int i=0;i<2*n;i++)
cin>>x[i]>>y[i];//输入 2n 个向量
dfs(0,1);//dfs 第 0 个向量，当前答案为 1（因为要乘法，所以初始值是 1 不是 0）
cout<<s.size()<<endl;//有几个不同的答案
}
T3 数字博弈
原题链接
简要思路
这是一道博弈题。DFS 搜索，搜索的两个状态就是两个人的当前数字，直接暴力搜索，可以发现状态并不多（详见代码注释）。
完整代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,b;
int dfs(int a,int b){
if(a>n||b>n)return a-b;//如果有人的答案超出 n，就返回两人的差
else return max(-dfs(b,a+b),-dfs(b,a*b));
//因为每个人都要保证解对于自己来说尽可能地优，所以返回为 max
//因为下一步遍历的是对方选数，所以取负数
//同上，下一步为对方选择方案，所以状态一为 b，状态二为两数的 和/积
}
signed main(){
cin>>n>>a>>b;
cout<<dfs(a,b)<<endl;//直接 dfs
return 0;
}
T4 放置棋子
原题链接
简要思路
发现：
- 当 \(n \not= m\) 的时候，答案为 \(0\)；
- 当 \(k = 0\) 的时候，答案为 \(1\)。
考虑将矩阵的每一行按照 01 串的字典序进行排序。如果两个矩阵排序后的矩阵相同，那么它们属于同一个等价类。搜索这样的等价类，每个类对答案的贡献都是一个组合数。
考虑用 meet-in-middle 双向搜索进行优化。
But，正解是按照上述算法进行打表。有一个小技巧：表是对称的，这样的话可以加快打表的速度。
完整代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m,k;
int ans[10][10]={{1},//n=1
{1, 1},//n=2
{1, 2, 1},//n=3
{1, 6, 6, 1},//n=4
{1, 24, 90, 24, 1},//n=5
{1, 120, 2040, 2040, 120, 1},//n=6
{1, 720, 67950, 297200, 67950, 720, 1},//n=7
{1, 5040, 3110940, 68938800, 68938800, 3110940, 5040, 1},//n=8
{1, 40320, 187530840, 24046189440ll, 116963796250ll, 24046189440ll, 187530840, 40320, 1},//n=9
{1, 362880, 14398171200ll, 12025780892160ll, 315031400802720ll, 315031400802720ll,12025780892160ll, 14398171200ll, 362880, 1}};//n=10
//要保证 k<n,n=m，所以可以减少打表的数量以及去除 m 这一维度的打表
signed main(){
cin>>n>>m>>k;
//先特判不符合题意的情况
if(k==0){
cout<<1<<endl;
return 0;
}
if(n!=m||k>n){
cout<<0<<endl;
return 0;
}
cout<<ans[n][k]<<endl;//输出打表程序
return 0;
}