【题目分析】将骰子|列Q求最大的侧面Q还要求盔R两个骰子接触面编L{？Q该如何解决呢？看图Q先来解决相ȝ两个面编L{的问题Q有囑־?/span>
题目中给Zq个条g是狠重要是Q就是一个骰子可以左双{动，q提C我们水q的四个面中~号最大的面L可以转到一个面上的。由此，我们可以定那个面和其余骰子接触的时候，定q个骰子提供的最大的面积?/span>
定q两个v初看是不定的问题，下面的算法就是比较通俗的了?/span>
?/span>
若只放一个筛子，
对于已放|的骰子Q可以{Ud为放|的上面Q所以，枚D合法的状态，然后d骰子Q同时更新状态倹{?/span>
【详l代码】下面是AC的代码?/span>
//Name: pku_2596_Dice Stacking
#include <iostream>
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<<n;
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<<i][i][j] = b[i][j];
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<<p))) {
for (q = 0; q < 6; q++) if(a[j][k] == a[p][f[q]]) {
t = i|(1<<p);
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;
}
]]>
【题目概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其中，tZ一行的某个与当前行不相冲突的状态）
4. 旉复杂度ؓ 昄q样的复杂度Z满条g的。因此需要优?/span>
5. 我们发现Q题目中有一个限制的条g是没用到的。就是同一行也不满相M可取的。由此，我们可以实现预处理，剔除掉多余的状态，q样Q最后的每行合法的状态，最多只?/span>367个?/span>
【题目代码】下面是AC的代码?/span>
//Name: pku_3254_Corn Fields
#include <iostream>
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<<j))) != i;}
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<<m, m);
for(int i = 1; i <= n; i++)
for (int j = 0; j < m; j++)
scanf("%d", map[i]+j);
SCDP();
return 0;
}
]]>
【题目概q】求NQ?span>N<=10Q个子串的最短和Ԍ且不会发生一?/span>完全包涵另外一个的现象?/span>
【题目分析】简单的状?span>DP问题Q一开始想用字W串的思想解决Q发现状态之_不好变换。正好自己做压羃DP的专题，q是Q用q个Ҏ吧！
1. 对于每个字符串的攄Q和Ҏ直接影响的是上一个字W的攄情况。由此，我们可以建立一个状态{ULE?/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 <iostream>
#include <cstring>
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;
}
]]>
【题目概q】告诉一张地图，地图上有N(2<=2<= 30)个城市，׃个城市到另外一个城市的唯一交通工h马RQ不同型L马Rp的时_q里的时间计用两地的距除以该马R骂的数量Q马多快Q不一栗现在给?/span>N(1<=N<=8)两马晨，每辆马R告诉马的数量Q求有一个城市到另外一个城市的最短时间?/span>
【题目分析】参考了hobby的代码，?/span>froeverLin提示Q在q里予以说明?/span>
l 像是一个最短\问题Q但是增加了限制条gQ解?/span>DP毋庸|疑Q给定马车的数量<= 8Q?/span> 状态压~?/span>DP.
l 要求的仅仅是最短的旉Q没有求分配ҎQ这无疑佉K题简单话了?/span>
l 影响节点Q城市）之间的花费的唯一变化因素是马的数量（距离是固定的Q?/span>
l ?/span> 表示当前状态ؓsQ走到城?/span>j的最时间?/span>
状态{ULE，?/span> 对于M一个与j相连的节?/span>k?/span>
其中Q?/span> r为和k相连的城市， rZ?/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 <iostream>
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);
}
}
]]>
|
|
|
|
再回?/p> 再回? 云遮断归? 再回? 荆棘密布/ 今夜不会再有难舍的旧?/ 曄与你共有的梦 / 今后要向谁诉?br>再回? 背媄已远? 再回? 泪眼朦胧/ 留下你的福/ 寒夜温暖? 不管明天要面对多伤痛和qh 想了解我的，p一下这文章了Q读之前请先打开音乐-《回首》听一遍！ 偶然听到q首?---《再回首》，感觉q首歌的旋律是那么的柔，让我一阵之后，心中U聚的情感再也无法控Ӟ像洪水般要爆发出来！回首Q当歌词一ơ次的重复这个词的时候，自己内心的深处有许多东西在蠕?--是记忆！ 以前有过Q但是没有那么的强烈q！也许是时?#8220;回首”一下了Q?/p> 我是一个不善于处理情感的hQ当?#8220;回首”一下的时候，反而发C知道从哪里开始了Q脑子里一团ؕ麻！沿着我上学的U\Q来回首一下！Q认识我的兄弟，别嫌我唠叨，我给自己听的Q不习惯Q堵上xQ） 学的记忆是珍贵的，因ؓ太少?大多的都忘记了！Q感慨岁月的强大杀伤力Q）记得我踏q校园的校门的时候，是我?#8220;虎子?#8221;领着我去的！Q那时候的自己像只野猴子（听我虎子哥说的）Q整天穿上串下的Q还记得W一ơ踏q校门的时候那U?#8220;骄傲?#8221;心情Q有一U无法言ȝ自豪感！q记得校门上“好好学习Q天天向?#8221;那八个打字（虽然有些锈迹了，但是Ҏ来书那里面是那么的神U！l于Q自己怀着一?#8220;探秘”的目的，那么的走进MQ给我登记的校长Q姓吴吧Q忘不了他！我去报名的时候，他们几个“大h”正在吃西瓜！我站C面前的时候，两眼直勾勄盯着他手里的习惯Q他可能感觉尬啦，q忙?#8220;家伙，来吃块！“Q但是我果断而且坚决的拒l了Q他说我有礼貌，而实际上呢？现在可以说了Q?#8221;他给我的是西瓜有一多半是生的，你让我吃Q我d!Q?#8221;呵呵 学的记忆是短暂的，但是Q仅有的记忆都是甜美的！我这辈子也不会忘讎ͼ因ؓ那里有我太多童年的欢W了Q?提一下我学的哥们儿Q?/p> 国华——我学的铁哥们Q胖胖的Qؓ人热情，爱打׃qI学里帮了我不少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老师QMr 徐， Mr 焦！徐老是我的老班Q所以他Ҏ要求是很严的Q但是给我的启_也是最大的Q我不是一个聪明的人，但是Q我那时候是一个勤奋的人！他告诉我?#8220;宝剑锋从砺出，梅花香自苦寒来！”。那时候的自己比现在懂得那是什么意思！现在xZ服自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兄弟情谊是斩不断的QI Believe I Can! q有没磕q头Q但是关pd样很好的Q几个：阿胡Q讲义气的好哥们Q，朱Q同L好朋友）Q菲Q环Q同L?#8220;兄弟"(两个女生Q叫兄弟是说关系好，别误会！Q还得提一下：超Q班里最会搞的，l我带来了很多欢W！ q有很多Q就不说啦，他们也是我的好朋友！ 初中的生zL充实的，是充满欢W的Q但是，也还有一些无法I补的遗憾?以前的自己只喜欢整天埋在书里Q所以，错过了好多，也无a里伤q了一些hQ我知道一?#8220;对不?#8221;Q是q不回来什么的Q但是，却是我心里憋了几q的话，好几ơ想说来着Q却又怕提起了Q反而更伤心Q用电媄里的一具对白：让她留在记忆里吧QWish you have a happiness life , 徐！ 抛开惆怅，抛开多情Q我d了初中，来到了高中！高中的生zd该说是记忆里最清晰的，但是Q那却是我最不愿意记LQ高中的生活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这个hQ是我这辈子都可以交心的Q徏P我的挚友Q陪我走q三q\E的人！而且始终是在支持物哦的hQ好兄弟Q兄弟我什么也不说了！ 鹏，让我叫你声哥Q不亏！ 芻I谢谢你！p老师Q谢谢你l我勇气Q让我勇于面对！学生不会忘记您！生物老师Q我复读的时候的老师Q，谢谢你的鼓励Q?/p> 人生的完就在于她的不完！带着些许的遗憾，我踏上了南去的火车，M我的大学Q虽然一路上太多的坎P但是Q我q是来到了！大学Q给我的W一印象是“?#8221;Qh“?#8221;Q一开始来大学自己对大学有些失望的Q电视里?#8220;教授学?#8221;Q坐在校园里到处可见的场景，我从没看到过Q激情洋溢的愤青到处作演说的场面Q仿佛永q定格在说里了Q这些只是表面，或许没有也没什么！但是……在学生会带过半年之后Q发?#8220;太多的太多的事情世俗话啦Q还不仅如此Q更可悲的是Q学校竟焉q些东西炫耀Q拿着一些本来就应该有或做的事情炫耀Q一些不知道事情的hQ还真的自以?#8220;?#8221;Q不说这些了Q经q一些迷茫之后，我在茫茫的大上Q还是看C“北极?#8221;Q北极星永远指着北方Q?-学校acmQ这让我感觉刎ͼq是有哪么一个地方，像我x那样Q远M俗，充满学术的氛围。我pq到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敞开心扉吧，朋友Qh和h之间需要的是沟通！ 回首自己的过去，我是q运的，我困惑的饿时候，L那么几个老师或朋友，支持我，l我Cȝ勇气Q让我学会很多生存的法则和技能！我不孤独寂寞——反驳一些h拿这个和我开玩笑的，我只是珍惜我们之间徏立的友谊Q?#8220;待h要真Q交友交心！”
唠唠叨叨了这么多Q不为别的，只是有感而发Q这两天l好几个了生日，q一ơ生日就代表我们又长大一岁，p懂点事儿Q明天是我的生日Q我把这个《回首》送给自己Q不为别的，为的是自p勇敢的向前看Q?/p> |
|
|
Dragon(志)
|
]]>
|
|
/*================================================================================================*\ | Gauss消元法求解开关灯问题 \*================================================================================================*/ 开关问题：有N个相同的开养I每个开关都与某些开x着联系Q每当你打开或者关闭某个开关的时候，其他的与 对于q类问题Qy妙的q用位运和gauss法可以高效的解冟?/p> ---------------------------------------------------------------------------------------- 开灯问题告诉N(N<=63)盏灯和M(M<=N)个开?每个开兛_以控制K(K<=N)盏灯Q给定N盏灯的初始状态S?br>要求通过开x制得到的目标状态EQ求可以辑ֈ目标状态的Ҏ数?/p> ---------------------------------------------------------------------------------------- 单分析：对于每个开养I有按和不按两U选择Q记?/1Q? 对于每盏灯有变和不变两种情况Q?/1Q?如果初态和l态不一?br>Q那么这盏灯是一定要变化的。由此我们就可以得到一?/1的矩阵：让N盏灯灯作为列向量Q开关作为横向量Q把每盏灯是否变?br>作ؓWM列（?开始）q样得C个N*(M+1)的矩?该矩阉|如下性质Q?/p> 1. 如果N = M Q那么矩阵ؓ增广矩阵?/p> 2. 该矩늛当于方程lA * X = B,因此可以求其解?/p> 1. 若方E组有唯一解，那么QN = 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类问题是上面问题的一U简化： 对于问题一、可以直接套用上面的公式QN=MQ?/p> 对于问题二、如果构造得到的方程l只有一个解Q那么问题解冻Iq里主要讨论一下多解， 下面是简单的枚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() { //……代码见上Qn=mQ?#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 |
|
]]>
|
//Name: pku_1753_Flip Game //Author: longxiaozhi http://hi.baidu.com/xiehuixb/blog/item/9ce25f10ee8a2e77ca80c4d1. //Root: 和前面的pku1681一个意?span>,但是Q测试数据加ZQ这个题目需要考虑自由元！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 <iostream> #include <string.h> 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); } 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; } |
]]>