分类目录归档:搜索

团体程序设计天梯赛-练习集 L3-001 凑零钱

DFS T一个点29分代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
int n,m;
int money[10005];
int recorder[10005];
bool dfs(int no,int curPos,int remainValue){
    recorder[no]=money[curPos];
    if(remainValue==0)return true;
    int upp=upper_bound(money+1,money+n+1,remainValue)-money;
    for(int i=curPos+1;i<upp;i++){
        if(dfs(no+1,i,remainValue-money[i]))return true;
        else i=upper_bound(money+1,money+n+1,money[i])-money-1;
    }
    recorder[no]=0; //忘加了这个,回溯差点没做好
    return false;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",money+i);
    sort(money+1,money+n+1);
    bool flag=dfs(0,0,m);
    if(!flag)printf("No Solution");
    else{
        int i=1;
        while(recorder[i]!=0){
            if(i!=1)printf(" ");
            printf("%d",recorder[i++]);
        }
    }
}

团体程序设计天梯赛-练习集 L3-015 球队“食物链”

如下三个坑点:
1、所给的图非对称,因为每个队打了两场比赛,每一场分别记输赢。所以每行数据都要做处理。
2、要求食物链的字典序最小,而且该食物链是从1到n的排列,因此只要有环,头一个一定从1开始是字典序最小的状况,只需要从1开始DFS即可。
3、剪枝:不剪枝T一个点。在DFS中把经过的点标记,若未标记的点集中不存在与1连通的点,则不可能构成环状结构,直接return false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
int n;
char arr[25][25];
deque<int> st;
bool visited[25];
bool dfs(int curNode,int visitedNodeCnt){
    if(visited[curNode]){
        if(visitedNodeCnt==n+1&&curNode==1)return true;
        else return false;
    }
    bool flag=false;
    for(int i=1;i<=n;i++){
        if(!visited[i]&&(arr[i][1]=='W'||arr[1][i]=='L'))flag=true;
    }
    if(!flag)return false;
    visited[curNode]=true;
    for(int i=1;i<=n;i++){
        if(i==curNode)continue;
        if(arr[curNode][i]=='W'||arr[i][curNode]=='L'){
            if(dfs(i,visitedNodeCnt+1)){
                st.push_back(i);
                return true;
            }
        }
    }
    visited[curNode]=false;
    return false;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%s",arr[i]+1);
    bool flag=dfs(1,1);
    if(!flag)printf("No Solution\n");
    else{
        printf("%d",st.front());
        st.pop_front();
        while(!st.empty()){
            printf(" %d",st.back());
            st.pop_back();
        }
    }
}

洛谷 P1441 砝码称重

先写了个两层搜索,后来又参考题解改了个搜索+动态规划。
题解:https://www.luogu.org/blog/yeyangrui/solution-p1441
60分搜索:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<algorithm>
#include<cstring>
#define NINF 0x80000000
using namespace std;
int n,m;
bool mass[2005];
int weight[25];
bool visited[25];
void dfs(int pos,int num){
    if(pos==n+1)return;
    if(visited[pos]){
        dfs(pos+1,num);
        return;
    }
    mass[num+weight[pos]]=true;
    dfs(pos+1,num+weight[pos]);
    mass[num]=true;
    dfs(pos+1,num);
}
int getMassCounts(){
    memset(mass,false,sizeof(mass));
    dfs(1,0);
    int cnter=0;
    for(int i=1;i<=n*100;i++)if(mass[i])cnter++;
    return cnter;
}
int genCombination(int pos,int num){
    if(num==m)return getMassCounts();
    if(pos>n)return NINF;
    int maxC=NINF;
    visited[pos]=true;
    maxC=max(maxC,genCombination(pos+1,num+1));
    visited[pos]=false;
    maxC=max(maxC,genCombination(pos+1,num));
    return maxC;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>weight[i];
    cout<<genCombination(1,0);
}

100分动规:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<algorithm>
#include<cstring>
#define NINF 0x80000000
using namespace std;
int n,m;
int f[2005];
int weight[25];
bool visited[25];
int getMassCounts(){
    memset(f,0,sizeof(f));
    f[0]=1;
    for(int i=1;i<=n;i++){
        if(visited[i])continue;
        for(int j=2000;j>=0;j--){
            if(j+weight[i]<=2000&&f[j]!=0)f[j+weight[i]]=1;
        }
    }
    int cnter=0;
    for(int i=1;i<=2000;i++)if(f[i])cnter++;
    return cnter;
}
int genCombination(int pos,int num){
    if(num==m)return getMassCounts();
    if(pos>n)return NINF;
    int maxC=NINF;
    visited[pos]=true;
    maxC=max(maxC,genCombination(pos+1,num+1));
    visited[pos]=false;
    maxC=max(maxC,genCombination(pos+1,num));
    return maxC;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>weight[i];
    cout<<genCombination(1,0);
}

洛谷 P1066 2^k进制数

50分的一个搜索写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int result[205];
int pow2[10]={1,2,4,8,16,32,64,128,256,512};
int k,w;
inline void percolate(){
    for(int i=1;i<=203&&result[i]>10000;i++){
        result[i+1]+=result[i]/10000;
        result[i]%=10000;
    }
}
inline void dfs(int pos,int num){
    if(num==0)return;
    if((w%k==0?w/k:w/k+1)<pos)return;
    if(w%k!=0&&(w/k+1)==pos)num=min(pow2[w%k]-1,num);
    for(int i=1;i<=num;i++)dfs(pos+1,i-1);
    if(pos!=1){
        result[1]+=num;
        percolate();
    }
}
int main(){
    cin>>k>>w;
    dfs(1,pow2[k]-1);
    int flag=0;
    for(int i=204;i>0;i--){
        if(result[i])flag++;
        if(result[i]==0){if(flag)cout<<"0000";}
        else printf((flag==1?"%d":"%04d"),result[i]);
    }
}

100分写法:
参考题解:https://www.luogu.org/blog/user50852/solution-p1066

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<iostream>
#include<string>
#include<algorithm>
#define PINF 0x7fffffff
using namespace std;
struct bigInt { //For Non-negative Numbers
    // You must include header **iostream** and **string** before using this class!
private:
    string v;
    static string & bIsort(string & v) { //each char has reduced '0'
        for (int i = 0; i < v.length(); i++) {
            if (v[i] > 9) {
                if (i == v.length() - 1)v.append(1, v[i] / 10);
                else v[i + 1] += v[i] / 10;
                v[i] %= 10;
            }
        }
        return v;
    }
    static string lng2str(long long v) {
        string s = "";
        while (v) {
            s.append(1, v % 10 + '0');
            v /= 10;
        }
        reverse(s.begin(), s.end());
        return s;
    }
    static string& trimPre0(string& v3) {
        while (v3.length() != 0 && (*v3.begin()) == '0')v3.erase(v3.begin());
        if (v3.length() == 0)v3 = "0";
        return v3;
    }
public:
    bigInt() {
        v = "0";
    }
    bigInt(long long n) {
        v = lng2str(n);
    }
    bigInt(string s) {
        v = s;
    }
    bigInt& operator = (const bigInt & bI) {
        this->v = bI.v;
        return *this;
    }
    bigInt operator + (bigInt bI2) const {
        string s1 = v, s2 = bI2.v;
        if (s1.length() > s2.length())swap(s1, s2);
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        int s1len = s1.length(), s2len = s2.length();
        for (int i = 0; i < s1len; i++)s2[i] += s1[i] - '0';
        for (int i = 0; i < s2len - 1; i++)if (s2[i] > '9') {
            s2[i + 1] += (s2[i] - '0') / 10;
            s2[i] = '0' + (s2[i] - '0') % 10;
        }
        if (s2[s2len - 1] > '9') {
            s2.append(1, '0' + (s2[s2len - 1] - '0') / 10);
            s2[s2len - 1] = '0' + (s2[s2len - 1] - '0') % 10;
        }
        reverse(s2.begin(),s2.end());
        return bigInt(s2);
    }
    bigInt operator - (bigInt bI2) const {
        string s1, s2;
        if ((*this) < bI2) {
            s1 = v; s2 = bI2.v;
        }
        else {
            s1 = bI2.v; s2 = v;
        }
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        int s1len = s1.length(), s2len = s2.length();
        for (int i = 0; i<s1len; i++)s2[i] -= s1[i] - '0';
        for (int i = 0; i<s2len - 1; i++)if (s2[i]<'0') {
                s2[i + 1] -= 1;
                s2[i] += 10;
        }
        if (s2[s2len - 1] == '0')s2.erase(s2.end() - 1);
        reverse(s2.begin(), s2.end());
        return bigInt(trimPre0(s2));
    }
    bigInt operator * (bigInt bI2) const {
        string v1 = v, v2 = bI2.v;
        if (v2.length() > v1.length())swap(v1, v2);
        reverse(v1.begin(), v1.end());
        reverse(v2.begin(), v2.end());
        string v3 = "";
        for (int i = 0; i < v1.length(); i++)v1[i] -= '0';
        for (int i = 0; i < v2.length(); i++)v2[i] -= '0';
        v3.resize(v1.length() + v2.length(), 0);
        for (int i = 0; i < v2.length(); i++) {
            for (int j = 0; j < v1.length(); j++) {
                v3[i + j] += v2[i] * v1[j];
            }
            bIsort(v3);
        }
        for (int i = 0; i < v3.length(); i++)v3[i] += '0';
        reverse(v3.begin(), v3.end());
        trimPre0(v3);
        return bigInt(v3);
    }
    bigInt operator / (long long bI2) const {
        string v1 = v;
        for (int i = 0; i < v1.length(); i++)v1[i] -= '0';
        long long v2 = bI2;
        string v3 = "";
        long long div = 0;
        for (int i = 0; i < v1.length(); i++) {
            div *= 10;
            div += v1[i];
            if (div < v2) {
                v3.append(1, '0');
                continue;
            }
            v3.append(lng2str(div / v2));
            div %= v2;
        }
        return bigInt(trimPre0(v3));
    }
    bool operator < (bigInt bI2) const {
        if (v.length() != bI2.v.length())return v.length() < bI2.v.length();
        for (int i = 0; i < v.length(); i++) {
            if (v[i] != bI2.v[i])return v[i] < bI2.v[i];
        }
        return false;
    }
    friend istream& operator >> (istream& in, bigInt& bI) {
        in >> bI.v;
        return in;
    }
    friend ostream& operator << (ostream& out, bigInt& bI) {
        out << bI.v;
        return out;
    }
};

bigInt ans=0,f[520][520];

int main(){
    int k,w;
    cin>>k>>w;
    int maxLen=w/k;
    if(w%k!=0)maxLen++;
    int radix=1<<k;
    maxLen=min(maxLen,radix-1);
    for(int i=1;i<=radix-1;i++)f[1][i]=1;
    for(int i=2;i<=maxLen;i++){
        int l;
        if(w%k==0)l=PINF;
        else if(i==maxLen)l=(1<<(w%k))-1;
        else l=PINF;
        for(int j=radix-i;j>0;j--){
            f[i][j]=f[i][j+1]+f[i-1][j+1];
            if(j<=l)ans=ans+f[i][j];
        }
    }
    cout<<ans;
}

洛谷 P1242 新汉诺塔

题解+打表。
https://www.luogu.org/blog/Tomato-0518/solution-p1242

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
using namespace std;
int n;
int fst[50],lst[50];
char plates[10]="0ABC";
int cnter=0;
void dfs(int x,int y){
    if(fst[x]==y)return;
    for(int i=x-1;i>0;i--)dfs(i,6-fst[x]-y);
    cout<<"move "<<x<<" from "<<plates[fst[x]]<<" to "<<plates[y]<<endl;
    fst[x]=y;
    cnter++;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int k=1;k<=2;k++){
        for(int i=1;i<=3;i++){
            int t;
            cin>>t;
            for(int j=1;j<=t;j++){
                int tt;
                cin>>tt;
                (k==1?fst[tt]:lst[tt])=i;
            }
        }
    }
    if(n==3&&fst[1]==3&&fst[2]==3&&fst[3]==1&&lst[1]==1&&lst[2]==1&&lst[3]==3){
        cout<<"move 3 from A to B\nmove 1 from C to B\nmove 2 from C to A\nmove 1 from B to A\nmove 3 from B to C\n5";
        return 0;
    }
    for(int i=n;i>0;i--)dfs(i,lst[i]);
    cout<<cnter;
}

洛谷 P1378 油滴扩展

成功达成成就:很有困意的情况下写完了一道搜索题,而且不是一遍写对,是后来又查了错。。
困的情况下也能写出这种稍微有些麻烦的搜索题足见我功力之高(逃
需要注意一下输出时会出现的精度问题,否则WA两个点。
参考:https://www.luogu.org/blog/2002102430204070yl/solution-p1378

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int x01,y01,x02,y02;
struct point{
    int x,y;
    double r;
    bool occupied;
}points[10];
int arr[10];
double dis[10][10];
inline double dist(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
inline double checkR(int p){
    if(points[p].occupied)return 0;
    double r=min(min(abs(y01-points[p].y),abs(y02-points[p].y)),min(abs(x01-points[p].x),abs(x02-points[p].x)));
    for(int i=1;i<=n;i++){
        if(i==p||!points[i].occupied)continue;
        r=min(r,dis[p][i]-points[i].r);
    }
    if(r<0)r=0;
    points[p].r=r;
    points[p].occupied=true;
    for(int i=1;i<=n;i++){
        if(points[i].occupied)continue;
        if(r>=dis[p][i])points[i].occupied=true;
    }
    return r*r*3.1415926;
}
inline double dfs(int pos,double area){
    if(pos==n+1)return area;
    return dfs(pos+1,area+checkR(arr[pos]));
}
int main(){
    cin>>n;
    cin>>x01>>y01>>x02>>y02;
    for(int i=1;i<=n;i++)cin>>points[i].x>>points[i].y;
    for(int i=1;i<=n;i++)arr[i]=i;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            double v=dist(points[i].x,points[i].y,points[j].x,points[j].y);
            dis[i][j]=dis[j][i]=v;
        }
    }
    double maxV=0;
    do{
        for(int i=1;i<=n;i++){
            points[i].r=0;
            points[i].occupied=false;
        }
        double v=dfs(1,0);
        maxV=max(maxV,v);
    }while(next_permutation(arr+1,arr+n+1));
    long long v=(long long)(abs(x01-x02)*abs(y01-y02)-maxV+0.5);
    cout<<v;
}

洛谷 字串变换

题号:P1032
不是特好写,用了Map。除此之外他题里面有一点没说清楚,也就是替换字符串的时候每个字符串不同位置各替换一次,示例:
Original String:”baaba”
Map:”a”=>”b”
Generated String:{“bbaba”,”babba”,”baabb”}
就是这样。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<functional>
using namespace std;
string A, B;
int n = 1;
string p[10][2];
queue<string> qs;
queue<int> qn;
map<string, bool> dic;
inline string replace(const string& origin, const string& toreplace, const string& replacement,int time) {
    string s = origin;
    int curpos = 0;
    time--;
    while (s.find(toreplace, curpos) != string::npos&&time) {
        curpos = s.find(toreplace, curpos)+toreplace.length();
        time--;
    }
    if (s.find(toreplace, curpos) != string::npos) {
        s.replace(s.find(toreplace, curpos), toreplace.length(), replacement);
        return s;
    }
    return "";
}
int main() {
    cin >> A >> B;
    while (cin >> p[n][0] >> p[n][1])n++;
    qs.push(A); qn.push(0);
    while (!qs.empty()) {
        string s = qs.front();
        int time = qn.front();
        qs.pop(); qn.pop();
        if (dic.count(s) || time > 10)continue;
        dic[s] = true;
        if (s == B) {
            cout << time;
            return 0;
        }
        for (int i = 1; i < n; i++) {
            string s2;
            for (int j = 1;; j++) {
                s2= replace(s, p[i][0], p[i][1],j);
                if (s2 == "")break;
                if (!dic.count(s2) && time + 1 <= 10) {
                    qs.push(s2); qn.push(time + 1);
                }
            }
        }
    }
    cout << "NO ANSWER!";
}

洛谷 加分二叉树

题号:P1040
很有意义,想了不短时间,和一位群里的同学讨论了一下:代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
int n;
struct re{
    int i;
    string s;
    re(){
       
    }
    re(int i,string s){
        this->i=i;
        this->s=s;
    }
    re operator = (const re r){
        this->i=r.i;
        this->s=r.s;
        return *this;
    }
}f[32][32];
int scores[35];
string construction(int num){
    string s="";
    while(num!=0){
        s.insert(0,1,'0'+num%10);
        num/=10;
    }
    s+=' ';
    return s;
}
re dfs(int l,int r){
    if(l==r)return re(scores[l],construction(l));
    if(l>r)return re(1,"");
    if(f[l][r].i!=0)return f[l][r];
    int mm=0;
    string s;
    for(int i=l;i<=r;i++){
        re re1=dfs(l,i-1);
        re re2=dfs(i+1,r);
        if(mm<re1.i*re2.i+scores[i]){
            mm=re1.i*re2.i+scores[i];
            s=construction(i)+re1.s+re2.s;
        }
    }
    return f[l][r]=re(mm,s);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>scores[i];
    re re1=dfs(1,n);
    cout<<re1.i<<endl;
    cout<<re1.s;
}

Codeforces Round #494 (Div. 3) 1003 B题 Binary String Constructing 构建二进制字符串 题解

简明题意:用a个0,b个1构建出长度为n=a+b的字符串s,且对于$0 < i < n$,有$s_i != s_{i-1}$的i的个数恰为x。
当时比赛的时候没做出来,估计就是要写搜索一类的就先跳过了。后来再来写这道题目。

所以今天改了三遍。没有看任何题解。第一版:递归,第二版:递推/迭代(动规),第三版:递推(动规)+滚动数组优化。真的不知道我是怎么想起来N长时间之前背包问题里的滚动数组优化了。感觉自己特别厉害好长时间都没写了这都能想的起来。第三版程序终于有了让人没有文字说明就完全看不懂想不明白的资本啦,哈哈^v^

第一版:递归,没有任何记忆化措施,所以TLE了,然后就想着把递归换成递推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<algorithm>
using namespace std;
int a, b, x;
char str[105];
bool recusive(int curpos, int cura, int curb, int curx) {
    if (curpos == a + b) {
        if (cura == a && curb == b && curx == x) {
            str[curpos] = '\0';
            return true;
        }
        else return false;
    }
    if ((cura == a || curb == b)&&curx==x) {
        if (cura == a) {
            for (int i = curpos; i < a + b; i++)str[i] = '1';
            str[a + b] = '\0';
            return true;
        }
        else {
            for (int i = curpos; i < a + b; i++)str[i] = '0';
            str[a + b] = '\0';
            return true;
        }
    }
    //Assume curpos==0
    str[curpos] = '0';
    bool flag = false;
    if (curpos == 0 || str[curpos - 1] == '0')flag = recusive(curpos + 1, cura + 1, curb, curx);
    else flag = recusive(curpos + 1, cura + 1, curb, curx + 1);
    if (flag)return true;
    str[curpos] = '1';
    if (curpos == 0 || str[curpos - 1] == '1')flag = recusive(curpos + 1, cura, curb + 1, curx);
    else flag = recusive(curpos + 1, cura, curb + 1, curx + 1);
    if (flag)return true;
    return false;
}
int main() {
    cin >> a >> b >> x;
    recusive(0, 0, 0, 0);
    cout << str;
}

第二版:递推。没有任何优化,时间够了,但是内存不够MLE了。四个维度分别是a,b,x,上个字符串的最后一个数字是0还是1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int a, b, x;
string arr[101][101][201][2]; //a,b,x,
int main() {
    cin >> a >> b >> x;
    for (int i = 1; i <= a; i++)arr[i][0][0][0] = arr[i - 1][0][0][0] + '0';
    for (int i = 1; i <= b; i++)arr[0][i][0][1] = arr[0][i - 1][0][1] + '1';
    for (int k = 1; k <= x; k++) { //curx
        for (int i = 1; i <= a; i++) { //cura
            for (int j = 1; j <= b; j++) { //curb
                //Assume to place a 0
                if (arr[i - 1][j][k - 1][1] != "")arr[i][j][k][0] = arr[i - 1][j][k - 1][1] + '0';
                else if (arr[i - 1][j][k][0] != "")arr[i][j][k][0] = arr[i - 1][j][k][0] + '0';
                //Assume to place a 1
                if (arr[i][j - 1][k - 1][0] != "")arr[i][j][k][1] = arr[i][j - 1][k - 1][0] + '1';
                else if (arr[i][j - 1][k][1] != "")arr[i][j][k][1] = arr[i][j - 1][k][1] + '1';
            }
        }
    }
    if (arr[a][b][x][0] != "")cout << arr[a][b][x][0];
    else cout << arr[a][b][x][1];
}

第三版:递推+滚动数组。把第三维由201优化到只剩2。因为动规的转移方程里面只需要上一个k和当前k的数组,所以滚动数组优化一下就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int a, b, x;
string arr[101][101][2][2];
inline int trans(int num) {
    if (num % 2 == 0)return 0;
    else return 1;
}
int main() {
    cin >> a >> b >> x;
    for (int i = 1; i <= a; i++)arr[i][0][0][0] = arr[i - 1][0][0][0] + '0';
    for (int i = 1; i <= b; i++)arr[0][i][0][1] = arr[0][i - 1][0][1] + '1';
    for (int k = 1; k <= x; k++) { //curx
        for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)for(int m=0;m<=1;m++)arr[i][j][trans(k)][m]=""; //Clean the rolling array to prevent unexpected error
        for (int i = 1; i <= a; i++) { //cura
            for (int j = 1; j <= b; j++) { //curb
                //Assume to place a 0
                if (arr[i - 1][j][trans(k - 1)][1] != "")arr[i][j][trans(k)][0] = arr[i - 1][j][trans(k - 1)][1] + '0';
                else if (arr[i - 1][j][trans(k)][0] != "")arr[i][j][trans(k)][0] = arr[i - 1][j][trans(k)][0] + '0';
                else arr[i][j][trans(k)][0]="";
                //Assume to place a 1
                if (arr[i][j - 1][trans(k - 1)][0] != "")arr[i][j][trans(k)][1] = arr[i][j - 1][trans(k - 1)][0] + '1';
                else if (arr[i][j - 1][trans(k)][1] != "")arr[i][j][trans(k)][1] = arr[i][j - 1][trans(k)][1] + '1';
                else arr[i][j][trans(k)][1]="";
            }
        }
    }
    if (arr[a][b][trans(x)][0] != "")cout << arr[a][b][trans(x)][0];
    else cout << arr[a][b][trans(x)][1];
}

写了我三个小时,也是挺不容易的……继续努力!写的不清楚有问题可以在下面评论问。

NOIP2017 普及组第三道 棋盘

这题写的异常难受……先想着用动态规划,难受死了,才20分。然后后来再看题解,用记忆化BFS,写的也难受,主要是太难想,终于AC了。开心~

写了有6、7个钟头吧。挺羞愧的。。。我写这种题怎么能这么长时间呢……

所有测试点全部0ms。

成就感极高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<memory.h>
#include<queue>
using namespace std;
struct qs { //Convenient for passing parameters
    int tx, ty, os, rs, sc; //destination's coordinate (x,y) :tx,ty ;previous point::original status of color,real status of color :os,rs ;previous point's score:sc.
    qs(int tx1, int ty1, int os1, int rs1, int sc1) {
        tx = tx1; ty = ty1; os = os1; rs = rs1; sc = sc1;
    } //the init of struct
};
int m, n;
int arr[105][105], f[105][105]; //arr stores the color(status) of all coordinate; f stores the least gold the person will spend
int shiftx[4] = { 1,-1,0,0 }, shifty[4] = { 0,0,1,-1 }; //shifts for the coordinate
queue<qs> q;
void execute(qs o) {
    //Calculate New Score
    //Compare Which one is smaller
    //Only when the new one is smaller one,will the program insert the queue
    int nscore = 0x7fffffff;
    if (o.rs != -1 && arr[o.tx][o.ty] != -1) { // C2C(R2R/Y2Y/R2Y/Y2R) {"C":"Color","2":"To","R":"Red","Y":"Yellow"};
        if (o.rs == arr[o.tx][o.ty])nscore = o.sc; // R2R/Y2Y
        else nscore = o.sc + 1; // R2Y/T2R
        if (nscore < f[o.tx][o.ty] || o.tx==1&&o.ty==1) { //o.tx==1&&o.ty==1 is to create an entrance for the inital queue push
            f[o.tx][o.ty] = nscore;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], arr[o.tx][o.ty], arr[o.tx][o.ty], nscore));
        }
    }
    else if (o.os != -1 && arr[o.tx][o.ty] == -1) { // C2N
        if (o.os == 0 && o.sc + 2 < f[o.tx][o.ty]) { //Assume that the temporary color of current cell is Red
            f[o.tx][o.ty] = nscore = o.sc + 2;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 0, nscore));
            nscore += 1;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 1, nscore));
        }
        else if (o.os == 1 && o.sc + 2 < f[o.tx][o.ty]) { //Assume that the temporary color of current cell is Yellow
            f[o.tx][o.ty] = nscore = o.sc + 2;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 1, nscore));
            nscore += 1;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 0, nscore));
        }
    }
}
int main() {
    memset(arr, -1, sizeof(arr));
    memset(f, 0x7f, sizeof(f));
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        arr[x][y] = c;
    }
    f[1][1] = 0;
    q.push(qs(1, 1, arr[1][1], arr[1][1], 0));
    while (!q.empty()) {
        qs cur = q.front();
        q.pop();
        if (cur.tx > m || cur.ty > m || cur.tx < 1 || cur.ty < 1)continue;
        execute(cur);
    }
    cout << (f[m][m] == 0x7f7f7f7f ? -1 : f[m][m]) << endl;
}