首先用两个数组分别保存排了序的数组和没排序的数组，然后再根据这两个判断，当前这个位置上应该是放什么数，而实际上放的是什么数，如果两个位置上需要的都正好是对方所有的，那么这是最好的，进行循环，把所有这种的都交换掉，然后累计交换次数。 但是最后会有这么一种情况，三个位置需要的分别是1, 2, 3，而他们有的分别是3, 1, 2，这时就要交换两次了，而且仔细考虑的话会发现当前面循环完了之后，就只可能剩下这么一种情况了，当然，对数可能不止一对，所以就累计需要的和拥有的不相同的那些，统计起来，处以三再除以二，就是交换次数，结果就出来了。 代码如下： / ID: yylogoo1 PROG: sort3 LANG: C / #include
分类： OI路程
-
USACO 2.1.3 Sorting A Three-Valued Sequence 解题报告
int 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。
其实还有很多细节，但是这两天的细节太多了，不想写，，就这样潦潦草草的流水帐下吧。
-
Noip 2010之旅(上)
学校第37届运动会闭幕式刚结束, 李智老师就准备带着我去长沙了. 他先带我去和别的老师一起吃了一餐饭, 然后就出发了!
好久没来火车站了, 发现这里比以前要好很多了, 以前我爸带我到这里, 跟我说以前是怎么逃票的, 后来好像本来是要带我逃票的吧, 好像是我良心过不去, 所以就没了, 不太记得了, 反正现在进去就要先查票, 然后把行李放到那个检查的地方, 然后用测电子仪器的东西"搜身", 检查身份证. 搜身的时候她还问了我一句, 你是学生啊? 去干吗? 你看有多么的严谨了!
岳阳走的时候老师碰到了一个熟人, 也是去长沙的..到了长沙在动车旁边照了相. 一出火车站老师把他带的药给他爸爸(老师顺便带了点药给她母亲, 他父亲过来拿.)一的士冲到雅礼, 梦寐以求好久了, 不过我还是在四中待着吧, 一个头发几乎没有的女的给我们签到, 我好害怕, 生怕以后和她一样, 这么恐怖..
后来一辆702到了长沙理工学院, 坐了1个多小时的车~~~ (后来发现到了这里是长沙县).
理工学院好大啊~ 像个小城是一样的, 在门口有校内的公交车, 一个半敞棚, 透明的车, 司机坐在上面等乘客, 从入口处到我考试的场所, 走了十几二十分钟的路, 而且这才是门口的地图上的一小根横线. 在校外, 我看到学校的栏杆从侧面看好整齐, 好杀气, 有一种威武的感觉, 想在它前面照一张, 老师没照, 就算了~~(可惜中..)
到了我考试的机房, 好大啊~ 一个教室一个教室都是机房, 透明的窗户, 里面的电脑看的清清楚楚, 一排排液晶电脑, 真想冲上去玩下啊….
看完机房后, 就找位置住, 找了好久好久~~ 第一家没有双人房, 说要我们去隔壁, 结果他喊另外一个人带我们去那家去看, 不过没电了,她说这一篇都没有, 就到这里住啦, 老师没理她.
找了好久, 都没有电, 大部分也都没有双人间, 最后运气好, 发现那里还有一个商务宾馆, 虽然没有双人间, 但住在一个好大的单人间! 有台电脑, 简单的复习了一下, 看了下电视就睡了..