| Section 2.2 | DONE | 2012.08.29 | TEXT Data Structures |
| DONE | 2012.08.29 | TEXT Dynamic Programming | |
| DONE | 2012.08.30 | PROB Preface Numbering [ANALYSIS] | |
| DONE | 2012.08.29 | PROB Subset Sums [ANALYSIS] | |
| DONE | 2012.08.31 | PROB Runaround Numbers [ANALYSIS] | |
| DONE | 2012.08.31 | PROB Party Lamps [ANALYSIS] |
2.2关的参考材料讲解了常用的散列表、二叉树、堆等数据结构和动态规划（DP）的思想。
Preface Numbering：
罗马数字用一系列符号表示特定数值，I 1 V 5 X 10 L 50 C 100 D 500 M 1000。
一本书的页码从1到N（N<=3500）用罗马数字表示，统计所用的各种罗马数字符号的个数。
比如N=5时， I, II, III, IV, V一共需要7个I和2个V。
N的上限不大，关键是找到将一般数字转化为罗马数字的方法。为此我根据罗马数字组成规则先将其能表示的“不可分解”数值由大到小列出：M 1000，CM 900，D 500，CD 400，C 100，XC 90，L 50，XL 40，X 10，IX 9，V 5I，V 4，I 1
对特定页码，按从大到小的顺序用这些数值对其进行分解，比如3409=3*1000+400+9=MMMCDIX
点击查看我的源码：
/*
ID: *******
LANG: C++
TASK: preface
*/
#include<stdio.h>
#include<stdlib.h>
/*M 1000
CM 900
D 500
CD 400
C 100
XC 90
L 50
XL 40
X 10
IX 9
V 5
IV 4
I 1
I V X L C D M
*/
FILE *fin,*fout;
int N;
int count[3501][7];
int dict[13][7]={
{0,0,0,0,0,0,1},
{0,0,0,0,1,0,1},
{0,0,0,0,0,1,0},
{0,0,0,0,1,1,0},
{0,0,0,0,1,0,0},
{0,0,1,0,1,0,0},
{0,0,0,1,0,0,0},
{0,0,1,1,0,0,0},
{0,0,1,0,0,0,0},
{1,0,1,0,0,0,0},
{0,1,0,0,0,0,0},
{1,1,0,0,0,0,0},
{1,0,0,0,0,0,0}
};
int hash[13]={
1000,900,500,400,100,90,50,40,10,9,5,4,1
};
char ch[7]={'I','V','X','L','C','D','M'};
int main(){
fin=fopen("preface.in","r");
fout=fopen("preface.out","w");
fscanf(fin,"%d",&N);
int i,j;
for(i=1;i<=N;i++){
for(j=0;j<7;j++)
count[i][j]=count[i-1][j];
int t=i;
for(j=0;j<13;j++){
if(t==0)break;
int m=t/hash[j];
int k;
for(k=0;k<7;k++)
count[i][k]+=dict[j][k]*m;
t%=hash[j];
}
}
for(i=0;i<7;i++)
if(count[N][i]>0)
fprintf(fout,"%c %d\n",ch[i],count[N][i]);
return 0;
}
Subset Sums：
对于集合{1,2,...,N}（N<=39），将其划分为两个互补的子集，使得两个子集各自元素之和相等，求可行的划分方法数。
比如{1,2,...,7}可以有4种划分：
- {1,6,7} and {2,3,4,5}
- {2,5,7} and {1,3,4,6}
- {3,4,7} and {1,2,5,6}
- {1,2,4,7} and {3,5,6}
集合的子集一共有2N个，直接枚举显然会超时。实际上这是一个典型的动态规划问题。
首先我们对问题做进一步的抽象（这一步很重要）。给定一个N之后，元素的总和为(N+1)*N/2，那么实际上我们是要求出所有元素和为(N+1)*N/4的子集，然后这个子集数量除以2就是我们要的结果。当然如果(N+1)*N/2为奇数，那么一定无解。我们用dp[i][s]表示集合{1,2,...,i}的元素总和为s的子集的数量，比如根据上边的例子，dp[7][14]=8。
状态转移方程：
dp[i][s]=dp[i-1][s]+dp[i-1][s-i]
这个状态转移方程是怎么得到的呢？我们对第i个元素（也就是i）进行讨论，如果符合条件的子集中不包含i，这样的子集个数是dp[i-1][s]；如果符合条件的子集中包含i，这样的子集个数是dp[i-1][s-i]！这样我们就把计算dp[i][s]转换成了更小规模的子问题（计算dp[i-1][s]和dp[i-1][s-i]），并且能在常数时间内对子问题进行“拼装”构造出更大规模的问题的解！这也正是动态规划的奥义所在。
下一步我们就要确定问题的“边界条件”了。在计算dp[i][s]的时候，问题规模越来越小（换句话说，参数i、s的值越来越小），但是总归要有一个界限，这个界限就是“边界条件”。边界条件一般是一些极限情况，比如在这里我们考虑i=1，s>0时的情况，显然除了dp[1][1]=1 其余dp[1][s]都为0。那么当s足够小的时候会出现什么情况呢，我们考虑s=0，那么dp[i][0]=1，这是为什么呢，因为任何集合有一个空集作为子集。现在我们可以将dp矩阵表示为下图，从图示中我们可以看到“边界条件”的确在dp矩阵中占据了边界位置。
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
|---|---|---|---|---|---|---|
| 1 | ||||||
| 1 | ||||||
| 1 | ||||||
| 1 | ||||||
| 1 |
因为dp[i][s]的计算只会用到dp矩阵中同一层的左边和上一层的值，我们从i=2开始，将迭代计算的顺序安排为从上到下，从左到右，一直计算到dp[N][N*(N+1)/4]，这个值的一半即为答案。
点击查看我的源码：
/*
ID: *******
LANG: C++
TASK: subset
*/
#include<stdio.h>
#include<stdlib.h>
FILE *fin,*fout;
int N;
long long dp[40][391];
//dp[i][sum]=dp[i-1][sum-i]+dp[i-1][sum]
int main(){
fin=fopen("subset.in","r");
fout=fopen("subset.out","w");
fscanf(fin,"%d",&N);
int sum=(N+1)*N/2;
if(sum%2==1){
fprintf(fout,"0\n");
return 0;
}
sum/=2;
int i,j;
dp[1][1]=1;
for(j=2;j<=sum;j++)
dp[1][j]=0;
for(i=1;i<=N;i++)
dp[i][0]=1;
for(i=2;i<=N;i++)
for(j=1;j<=sum;j++){
dp[i][j]=dp[i-1][j];
if(j-i>=0)
dp[i][j]+=dp[i-1][j-i];
}
fprintf(fout,"%lld\n",dp[N][sum]/2);
return 0;
}
Runaround Numbers：
一个Runaround Number的例子是81362
Runaround numbers are integers with unique digits, none of which is zero (e.g., 81362) that also have an interesting property, exemplified by this demonstration:
- If you start at the left digit (8 in our number) and count that number of digits to the right (wrapping back to the first digit when no digits on the right are available), you'll end up at a new digit (a number which does not end up at a new digit is not a Runaround Number). Consider: 8 1 3 6 2 which cycles through eight digits: 1 3 6 2 8 1 3 6 so the next digit is 6.
- Repeat this cycle (this time for the six counts designed by the `6') and you should end on a new digit: 2 8 1 3 6 2, namely 2.
- Repeat again (two digits this time): 8 1
- Continue again (one digit this time): 3
- One more time: 6 2 8 and you have ended up back where you started, after touching each digit once. If you don't end up back where you started after touching each digit once, your number is not a Runaround number.
Given a number M (that has anywhere from 1 through 9 digits), find and print the next runaround number higher than M, which will always fit into an unsigned long integer for the given test data.
方法一：
如果能注意到开始的“Runaround numbers are integers with unique digits”这个信息，可以想到Runaround Number最多只有9位，我们最多需要排列9个数字，枚举每种可能并且检验其是否为大于M的Runaround Number，然后从中选取一个最小的Runaround Number，枚举量为9!=362880，即使考虑到M比位数相同的数字中最大的Runaround Number还要大的情况，枚举量最多也只有8!+9!=403200，是可行的。
至于数字的全排列可以用“洗牌”算法搞定，比如1 2 3 4 四个数字的全排列，我们可以从1开始，让1不动或者与其后的数字交换，然后我们对第二位、第三位执行相同的步骤，让这些位置上的数字不动或者与其后的数字进行交换，这样就构造出了所有可能的排列。
方法二：
实际上我没有注意到“Runaround numbers are integers with unique digits”这个条件。但是我用一种构造方法同样解决了这个问题。首先我意识到一个Runaround Number各个数位上的值是由我们做“Runaround”的顺序决定的，比如81362循环的顺序是8-6-2-1-3。我们把每个数字用它出现的顺序代替就得到了14523，这实际上是{1,2,3,4,5}全排列的一种情况！这样我们通过生成一个5位的全排列就能决定一种Runaround Number，之所以我在这里说“一种”是因为一个排列可能对应多个Runaround Number，比如从排列14523生成，“1”和“2”之间相差3位，那么第一位上我们可以放置3或者8。由于我们总是从第一位开始数，所以要生成所有n位的Runaround Number，我们只需要做一个{1,2,3,...,n-1}的全排列，对于M=9，枚举量为8!，考虑到M比位数相同的数字中最大的Runaround Number还要大的情况，枚举量最多为8!+7!=45360。由于这种方法直接生成所有可能的Runaround Number，效率比方法一要高，但是构造过程增加了编程的复杂度。
点击查看我的代码：
/*
ID: *******
LANG: C++
TASK: runround
*/
#include<stdio.h>
#include<stdlib.h>
FILE *fin,*fout;
int order[10];
int num[10];
unsigned long int M;
unsigned long int ans;
int L;
bool found;
int max[10]={4,2,9,4,9,6,7,2,9,5};
void check(int l){
int i;
if(l==10)
for(i=0;i<10;i++){
if(num[i]<max[i])break;
else if(num[i]>max[i])
return;
}
int j;
for(i=0;i<l;i++)
for(j=0;j<l;j++){
if(i!=j && num[i]==num[j])
return;
}
unsigned long int t=0;
unsigned long int weight=1;
for(i=l-1;i>=0;i--){
t+=weight*num[i];
weight*=10;
}
if(t>M && t<ans){
found=true;
ans=t;
}
return;
}
void createNum(int po,int l){
if(po==l){
check(l);
return;
}
int next=(order[po]+1)%l;
int nextPo;
for(nextPo=0;nextPo<l;nextPo++)
if(order[nextPo]==next)
break;
int numPo=nextPo-po;
if(numPo<0)
numPo+=l;
while(numPo<10){
num[po]=numPo;
createNum(po+1,l);
numPo+=l;
}
return;
}
void swap(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
return;
}
void createOrder(int po,int l){
if(po==l){
createNum(0,l);
return;
}
int i;
for(i=po;i<l;i++){
swap(&order[po],&order[i]);
createOrder(po+1,l);
swap(&order[po],&order[i]);
}
return;
}
int main(){
fin=fopen("runround.in","r");
fout=fopen("runround.out","w");
fscanf(fin,"%lu",&M);
L=0;
unsigned long int t=M;
while(t){
L++;
t/=10;
}
found=false;
ans=0xffffffff;
int i;
for(i=0;i<L;i++)
order[i]=i;
createOrder(1,L);
if(!found && L<10){
for(i=0;i<L+1;i++)
order[i]=i;
createOrder(1,L+1);
}
fprintf(fout,"%lu\n",ans);
return 0;
}
Party Lamps：
To brighten up the gala dinner of the IOI'98 we have a set of N (10 <= N <= 100) colored lamps numbered from 1 to N.
The lamps are connected to four buttons:
- Button 1: When this button is pressed, all the lamps change their state: those that are ON are turned OFF and those that are OFF are turned ON.
- Button 2: Changes the state of all the odd numbered lamps.
- Button 3: Changes the state of all the even numbered lamps.
- Button 4: Changes the state of the lamps whose number is of the form 3xK+1 (with K>=0), i.e., 1,4,7,...
A counter C records the total number of button presses.
When the party starts, all the lamps are ON and the counter C is set to zero.
You are given the value of counter C (0 <= C <= 10000) and the final state of some of the lamps after some operations have been executed. Write a program to determine all the possible final configurations of the N lamps that are consistent with the given information, without repetitions.
我们首先注意到每个按钮按2次相当于没有按，同时按钮的顺序对结果没有影响。这样对于每种按钮实际上只有按和不按两种效果，枚举每个按钮按或不按，那么最终状态最多为16种（虽然有重复，比如 按下按钮1 和 按下按钮2与按钮3 就可以得到同样的结果，但我们仍然认为这是两种，因为达到这一状态的基本操作是不同的，这在我们判断此状态能否通过C次按键得到时很重要）。我们计算出这16种情况，找出最终状态符合题设的那些并且检验能否用C次按键达到这种状态就可以了。
如何检验某种状态是否可以在C次按键后达到？这16种状态每种都有一个最小按键数（最小为0，最大为4），也就是我们枚举过程中按下的按钮总数。对于状态x，如果C超过了它的最小按键数，那么我们按C次按钮可以得到状态x吗？答案是如果C超出最小按键数1次则不可能，否则完全可以。首先我们可以随意按某个按钮两次来增加按键数，此外按下1 2 3三个按钮各一次也相当于没按！而任意一个大于1的数都能用2和3的线性组合得到，这样我们一定能够通过叠加这些“无用操作”保持最小按键数的效果，同时将按键数增加到C！
点击查看我的源码：
/*
ID: *******
LANG: C++
PROG: lamps
*/
#include<stdio.h>
#include<stdlib.h>
FILE *fin,*fout;
int N;
int C;
bool onset[100];
bool offset[100];
bool ansset[16][100];
bool change[4][100];
bool tmp[100];
int count[16];
int tailAns;
void createChange(){
int i;
for(i=1;i<=100;i++){
change[0][i-1]=true;
if(i%2==1)
change[1][i-1]=true;
if(i%2==0)
change[2][i-1]=true;
if(i%3==1)
change[3][i-1]=true;
}
}
void changeLamps(int n,bool *t){
int i;
for(i=1;i<=N;i++)
if(change[n][i-1])
t[i-1]=1-t[i-1];
}
int cmp(bool *a,bool *b,int l){
int i;
for(i=0;i<l;i++)
if(a[i]>b[i])return 1;
else if(a[i]<b[i])return -1;
return 0;
}
void createAnsset(int n,int c){
int i,j;
if(n==4){
for(i=tailAns;i>=0;i--){
if(cmp(tmp,ansset[i],N)==-1){
count[i+1]=count[i];
for(j=0;j<N;j++)
ansset[i+1][j]=ansset[i][j];
}
else
break;
}
tailAns++;
count[i+1]=c;
for(j=1;j<=N;j++)
ansset[i+1][j-1]=tmp[j-1];
return;
}
createAnsset(n+1,c);
changeLamps(n,tmp);
createAnsset(n+1,c+1);
changeLamps(n,tmp);
return;
}
bool check(int n,int pre){
int i;
for(i=0;i<N;i++){
if(onset[i] && !ansset[n][i])return false;
if(offset[i] && ansset[n][i])return false;
}
if(C-count[n]==1||C-count[n]<0){
return false;
}
if(pre==-1)return true;
for(i=0;i<N;i++)
if(ansset[n][i]!=ansset[pre][i])
return true;
return false;
}
int main(){
fin=fopen("lamps.in","r");
fout=fopen("lamps.out","w");
fscanf(fin,"%d\n%d",&N,&C);
int t=0;
int i;
while(t!=-1){
fscanf(fin,"%d",&t);
onset[t-1]=true;
}
t=0;
while(t!=-1){
fscanf(fin,"%d",&t);
offset[t-1]=true;
}
createChange();
for(i=1;i<=N;i++)
tmp[i-1]=true;
tailAns=-1;
createAnsset(0,0);
int pre=-1;
bool exit=false;
for(i=0;i<=tailAns;i++){
if(check(i,pre)){
exit=true;
int j;
for(j=0;j<N;j++)
fprintf(fout,"%d",ansset[i][j]);
fprintf(fout,"\n");
pre=i;
}
}
if(!exit)fprintf(fout,"IMPOSSIBLE\n");
return 0;
}
评论 (0)
