91久久精品www人人做人人爽,欧美三级电影一区,久久先锋资源

Dice Stacking

��志 — Mon, 09 Aug 2010 14:05:00 GMT

Dice Stacking

【题目概�q�】罗骰子游戏�Q?/span>N�Q?/span>1<=N<=10�Q�个骰子�Q�每个骰子有六个�~�号�?/span>0~5的面�Q�现在要求把骰子�|�成一摞，且要求两个骰子重叠的面的�~�号相等�Q�求�|�成的长方体四个侧面中最大面�U�的侧面的面子�?/span>

【题目分析】将骰子�|�列�Q�求最大的侧面�Q�还要求盔R��两个骰子接触面编��L��{�？�Q�该如何解决呢？看图�Q�先来解决相�ȝ��两个面编��L��{�的问题�Q�有囑־��?/span> 因此�Q�可以很�Ҏ��的判断一个面的对立面�Q�第一个问题解冟�?/span>

题目中给��Z��q�个条�g是狠重要��是�Q�就是一个骰子可以左双��{动，�q�提�C�我们水�q�的四个面中�~�号最大的面��L��可以转到一个面上的。由此，我们可以��定那个面和其余骰子接触的时候，��定�q�个骰子提供的最大的面积�?/span>

��定�q�两个�v初看是不��定的问题，下面的算法就是比较通俗的了�?/span>

�?/span> 表示最大��|��其中�Q?/span>i为已攑օ�的骰子，�W?/span>j个骰子的�W?/span>k个面朝上。则

若只放一个筛子， , 其中b[i][j]表示�W?/span>i个骰子的�W?/span>j个面向上攄��贡献的最大��|��可以预处理的时候求出�?/span>

对于已放�|�的骰子�Q�可以�{�U�d��为放�|�的上面�Q�所以，枚�D合法的状态，然后��d��骰子�Q�同时更新状态倹{�?/span>

【详�l�代码】下面是AC的代码�?/span>

//Name: pku_2596_Dice Stacking

#include

using namespace std;

#define max(a, b)((a)=((a)>(b)?(a):(b)))

const int f[6]={5,4,3,2,1,0};

int a[10][10], b[10][10];

int dp[1<<10][10][6], n, ans;

int main() {

//freopen("in.in", "r", stdin);

int ca, i, j, k, p, q, t, kn;

scanf("%d", &ca);

while(ca-- && scanf("%d", &n)) {

kn = 1<

memset(b, 0, sizeof(b));

for(i = 0; i < n; i++) {

for(j = 0; j < 6; j++) scanf("%d",a[i]+j);

for(j = 0; j < 6; j++)

for(k = 0; k < 6; k++) if(k!=j && k != f[j])

max(b[i][j], a[i][k]);

}

memset(dp, -1, sizeof(dp));

for(i = 0; i < n; i++)

for(j = 0; j < 6; j++) dp[1<

for (i = 0; i < kn; i++) {

for (j = 0; j < n; j++) {

for (k = 0; k < 6; k++) if(dp[i][j][k] != -1) {

for(p = 0; p < n; p++) if(!(i & (1<

for (q = 0; q < 6; q++) if(a[j][k] == a[p][f[q]]) {

t = i|(1<

max(dp[t][p][q], dp[i][j][k] + b[p][q]);

}//ifq

}//ifp

}//ifk

}//fj

}//fi

ans = 0;

for (i = 0; i < n; i++)

for (j = 0; j < 6; j++) max(ans, dp[kn-1][i][j]);

printf("%d\n", ans);

}

return 0;

}

��志 2010-08-09 22:05 发表评论

pku_3254_Corn Fields

��志 — Mon, 09 Aug 2010 04:26:00 GMT

pku_3254_Corn Fields

【题目概�q�】告诉��^面上一些点�Q�从中选择部分点出来，要求不能选择盔R��的点�Q�求所有的�Ҏ��数�?/span>

【题目分析】学�q?/span>gohst�?/span>wei的代码风��g��后，�W�一道小�l�兵。花的时间虽焉��了点�Q�但是，感觉�q�不错�?/span>

1. 首先�q�是分析采取�׃��而下�Q�逐行分析的策略�?/span>

2. 我们发现�Q�媄响当前行的状态的只有上一行，即上一行和下一行的要满��相��M��相等原则�?/span>

3. �?/span> 表示�?/span>i行的�Ҏ��敎ͼ�且第i行的状态�ؓs.

转移方程�Q?/span>

�Q�其中，t��Z��一行的某个与当前行不相冲突的状态）

4. 旉��复杂度�ؓ 昄��q�样的复杂度��Z��满��条�g的。因此需要优�?/span>

5. 我们发现�Q�题目中有一个限制的条�g是没用到的。就是同一行也不满��相��M��可取的。由此，我们可以实现预处理，剔除掉多余的状态，�q�样�Q�最后的每行合法的状态，最多只�?/span>367个�?/span>

【题目代码】下面是AC的代码�?/span>

//Name: pku_3254_Corn Fields

#include

using namespace std;

const int maxs = 1<<12;

const int mod = 100000000;

int map[13][13], n, m;

int stk[maxs], sn;

int dp[2][maxs];

inline bool one(int i, int j) { return (i&(~(1<

bool check(int i, int j) {

if (j > 0 && one(i, j-1)) return 0;

if (j < m-1 && one(i, j+1)) return 0;

return 1;

}

void Proced(int km, int m) {

sn = 0; int i, j;

for (i = 0,j; i < km; i++) {

for (j = 0; j < m; j++)

if(one(i, j) && !check(i,j)) break;

if (j == m) stk[sn++] = i;

}

// for (i = 0; i < sn; i++) printf("stk[%d] = %d\n", i, stk[i]);

}

void SCDP() {

int i, j, s1, s2, k1, k2, e1 = 0, e2 = 1;

for (j = 0; j < sn; j++) dp[0][stk[j]] = 0;

dp[0][0] = 1;

for (i = 1; i <= n; i++) {

for (j = 0; j < sn; j++) dp[e2][stk[j]] = 0;

for (k1 = 0; k1 < sn; k1++) {

for (k2 = 0; k2 < sn; k2++) {

s1 = stk[k1]; s2 = stk[k2];

if(s1 & s2)continue;

for(j = 0; j < m; j++)

if (!map[i][j] && one(s2, j)) break;

if (j == m) {

dp[e2][s2] = (dp[e2][s2]+dp[e1][s1])%mod;

}

e1 ^= 1; e2 ^= 1;

}

int ans = 0;

for (k1 = 0; k1 < sn; k1++)

ans = (ans + dp[e1][stk[k1]])%mod;

printf("%d\n", ans);

}

int main() {

freopen("in.in", "r", stdin);

scanf("%d %d", &n, &m);

Proced(1<

for(int i = 1; i <= n; i++)

for (int j = 0; j < m; j++)

scanf("%d", map[i]+j);

SCDP();

return 0;

}

��志 2010-08-09 12:26 发表评论

pku_1699_Best Sequence

��志 — Sun, 08 Aug 2010 08:05:00 GMT

pku_1699_Best Sequence

【题目概�q�】求N�Q?span>N<=10�Q�个子串的最短和�Ԍ��且不会发生一�?/span>完全包涵另外一个的现象�?/span>

【题目分析】简单的状�?span>DP问题�Q�一开始想用字�W�串的思想解决�Q�发现状态之��_��不好变换。正好自己做压羃DP的专题，�q�是�Q�用�q�个�Ҏ��吧！

1. 对于每个字符串的攄��Q�和�Ҏ��直接影响的是上一个字�W�的攄��情况。由此，我们可以建立一个状态�{�U�L��E?/span>

�?/span> 表示当前状�?/span>s以第i个字�W�串�l�尾产生的最��和串的长度。则

2. �?/span>s只包含一个串的时候，其中len[i]表示�W?/span>i个子串的长度�?/span>

3. 否则�Q�如果当前的状态合法，�?/span>s状态集中，不包含有j�Ԍ��那么,�Q?/span> �?/span>

a) 如果其中�Q?/span>com[I, j] 表示�W?/span>i个串之后是第j个串的公共子串的长度�?/span>

b) 否则�Q�不处理�?/span>

4. 最后的�l�果��是�Q?/span> i是所有的子串�?/span>

【题目代码】：

//Name: pku_1699_Best Sequence

#include

using namespace std;

const int inf = 1<<20;

const int maxn = 1<<10;

char str[10][20];

int len[10], com[20][20], n, m;

int dp[maxn][10], ans;

void Link(int x, int y) {

int i, j, k, mlen = min(len[x], len[y]);

for (k = mlen; k >= 0; k--) {

for (i = len[x]-k, j = 0; i < len[x]; i++, j++)

if (str[x][i] != str[y][j]) break;

if (i == len[x]) {

com[x][y] = k; break;

}

for (k = mlen; k >= 0; k--) {

for (i = len[y]-k, j = 0; i < len[y]; i++, j++)

if (str[y][i] != str[x][j]) break;

if (i == len[y]) {

com[y][x] = k; break;

}

int main() {

// freopen("in.in", "r", stdin);

int t, i, j, s, r; scanf("%d", &t);

while(t-- && scanf("%d", &n)) {

memset(com, 0, sizeof(com));

for(i = 0; i < n; i++) {

scanf("%s", str+i);

len[i] = strlen(str[i]);

for (j = 0; j < i; j++) Link(i, j);

}

// for(i = 1; i < n; i++) printf("%d\n", com[i-1][i]);

for(i = 1; i < 1<<n; i++)

for (j = 0; j < n; j++) dp[i][j] = inf;

for(i = 0; i < n; i++) dp[1<<i][i] = len[i];

for(s = 1; s < 1<<n; s++) {

for (i = 0; i < n; i++) if(s&(1<<i)) {

for(j = 0; j < n; j++) if(i!=j && !(s&(1<<j))) {

r = s|(1<<j);

dp[r][j] = min(dp[r][j], dp[s][i] - com[i][j] + len[j]);

// printf("dp[%d][%d] = %d\n", r, j, dp[r][j]);

}

// for(i = 0; i < n; i++) printf("%d\n", dp[s-1][i]);

ans = inf;

for(i = 0; i < n; i++)

if (dp[s-1][i] < ans) ans = dp[s-1][i];

printf("%d\n", ans);

}

return 0;

}

��志 2010-08-08 16:05 发表评论

pku_2686_Traveling by Stagecoach

��志 — Sun, 08 Aug 2010 06:01:00 GMT

Traveling by Stagecoach

【题目概�q�】告诉一张地图，地图上有N(2<=2<= 30)个城市，�׃��个城市到另外一个城市的唯一交通工��h��马�R�Q�不同型��L��马�R��p��的时��_��q�里的时间计��用两地的距��除以该马�R骂的数量�Q�马��多��快�Q�不一栗��现在给�?/span>N(1<=N<=8)两马晨，每辆马�R告诉马的数量�Q�求有一个城市到另外一个城市的最短时间�?/span>

【题目分析】参考了hobby的代码，�?/span>froeverLin提示�Q�在�q�里予以说明�?/span>

l 像是一个最短�\问题�Q�但是增加了限制条�g�Q�解�?/span>DP毋庸�|�疑�Q�给定马车的数量<= 8�Q?/span> 状态压�~?/span>DP.

l 要求的仅仅是最短的旉��Q�没有求分配�Ҏ��Q�这无疑佉K��题简单话了�?/span>

l 影响节点�Q�城市）之间的花费的唯一变化因素是马的数量（距离是固定的�Q��?/span>

l �?/span> 表示当前状态�ؓs�Q�走到城�?/span>j的最��时间�?/span>

状态�{�U�L��E�，�?/span> 对于��M��一个与j相连的节�?/span>k�?/span>

其中�Q?/span> r为和k相连的城市， r��Z��?/span>s中的某个马�R的加入后的状态， t[w]��马�R的马�Ҏ��?/span>

l 初始化问题�?/span>

n �׃��求的是最��|��我们初始�?/span>dp为某个最大倹{�?/span>

for(p = 1; p < (1<<n); p++)

for(i = 0; i < m; i++) dp[p][i] = inf;

n �׃��每次都是�?/span>a开始的�Q�所以初始化的时候要初始化和a与关�pȝ��边的转移�?/span>

for (i = 0; i < m; i++) if(map[a][i] != -1)

for(k = 0; k < n; k++) dp[1<<k][i] = map[a][i]/t[k];

【题目代码�?/span>

//Name: pku_2686_Traveling by Stagecoach

// dp[i][j]表示当前使用的票的状态�ؓi到达�?span>j城市的最��用�?/span>

// 若第k个城市与j相连通，且，枚�D枚�D��数最��的

#include

using namespace std;

#define inf 1<<30

int map[30][30];

int n, m, p, a, b, d, r, q;

double dp[1<<8][30], t[30], tmp, ans;

int main() {

// freopen("in.in", "r", stdin);

int i, j, k, x, y;

while(scanf("%d%d%d%d%d",&n,&m,&p,&a,&b) != EOF) {

if (!(n||m||p||a||b)) break;

a--; b--;

for(i = 0; i < n; i++) scanf("%lf", t+i);

memset(map, -1,sizeof(map));

for (i = 1; i <= p; i++) {

scanf("%d %d %d", &x, &y, &d); x--;y--;

map[x][y] = map[y][x] = d;

}

for(p = 1; p < (1<<n); p++)

for(i = 0; i < m; i++) dp[p][i] = inf;

for (i = 0; i < m; i++) if(map[a][i] != -1)

for(k = 0; k < n; k++)

dp[1<<k][i] = map[a][i]/t[k];

for (p = 1; p < (1<<n); p++) {

for (j = 0; j < m; j++) if(dp[p][j] != inf) {

for (k = 0; k < m; k++) if(k!=j && map[j][k]!=-1) {

for (r = 0; r < n; r++) if(!(p&(1<<r))) {

q = p + (1<<r);

tmp = dp[p][j] + map[j][k] /t[r];

if (dp[q][k] > tmp) dp[q][k] = tmp;

}

ans = inf;

for (p = 1; p < (1<<n); p++)

if(dp[p][b] < ans) ans = dp[p][b];

if(ans == inf) printf("Impossible\n");

else printf("%lf\n", ans);

}

��志 2010-08-08 14:01 发表评论

回首

��志 — Sun, 13 Jun 2010 12:52:00 GMT

再回�?/p>

再回�? 云遮断归�? 再回�? 荆棘密布/ 今夜不会再有难舍的旧�?/ 曄��与你共有的梦 / 今后要向谁诉�?br>再回�? 背媄已远�? 再回�? 泪眼朦胧/ 留下你的��福/ 寒夜温暖�? 不管明天要面对多��伤痛和�q�h��
曄��在幽�q�暗暗反反复复中�q�问/ 才知道��^�q�x�E淡从从容�Ҏ��最�? 再回首恍然如�?/ 再回首我心依�? 只有那无��的长�\伴着�?

　　　　想了解我的，��p��一下这��文章了�Q�读之前请先打开音乐-《回首》听一遍！

偶然听到�q�首�?---《再回首》，感觉�q�首歌的旋律是那么的柔，让我一阵之后，心中�U�聚的情感再也无法控�Ӟ��像洪水般要爆发出来！回首�Q�当歌词一�ơ次的重复这个词的时候，自己内心的深处有许多东西在蠕�?--是记忆！以前有过�Q�但是没有那么的强烈�q�！也许是时�?#8220;回首”一下了�Q?/p>

我是一个不善于处理情感的�h�Q�当�?#8220;回首”一下的时候，反而发��C��知道从哪里开始了�Q�脑子里一团�ؕ麻！��沿着我上学的�U��\�Q�来回首一下！�Q�认识我的兄弟，别嫌我唠叨，我给自己听的�Q�不习惯�Q�堵上��x��Q�）

��学的记忆是珍贵的，因�ؓ太少�?大多的都忘记了！�Q�感慨岁月的强大杀伤力�Q�）记得我踏�q�校园的校门的时候，是我�?#8220;虎子�?#8221;领着我去的！�Q�那时候的自己像只野猴子（听我虎子哥说的）�Q�整天穿上串下的�Q�还记得�W�一�ơ踏�q�校门的时候那�U?#8220;骄傲�?#8221;心情�Q�有一�U�无法言�ȝ��自豪感！�q�记得校门上“好好学习�Q�天天向�?#8221;那八个打字（虽然有些锈迹了，但是�Ҏ��来书那里面是那么的神�U�！�l�于�Q�自己怀着一�?#8220;探秘”的目的，��那么的走进��M��Q�给我登记的校长�Q�姓吴吧�Q�忘不了他！我去报名的时候，他们几个“大�h”正在吃西瓜！我站��C��面前的时候，两眼直勾勄��盯着他手里的习惯�Q�他可能感觉��尬啦，�q�忙�?#8220;��家伙，来吃块！“�Q�但是我果断而且坚决的拒�l�了�Q�他说我有礼貌，而实际上呢？现在可以说了�Q?#8221;他给我的是西瓜有一多半是生的，你让我吃�Q�我��d��!�Q?#8221;呵呵

��学的记忆是短暂的，但是�Q�仅有的记忆都是甜美的！我这辈子也不会忘讎ͼ�因�ؓ那里有我太多童年的欢�W�了�Q?提一下我��学的哥们儿�Q?/p>

国华——我��学的铁哥们�Q�胖胖的�Q��ؓ人热情，爱打�׃��q�I��学里帮了我不少�Q?/p>

张琦——挺好的名字�Q�好朋友�Q�我们一起度�q�了不少时光�Q?/p>

腾，凯，才，我一辈子的朋友！

�q�有几个不是很俗的，但是�l�我影响很大的！我小学的班长�Q�何�Q�当了五�q�的班长�Q�辛苦她了！�Q�，挺敬佩她的，一个小奛_��把一��?#8220;��野孩子”��住�Q�不�Ҏ��啊！刘：对不住她的，曾把�Ҏ��哭了�Q�还叫了她家长！�Q�后话，�Ҏ��了我高中同学�Q�）徐：后话了！

不要停顿�Q�让我们�l�箋往前走�Q�到初中了！初中的时候，是我学习最刻苦的时候（不是我说的，朋友们说的，其实我没感觉�Q�。在初中�Q�我遇到了给我启发最大的�Q�媄响最��q��老师�Q�Mr 徐， Mr 焦！徐老是我的老班�Q�所以他�Ҏ��要求是很严的�Q�但是给我的启��_也是最大的�Q�我不是一个聪明的人，但是�Q�我那时候是一个勤奋的人！他告诉我�?#8220;宝剑锋从��砺出，梅花香自苦寒来！”。那时候的自己比现在懂得那是什么意思！现在��x��Z��服自��q��毅力的！因�ؓ我做��C��别�h做不到的�Q�所以也得到了别人得不到了（不是对聪明�h说的�Q�我说的是像我一��h��钝的人）。焦老，怎么说呢�Q�徐老是打我最重的人，他是骂我最狠的�Q�（事实如此�Q?�q�记得一件事�Q�那时候我的字体写的小�Q�（他可能是惌��我写大些�Q�有一�ơ上译ְ�在课上，在黑板上用粉�W�花了一个大大的“�?#8221;字（以前的作业本�Q�，然后用粉�W�写了三个小��小的三个字�Q�我名字�Q�绝�Ҏ��讽刺�Q�还好是我，心里素质那么好的�Q�要不估计早“以头强地"了！�Q�但是我�q�是从他�w�上学到了对自己的严��D��求，�q�让我受用终�w�的�Q�）我不会忘��C��们！��来有时候回�ȝ��看，学校是没了，但是师生情还在！

　　初中的朋友就相对较多了，而且�q�交��C��我一辈子�?#8220;兄弟”�Q�别�W�，我没夸大�Q�胦��爷面前扣过��_��邵国香的�Q�我老大�Q�小义老二�Q�鲁子老三�Q�，我么一起度�q�了很多快乐��好的时光，而且由无��的�Ƣ声�W�语�Q�让我的初中生活是那么的令�h隑ֿ��Q�虽然后来我们分开了，但是�Q�兄弟情谊是斩不断的�Q�I Believe I Can! �q�有没磕�q�头�Q�但是关�p�d��样很好的�Q�几个：阿胡�Q�讲义气的好哥们�Q�，��朱�Q�同��L��好朋友）�Q�菲�Q�环�Q�同��L��?#8220;兄弟"(两个女生�Q�叫兄弟是说关系好，别误会！�Q�还得提一下：��超�Q�班里最会搞的，�l�我带来了很多欢�W�！ �q�有很多�Q�就不说啦，他们也是我的好朋友！

　　　　初中的生�z�L��充实的，是充满欢�W�的�Q�但是，也还有一些无法��I补的遗憾�?以前的自己只喜欢整天埋在书里�Q�所以，错过了好多，也无�a�里伤�q�了一些�h�Q�我知道一�?#8220;对不�?#8221;�Q�是�q�不回来什么的�Q�但是，却是我心里憋了几�q�的话，好几�ơ想说来着�Q�却又怕提起了�Q�反而更伤心�Q�用电媄里的一具对白：让她留在记忆里吧�Q�Wish you have a happiness life , 徐！

　　　抛开惆怅，抛开多情�Q�我��d��了初中，来到了高中！高中的生�z�d��该说是记忆里最清晰的，但是�Q�那却是我最不愿意记��L��Q�高中的生活�Q�我的从山顶跌倒了山底�Q�心中的压抑�Q�郁��P��堕落�Q�自暴自�?#8230;…一切不好的词，都可以用来�Ş�Ҏ��的！�q�时我走��C��背叛的顶峎ͼ�仿佛�q�个世界的一切都是我的眼中刺�Q�不��眼�Q�当�Ӟ��所�?#8220;成�W”也不是很好！上不去，又下不来�Q�我��在那里挂着�Q�压力也很大�Q�但是很危险的，因�ؓ一旦导火烦被点燃，��一发不可收拾！�l�于�Q�高二，奶奶的去世，让我��d��的崩溃了�Q�我��d��的失��M��信心�Q�一个�h什么时候最可怕，��是他对自己失去信心的时候！但是我是�q�运的，当我最�l�望的时候，她的安慰让我�E�感舒适！渐渐的��E忘了�Q�等我彻底清醒的时候，已经是高三的下半学期�Q�升学的压力有一�ơ压��C��我肩上！�q�好自己�q�可以努力！

　　　　�W�一�ơ的��p�|�Q�让我第二次觉悟�Q�代价高了点�Q�但是挺�q�来了！回忆��q��不开人的�Q�这个�h�Q�是我这辈子都可以交心的�Q�徏��P��我的挚友�Q�陪我走�q�三�q��\�E�的人！而且始终是在支持物哦的�h�Q�好兄弟�Q�兄弟我什么也不说了！鹏，让我叫你声哥�Q�不亏！芻I��谢谢你！��p��老师�Q�谢谢你�l�我勇气�Q�让我勇于面对！学生不会忘记您！生物老师�Q�我复读的时候的老师�Q�，谢谢你的鼓励�Q?/p>

　　　　人生的完��就在于她的不完��！带着些许的遗憾，我踏上了南去的火车，��M��我的大学�Q�虽然一路上太多的坎��P��但是�Q�我�q�是来到了！大学�Q�给我的�W�一印象��是“�?#8221;�Q��h“�?#8221;�Q�一开始来大学自己对大学有些失望的�Q�电视里�?#8220;教授学�?#8221;�Q�坐在校园里到处可见的场景，我从没看到过�Q�激情洋溢的愤青到处作演说的场面�Q�仿佛永�q�定格在��说里了�Q�这些只是表面，或许没有也没什么！但是……在学生会带过半年之后�Q�发�?#8220;太多的太多的事情世俗话啦�Q�还不仅如此�Q�更可悲的是�Q�学校竟焉��q�些东西炫耀�Q�拿着一些本来就应该有或做的事情炫耀�Q�一些不知道事情的�h�Q�还真的自以�?#8220;�?#8221;�Q�不说这些了�Q�经�q�一些迷茫之后，我在茫茫的大��上�Q�还是看��C��“北极�?#8221;�Q�北极星永远指着北方�Q?-学校acm�Q�这让我感觉刎ͼ��q�是有哪么一个地方，像我��x��那样�Q�远��M��俗，充满学术的氛围。我��p��q�到�q�么一个组�l�感到庆�q�！周老师�Q�应该是我的大学里的恩师了！他无�U�奉献的�_��Q�让交大荣耀�Q�让交大某些老师惭愧�Q�我不是吹嘘�Q�不信，你可以自己来看！

　　让我们回到现在！来交大一�q�多了，一切进行的�q�没有多大的异常�Q�但有一�Ҏ��觉得自己交到的朋友太��了�Q�可能是��d��太远的缘故，�q�里么有同学�Q�缺��交心的朋友�Q�心里话不知道该和谁��_��我没有过那么�q�切的想交朋友的心情�Q�我常常想着�Q�等到自��p��的时候，能否惌��v自己大学时光怎么�q�的�Q�有没有那么几个可以�U�得上一辈子的朋友！我想会有的！大学里面什么都要均衡，旉��也是�Q�不能把旉��全都投入到自己喜�Ƣ的事情上去。以前自己太偏激了，对大学里最值得学习的一门知识疏忽了“交友……友谊”�Q�敞开心扉吧，朋友�Q��h和�h之间需要的是沟通！

　　　回首自己的过去，我是�q�运的，我困惑的饿时候，��L��那么几个老师或朋友，支持我，�l�我��C��ȝ��勇气�Q�让我学会很多生存的法则和技能！我不孤独寂寞——反驳一些�h拿这个和我开玩笑的，我只是珍惜我们之间徏立的友谊�Q?#8220;待�h要真�Q�交友交心！”

　　说了以上�Q�似乎是我忘记提他们了——我的父母！我的父母在我心里的位�|�永�q�是最重要的，如果明天是世界末日，你会选择和谁在一��P��我的父母�Q�that's my answer, and never changed �Q?现在回想一下，自己上学的经历，我又是幸�q�的�Q�我得到了我父母的充分的信�Q�Q�他们从来没督促�q�我的学习，不是他们不关�p�，而是他们�怿�他们的儿子！我母亲说�q�一句话“只要你好好的�Q�我们喝凉水都甜�Q?#8221;�Q�每�ơ想到都心里酔R��的！我是吃豆腐长大的�Q�我的父母用豆腐供出了两个大学生�Q�我二舅和我�Q�我为我的父母感到骄�Ԍ��别�h说我皮肤白，我说我是我爸妈用豆腐长大的，�q�不是玩�W�话�Q?/p>

　　　　唠唠叨叨了这么多�Q�不为别的，只是有感而发�Q�这两天�l�好几个��了生日，�q�一�ơ生日就代表我们又长大一岁，��p��懂点事儿�Q�明天是我的生日�Q�我把这个《回首》送给自己�Q�不为别的，为的是自��p��勇敢的向前看�Q?/p>

Dragon(��志)

��志 2010-06-13 20:52 发表评论

��志 — Fri, 11 Jun 2010 10:53:00 GMT

题目链接�Q?/p>

pku_1850_Code_ http://162.105.81.212/JudgeOnline/problem?id=1850

pku_1496_Word Index http://162.105.81.212/JudgeOnline/problem?id=1496

【问题概�q�】：�l�定一个长度�ؓN(n<=10)的由��写字母�l�成的字�W�串�Q?br>如果该字�W�串左边的字�W�都比右边的字符的字典序大，则我们称�q�个字符串是合法的，
否则不合法：

e.g: 字符�Ԍ��abc ade 是合法的�Q�而字�W�串�Q�bac bca dae 则是不合法的�?/p>

现在对合法的字符串进行如下的�~�码�Q�编��P��Q?br>a - 1
b - 2
...
z - 26
ab - 27
...
az - 51
bc - 52
...
vwxyz - 83681
...
我们的�Q务就是对于给定的字符�Ԍ��如果�Ҏ��合法的，则找到她的编��P��否则不合法，输出0�Q?/p>

【问题分析】：首先惛_��的应该是暴力�Q�但是暴力的复杂度会辑ֈ�O(10^26)�Q�可能会��时�Q�当然有人爆�q�了�?br>�q�里��一个更为高效的��法。先看一下这个图�Q?img style="WIDTH: 215px; HEIGHT: 79px" border=0 alt="" align=right src="http://m.shnenglu.com/images/cppblog_com/dragon521/a.png" width=215 height=79>
我们可以知道�Q�长度�ؓk�Q�k>=1)的字�W�串的编��h��在长度�ؓk-1的基��上增加而来的，��Z��计算的方便，我们可以先计��出长度为k-1的字�W�串可以�~�号为多��，也就知道了长度�ؓk的第一个字�W�串的编��P��加一��可以）。但是问题还没得到解冻I��下面是重点：该如何统计当前输入的长度为k的字�W�串的编��P��她等于长度�ؓk-1的最大编号加上当前字�W�串在当前长度的�~�号。由此如何快速统计当前字�W�串在当前长度的集合�Q�把不同的长度的字符串划分�ؓ不同的集合）里编��h��解决�q�个题目的第二个要点�?/span>

设s[k][i](0< i<= 26)表示长度�{�于k的合法串以字�?i+'a'-1)开头的串的数目�Q�则规定s[k][26]表示长度为k的集合的合法串的�ȝ��个数。对于给定的长度为n的字�W�串�Q�我们由叛_��左考虑�Q�找�W�i个字�W�和�W�i-1个字�W�的关系�Q��otmp = s[ k ][ str[i] - 1] - s[k][ str[i-1] ]�Q�表�C�在前i-1个字�W�不变时�Q�可得到的不同的新合法字�W�串的个数。对于第一个字�W�，我们要判断她是不是第一个字�?#8216;a',不是的话�Q�她可以得到的心合法字符串的个数为s[k][str[0]-1]. 最后的话，我们再把所有长度小于n的字�W�长的个数加��h��是我们要求的：下面是简单的代码�Q�供大家讨论交流�Q?/span>

#include

using namespace std;

const int maxn = 28;

int s[11][maxn], n;

bool isValid(char *s, int &n) {

int i = n = 0;

for(i = 1; s[i]; i++)

if(s[i] <= s[i-1]) return 0;

n = i;

return 1;

}

void init() {

s[0][27] = 1;

for (int k = 1; k < 11; k++) {

int m = 26-k+1;

for (int i = 1; i <= m; i++) {

s[k][i] += s[k][i-1] + s[k-1][m+1]-s[k-1][i];

}

s[0][27] = 0;

}

void pt() {

int sum = 0;

for (int k = 1; k < 11; k++) {

int m = 26-k+1;

for (int i = 1; i <= m; i++) {

printf("s[%d][%d] = %d\n", k, i, s[k][i]);

}

sum += s[k][m];

}

printf("%d\n", sum);

}

inline int d(char c) { return c-'a'+1;}

int main() {//freopen("in.in", "r", stdin);

init(); //pt();

char str[11];

int m, i, k;

while(scanf("%s", str) != EOF) {

if (!isValid(str, n)) { puts("0"); continue;}

for (i = n-1, k = 1, m = 1; i >= 1; i--, k++)

m += s[k][d(str[i]-1)] - s[k][d(str[i-1])];

if (str[0] != 'a') m += s[k][d(str[0]-1)];

for (i = 1; i < k; i++) m += s[i][26-i+1];

printf("%d\n", m);

}

return 0;

}

��志 2010-06-11 18:53 发表评论

Gauss消元��法求解开关灯问题

��志 — Wed, 26 May 2010 09:23:00 GMT

/*================================================================================================*\

| Gauss消元��法求解开关灯问题

\*================================================================================================*/

开关问题：有N个相同的开养I��每个开关都与某些开��x��着联系�Q�每当你打开或者关闭某个开关的时候，其他的与
此开关相兌��的开关也会相应地发生变化�Q�即�q�些相联�pȝ��开关的状态如果原来�ؓ开��变为关�Q�如果�ؓ兛_��变�ؓ开�?/p>

对于�q�类问题�Q��y妙的�q�用位运��和gauss��法可以高效的解冟�?/p>

----------------------------------------------------------------------------------------

开灯问题告诉N(N<=63)盏灯和M(M<=N)个开�?每个开兛_��以控制K(K<=N)盏灯�Q�给定N盏灯的初始状态S�?br>要求通过开��x��制得到的目标状态E�Q�求可以辑ֈ�目标状态的�Ҏ��数�?/p>

----------------------------------------------------------------------------------------

��单分析：对于每个开养I��有按和不按两�U�选择�Q�记�?/1�Q? 对于每盏灯有变和不变两种情况�Q?/1�Q?如果初态和�l�态不一�?br>�Q�那么这盏灯是一定要变化的。由此我们就可以得到一�?/1的矩阵：让N盏灯灯作为列向量�Q�开关作为横向量�Q�把每盏灯是否变�?br>作�ؓ�W�M列（�?开始）�q�样��得��C��个N*(M+1)的矩�?该矩阉|��如下性质�Q?/p>

1. 如果N = M �Q�那么矩阵�ؓ增广矩阵�?/p>

2. 该矩�늛�当于方程�l�A * X = B,因此可以求其解�?/p>

1. 若方�E�组有唯一解，那么�Q�N = M (逆命题：如果M = N ,那么方程�l�有唯一�?不成�?

2. 若方�E�组无实数解�Q�那么，该方�E�不可以化成严格上三角�Ş式（具体的证明见相关资料�Q�这里不再证明）

3. 若方�E�组有多接，卛_��在自由变元，因�ؓ每个自由变元可以�?/1两种情况�Q�那么��d��?^m(m为变元数)�?br>(也就是不影响最后结果的自由开关的数目�Q?/p>

下面是经�q�验证的代码�Q?/p>

int getRow(int p, int q, int &row) {

for (int i = p; i < n; i++)

if (!zero(a[i][q])) return a[row=i][q];

return row=0;

}

void swapRow(int p, int row, int q) {

for (int k = q; k <= m; k++)

swap(a[p][k], a[row][k]);

}

i64 gauss() {

int i = -1, j = -1, k, p, q, ret, row;

while(++i < n && ++j < m) {

ret = getRow(i, j, row);

if (zero(ret)) { i--; continue;}

if (row != i) swapRow(i, row, j);

for (p = i+1; p < n; p++) if (a[p][j])

for (q = j; q <= m; q++)

a[p][q] ^= a[i][q];

}

for (k = i; k < n; k++) if(a[k][m]) return -1;

return (i64)1 << (m-i);

} //link: hdu3364 http://acm.hdu.edu.cn/showproblem.php?pid=3364

----------------------------------------------------------------------------------------

开关问题：有N个相同的开养I��每个开关都与某些开��x��着联系�Q�每当你打开或者关闭某个开关的时候，
其他的与此开关相兌��的开关也会相应地发生变化�Q�即�q�些相联�pȝ��开关的状态如果原来�ؓ开��变为关�Q?br>果�ؓ兛_��变�ؓ开。求�Q?1. �Ҏ��敎ͼ�自由变元的数目） 2. �l�定一个最��的开��x��?/p>

----------------------------------------------------------------------------------------

�q�类问题是上面问题的一�U�简化：

对于问题一、可以直接套用上面的公式�Q�N=M�Q?/p>

对于问题二、如果构造得到的方程�l�只有一个解�Q�那么问题解冻I��q�里主要讨论一下多解，
存在自由变元的情��c��如果存在自由变元，我们��p��枚�D每个自由变元�Q?/1�Q�然后比较选择最��?br>枚�D旉��复杂度�ؓ2^m(m��由变元的个数)

下面是简单的枚�D自由元的��法�?/p>

int gans(int a[][maxn+1]) {

int i, j, ret = a[n-1][n];

for (i = n-2; i >= 0; i--) {

for (j = i+1; j < n; j++)

a[i][n] ^= a[i][j] && a[j][n];

ret += b[i][n];

}

return ret;

}

void dfs(int p, int k) {

if (p == k) {

memcpy(b, a, sizeof(b));

int ret = gans(b);

if (ret < ans) ans = ret;

return;

}

a[p][n] = 1; dfs(p-1, k);

a[p][n] = 0; dfs(p-1, k);

}

int gauss() { //……代码见上�Q�n=m�Q?#8230;…//

dfs(n-1, i-1);

return ans;

}

Link: pku_1222 http://162.105.81.212/JudgeOnline/problem?id=1222

pku_1681 http://162.105.81.212/JudgeOnline/problem?id=1681

pku_1753 http://162.105.81.212/JudgeOnline/problem?id=1753

pku_1830 http://162.105.81.212/JudgeOnline/problem?id=1830

pku_3185 http://162.105.81.212/JudgeOnline/problem?id=3185
hdu_2285 http://acm.hdu.edu.cn/showproblem.php?pid=2285

��志 2010-05-26 17:23 发表评论

pku_1753_Flip Game--Gauss+Dfs

��志 — Mon, 24 May 2010 15:55:00 GMT

//Name: pku_1753_Flip Game

//Author: longxiaozhi

http://hi.baidu.com/xiehuixb/blog/item/9ce25f10ee8a2e77ca80c4d1.

//Root: 和前面的pku1681一个意�?span>,但是�Q�测试数据加��Z��Q�这个题目需要考虑自由元！�Q�也��是我以前的gauss的所在，

//�q�个问题一直困��C��我两天天。以前的题目的测试数据好像�ƈ没有考虑�q�一点，所以可以水果去�Q�但是这个题目就不行啦�?/span>

//但是�Q�还是可以用gauss的算法解决的。如果不存在自由变元�Q�那么说明原方程�l�只有一�l�解�Q�也��是我们要求的；

//如果存在自由变元�Q�则说明我们求道的方�E�的解只是其中的一�U�情况，但不一定是最优的�?/span>

//一�ơ我们还要考虑自由变元因�ؓ我们求出来的知识满��条�g的一�U�解�Q��ƈ不是�q�里要求的最优解�?/span>

//我们要考虑自由变元的取��|��

//每个自由元我们都枚�D她的��|��或）让后�q�行一�ơ深搜就可以把自由元的情况加�q�去�Q�正�?span>xiehui博客里写的一栗��?/span>

#include

using namespace std;

#define eps 1e-10

#define fabs(x) ((x)>0?(x):-(x))

#define zero(x) (fabs(x) < eps)

const int maxn = 16;

int a[maxn][maxn+1], b[maxn][maxn+1];

int n, m, ans;

const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

inline int isBound(int a, int b) {

return a < 0 || a >= m || b < 0 || b >= m;

}

void pmat(int a[][maxn+1]) {

for (int i = 0, j; i < n; i++) {

for (j = 0; j < n; j++)

printf("%d ", a[i][j]);

printf("%d\n", a[i][j]);

}

void pans(int a[][maxn+1]) {

for (int i = 0; i < n; i++)

printf((i+1)%m ? "%d ":"%d\n", a[i][n]);

}

int gans(int a[][maxn+1]) {

int i, j, ret = a[n-1][n];

for (i = n-2; i >= 0; i--) {

for (j = i+1; j < n; j++)

a[i][n] ^= a[i][j] && a[j][n];

ret += b[i][n];

}

return ret;

}

void dfs(int p, int k) {

if (p == k) {

memcpy(b, a, sizeof(b));

int ret = gans(b);

if (ret < ans) ans = ret;

return;

}

a[p][n] = 1; dfs(p-1, k);

a[p][n] = 0; dfs(p-1, k);

}

int getRow(int p, int q, int &row) {

for (int i = p; i < n; i++)

if (!zero(a[i][q])) return a[row=i][q];

return row = 0;

}

void swapRow(int i, int row, int q) {

for (int k = q; k <= n; k++)

swap(a[i][k], a[row][k]);

}

int gauss() {

int i = 0, j = -1, k, p, q, ret, row;

while(i < n && ++j < n) {

ret = getRow(i, j, row);

if (zero(ret)) continue;

if (row != i) swapRow(i, row, j);

for (p = i + 1; p < n; p++) if (a[p][j])

for (q = j; q <= n; q++)

a[p][q] ^= a[i][q];

++i;

}pmat(a);

for (k = i; k < n; k++) if (a[k][n]) return -1;

dfs(n-1, i-1);
return ans;

}

int main() {

//freopen("in.in", "r", stdin);

int i, j, k, x, y, p, q; char s[5][5];

n = 16; m = 4;

for (i = 0; i < m; i++) {

scanf("%s", s[i]);

for (j = 0; j < m; j++) {

a[i*m+j][n] = s[i][j] == 'b';

a[i*m+j][i*m+j] = 1;

for (k = 0; k < 4; k++) {

x = i + dir[k][0];

y = j + dir[k][1];

if (isBound(x, y)) continue;

a[i*m+j][x*m+y] = 1;

}

ans = 1 << 20;

p = gauss(); // printf("p = %d\n", p);

memset(a, 0, sizeof(a));

for (i = 0; i < m; i++) {

for (j = 0; j < m; j++) {

a[i*m+j][n] = s[i][j] == 'w';

a[i*m+j][i*m+j] = 1;

for (k = 0; k < 4; k++) {

x = i + dir[k][0];

y = j + dir[k][1];

if (isBound(x, y)) continue;

a[i*m+j][x*m+y] = 1;

}

ans = 1 << 20;

q = gauss(); // printf("q = %d\n", q);

if (p == -1 && q == -1) puts("Impossible");

else if (p == -1) printf("%d\n", q);ac

else if (q == -1) printf("%d\n", p);

else printf("%d\n", p <= q ? p:q);

return 0;

}

��志 2010-05-24 23:55 发表评论

91久久精品www人人做人人爽,欧美三级电影一区,久久先锋资源

Dice Stacking

pku_3254_Corn Fields

pku_1699_Best Sequence

pku_2686_Traveling by Stagecoach

回首

Gauss消元���法求解开关灯问题

pku_1753_Flip Game--Gauss+Dfs

Gauss消元��法求解开关灯问题