分类目录归档:搜索

洛谷 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;
}

洛谷 P1120 小木棍 [数据加强版]

写的很绝望……看了三遍所有题解仍然69……

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
#include<bits/stdc++.h>
using namespace std;
int n, sum = 0;
int lens[100] = { 0 };
bool visited[100] = { false };
int sums[100] = { 0 };
int o_min = 0, o_max;
vector<int> divisors;
int min_len;
inline bool dfs(int curpos, int curvalue, int groups){
    if (curvalue == min_len){
        if (groups == sum / min_len - 1)return true;
        else{
            int i;
            for (i = 1; i <= n; i++){
                if (!visited[i])break;
            }
            assert(i != n + 1);
            visited[i] = true;
            bool flag = dfs(i, lens[i], groups + 1);
            visited[i] = false;
            return flag;
        }
    }
    bool flag_finished = false;
    for (int i = curpos + 1; i <= n; i++){
        if (curvalue + lens[n] > min_len || curvalue + sums[i]<min_len)break;
        if (visited[i] || curvalue + lens[i] > min_len)continue;
        visited[i] = true;
        if (dfs(i, curvalue + lens[i], groups))flag_finished = true;
        visited[i] = false;
        if (flag_finished)return true;
        for (int j = i + 1; j <= n; j++){
            if (lens[j] != lens[i]){
                i = j - 1;
                break;
            }
        }
    }
    return false;
}
inline bool process(int min_length){
    min_len = min_length;
    visited[1] = true;
    bool flag = dfs(1, lens[1], 0);
    visited[1] = false;
    return flag;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> lens[i];
        if (lens[i] > 50){
            i--;
            n--;
        }
    }
    sort(lens + 1, lens + n + 1, greater<int>());
    for (int i = 1; i <= n; i++){
        o_min = max(o_min, lens[i]);
        sum += lens[i];
    }
    for (int i = n; i >= 1; i--){
        sums[i] = sums[i + 1] + lens[i];
    }
    o_max = sum;
    for (int i = o_min; i <= o_max / 2; i++){
        if (o_max%i == 0)divisors.push_back(i);
    }
    divisors.push_back(o_max);
    for (int i = 0; i < divisors.size(); i++){
        if (process(divisors[i])){
            cout << divisors[i];
            break;
        }
    }
}

20180811日更新:已经AC。
这题真的很麻烦,之前做过一回,69分放弃了,今天又重新做,改到了78AC22TLE,又看题解里的优化终于改到了AC。
题解:https://www.luogu.org/blog/complexity/solution-p1120
https://www.luogu.org/blog/cm-nanyi2018/solution-p1120
https://www.luogu.org/blog/ogawa/solution-p1120

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<vector>
#include<algorithm>
#include<cmath>
#include<functional>
using namespace std;
int n,lens[70],curLen,totSum=0;
int bucket[60],lst[60],lstPtr=0;
vector<int> possibleLen;
inline int check(){
    int i;
    for(i=1;i<=lstPtr;i++)if(bucket[lst[i]]!=0)return i;
    return i;
}
inline bool dfs(int lstPos,int len){//have already added lst[lstPos] before entering this recursive function
    if(len==totSum||len==totSum-curLen)return true;
    if(len%curLen==0){
        int i=check();
        bucket[lst[i]]--;
        bool flag=dfs(i,len+lst[i]);
        bucket[lst[i]]++;
        return flag;
    }
    int curRemain=curLen-len%curLen;
    for(int i=lstPos;i<=lstPtr;i++){
        if(lst[i]>curRemain||bucket[lst[i]]==0)continue;
        bucket[lst[i]]--;
        if(dfs(i,len+lst[i])){
            bucket[lst[i]]++;
            return true;
        }
        bucket[lst[i]]++;
        if(curRemain==lst[i])return false;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    int maxV=0;
    for(int i=1;i<=n;i++){
        cin>>lens[i];
        if(lens[i]>50){
            i--;n--;
            continue;
        }
        bucket[lens[i]]++;
        maxV=max(maxV,lens[i]);
    }
    for(int i=50;i>=1;i--)if(bucket[i]!=0)lst[++lstPtr]=i;
    for(int i=1;i<=n;i++)totSum+=lens[i];
    for(int i=maxV;i<=totSum/2;i++)if(totSum%i==0)possibleLen.push_back(i);
    possibleLen.push_back(totSum);
    bucket[lst[1]]--;
    for(int i=0;i<possibleLen.size();i++){
        curLen=possibleLen[i];
        if(dfs(1,lst[1])){
            cout<<curLen;
            return 0;
        }
    }
}

洛谷10月月赛R1·浴谷八连测R1·提高组 SAC E#1 – 一道大水题 Knight

洛谷题号:P3930
2017.10.20更新:
有人在洛谷上指出了本程序的错误:测试样例:
5
….X
…..
…..
….B
..O..
存在一种4步的解法。
….4
…..
…3.
….1
..2..
但程序会输出-1。
经过检查,所给出的测试样例中四步解法经过了之前已经经过的点,这种情况是我的程序所无法处理的。因此我的程序存在漏洞,目前还没有想到什么好办法解决。。
原文章:
本来没想着这题能得分,结果这题月赛时竟然80分,后来出题人说有两个点错了,重测就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
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
int n;
char arr[60][60]; //存放棋子
bool attack[2][60][60]; //某点是否可以被攻击(第一维没有用处,只用了第一维的1)
int dp[60][60];
int O_x, O_y, X_x_pos, X_y_pos;
int K_x[8] = {1,2,2,1,-1,-2,-2,-1};
int K_y[8] = {2,1,-1,-2,-2,-1,1,2};
int X_x[8] = {-1,0,1,-1,1,-1,0,1};
int X_y[8] = {-1,-1,-1,0,0,1,1,1};
inline void render(int x, int y, int no){ //针对坐标为(x,y)的棋子在attack数组中绘制出攻击范围
    switch (arr[x][y]){
    case 'C'://城堡
        for (int i = x + 1; i <= n; i++){
            if (arr[i][y] == '.')attack[no][i][y] = true;
            else {
                attack[no][i][y] = true;
                break;
            }
        }
        for (int i = x - 1; i >= 1; i--){
            if (arr[i][y] == '.')attack[no][i][y] = true;
            else {
                attack[no][i][y] = true;
                break;
            }
        }
        for (int i = y + 1; i <= n; i++){
            if (arr[x][i] == '.')attack[no][x][i] = true;
            else {
                attack[no][x][i] = true;
                break;
            }
        }
        for (int i = y - 1; i >= 1; i--){
            if (arr[x][i] == '.')attack[no][x][i] = true;
            else {
                attack[no][x][i] = true;
                break;
            }
        }
        break;
    case 'K'://骑士
        for (int i = 0; i < 8; i++){
            if (x + K_x[i]>0 && x + K_x[i] <= n&&y + K_y[i] > 0 && y + K_y[i] <= n){
                attack[no][x + K_x[i]][y + K_y[i]] = true;
            }
        }
        break;
    case 'B'://主教
        for (int i = 1; y - i > 0 && x + i <= n; i++){//向右上角移动
            if (arr[x + i][y - i] == '.')attack[no][x + i][y - i] = true;
            else {
                attack[no][x + i][y - i] = true;
                break;
            }
        }
        for (int i = 1; y + i <= n && x + i <= n; i++){//向右下角移动
            if (arr[x + i][y + i] == '.')attack[no][x + i][y + i] = true;
            else{
                attack[no][x + i][y + i] = true;
                break;
            }
        }
        for (int i = 1; y + i <= n && x - i > 0; i++){//向左下角移动
            if (arr[x - i][y + i] == '.')attack[no][x - i][y + i] = true;
            else{
                attack[no][x - i][y + i] = true;
                break;
            }
        }
        for (int i = 1; y - i > 0 && x - i > 0; i++){//向左上角移动
            if (arr[x - i][y - i] == '.')attack[no][x - i][y - i] = true;
            else{
                attack[no][x - i][y - i] = true;
                break;
            }
        }
        break;
    case 'Q'://皇后
        //城堡
        for (int i = x + 1; i <= n; i++){
            if (arr[i][y] == '.')attack[no][i][y] = true;
            else {
                attack[no][i][y] = true;
                break;
            }
        }
        for (int i = x - 1; i >= 1; i--){
            if (arr[i][y] == '.')attack[no][i][y] = true;
            else {
                attack[no][i][y] = true;
                break;
            }
        }
        for (int i = y + 1; i <= n; i++){
            if (arr[x][i] == '.')attack[no][x][i] = true;
            else {
                attack[no][x][i] = true;
                break;
            }
        }
        for (int i = y - 1; i >= 1; i--){
            if (arr[x][i] == '.')attack[no][x][i] = true;
            else {
                attack[no][x][i] = true;
                break;
            }
        }
        //主教
        for (int i = 1; y - i > 0 && x + i <= n; i++){//向右上角移动
            if (arr[x + i][y - i] == '.')attack[no][x + i][y - i] = true;
            else {
                attack[no][x + i][y - i] = true;
                break;
            }
        }
        for (int i = 1; y + i <= n && x + i <= n; i++){//向右下角移动
            if (arr[x + i][y + i] == '.')attack[no][x + i][y + i] = true;
            else{
                attack[no][x + i][y + i] = true;
                break;
            }
        }
        for (int i = 1; y + i <= n && x - i > 0; i++){//向左下角移动
            if (arr[x - i][y + i] == '.')attack[no][x - i][y + i] = true;
            else{
                attack[no][x - i][y + i] = true;
                break;
            }
        }
        for (int i = 1; y - i > 0 && x - i > 0; i++){//向左上角移动
            if (arr[x - i][y - i] == '.')attack[no][x - i][y - i] = true;
            else{
                attack[no][x - i][y - i] = true;
                break;
            }
        }
        break;
    case 'X'://国王
        for (int i = 0; i < 8; i++){
            if (x + X_x[i]>0 && x + X_x[i] <= n&&y + X_y[i] > 0 && y + X_y[i] <= n){
                attack[no][x + X_x[i]][y + X_y[i]] = true;
            }
        }
        break;
    case 'P'://普通士兵
        if (x - 1 > 0 && x - 1 <= n&&y + 1 > 0 && y + 1 <= n){
            attack[no][x - 1][y + 1] = true;
        }
        if (x + 1 > 0 && x + 1 <= n&&y + 1 > 0 && y + 1 <= n){
            attack[no][x + 1][y + 1] = true;
        }
        break;
    }
}
inline void render_all(){//将地图上的所有点全部重绘
    memset(attack, false, sizeof(attack));
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            switch (arr[i][j]){
            case 'O'://标记好白骑士的起始点
                O_x = i;
                O_y = j;
                break;
            case '.':
            case '\0':
                break;
            case 'X'://黑国王的终止点
                X_x_pos = i;
                X_y_pos = j;
            default:
                render(i, j, 1);
            }
        }
    }
}
void dfs(int x, int y,int step){//记忆化dfs
    if (x <= 0 || y <= 0 || x > n || y > n)return; //超出边界的情况
    if (arr[x][y] == 'X'){ //dfs到了黑国王
        if (step < dp[x][y])dp[x][y] = step;
        return;
    }
    if (attack[1][x][y])return; //刚跳到坐标x,y就被攻击了
    if (step>=dp[x][y])return; //注意,这里是重点,也是为什么DFS不会超时的原因,因为我写的这个DFS记忆化不满足无后效性,所以只要走到一点后,当前步数大于之前走到过这里的最小步数就可以退出了。
    dp[x][y] = step;
    if (arr[x][y] != '.'){ //该格子上有棋子
        char ch = arr[x][y];
        arr[x][y] = '.';
        render_all(); //把棋子吃掉以后重新绘制攻击情况
        for (int i = 0; i < 8; i++){
            if (x + K_x[i]>0 && x + K_x[i] <= n&&y + K_y[i] > 0 && y + K_y[i] <= n){
                dfs(x + K_x[i], y + K_y[i], step + 1);
            }
        }
        arr[x][y] = ch; //回溯
        render_all();
    }
    else{ //该格子上无棋子
        for (int i = 0; i < 8; i++){
            if (x + K_x[i]>0 && x + K_x[i] <= n&&y + K_y[i] > 0 && y + K_y[i] <= n){
                dfs(x + K_x[i], y + K_y[i], step + 1);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false); //加快cin速度
    while (cin >> n){ //多组数据
        memset(arr, 0, sizeof(arr));
        memset(attack, false, sizeof(attack));
        memset(dp, 0x7f, sizeof(dp));
        for (int i = 1; i <= n; i++){
            cin >> arr[i] + 1;
        }
        render_all(); //先进行整幅地图攻击情况的绘制
        dfs(O_x, O_y, 0);
        if (dp[X_x_pos][X_y_pos] == 0x7f7f7f7f){
            cout << -1 << endl;
        }
        else{
            cout << dp[X_x_pos][X_y_pos] << endl;
        }
    }
    return 0;
}