HDU 4259 Double Dealing(離散数学)#By Plato
http://acm.hdu.edu.cn/showproblem.php?pid=4259
あなたにn枚のカードをあげて、k人に分けて、1-nから順番に分けます.そして、再びカードを一緒に置きます.1人目の人は一番上に、後ろの人は順番に下に置きます.もう一度分けて、置いて、何回聞いたら元に戻りますか.
Idea:
素朴な思想:シミュレーションは各点に対して変換を行って、それぞれ周期Ciを求めて、それから彼らの最小公倍数を求めます.(TLE)
最適化:ある位置のカードがAからAに戻ると、A->B->C->...->Aの密閉サイクルが経験されることがわかり、サイクル内の各要素について、いずれかの要素を計算するだけでよい.
【ついでにHDUピットお父さんのlong long出力に突っ込み、printf("%lld",ans)でWAに違いない.G++でもC++でも.そしてpirntf("%I 64 d",ans)、cout<
Add:位置交代の原理と実現
a[i] = j;位置iが位置jのカードに置き換えられることを示す.
i<-j <-k;i変換を2回要求してそのカードに置き換えられた場合、すなわちj変換がどのカードに置き換えられるかを求める.もちろんここのi,j,kはいずれも初回の初期位置番号であり、カードとしても理解できる.
実現するには,1)main()では逆順で読む方法を先に区別することが直感的である.
2)他の人のプログラムを見て、一歩一歩の方法で、
for (int i = 1;i <= K;i++)
{
for (int j = (N- i)/K *K + i;j > 0;j -= K)
{ a[num++] = j; }
}i番目の列について、その持つ要素の個数が(N-i)/K+1であることを知れば、よく理解できる
あなたにn枚のカードをあげて、k人に分けて、1-nから順番に分けます.そして、再びカードを一緒に置きます.1人目の人は一番上に、後ろの人は順番に下に置きます.もう一度分けて、置いて、何回聞いたら元に戻りますか.
Idea:
素朴な思想:シミュレーションは各点に対して変換を行って、それぞれ周期Ciを求めて、それから彼らの最小公倍数を求めます.(TLE)
最適化:ある位置のカードがAからAに戻ると、A->B->C->...->Aの密閉サイクルが経験されることがわかり、サイクル内の各要素について、いずれかの要素を計算するだけでよい.
【ついでにHDUピットお父さんのlong long出力に突っ込み、printf("%lld",ans)でWAに違いない.G++でもC++でも.そしてpirntf("%I 64 d",ans)、cout<
#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
long long gcd(long long a,long long b)
{
return b?gcd(b,a%b):a;
}
int main()
{
freopen("test.txt","r",stdin);
int N,K;
while (scanf("%d%d",&N,&K),N|| K)
{
static int rec[810][810];
static int a[810];
int num = 1;
for (int i = 1;;i++)
{
for (int j = 1;j <= K;j++)
{
rec[i][j] = num++;
if (num >N) break;
}
if (num > N) break;
}
num = 1;
for (int i = 1;i <= K;i++)
{
for (int j = (N-i)/K+1;j >= 1;j--)
{
a[num++] = rec[j][i];
}
}
static bool vd[810];
memset(vd,0,sizeof(vd));
long long ans = 1;
for (int i = 1;i <= N;i++)
{
if (vd[i]) continue;
num = i;
long long count = 0;
do
{
num = a[num];
vd[num] = true;
count++;
}
while (num != i);
ans = ans/gcd(ans,count)*count;
}
printf("%I64d
",ans);
}
return 0;
}
/*
for (int i = 1;i <= K;i++)
{
for (int j = (N- i)/K *K + i;j > 0;j -= K)
{
a[num++] = j;
}
}
*/
Add:位置交代の原理と実現
a[i] = j;位置iが位置jのカードに置き換えられることを示す.
i<-j <-k;i変換を2回要求してそのカードに置き換えられた場合、すなわちj変換がどのカードに置き換えられるかを求める.もちろんここのi,j,kはいずれも初回の初期位置番号であり、カードとしても理解できる.
実現するには,1)main()では逆順で読む方法を先に区別することが直感的である.
2)他の人のプログラムを見て、一歩一歩の方法で、
for (int i = 1;i <= K;i++)
{
for (int j = (N- i)/K *K + i;j > 0;j -= K)
{ a[num++] = j; }
}i番目の列について、その持つ要素の個数が(N-i)/K+1であることを知れば、よく理解できる