UVa 11464 Even Parity

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题7.

思路

大概是个带有机智成分的枚举。

为什么这么说，因为这道题的关键思路点就是发现只要知道第一行，就可以构造出整个数表，这样我们只要枚举第一行就可以解决问题，复杂度直接降低了一次幂。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int n;
int per[16];
int orig[16][16];
int now[16][16];

void genPermutation(int s){
    int cur = n;
    while(cur){
        if(s&1){
            per[cur] = 1;
        }else{
            per[cur] = 0;
        }
        cur--;
        s >>= 1;
    }
}

void genNow(){
    memset(now,0,sizeof(now));
    for(int i = 1; i <= n; i++){
        now[1][i] = per[i];
    }
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= n; j++){
            int cnt = now[i-1][j] + now[i][j-1] + now[i][j+1];
            if(cnt % 2){
                now[i+1][j] = 1;
            }else{
                now[i+1][j] = 0;
            }
        }
    }
}

int compare(){
    int ret = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(now[i][j] == 0 && orig[i][j] == 1){
                return 0x3f3f3f3f;
            }
            if(now[i][j] != orig[i][j]){
                ret++;
            }
        }
    }
    return ret;
}



int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++){
        scanf(" %d",&n);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                scanf(" %d",&orig[i][j]);
            }
        }
        int res = 0x3f3f3f3f;
        for(int i = 0; i < (1 << n); i++){
            genPermutation(i);
            genNow();
            res = min(res,compare());
        }
        if(res == 0x3f3f3f3f){
            res = -1;
        }
        printf("Case %d: %d\n",d,res);
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int n;

int per[16];

int orig[16][16];

int now[16][16];

void genPermutation(int s){

int cur = n;

while(cur){

if(s&1){

per[cur] = 1;

}else{

per[cur] = 0;

}

cur--;

s >>= 1;

}

void genNow(){

memset(now,0,sizeof(now));

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

now[1][i] = per[i];

}

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

for(int j = 1; j <= n; j++){

int cnt = now[i-1][j] + now[i][j-1] + now[i][j+1];

if(cnt % 2){

now[i+1][j] = 1;

}else{

now[i+1][j] = 0;

}

int compare(){

int ret = 0;

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

for(int j = 1; j <= n; j++){

if(now[i][j] == 0 && orig[i][j] == 1){

return 0x3f3f3f3f;

}

if(now[i][j] != orig[i][j]){

ret++;

}

return ret;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

for(int d = 1; d <= caseCnt; d++){

scanf(" %d",&n);

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

for(int j = 1; j <= n; j++){

scanf(" %d",&orig[i][j]);

}

int res = 0x3f3f3f3f;

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

genPermutation(i);

genNow();

res = min(res,compare());

}

if(res == 0x3f3f3f3f){

res = -1;

}

printf("Case %d: %d\n",d,res);

}

return 0;

}

UVA 10881 Piotr's Ants

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题5

思路

两个蚂蚁相遇会马上调换方向，从视觉上看其实相当于擦身而过（虽然两只蚂蚁的身份并没有交换）。就像在物理中，两个质量相等的小球发生完全弹性碰撞，交换速度。这里是本题第一个思路点。

无论在任何时候，第i只蚂蚁永远是第i只蚂蚁，因为上面也说了，只是视觉上的擦身，实际上蚂蚁又各自回去了。这是第二个思路点。在这个地方还有一个问题，那就是可能会以为仅仅是位置关系保持原来的顺序，其实方向关系也是保持原来的顺序的，这样就可以解决蚂蚁的最终状态的判定问题。

这样我们就有了解法：首先利用擦身而过的想法，求出最终所有蚂蚁的分布。然后利用标号守恒的想法，把终止状态和起始状态对应。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

struct Ant{
    int pos;
    int dir;//1:R -1:L 0:turing
    int id;
    bool operator < (const Ant &b) const{
        return pos < b.pos;
    }
};

bool cmp(const Ant &a, const Ant &b){
    return a.id < b.id;
}

vector<Ant> all;
int loc[10005];

int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++){
        int L,T,n;
        scanf(" %d %d %d",&L,&T,&n);
        Ant tmp;
        all.clear();
        all.resize(n);
        for(int i = 0; i < n; i++){
            tmp.id = i;
            scanf(" %d",&tmp.pos);
            char dir;
            scanf(" %c",&dir);
            if(dir == 'L'){
                tmp.dir = -1;
            }else{
                tmp.dir = 1;
            }
            all[i] = tmp;
        }
        sort(all.begin(),all.end());
        for(int i = 0; i < n; i++){
            loc[all[i].id] = i;
            all[i].pos += all[i].dir * T;
        }
        sort(all.begin(),all.end());
        for(int i = 0; i < all.size(); i++){
            if((i > 0 && all[i].pos == all[i-1].pos) || (i < all.size()-1 && all[i+1].pos== all[i].pos)){
                all[i].dir = 0;
            }
        }
        //sort(all.begin(),all.end(),cmp);
        printf("Case #%d:\n",d);
        for(int i = 0; i < all.size(); i++){
            if(all[loc[i]].pos < 0 || all[loc[i]].pos > L){
                puts("Fell off");
            }else{
                printf("%d ",all[loc[i]].pos);
                if(all[loc[i]].dir == 1){
                    puts("R");
                }else if(all[loc[i]].dir == -1){
                    puts("L");
                }else{
                    puts("Turning");
                }
            }
        }
        puts("");
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

struct Ant{

int pos;

int dir;//1:R -1:L 0:turing

int id;

bool operator < (const Ant &b) const{

return pos < b.pos;

}

};

bool cmp(const Ant &a, const Ant &b){

return a.id < b.id;

}

vector<Ant> all;

int loc[10005];

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

for(int d = 1; d <= caseCnt; d++){

int L,T,n;

scanf(" %d %d %d",&L,&T,&n);

Ant tmp;

all.clear();

all.resize(n);

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

tmp.id = i;

scanf(" %d",&tmp.pos);

char dir;

scanf(" %c",&dir);

if(dir == 'L'){

tmp.dir = -1;

}else{

tmp.dir = 1;

}

all[i] = tmp;

}

sort(all.begin(),all.end());

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

loc[all[i].id] = i;

all[i].pos += all[i].dir * T;

}

sort(all.begin(),all.end());

for(int i = 0; i < all.size(); i++){

if((i > 0 && all[i].pos == all[i-1].pos) || (i < all.size()-1 && all[i+1].pos== all[i].pos)){

all[i].dir = 0;

}

//sort(all.begin(),all.end(),cmp);

printf("Case #%d:\n",d);

for(int i = 0; i < all.size(); i++){

if(all[loc[i]].pos < 0 || all[loc[i]].pos > L){

puts("Fell off");

}else{

printf("%d ",all[loc[i]].pos);

if(all[loc[i]].dir == 1){

puts("R");

}else if(all[loc[i]].dir == -1){

puts("L");

}else{

puts("Turning");

}

puts("");

}

return 0;

}

LA 3708 Graveyard

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题4.

思路

大概是构造题。

跟白书不太一样的解法，贪心地把两种方案的一个顶点对在一起，然后逐个检查，取两种方案的最小角度差，加在一起，就是答案。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int main(){
    double a,b;
    while(scanf(" %lf %lf",&a,&b) != EOF){
        double sumdeg = 0;
        for(int i = 0; i <= a; i++){
            double deg = 360.0*(double)i/a;
            while(deg > 360.0/(a+b)){
                deg -= 360.0/(a+b);
            }
            sumdeg += min(deg,abs(360.0/(a+b)-deg));
        }
        double ans = sumdeg*10000.0/360.0;
        printf("%.4lf\n",ans);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int main(){

double a,b;

while(scanf(" %lf %lf",&a,&b) != EOF){

double sumdeg = 0;

for(int i = 0; i <= a; i++){

double deg = 360.0*(double)i/a;

while(deg > 360.0/(a+b)){

deg -= 360.0/(a+b);

}

sumdeg += min(deg,abs(360.0/(a+b)-deg));

}

double ans = sumdeg*10000.0/360.0;

printf("%.4lf\n",ans);

}

return 0;

}

UVa 11300 Spreading the Wealth

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白第一章例题3

思路

大概是个构造题。

解决的方法是把整个题转化成一个方程组，令每个人手里的初始金币数量为Ai(已知)，送出数量Xi,受付数量Yi,最终每个人金币数量M(已知)，这样得到由若干形如Ai-Xi+Yi=M方程组成的方程组，当所有方程形式一样时，考虑逐个联立消去未知量，最终得到了关于X1和Xi的若干等式（注意到Xi和Yi+1的相等关系），我们的目标是令Xi之和最小，我们把所有Xi加在一起，就得到了一个仅关于X1的和式。

这个和式的形式可以几何表示是求数轴上一个点，使得其与若干已知点距离之和最短，这个问题的解取在中位数，这样本问题就可以解决了。（中位数是解的想法在白书上有详细的证明，使用反证法）

综合来看，本体需要适当转化，数学变形，数形结合。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

long long n;
long long c[1000005];

int main() {
    while(scanf(" %lld",&n) != EOF) {
        unsigned long long m = 0;
        for(int i = 1; i <= n; i++) {
            scanf(" %llu",&c[i]);
            m += c[i];
        }
        m /= n;
        for(int i = 1; i <= n; i++) {
            c[i] -= m;
            c[i] += c[i-1];
        }
        sort(c,c+n);
        long long rf;
        if(n % 2) {
            rf = c[n/2];
        } else {
            rf = (c[n/2] + c[n/2-1])/2;
        }
        long long res = 0;
        for(int i = 0; i <= n-1; i++) {
            res += abs(c[i] - rf);
        }
        printf("%lld\n",res);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

long long n;

long long c[1000005];

int main() {

while(scanf(" %lld",&n) != EOF) {

unsigned long long m = 0;

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

scanf(" %llu",&c[i]);

m += c[i];

}

m /= n;

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

c[i] -= m;

c[i] += c[i-1];

}

sort(c,c+n);

long long rf;

if(n % 2) {

rf = c[n/2];

} else {

rf = (c[n/2] + c[n/2-1])/2;

}

long long res = 0;

for(int i = 0; i <= n-1; i++) {

res += abs(c[i] - rf);

}

printf("%lld\n",res);

}

return 0;

}

UVa 11729 Commando War

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考《LRJ大礼包::白》第一章例题2

思路

大概是贪心。

只要交代了任务，部下自己就会给做完了，基于这样的题意我们就可以设计这样的一种贪心策略：优先考虑完成任务时间长的，这样交代完了之后就会有更多的时间可以一边交代任务一边有人完成任务，更有效率。

具体操作就是把完成任务时间从大到小排个序，然后顺着检查一遍。

这个策略的证明在白书上面有提供，大概的证明套路就是说明不用这个策略时得到的答案不会更优，在证明时分类讨论了两种情况。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int n;
pair<int,int> task[1005];

bool cmp(pair<int,int> a,pair<int,int> b){
    if(a.second == b.second){
        return a.first < b.first;
    }else{
        return a.second > b.second;
    }
}

int work(){
    int bound = 0;
    int now = 0;
    for(int i = 1; i <= n; i++){
        now += task[i].first;
        bound = max(now + task[i].second, bound);
    }
    return bound;
}

int main(){
    int d = 0;
    while(scanf(" %d",&n) != EOF){
        d++;
        if(!n){
            break;
        }
        for(int i = 1; i <= n; i++){
            scanf(" %d %d",&task[i].first,&task[i].second);
        }
        sort(task+1,task+1+n,cmp);
        printf("Case %d: %d\n",d,work());
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int n;

pair<int,int> task[1005];

bool cmp(pair<int,int> a,pair<int,int> b){

if(a.second == b.second){

return a.first < b.first;

}else{

return a.second > b.second;

}

int work(){

int bound = 0;

int now = 0;

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

now += task[i].first;

bound = max(now + task[i].second, bound);

}

return bound;

}

int main(){

int d = 0;

while(scanf(" %d",&n) != EOF){

d++;

if(!n){

break;

}

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

scanf(" %d %d",&task[i].first,&task[i].second);

}

sort(task+1,task+1+n,cmp);

printf("Case %d: %d\n",d,work());

}

return 0;

}

POJ 3646 The Dragon of Loowater

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考<LRJ大礼包::白>的第一章例题1.

思路

大概是贪心。因为骑士的能力=能砍多大=花多少钱，这样的话只要排个序，从最便宜的英雄开始检查，从小头开始砍，直到检查完最后一个英雄。

如果没砍死就是没解，否则一定是最优解，这个思维和Kruskal算法是一致的。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int n,m;
vector<int> dia;
vector<int> bat;

int work(){
    int ret = 0;
    int cur = 0;
    for(int i = 0; i < bat.size(); i++){
        if(cur < n && dia[cur] <= bat[i]){
            ret += bat[i];
            cur++;
        }
    }
    if(cur < n){
        return -1;
    }
    return ret;
}

int main(){
    while(scanf(" %d %d",&n,&m) != EOF){
        if(n == 0 && m == 0){
            break;
        }
        dia.clear();
        bat.clear();
        dia.resize(n);
        bat.resize(m);
        for(int i = 0; i < n; i++){
            scanf(" %d",&dia[i]);
        }
        for(int i = 0; i < m; i++){
            scanf(" %d",&bat[i]);
        }
        sort(dia.begin(),dia.end());
        sort(bat.begin(),bat.end());
        int res = work();
        if(res == -1){
            puts("Loowater is doomed!");
        }else{
            printf("%d\n",res);
        }
    }


    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int n,m;

vector<int> dia;

vector<int> bat;

int work(){

int ret = 0;

int cur = 0;

for(int i = 0; i < bat.size(); i++){

if(cur < n && dia[cur] <= bat[i]){

ret += bat[i];

cur++;

}

if(cur < n){

return -1;

}

return ret;

}

int main(){

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

if(n == 0 && m == 0){

break;

}

dia.clear();

bat.clear();

dia.resize(n);

bat.resize(m);

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

scanf(" %d",&dia[i]);

}

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

scanf(" %d",&bat[i]);

}

sort(dia.begin(),dia.end());

sort(bat.begin(),bat.end());

int res = work();

if(res == -1){

puts("Loowater is doomed!");

}else{

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

}

return 0;

}

Editoral for SCUT ICPC Team Qualification Round A

December 05, 20152015-12-05hahaschoolLeave a comment

点按此处下载题面

PROBLEM A

很明显，双方最优策略是一直往前走，对手一直往前就能赢了，所以bx hao sui啊！

PROBLEM B

做这个题需要知道二项式定理，乘法逆元和等比数列求和，组合数取模。

$\sum_{i=1}^{n}(a^{i}+b^{i})^{k} = \sum_{i=1}^{n}\sum_{j=0}^{k} \binom{k}{j} a^{ij}b^{i(k-j)}=\sum_{j=0}^{k}\binom{k}{j} \sum_{i=1}^{n}q^{i}$

$q = a ^ {j} b ^ {k-j}$

后面就是等比数列的求和。

需要注意的是q＝1的时候。

二项式系数可以用阶乘和逆元预处理，等比数列求和也可以用逆元求出来。复杂度O(Klog(N))。

PROBLEM C

这题求的是一个有向无环图的最小树形图。可以对每个点，选一个权值最小的入边加起来就是答案。

PROBLEM D

直接模拟统计出到最后时刻情怀值会受损多少。对于每个时间点，如果不能ak，则损害值增加tn-ti。最后总的损害值如果比原始情怀值小则just enjoy coding，否则fail to graduate。

PROBLEM E

PROBLEM F

PROBLEM G

//模拟易知，画出来的图形是Sierpinski三角形，一种分形图像
//所以可以直接模拟，也可以用递归绘制（just for fun）
//如果你看到的注释没对齐，请在CodeBlocks中打开本代码

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100;

int n;
char canvas[MAXN][MAXN * 2 - 1];							//画布

#define _USE_FRACTAL_METHOD_								//注释本行，将使用普通画法；否则，使用递归绘制分形

#ifndef _USE_FRACTAL_METHOD_
void draw() {												//普通画法
	canvas[0][n - 1] = '*';									//将第一行中间那个人设为*
	for (int i = 1; i < n; ++i) {							//对于接下来每一行
		for (int j = 0; j < 2 * n - 1; ++j) {				//从左到右查看
			bool flag[3];									//用来记录前方的人的状态
			if (j == 0)										//如果是最左边的人，就不用查看左前方
				flag[0] = false;
			else
				flag[0] = canvas[i - 1][j - 1] == '*';
			flag[1] = canvas[i - 1][j] == '*';				//记录正前方
			if (j == 2 * n - 2)								//如果是最右边的人，就不用查看右前方
				flag[2] = false;
			else
				flag[2] = canvas[i - 1][j + 1] == '*';
			if (!flag[0] && !flag[1] && flag[2])			//四种需要设为*的情况
				canvas[i][j] = '*';
			else if (!flag[0] && flag[1] && flag[2])
				canvas[i][j] = '*';
			else if (flag[0] && !flag[1] && !flag[2])
				canvas[i][j] = '*';
			else if (flag[0] && flag[1] && !flag[2])
				canvas[i][j] = '*';
		}
	}
}
#else
void draw(int row, int col, int size) {						//分形画法，以(row, col)为顶角，绘制大小为size的分形三角形
	if (row >= n || col < 0 || col >= 2 * n - 1)			//如果超出画布范围，就不画了
		return;
	if (size == 1)											//若已经是最小的三角形，直接绘制
		canvas[row][col] = '*';
	else {													//否则递归
		draw(row, col, size / 2);							//三个小三角形的顶角坐标如参数所示
		draw(row + size / 2, col - size / 2, size / 2);
		draw(row + size / 2, col + size / 2, size / 2);
	}
}
#endif // _USE_FRACTAL_METHOD_

int main() {
	while (cin >> n) {
		memset(canvas, '.', sizeof(canvas));				//初始化，将画布充填为.
#ifndef _USE_FRACTAL_METHOD_
		draw();												//普通画法
#else
		int size;											//分形画法需要计算最大三角形的size，size为2^k
		for (size = 1; size < n; size *= 2);				//寻找大于等于n的最小的size
		draw(0, n - 1, size);								//分形画法
#endif // _USE_FRACTAL_METHOD_
		for (int i = 0; i < n; ++i) {						//输出
			for (int j = 0; j < 2 * n - 1; ++j)
				cout << canvas[i][j];
			cout << endl;
		}
		cout << endl;										//输出额外的空行
	}
	return 0;
}

//模拟易知，画出来的图形是Sierpinski三角形，一种分形图像

//所以可以直接模拟，也可以用递归绘制（just for fun）

//如果你看到的注释没对齐，请在CodeBlocks中打开本代码

#include <iostream>

#include <cstring>

using namespace std;

const int MAXN = 100;

int n;

char canvas[MAXN][MAXN * 2 - 1]; //画布

#define _USE_FRACTAL_METHOD_ //注释本行，将使用普通画法；否则，使用递归绘制分形

#ifndef _USE_FRACTAL_METHOD_

void draw() { //普通画法

canvas[0][n - 1] = '*'; //将第一行中间那个人设为*

for (int i = 1; i < n; ++i) { //对于接下来每一行

for (int j = 0; j < 2 * n - 1; ++j) { //从左到右查看

bool flag[3]; //用来记录前方的人的状态

if (j == 0) //如果是最左边的人，就不用查看左前方

flag[0] = false;

else

flag[0] = canvas[i - 1][j - 1] == '*';

flag[1] = canvas[i - 1][j] == '*'; //记录正前方

if (j == 2 * n - 2) //如果是最右边的人，就不用查看右前方

flag[2] = false;

else

flag[2] = canvas[i - 1][j + 1] == '*';

if (!flag[0] && !flag[1] && flag[2]) //四种需要设为*的情况

canvas[i][j] = '*';

else if (!flag[0] && flag[1] && flag[2])

canvas[i][j] = '*';

else if (flag[0] && !flag[1] && !flag[2])

canvas[i][j] = '*';

else if (flag[0] && flag[1] && !flag[2])

canvas[i][j] = '*';

}

#else

void draw(int row, int col, int size) { //分形画法，以(row, col)为顶角，绘制大小为size的分形三角形

if (row >= n || col < 0 || col >= 2 * n - 1) //如果超出画布范围，就不画了

return;

if (size == 1) //若已经是最小的三角形，直接绘制

canvas[row][col] = '*';

else { //否则递归

draw(row, col, size / 2); //三个小三角形的顶角坐标如参数所示

draw(row + size / 2, col - size / 2, size / 2);

draw(row + size / 2, col + size / 2, size / 2);

}

#endif // _USE_FRACTAL_METHOD_

int main() {

while (cin >> n) {

memset(canvas, '.', sizeof(canvas)); //初始化，将画布充填为.

#ifndef _USE_FRACTAL_METHOD_

draw(); //普通画法

#else

int size; //分形画法需要计算最大三角形的size，size为2^k

for (size = 1; size < n; size *= 2); //寻找大于等于n的最小的size

draw(0, n - 1, size); //分形画法

#endif // _USE_FRACTAL_METHOD_

for (int i = 0; i < n; ++i) { //输出

for (int j = 0; j < 2 * n - 1; ++j)

cout << canvas[i][j];

cout << endl;

}

cout << endl; //输出额外的空行

}

return 0;

}

PROBLEM H

对于每个数，我们需要满足的条件有两个：一个是各数位数字单调递减，第二个是这个数字满足被6整除。首先，如果直接枚举满足第二个条件的数，那么要枚举的数太多，复杂度太高。那么我们首先考虑满足第一个条件。各个数位的数字单调递减说明了各个数字不同（即每个数只能选一次），而数字只能在0-9这10个数选取（说明最多取10个数），且满足单调递减（说明对每组取的数，只有一个方案是符合的）。于是所有满足条件“各数位数字单调递减”的数字只有C(10, 1) + C(10, 2) + C(10, 3) + … + C(10, 9) + C(10, 10) = 2^10-1 = 1023。于是我们可以通过搜索的方法找到所有满足第一个条件的数，然后判断是否满足第二个条件。搜索的方法是先枚举高位，再枚举低位，每次枚举的数都得比高位的数小，直到没有数可以枚举（最小是0）结束。用递归可以解决。最后我们求出所有满足第一和第二个条件的数只有两百多个。注意最大的数会超出int的范围，所以我们可以用一个long long数组存下满足条件的数。接下来我们由于我们最多只有20组数据，所以我们可以判断每个合法的数是否小于或等于输入数据。

主要部分代码如下：

ong long sum = 0, a[300];
int cnt = 0;

void dfs(int n) {
	for(int i = n-1; i >= 0; --i) {
		sum = sum * 10 + i;
		if(sum % 6 == 0) a[cnt++] = sum;
		dfs(i);
		sum /= 10;
	}
}

ong long sum = 0, a[300];

int cnt = 0;

void dfs(int n) {

for(int i = n-1; i >= 0; --i) {

sum = sum * 10 + i;

if(sum % 6 == 0) a[cnt++] = sum;

dfs(i);

sum /= 10;

}

PROBLEM I

//题意为，在输入矩阵中，数出
//横着或竖着
//连续三个或以上同颜色珠
//的次数
//如果你看到的注释没对齐，请在CodeBlocks中打开本代码

#include <iostream>
using namespace std;

int n, m;
char board[128][128];

int main() {
	int t;
	cin >> t;										//输入数据的组数
	while (t--) {
		cin >> n >> m;								//输入矩阵尺寸
		for (int i = 0; i < n; ++i)					//读取矩阵
			for (int j = 0; j < m; ++j)
				cin >> board[i][j];
		int ans = 0;								//答案
		char pre_type;								//储存遇到的上一个珠子的种类
		int cnt;									//计数器，记录当前这种珠子遇到连续几个了
		for (int i = 0; i < n; ++i) {				//对于每一行进行检查
			for (int j = 0; j < m; ++j)
				if (j == 0) {						//如果是第一颗珠子
					pre_type = board[i][j];			//设定
					cnt = 1;
				}
				else {
					if (pre_type == board[i][j])	//如果与上一颗珠子的种类一样
						++cnt;						//累加计数器
					else {							//如果与上一颗珠子的种类不一样
						if (cnt >= 3)				//如果上一种珠子出现的颗数大于等于3
							++ans;					//累加答案
						pre_type = board[i][j];		//更新
						cnt = 1;					//重置计数器
					}
				}
			if (cnt >= 3)							//不要忘了对最后出现的那种珠子判断
				++ans;
		}
		for (int i = 0; i < m; ++i) {				//对于每一列进行检查，下同对行的检查
			for (int j = 0; j < n; ++j)
				if (j == 0) {
					pre_type = board[j][i];
					cnt = 1;
				}
				else {
					if (pre_type == board[j][i])
						++cnt;
					else {
						if (cnt >= 3)
							++ans;
						pre_type = board[j][i];
						cnt = 1;
					}
				}
			if (cnt >= 3)
				++ans;
		}
		cout << ans << endl;						//输出答案
	}
	return 0;
}

//题意为，在输入矩阵中，数出

//横着或竖着

//连续三个或以上同颜色珠

//的次数

//如果你看到的注释没对齐，请在CodeBlocks中打开本代码

#include <iostream>

using namespace std;

int n, m;

char board[128][128];

int main() {

int t;

cin >> t; //输入数据的组数

while (t--) {

cin >> n >> m; //输入矩阵尺寸

for (int i = 0; i < n; ++i) //读取矩阵

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

cin >> board[i][j];

int ans = 0; //答案

char pre_type; //储存遇到的上一个珠子的种类

int cnt; //计数器，记录当前这种珠子遇到连续几个了

for (int i = 0; i < n; ++i) { //对于每一行进行检查

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

if (j == 0) { //如果是第一颗珠子

pre_type = board[i][j]; //设定

cnt = 1;

}

else {

if (pre_type == board[i][j]) //如果与上一颗珠子的种类一样

++cnt; //累加计数器

else { //如果与上一颗珠子的种类不一样

if (cnt >= 3) //如果上一种珠子出现的颗数大于等于3

++ans; //累加答案

pre_type = board[i][j]; //更新

cnt = 1; //重置计数器

}

if (cnt >= 3) //不要忘了对最后出现的那种珠子判断

++ans;

}

for (int i = 0; i < m; ++i) { //对于每一列进行检查，下同对行的检查

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

if (j == 0) {

pre_type = board[j][i];

cnt = 1;

}

else {

if (pre_type == board[j][i])

++cnt;

else {

if (cnt >= 3)

++ans;

pre_type = board[j][i];

cnt = 1;

}

if (cnt >= 3)

++ans;

}

cout << ans << endl; //输出答案

}

return 0;

}

PROBLEM J

把下标乘上1000得到一个递推式子，

BX(n) = BX(n – 1000) + BX(n – 1234)。

答案就是BX(n*1000)

Author Information

ABCJ : doubility(czk)

DH : ConquererV587(kbx)

GI: Xdynix(rxy)

动态规划初步

November 14, 20152018-08-26hahaschoolLeave a comment

[toc]

什么是动态规划

动态规划是一种方法，或者说思想，它并不是某种特定算法。
动态规划方法的通俗解释：将原来比较复杂的问题分解为若干比较简单的子问题，将这些子问题逐个解决，并存储这些子问题的答案，原来的问题的答案将会从这些分解了的子问题的答案中导出。等到下一次遇到了相同的子问题时，我们只是提取出事前存储的问题的答案，而不是重新做一次计算。
对上面通俗解释的解释：无论是原问题，还是子问题，都是问题，我们拿到一个问题，给他分解为若干子问题，那么接下来我们如何解决子问题？那就是把每个子问题当成原问题再度分解，得到子问题的子问题，然后为了解决这些“子问题的子问题”，我们再度分解。。。直到最终我们得到了已经无法再分的“原子问题”，我们假定原子问题是可以很好地被解决的，那么我们理论上只要解决的全部的原子问题，再回推，就可以解决掉全部子问题，最终解决最根本的问题，也就是我们拿到的问题。而动态规划方法体现在我们加速这个过程上，在问题的分解过程中，我们可能会遇到重复的情况，如果我们对这些重复的情况调用之前计算好的答案，就不用再次深入分解问题，这样能大大加快整个求解进程。
动态规划的关键字：递推、记忆化、状态转移

状态

什么是状态

字面含义：物质系统所处的状况。
我们这里所说的状态是一种抽象观念。
在动态规划的设计上，一个“状态”，表达的是在某个情形下的子问题。
在动态规划的操作上，状态最终表现为一个又一个的值，也就是在某个特定情形下的子问题的答案。

状态转移

基于当前状态和其他输入，移动到其他状态。
说人话：某个东西现在是某个样子的，然后我对他动了些手脚，这个东西变成了另外一幅样子。
当前状态能不能转移到当前状态？可以
如何表达状态转移？
- 状态转移方程（你可以列个公式）
- 状态转移图（你可以把状态形象化为点，把转移条件形象化为边）
- 状态转移表（你听说过函数表吗？虽然没怎么用过但这是初中内容。）

那么状态和动态规划有什么关系？

上面说到了，在动态规划里的“状态”表达的是“子问题”，前面也说了，动态规划整体来看是一个操作子问题的方法，这样我们也可以说动态规划是一个操作状态的方法。在动态规划过程中，我们分解当前状态，得到子状态，处理子状态，记忆子状态，最终处理好全部需要处理的状态，从所有状态中挑出合适的、我们需要的状态来代表最终答案。

用动态规划解决问题

必要条件

不是所有的问题都能用动态规划解决，能够使用动态规划方法解决的问题必须满足以下两个基本性质：

对于一个问题，如果它取得了最优解，那么这个问题所能分解出来的所有子问题的解也是最优的，这个性质称为最优子问题/最优子结构。
如果我们已经解决了一些问题，那么当我们解决其他问题的时候，已经解决的问题的答案必须不能受新解决的问题影响。也就是说某个状态之后的过程不可以影响之前的状态。这一性质，称为无后效性。

分治？

聪明的你发现了，分治法不也是把当前问题分解为小一点的问题直到不能再分，然后解决原子问题回推得到根问题的答案吗？分治和动态规划有什么区别？

适用于用动态规划法求解的问题，分解后的子问题往往不是独立的，在之后的求解过程中会用到之前已经解决的问题的答案。

上面说过了，动态规划过程中每个子问题的答案将会被保存以避免重复计算，这里才是我们高速解决问题的原因。因此我们有下面这种说法：

使用动态规划有意义的条件

子问题之间不是独立的，一个子问题在之后的求解过程中可能会被多次使用到。这个性质称为重叠子问题。
需要注意重叠子问题并不是动态规划适用的必要条件，但是如果没有这个性质，使用动态规划并没有意义。

操作步骤

我们使用动态规划方法解决问题时，一般按照以下思维和操作程序：

分析问题：判定其是否能且有意义使用动态规划。
再度分析：找出将问题分解的方法，将分解后的问题合并的方法，确定原子问题的位置（即边界条件）。
定义状态：确定每个状态对应的问题是什么，答案表示什么，携带的情形是什么。
处理状态：递推 and/or 记忆化。
选择答案：从处理好的状态中选择我们需要的合适的状态作出最终答案。

关键点

状态设计
转移方程
初始化
二次优化（本文不讨论）

如果把目光放长远一点

动态规划方法解决了一个问题，但这很可能并不是你要解决的问题的全部。
递推可以叫动态规划吗？我认为可以，你可以看成每个问题只能分解出一个子问题，虽然感觉上有一点奇怪，而且你要注意到递推过程中并没有重叠子问题，即使你管他叫动态规划，那也是没啥意义的动态规划。
开一下脑洞：你用一种动态规划方法分解出来的原子问题需要另外一种动态规划方法解决？你现在动态规划解决的问题其实只是另一个问题的模块？想想就好了，高中生啥都干的出来。

一些经典且简单的模型

关于Fibonacci

广义/系数Fibonacci

首先要说的是，Fibonacci数列中，最有分量的一句话其实是 $f_i = f_{i-1} + f_{i-2}$ ， $f_1$ 和 $f_2$ 的值并不重要，所以我们在这里可以推广Fibonacci数列的含义为只要有这样的递推就可以称为(广义)Fibonacci数列。

我们都知道Fibonacci数列，要想快速应付多次查询我们可以事前预处理，要想快速应付一次巨大的查询我们可以使用矩阵快速幂。那么如果我给出下面的问题呢?

Given $f_1 = a$ , $f_2 = b$ , $f_i = f_{i-1} + f_{i-2}$ for every $f >= 3$ ,for each query you will get 3 numbers a,b,c,you have to output $f_c$ in condition of given a and b.