USACO 2.2

  • 序言页码 Preface Numbering
  • 集合 Subset Sums
  • 循环数 Runaround Numbers
  • 派对灯 Party Lamps

P1465 序言页码 Preface Numbering

其实,这题只要读懂题,
而且不要怕麻烦,就能AC?打表是正解?
总的来说,还是
暴力出奇迹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
char c[31][5]={
" ","I","II","III","IV","V","VI","VII","VIII","IX","X",
"XX","XXX","XL","L","LX","LXX","LXXX","XC","C","CC",
"CCC","CD","D","DC","DCC","DCCC","CM","M","MM","MMM"};
int num[31]={0,1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,
80,90,100,200,300,400,500,600,700,800,900,1000,2000,3000};//每个字母对应的数字
int n;
int a[26];//26个字母,大雾,其实是存那几个字母的数量
void find(int nn)//nn转成罗马数字然后统计?
{
int j=30;
char s[30];
while (num[j]>nn) j--;//找到第一个<=n的数
for (;j>=1;j--)
{
if (nn>=num[j])//如果nn比这个数大或者等于这个数
{/*其实是不用担心40被强行分成XXX和X的,因为40在表中*/
nn-=num[j];//减掉
for (int x=0;x<strlen(c[j]);x++)//统计各个字母的个数
a[int(c[j][x])-65]++;
}
if (nn==0) return; //节约时间。已经搜完了
}
}
int main()
{
freopen("preface.in","r",stdin);
freopen("preface.out","w",stdout);
scanf("%d",&n);//读入
for (int i=1;i<=n;i++)
find(i);
//输出,因为是按照这个顺序所以我找不到什么好办法输出了
if (a[int('I')-65]!=0) printf("I %d\n",a[int('I')-65]);
if (a[int('V')-65]!=0) printf("V %d\n",a[int('V')-65]);
if (a[int('X')-65]!=0) printf("X %d\n",a[int('X')-65]);
if (a[int('L')-65]!=0) printf("L %d\n",a[int('L')-65]);
if (a[int('C')-65]!=0) printf("C %d\n",a[int('C')-65]);
if (a[int('D')-65]!=0) printf("D %d\n",a[int('D')-65]);
if (a[int('M')-65]!=0) printf("M %d\n",a[int('M')-65]);
return 0;
}

集合 Subset Sums

n个数的总和为sum:=n*(n+1) >> 1,当且仅当sum为偶数的时候才有解,sum为奇数时直接输出0并且退出程序;然后每个数只有2种情况,放在第一个集合和不放在第一个集合。于是就是简单的01背包问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int sum/*1~n的和*/,n;
int f[40][800];
int i,j;
int main()
{
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
scanf("%d",&n);
sum=(n*(n+1))/2;//算出1~n的和。
if (sum%2==1)//仅当sum为偶数的时候才有解
{
printf("0\n");//因为分成的2份和要相等
return 0;
}
f[1][1]=1;//1中取任意个数的数使和为1的情况
f[1][0]=1;//1中取任意个数的数使和为0的情况
for (i=2;i<=n;i++)//1的情况已经算完了,所以从2开始
{
for (j=0;j<=sum;j++)
{
if (j>i)//有取这个数和不取两种情况
f[i][j]=f[i-1][j]+f[i-1][j-i];
else f[i][j]=f[i-1][j];//只能不取了
}
}
printf("%d\n",f[n][sum/2]);
return 0;
}

循环数 Runaround Numbers

这道题翻译得不是特别好,读题需要仔细,然后判断什么的都要有。总的来说算是复杂的枚举题

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include
//#include

#include

#include

#define LL unsigned long long
using namespace std;
long long n;int i;
int a[30],b[30],ii,c[30],be,f;//a存被强拆的n的每一位,ii存被拆的数的长度
void chai(long long gg)
{
ii=1;//防止报错?
int x=0;
int aa[233]={0};
long long g;
g=gg;
while (g>0)
{
x++;//记位数
b[x]=g%10;
if (aa[b[x]]==1)//重复了
{
f=0;
ii=1;//存下位数?防止报错!
return;
}
if (b[x]==0)//不能有0
{
f=0;
ii=1;//存下位数?防止报错!
return;
}
aa[b[x]]=1;//标记
g=g/10;
}//把g强拆了。

ii=x;//存下位数 
for (i=1;i<=x;i++)
    a[i]=b[ii-i+1];//正着存到a数组 
return;

}
int main()
{
freopen(“runround.in”,”r”,stdin);
freopen(“runround.out”,”w”,stdout);
cin>>n;//读入n;
do
{
n++;
f=1;//标记用,1代表这个数符合条件
chai(n);//把n拆了
//int yu=n%ii;//求出余数,数其实只要数余数
a[0]=a[ii];//如果数到余数是0的话,就是a[n]
for (i=0;i<30;i++) c[i]=0;//清0
be=1;//be是起始位;
if (f==1)//已经被排除的情况不要继续搜了
for (i=1;i<=ii;i++)//有多少位进行多少次枚举,出现
{
be=(be+a[be])%ii;//求第i次将被标记的数
if (c[be]==1)//搜过辣,之后肯定会死循环
{
f=0;//标记这个数不符合条件
break;//退出
}
c[be]=1;//标记;
}
if (f==1)//如果这个数符合条件
{
printf(“%d\n”,n);
return 0;
}
}
while (true);
return 0;
}

派对灯 Party Lamps

每个按钮按2次和没按效果是一样的。所以每个按钮或者按或者不按,一共有2^4=16种状态。枚举每个按钮是否按下,然后生成结果,排序输出即可(注意判重)。

另外灯1和灯7,2和8,3和9…是一样的因此当N>=6时只需处理前6个,排序时转换为10进制数, 输出时反复输出前6个的状态.

深究:

我们现在记不按按钮,以及按下1,2,3,4按钮分别O,①,②,③,④, 那么,按下3,4,可以记为③④,以此类推, 我们发现一个问题,那就是①,②,③之间微妙的关系, ①②=③,而②③=①,①③=②(可以自己试试),于是我们知道,①②③也相当与不按,即相差3的倍数也可互相转换;
所以,所谓前四个的16种按法其实只有8种, 分别为:O,①,②,③,④,①④,②④,③④;
然后讨论c, 由于当c>4时,均可化为当c<=4的情况, 所以我们先讨论当c<=4的情况,

当c=0时,只有一种O;

当c=1时,四种:①,②,③,④;

当c=2时,除了④均可(可以自己想想);

当c=3时,由于3-1=2,所以c=1的情况都满足,而在c=2中,把所有有前三类的展开,如①④变为②③④, 可知满足c=2的同时满足c=3,所以c=3其实是c=2和c=1的并集,即所有按法均可。

当c=4时,由于4-1=3(①②③相当于不按),且4-2=2,由上,c=4也是所有按法均可。
当c>4时,我先有一个引理:对于任意的正整数n>1,均可写成n=2p+3q(p,q为非负整数)的形式, 证明如下:若n为偶数,必然成立,若n为奇数,必然大于2,则n-3必为非负偶数,得证。 由这个引理我们可以知道,任意c>4均可写成,c=2p+3q+3(p,q为非负整数)的形式,而可知, 对于两个相同的按键,以及情况①②③(按键三次),均相当于不按,所以任意c>4均可化归为c=3的情况, 即当c>4时,所有按法均可。

综上所述,

当c=0时,只有一种O;

当c=1时,四种:①,②,③,④;

当c=2时,除了④均可;

当c>2时,所有按法均可。

好了,这样一来就非常简单了, 只有四种情况,8种按法。

于是我们就可以打个表了。打表也要注意下顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
int n,c,i,j;//c:计数器君,n:灯的盏数
int l[101];//最后灯的状态,-1为不作要求,1为亮,0为灭
int f;//标记有没有解,无解为0
int b[9][7]=//华丽的表
{0,0,0,0,0,0,0,
0,0,0,0,0,0,0,//按1
0,0,0,1,1,1,0,//按1按4
0,0,1,0,1,0,1,//按3
0,0,1,1,0,1,1,//按1按4
0,1,0,0,1,0,0,//按4
0,1,0,1,0,1,0,//按2
0,1,1,0,0,0,1,//按2按4
0,1,1,1,1,1,1,};//不按 注意顺序!
//int s[9]={0,1,1,1,1,2,2,2,0};//达到对应的某种状态最少需要按的次数
int main()
{
scanf("%d%d",&n,&c);
i=0;
int x;
for (i=1;i<=6;i++) l[i]=-1;
scanf("%d",&x);//读入
while (x!=-1)
{
if ((x%6)==0) l[6]=1;//标记
else l[x%6]=1;//标记 ,全部映射到1~6中
scanf("%d",&x);//读入
}
scanf("%d",&x);//读入
while (x!=-1)
{
if ((x%6)==0) l[6]=0;//标记
else l[x%6]=0;//标记 ,全部映射到1~6中
scanf("%d",&x);//读入
}
//-------------------读入完毕-------------------//
if (c>=4) c=3;//反正3以上所有方法都可行
switch (c)
{
case 0://什么都不按 ,别忽略,有2个点
{
for (i=8;i<=8;i++)//只有不按
{
int ah=1;//标记用
for (j=1;j<=6;j++)
{
if (l[j]!=-1)//对这一位有做要求
if (b[i][j]!=l[j])
{
ah=0;//标记
break;
}
}
if (ah==1)//这种情况符合条件
{
f=1;//标记
for (j=1;j<=n;j++)
printf("%d",b[i][(j-1)%6+1]);
printf("\n");
}
}
break;
}
case 1:
{
for (i=1;i<=8;i++)//前四种都可以有
{
if (i!=1||i!=3||i!=5||i!=6) continue;
int ah=1;//标记用
for (j=1;j<=6;j++)
{
if (l[j]!=-1)//对这一位有做要求
if (b[i][j]!=l[j])
{
ah=0;//标记
break;
}
}
if (ah==1)//这种情况符合条件
{
f=1;//标记
for (j=1;j<=n;j++)
printf("%d",b[i][(j-1)%6+1]);
printf("\n");
}
}
break;
}
case 2:
{
for (i=1;i<=8;i++)//除开4都可以
{
if (i==5) continue;
int ah=1;//标记用
for (j=1;j<=6;j++)
{
if (l[j]!=-1)//对这一位有做要求
if (b[i][j]!=l[j])
{
ah=0;//标记
break;
}
}
if (ah==1)//这种情况符合条件
{
f=1;//标记
for (j=1;j<=n;j++)
printf("%d",b[i][(j-1)%6+1]);
printf("\n");
}
}
break;
}
case 3:
{
for (i=1;i<=8;i++)//都可以
{
int ah=1;//标记用
for (j=1;j<=6;j++)
{
if (l[j]!=-1)//对这一位有做要求
if (b[i][j]!=l[j])
{
ah=0;//标记
break;
}
}
if (ah==1)//这种情况符合条件
{
f=1;//标记
for (j=1;j<=n;j++)
printf("%d",b[i][(j-1)%6+1]);
printf("\n");
}
}
break;
}
}
if (f==0) printf("IMPOSSIBLE\n");//无解
return 0;
}