P7800 [COCI2015-2016#6] PAROVI 方法记录
桔梗花于此开放
[COCI2015-2016#6] PAROVI
\(\text{Mirko}\) 和 \(\text{Slavko}\) 在玩一个游戏，先由 \(\text{Mirko}\) 在 \(1\dots N\) 中选出几组互质的数。例如当 \(N=5\) 时，\(\text{Slavko}\) 可以选择 \(\big\{\{1,2\},\{3,4\},\{2,5\},\{3,5\},\cdots\big\}\) 中的几组。
然后轮到 \(\text{Slavko}\)。他需要找到一个 \(x\in \big[2,n\big]\) 使得对于每组 \(\{a,b\}\) 都满足以下两个条件之一：
\(a\)，\(b<x\)
\(a\)，\(b\ge x\)
例如，如果 \(\text{Mirko}\) 选了 \(\big\{\{1,2\},\{3,4\}\big\}\)，那么 \(x\) 可以等于 \(3\)。
如果 \(\text{Slavko}\) 找不到满足条件的 \(x\) 值，则表示 \(\text{Mirko}\) 获得胜利。现在请你求出 \(\text{Mirko}\) 获胜的不同情况的总数，在对 \(10^9\) 取模后告诉他。
第一行包含一个整数 \(N\)。
第一行输出一个整数，为 \(\text{Mirko}\) 获胜的不同情况的总数对 \(10^9\) 取模后的值。
样例输入 #1
2样例输出 #1
1样例输入 #2
3样例输出 #2
5样例输入 #3
4样例输出 #3
21【样例 1 解释】
\(\text{Slavko}\) 只有一种取法 \(\big\{\{1,2\}\big\}\)。
【样例 2 解释】
\(\text{Slavko}\) 的其中一种取法为 \(\big\{\{1,2\},\{1,3\}\big\}\)。
【数据范围】
对于 \(100\%\) 的数据，\(1\le N\le 20\)。
【题目来源】
题目译自 COCI 2015-2016 CONTEST #6 T4 PAROVI。
本题分值按 COCI 原题设置，满分 \(120\)。
一道终究没能自己想出正解的题
错误的做法
注意到在\(1…N\)中选出几组互质的数，先试想\(N\)个数中选两个数，一共有多少种选法。
以\(N=4\)为例
1,2 1,3 1,4
2,3 2,4
3,4不难想到，可以用循环嵌套实现
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
//(i,j)就是一组
}
}接下来实现互质
若两个数的最大公因数为\(1\)，则这两个数互质
注意：形如\((1,n)\)的数对也算互质对。
结合欧几里得算法，在遍历数对的循环嵌套中加入一个判断函数，将通过判断的数对存储。
存储方法：由于N最大为20，遍历出来的两个数也很小，所以我们将第一个数乘\(1000\)，再加上第二个数，就可以用一个元素存下这个二元组。
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
bool judge(int a,int b)
{
if(a>b) swap(a,b);
if(a==1) return 1;
for(int i=2;i<=a;i++)
{
if(gcd(a,b)!=1) return 0;
}
return 1;
}
//
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(!judge(i,j)) continue;
choose[++cnt]=i*1000+j;
}
}这样我们可以得到每一组互质对的情况。而Mlavko可以在这些互质对中选取若干组，比如一共有\(3\)组（注意是组，和前面的互质的数区分。一个互质对是一组）
那么选取方案如下：
1 12 123 13 2 23 3可以用全组合获取。
#include<iostream>
#include<cstdio>
using namespace std;
int n,pd[1000],used[1000];
void dfs(int f,int s)
{
for(int i=s;i<=n;i++)
{
if(!pd[i])
{
pd[i]=1;
used[f]=i;
for(int j=1;j<=f;j++) cout<<used[j];
cout<<" ";
dfs(f+1,i);
pd[i]=0;
}
}
}
int main()
{
scanf("%d",&n);
dfs(1,1);
return 0;
}
//input 3
//output 1 12 123 13 2 23 3结合以上两项，我们可以得到所有可能选取的互质对，以及互质对中的两个元素。
如当\(N=3\)时：
（靠得近的为一组，输出的数为互质对中的数，括号中的为组编号）
12(1)
12(1) 13(2)
12(1) 13(2) 23(3)
12(1) 23(3)
13(2)
13(2) 23(3)
23(3)解题重点：确定什么情况下，Slavko能找到x满足要求
根据题意，有以下\(3\)种情况：
1.Mirko选的所有互质对的所有元素的最小值大于等于2——这时\(x=2\)Mirko就会输；
用minn记录最小值即可
2.Mirko选的所有互质对的所有元素的最大值小于n——这时\(x=n\)Mirko就会输；
用maxx记录最大值即可
3.Mirko选择\((a,b)(c,d)\)且满足\(a<b<c<d\)这样的，当\(x=c\)时Mirko就会输。
开一个\(int\)数组，每收到一组\((i,j)\)，就从i到j数组中的每一个元素值+1。处理完毕后遍历该数组，若有元素（1除外）的值大于1，则Mirko会输
特别地，若Mirko选择了\((1,n)\)，则Mirko必胜。但由于大部分的情况都被上述三种考虑过了，只有一种情况：即Mirko只选了\((1,n)\)这一组的情况未被考虑，所以可以单独判断，也可以直接给答案+1
void sat(int x)
{
int a,b;
bool p[1000];
for(int i=1;i<=n+1;i++) p[i]=1;
bool flag=1;
a=choose[x]/1000;//将两个元素还原出来
b=choose[x]-a*1000;
if(a==1&&b==n)
{
one_n=1;//这里特判了{1,n}
}
cout<<a<<b<<" ";
minn=min(a,minn);
maxx=max(b,maxx);
for(int i=a;i<=b;i++) reg[i]++;//累加数组
}综上所述，总代码如下
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int mod=1e9;
int n,cnt,ans;
int choose[1000],used[1000],reg[1000];
bool pd[1000],one_n=0;
int minn=1000,maxx=-1000;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
bool judge(int a,int b)
{
if(a>b) swap(a,b);
if(a==1) return 1;
for(int i=2;i<=a;i++)
{
if(gcd(a,b)!=1) return 0;
}
return 1;
}
void sat(int x)
{
int a,b;
bool p[1000];
for(int i=1;i<=n+1;i++) p[i]=1;
bool flag=1;
a=choose[x]/1000;
b=choose[x]-a*1000;
if(a==1&&b==n)
{
one_n=1;
}
cout<<a<<b<<" ";
minn=min(a,minn);
maxx=max(b,maxx);
for(int i=a;i<=b;i++) reg[i]++;
}
void dfs(int f,int s)
{
for(int i=s;i<=cnt;i++)
{
if(!pd[i])
{
pd[i]=1;
used[f]=i;
bool flag=1;
minn=1000,maxx=-1000;
memset(reg,0,sizeof(reg));
one_n=0;
for(int j=1;j<=f;j++)
{
sat(used[j]);
}
puts("");
for(int j=2;j<=n;j++)
{
if(reg[j]>1)
{
flag=0;
break;
}
}
ans++;
if(minn>=2||maxx<n||flag==1)
{
ans--;
if(one_n==1) ans++;
}
else cout<<" yes"<<endl;
dfs(f+1,i);
pd[i]=0;
}
}
}
int main()
{
//freopen("parovi.in","r",stdin);
//freopen("parovi.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(!judge(i,j)) continue;
choose[++cnt]=i*1000+j;
}
}
dfs(1,1);
printf("%d",ans);
return 0;
} 这是错误的做法
当\(n=2,3,4\)时输出均正确，但当\(n=5\)时答案错误，且这个程序复杂度很极品。我改了又改只为把\(n=5\)的情况整对，但还是失败了，所以这个程序是个错误的暴力。
下面是正确的做法
如果执意要用搜索的同学可以看看这篇
虽然我的做法是错的，但是部分分析是可以利用的
一、预处理互质对
二、Mirko会失败的情况：
1.Mirko选的所有互质对的所有元素的最小值大于等于2——这时\(x=2\)Mirko就会输；
2.Mirko选的所有互质对的所有元素的最大值小于n——这时\(x=n\)Mirko就会输；
3.Mirko选择\((a,b)(c,d)\)且满足\(a<b<c<d\)这样的，当\(x=c\)时Mirko就会输。
并且由第三种情况我们不难推出标算的思想：把互质对看做一条\(a->b\)的线段，问题就转化为区间覆盖问题
解题步骤
1.设计\(dp\)：\(dp[i][j]\)为选到第\(i\)个互质对，即第\(i\)条线段时，覆盖区间\(1~j\)的方案数，若cnt为互质对的总数，则答案为\(dp[cnt][n]\)；
2.将所有线段（互质对）按照右端点大小从小到大排序；
3.注意初始化：\(dp[0][1]=1\)。
4.推导\(dp\)方程：设\(l_i r_i\)分别为第\(i\)条线段的左右端点。
\(dp[i][j]=dp[i][j]+dp[i-1][j]\)
\(if(l_i<=j) dp[i][r_i]=dp[i][r_i]+dp[i-1][j]\)
\(if(l_i>j) dp[i][j]=dp[i][j]+dp[i-1][j]\)
以下为AC代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1500;
const int mod=1e9;
int n,cnt;
struct P
{
int x,y;
}a[N];
bool cmp(P a,P b)
{
return a.y<b.y;
}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
void Dp()
{
ll dp[N][25];
dp[0][1]=1;
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
if(a[i].x<=j) dp[i][a[i].y]=(dp[i][a[i].y]+dp[i-1][j])%mod;
else dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
}
}
printf("%lld\n",dp[cnt][n]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int Gcd=gcd(i,j);
if(Gcd==1) a[++cnt]={i,j};
}
}
sort(a+1,a+cnt+1,cmp);
Dp();
return 0;
} 手机扫一扫
移动阅读更方便
你可能感兴趣的文章