这题的话，话说感觉就是一个暴力的枚举，没多余要考虑的，一方面对所有整数开始枚举，设当前枚举的是i，那么在用i和所有已知的海明码进行比较，海明距离大于等于D的话就成为一个新的海明码，一直枚举出N个海明码。 得出海明距离也很简单，就从第一个位开始，一个不同的就记录一下，我直接把8位都枚举一次，所以B这个数据对我却是没有用，代码如下：
分类： 算法
-
USACO 2.1.5 Hamming Codes 解题报告
de lang="c">/ LANG: C ID: yylogoo1 PROG: hamming / #include int num[64]; int count = 0; int ham(int a, int b) { int c = 0 ; int i; for(i = 0; i <8 i ifa="(b" c a><= 1, b <<= 1; } return c; } int main(void) { int n, b, d; int i, j; freopen("hamming.in", "r", stdin); freopen("hamming.out", "w", stdout); scanf("%d%d%d", &n, &b, &d); for(i = 0; count != n; i++){ for(j = 0; j de> -
USACO 2.1.4 Healthy Holsteins 解题报告
咋一看，真是一个爆难的题目，但是仔细一想，其实也很简单，怎么个简单呢？对于每种食物来说，只有两种选择：吃或不吃，对吧，暴力枚举就是，只有2^15种方案，虽然数字还是非常大的，但是一秒钟的时限还是超不了，代码晚点发，在Linux下。 代码来了：
/ ID: yylogoo1 PROG: holstein LANG: C / #include#include int have[15][25]; int need[25]; int v, g; int got[25]; int used[15], ans[15]; int tot = 26, tmp; void check(void) { int i; if(tot tmp){ tot = tmp; memcpy(ans, used, sizeof(used)); }else if(tot == tmp){ for(i = 0; i ans[i]){ tot = tmp; memcpy(ans, used, sizeof(used)); return; }else if(used[i] <ans i return void srchint now int i check ifnow="= g){" return srchnow tmp usednow="1;" fori="0;" i v i goti="have[now][i];" srchnow tmp-- usednow="0;" fori="0;" i v i goti -="have[now][i];" int mainvoid int i j freopenholsteinin r stdin freopenholsteinout w stdout scanfd v fori="0;" i v i scanfd needi scanfd g fori="0;" i g i forj="0;" j v j scanfd haveij srch printfd tot fori="0;" i g i ifansi printf d i printfn return code> -
USACO 2.1.3 Sorting A Three-Valued Sequence 解题报告
首先用两个数组分别保存排了序的数组和没排序的数组，然后再根据这两个判断，当前这个位置上应该是放什么数，而实际上放的是什么数，如果两个位置上需要的都正好是对方所有的，那么这是最好的，进行循环，把所有这种的都交换掉，然后累计交换次数。 但是最后会有这么一种情况，三个位置需要的分别是1, 2, 3，而他们有的分别是3, 1, 2，这时就要交换两次了，而且仔细考虑的话会发现当前面循环完了之后，就只可能剩下这么一种情况了，当然，对数可能不止一对，所以就累计需要的和拥有的不相同的那些，统计起来，处以三再除以二，就是交换次数，结果就出来了。 代码如下：
/ ID: yylogoo1 PROG: sort3 LANG: C / #includeint n; int have[1000]; int need[1000]; int com(void const a, void const b) { return (int )a - (int )b; } int ans; int main(void) { int i, j; freopen("sort3.in", "r", stdin); freopen("sort3.out", "w", stdout); scanf("%d", &n); for(i = 0; i -
USACO 2.1.2 Ordered Fractions 解题报告
这题我的方法就是下面这个，不然的话就要爆搜，这个规律不知道平时用的上不，但现在这会儿挺好用：
0/1 1/1 1/2 1/3 2/3 1/4 2/5 3/5 3/4 1/5 2/7 3/8 3/7 4/7 5/8 5/7 4/5
利用这个规律可以非常快的解决，不过至于为什么你们自己想去吧（我也没想通，反正能用的规律就OK了，AC就是王道。） 代码晚一点发上来，在Linux那台电脑里。
2010 年 12 月 28 日 12:14:36
我的那个Fedora坏了，又忘记备份/home了，又全部更新了硬盘的文件系统，代码就被。。。就用标称算了，反正是一样的。
#include#include #include #include int n; FILE fout; / print the fractions of denominator n) / cut off recursion / return; genfrac(n1,d1, n1+n2,d1+d2); fprintf(fout, "%d/%d\n", n1+n2, d1+d2); genfrac(n1+n2,d1+d2, n2,d2); } void main(void) { FILE *fin; fin = fopen("frac1.in", "r"); fout = fopen("frac1.out", "w"); assert(fin != NULL && fout != NULL); fscanf(fin, "%d", &n); fprintf(fout, "0/1\n"); genfrac(0,1, 1,1); fprintf(fout, "1/1\n"); } -
Noip 2010 提高组 第三题 关押罪犯
这题的话，就是贪心，把最大的罪恶值的两个囚犯都不关在一个牢房里，反复的贪心，但是数据太大，不允许使用邻接表和邻接矩阵，用什么结构来保存呢？我觉得（也是网上的资料里的咯）使用动态分配是个方法，因为最多10000条边，根据实际情况来分配，这样不会有浪费的空间，也就不会导致空间爆掉了。
#include <stdio.h>
#include <stdlib.h>
int m, n;
struct list{
int a, b, v;
}list[100001];
struct link{
int b;
struct link next;
}head[20000];
int color[20000];
int nowco = 1;int com(const void
a, const void b)
{
return ((struct list)b)->v – ((struct list)a)->v;
}void add(int a, int b)
p;
{
struct link
p = malloc(sizeof(struct link));
p->b = b;
p->next = head[a].next;
head[a].next = p;
}int other_color(int c)
{
if(c & 1){
return c + 1;
}
return c – 1;
}int min(int a, int b)
{
return a > b ? b : a;
}void dfs(int a)
{
struct link i;
for(i = head[a].next; i != NULL; i = i->next){
if((color[i->b] – color[a] >= –1) && (color[i->b] – color[a] <= 1) &&
(min(color[i->b], color[a]) & 1)){
continue;
}
color[i->b] = other_color(color[a]);
dfs(i->b);
}
}#define d(a) #a
int main(void)
{
int i, j;
struct link p;
int a, b;
freopen("prison"d(5)".in", "r", stdin);
scanf("%d%d", &n, &m);
for(i = 0; i < m; i++){
scanf("%d%d%d", &list[i].a, &list[i].b, &list[i].v);
list[i].a–, list[i].b–;
}
qsort(list, m, sizeof(struct list), com);
for(i = 0; i < m; i++){
a = list[i].a;
b = list[i].b;
add(a, b);
add(b, a);
if(color[a] == 0 || color[b] == 0){
color[a] = nowco++;
color[b] = nowco++;
continue;
}else if(color[a] == 0){
color[b] = other_color(color[a]);
continue;
}else if(color[b] == 0){
color[a] = other_color(color[b]);
continue;
}
if(color[a] == color[b]){
break;
}
dfs(b);
}
printf("%d\n", list[i].v);
getch();
return 0;
} -
Noip 2010 提高组 第二题 乌龟棋
在考场上我的思想是这么的，f[n +
j] = max{当在n这个位置时还有布数为j的卡片|f[n] + map[n + j]}，后来发现这么是不行的，因为f[n + j]不是最大但也可能有更好的取值，因为它可以留下另外一张卡片，只有10分呢！
后来，我又想了另外一种算法，用一个维护一个栈，然后判断所有的可能性（说白了就是暴力枚举。），很自然读者都想到了两字——Time Out(超时)，不过也有30分！
经过我的冥思苦想，终于是想到了另外一个方程，题目说的很清楚，每种卡片最多40张，那么就用卡片来枚举，f[a][b][c][d] = max{f[a –
1][b][c][d], f[a][b – 1][c][d], f[a][b][c – 1][d], f[a][b][c][d – 1]} + map[1
a + 2 b + 3 c + 4 d];
很自然的，这个方程式无敌的～AC了，只可惜是在家里而不是考场。。#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
#define index_map
int map[351];
int f[41][41][41][41];
int card[4];
int used[4];void srch(int n)
{
int i;
if(n == 4){
int t = 0;
if(used[0] != 0){
t = max(t, f[used[0] – 1][used[1]][used[2]][used[3]]);
}
if(used[1] != 0){
t = max(t, f[used[0]][used[1] – 1][used[2]][used[3]]);
}
if(used[2] != 0){
t = max(t, f[used[0]][used[1]][used[2] – 1][used[3]]);
}
if(used[3] != 0){
t = max(t, f[used[0]][used[1]][used[2]][used[3] – 1]);
}
f[used[0]][used[1]][used[2]][used[3]] = t + map[used[0] + used[1] 2 + used[2] 3 + used[3] * 4 + 1];
return;
}
for(i = 0; i <= card[n]; i++){
used[n] = i;
srch(n + 1);
}
}int main(void)
{
int i, j, k, t;
int n, m;
// freopen("tmp.in", "r", stdin);
scanf("%d%d", &n, &m);
for(i = 1; i <= n; i++){
scanf("%d", &map[i]);
}
for(i = 1; i <= m; i++){
scanf("%d", &t);
card[t – 1]++;
}
srch(0);
printf("%d\n", f[card[0]][card[1]][card[2]][card[3]]);
// getch();
return 0;
} -
Noip 2010 提高组 第一题 机器翻译
纯水题，维护一个列队，作为内存列队，并且写两个操作：进列队、出列队；因为数据量十分的小（n<=1000）所以可以维护一个用于标记的数组，如果单词在列队中则置为1，不在则置为0，接着就是暴力——模拟就是。
#include <stdio.h>int queue[1001];
int used[1001];
int tail, head;
int ans = 0;void enqueue(int n)
{
ans++;
queue[tail++] = n;
used[n] = 1;
}int exqueue(void)
{
used[queue[head]] = 0;
return queue[head++];
}int main(void)
{
int i, j;
int m, n;
scanf("%d%d", &m, &n);
for(i = 0; i < n && tail – head != m; i++){
scanf("%d", &j);
if(!used[j]){
enqueue(j);
}
}
while(i < n){
scanf("%d", &j);
if(!used[j]){
exqueue();
enqueue(j);
}
i++;
}
printf("%d\n", ans);
return 0;
} -
算法: 求最长的回文字符串
最近USACO写到了(第三次)1.3.3，这一题我用的是我自己原创的一个算法（可能也有别人想到了，但是对于我来说，确实是我自己独立思考出来的），在此发表一下。
程序：输入：一行字符串，输出：最长的回文字符的长度以及把它们给输出来。
如：
输入：1596156432111234
输出：6
432111234回文的性质
首先先把题目撇开，单说回文数的性质，如abcba是一个长度为5的回文数，那它有什么性质呢？
回文数顾名思义，就是从左念和从右念是相同的，也可以说从左遍历和从右遍历是相同的，这些都是废话。因为它是回文数所以可以同时从左和右开始遍历，各个字符都是相同的。
其实上面那些性质也没什么用，算是铺垫吧，接下来的才是重点，那怎么样去构成一个回文数呢？就用abcba做例子吧，这个回文数的构成是由单个字符c两边同时放置b，构成的bcb再两边同时放置一个a构成的。回文的判定
那么假设要你判断abcba是不是有两种方法，但是我要说的不是两边同时开始遍历并且判断的方法，再用abcbad做例子吧，用程序判断它是不是一个回文数，我先把过程写出来，然后再把方式写出来。
下面把回文数和回文混用。
首先下标i=0…5，s[i]代表第i个字符。i从1开始递归，因为第一个字符不存在回文数，i=1时，当前回文长度为1，就是单个字符a。当前回文数长度是我自己定义的名词，就是说以i结尾的回文数的长度。然后i = 2时，当前回文数是单个字符c，长度为1；i=3时，这里需要注意一下了，从这里开始就有一些变化了，当前回文数的长度为3，为bcb，i=4时，当前回文数的长度为5，为abcba，接着i=5，当前回文长度为1，是单个字符d，这样它就不是一个回文数。当前回文数长度
那么求当前回文数的长度(不是标准的语言)：
i = 1
while(i3321吧，当i = 3时(123321)，start[i] = 2(123321) len[i] = 2；当i = 5时(123321)，start[i] = 0(123321)，len[i] = 6，也就是说当前回文数的取决于三种情况：
第一种：start[i – 1]的前面一个字符等于i时，当前回文就是(start[i – 1] – 1) ~ i，长度就是len[i – 1] + 2。
第二种：s[i – 1]等于s[i]，就是说两个相邻的字符相等的话，那么start[i] = i – 1;len[i] = 2。
第三种：什么都不是，就是单个字符回文,start[i] = i, len[i] = 1。
其实仔细想想可以把len[]这个数组去掉，因为len[i] = i – start[i] + 1;
但是，因为这篇文章时根据USACO那题写的，那个题目的s中包含空格和标点符号，但是又把它们记入len[]中，所以这个代码只是一个模式，遇到不同的题目要有不同的待遇，但是这种思想我觉得很重要/神奇，类似于DP但又不是。解题
那么上面的题目就好解了（只给出大致代码）：
i = 1, ans = 0
while(i < n){
if(s[start[i – 1] – 1] == s[i]){
start[i] = start[i – 1] – 1;
len[i] = len[i – 1] + 2;
}else if(s[i – 1] == s[i]){
start[i] = i – 1;
len[i] = 2;
}else{
start[i] = i;
len[i] = 1;
}
if(ans < len[i]){
ans = len[i];
k = i;
}
}
printf("%d\n", ans);
for(i = start[k]; i <= k; i++){
printf("%c", s[i]);
}
自己发明的算法，文本上没有什么可以参考的蓝本，写得不好请见谅。 -
Noip 2010之旅(下)
昨晚上让柜台6:30把我们闹醒，结果7点钟他们才打电话来，真是懒，幸好我起来的早，6点半不到就醒了，不然考试不就错过了。
早早地来到考场，虽然离考试还有一段时间，但是已经有非常多的人 在哪儿等候了，老师也碰到几个熟人，聊着聊着就开考了。
哇，这种考试就是不一样，真大啊～宽敞的机房，虽然昨天来看过了，但是身在庐山中和不在完全不同呢！半个小时的试机时间里大家都在打代码，我却不知道要干什么，写了个Hello World就去玩扫雷去了，到半个小时快结束的时候才发现我可以把一些常用的算法写出来。桌面上有一个压缩文件里面是题目，但是被加密了，伴随着铃声密码给我们了，我很快地扫过第一题，发现很简单，大概半个小时不到就写完了，第二题感觉也很简单，但是花了好一阵子，一看时间，发现9：30了，只有1.5小时了！！心里马上就急了，但很快就知道是8：30开始考试的。。。。第三题和第四题也都想到算法了，对于NOIP的题目能够全部全部写出来对我来说就是一个挑战！！这回战胜自己了，哈哈哈哈。
接下来就是等成绩了，吃完饭又回到理工学院，到处逛了下，想去图书馆，被学生卡挡住了，没有学生卡不能进入，在考场附近的一个草坪上看到一个人正在贴横条“当音乐和桌游碰撞”，有好多人在那里，我们也在那里休息了一下午（4～5个小时等成绩。），老师很快就和周公约会去了，我看他们弹吉他，玩桌游看了好久，那里有一个关于狼人的桌游感觉挺好玩的，好想玩～
后来到了五点钟，在那里成绩还是没有出来，预计的时间总是不准，到了六点多才出来，雅礼有6个满分！！！我210分落幕这届NOIP。
其实还有很多细节，但是这两天的细节太多了，不想写，，就这样潦潦草草的流水帐下吧。