特色文章

随笔

心里好累,今天也快期末考试了。今天2016年12月30日。放3天假。我决定以后每周五都刷1个小时的OJ。写此随笔立誓!
计划:阅读刘汝佳的教材,一点一滴从第一章开始做习题。
希望一年后的NOIP能拿到一等奖!

洛谷 金明的预算方案

题号:P1064
一维滚动数组优化。

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,m;
int v[65],p[65],q[65],w[65];
int q1[65],q2[65];
int iptr;
int f[35000];
void insert_subgood(int main,int sub){
    if(q1[main]==0)q1[main]=sub;
    else q2[main]=sub;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>v[i]>>p[i]>>q[i];
        w[i]=v[i]*p[i];
        if(q[i]!=0){
            insert_subgood(q[i],i);
        }
    }
    for(int i=1;i<=m;i++){
        if(q[i]!=0)continue;
        for(int j=n;j>=0;j--){
            if(j-v[i]>=0)
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            if(q1[i]!=0&&j-v[i]-v[q1[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q1[i]]]+w[i]+w[q1[i]]);
            if(q2[i]!=0&&j-v[i]-v[q2[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q2[i]]]+w[i]+w[q2[i]]);
            if(q1[i]!=0&&q2[i]!=0&&j-v[i]-v[q1[i]]-v[q2[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q1[i]]-v[q2[i]]]+w[i]+w[q1[i]]+w[q2[i]]);
        }
    }
    cout<<f[n];
}

洛谷 八皇后

题号1219

感觉写的非常满意……哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
n=13都不用打表啦!

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<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n;
int cnt;//情况计数器
bool line[14],row[14],left_diagonal[26],right_diagonal[26];
//占用情况数组:行;列;左上-右下对角线;右上-左下对角线
int pos[14];
//记录每一行的棋子放在哪一列
inline int calculate_left_dia(int x,int y){//计算x行y列的棋子在第几个左上-右下对角线上
    return x+y-1;
}
inline int calculate_right_dia(int x,int y){//计算x行y列的棋子在第几个右上-左下对角线上
    return (n+1-x)+y-1;
}
void search(int level){//dfs搜索:行
    if(level==n+1){//递归基
        cnt++;
        if(cnt>3)return;
        for(int i=1;i<=n;i++){//输出结果
            cout<<pos[i]<<" ";
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++){//遍历列
        if(!line[i]&&!row[i]&&!left_diagonal[calculate_left_dia(level,i)]&&!right_diagonal[calculate_right_dia(level,i)]){//满足要求
            pos[level]=i;
            line[i]=true;row[i]=true;
            left_diagonal[calculate_left_dia(level,i)]=true;
            right_diagonal[calculate_right_dia(level,i)]=true;
            search(level+1);//继续深搜
            line[i]=false;row[i]=false;//回溯
            left_diagonal[calculate_left_dia(level,i)]=false;
            right_diagonal[calculate_right_dia(level,i)]=false;
        }
    }
}
int main(){
    cin>>n;
    search(1);
    cout<<cnt;
}

洛谷 滑雪(重要!)

题号:P1434
这道题需要留着细细品味……
这道题也挺恶心,用尽各种优化方法……
需要写一下注释,省得我以后看不懂自己写的代码……

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int array[105][105];
int memory[105][105];
bool check[105][105];
struct s{
    int x,y,n;
    bool operator < (s& s2){
        return this->n>s2.n;
    }
}ss[11025];
int r,c;
int shift_x[5]={0,-1,1,0,0},shift_y[5]={0,0,0,-1,1};//left,right,up,down
int safe_array(int x,int y){
    if(x>=1&&x<=r&&y>=1&&y<=c)return array[x][y];
    else return -1;
}//保证数组不越界
int dfs(int x,int y,int last){//dfs是从截止点step为0推到起始点的
    if(safe_array(x,y)==-1||last<=array[x][y]||check[x][y])return 0;
    if(memory[x][y]!=-1)return memory[x][y];
    check[x][y]=true;
    int max_=-1;
    for(int i=1;i<=4;i++){
        int t=dfs(x+shift_x[i],y+shift_y[i],array[x][y]);
        if(t>max_)max_=t;
    }
    check[x][y]=false;
    return memory[x][y]=max_+1;
}
int main(){
    memset(memory,-1,sizeof(memory));
    cin>>r>>c;
    int ptr=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>array[i][j];
            ss[ptr].x=i;
            ss[ptr].y=j;
            ss[ptr].n=array[i][j];
            ptr++;
        }
    }
    int max_=-1;
    sort(ss,ss+ptr);//先排序,由坡高到坡低去进行dfs,这样坡低的在刚一开始就会因为记忆化搜索直接return
    for(int i=0;i<ptr;i++){
        int t=dfs(ss[i].x,ss[i].y,ss[i].n+1);
        if(t>max_)max_=t;//收集最长路径
    }
    cout<<max_;
}

洛谷 [USACO06FEB]数字三角形Backward Digit Su…

题号:P1118

必须用杨辉三角/组合数的方法做,同时要剪枝……这样才能A。不用这个只能60,剩下的全部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
43
44
45
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n,sum;
bool check[13];
int current[13];
int current_temp[13];
int yanghui[13];
int calculate(int k){
    int sum=0;
    for(int i=0;i<k;i++){
        sum+=yanghui[i]*current[i];
    }
    return sum;
}
void search(int level){
    if(level==n&&calculate(n)==sum){
        for(int i=0;i<n;i++){
            cout<<current[i]<<" ";
        }
        exit(0);
    }
    for(int i=1;i<=n;i++){
        if(!check[i]){
            check[i]=true;
            current[level]=i;
            if(calculate(level)<sum)search(level+1);
            check[i]=false;
        }
    }
}
int main(){
    memset(check,false,sizeof(check));
    cin>>n>>sum;
    //calculate yanghui
    yanghui[0]=1;
    for(int i=1;i<n;i++){
        yanghui[i]=(n-i)*yanghui[i-1]/i;
    }
    //end calculate
    search(0);
}

洛谷 拼数

题号:1012

这题也挺逗的,没有想到能这么做……
看了别人的题解……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
bool cmp(string & s1,string & s2){
    return s1+s2>s2+s1;
}
int main(){
    int n;
    cin>>n;
    string s[20];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++){
        cout<<s[i];
    }
}

洛谷 均分纸牌

题号:1031

参考某大神的题解,受了点启发,想了个思路,有可能是和别人是重的,但我还是说一下,毕竟别人的不是特别好懂。

首先读入数据,计算出每个堆上应有的平均分配之后的值。既然最终的目的是要求所有堆都统一为平均值,那我就先不管后面的,先把现在的当前堆管好再说。利用贪心的想法,从左向右遍历,当前堆上的牌数小于平均值就从右面一个堆往过要,大于平均值就把多的全部扔给右面一个堆。过程中有可能出现负数,但是最后肯定是会回到正常的状态。每个堆上的牌至多主动挪出一次,是符合题目要求的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main(){
    int n,arr[101],sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        sum+=arr[i];
    }
    int avg=sum/n;
    int step=0;
    for(int i=1;i<n;i++){
        if(arr[i]<avg){
            step++;
            arr[i+1]-=avg-arr[i];
        }else if(arr[i]>avg){
            step++;
            arr[i+1]+=arr[i]-avg;
        }
    }
    cout<<step;
}

永远的追忆与思念

配乐:徐梦圆 China-X

剪不断,理还乱,是离愁。别是一般滋味在心头。——题记
前几天,我才刚刚知道,下学期,白老师要离我们而去,前往新疆进行一年的支教活动。虽说这直到现在还是一条保密的消息,但我还是通过各种渠道提前得知了。
听到这条消息,我的第一反应就是:为什么要让这么好的白老师前去支教呢!随便让谁去不好呢?然而残酷的现实决定了学校不得不这样做:全校数学教研组,只有白老师一个人没有结婚。他便成了支教的最佳人选。
他是2015级13班的班主任老师,他自从我们进入潞河中学学习就一直教授我们数学。白老师的严厉是出了名的,全校同学一听到他的名字都会胆战心惊。正是因为他的严厉,我们每个同学才能够有动力取得长足的进步。同时,他也是爱我们的,为我们着想并且负责的老师。虽然他每次批评我们的语言都令我们难以接受,但是这也证明了他的心里有我们,时时刻刻的考虑着学生,而且这种语言还让我们有了极其强大的抗打击能力。
进入高中以来,我的各方面都有了极大的改变与进步。这很多都源于白老师的功劳。
我刚刚进去高中的时候,性格是十分内向的,不想也不会和别的同学多说话。13班也有一部分同学是这样。白老师就及时的提醒我们,注意多与别的同学进行沟通交流。现在,13班的每一个同学都能够算是活泼开朗,有一个属于自己的社交圈子。这都要归功于白老师。
还记得高一的数学课上,学习函数。高中数学中,最难的一个部分就是函数。难的我根本啥都听不懂,学不会。非常着急,脸色很难看。白老师在课堂上看到我脸色不好,就关心我,让我不要着急,下了课去办公室找他。到了办公室,白老师还没问什么,我就难受的哭了起来,说自己一点都跟不上,白老师也安慰我,而且还鼓励我,让我加油,说:‘多多练习总能跟得上的。’我很感激白老师对我的鼓励,直到现在我还仍旧记忆犹新。
除此之外,白老师一直所说的‘自主招生’也对我起了很大的作用。老师初次说自主招生怎样怎样我还不以为然,后来抱着“老师说的肯定没错的心态”停课三天,参加了一次信息学联赛,获得了一个省级二等奖,这着实让我高兴了好几天。到了后来,我才真正明白了自主招生的作用,不由得佩服白老师的远见。
除此之外,还有白老师说的提前在高二语文,英语背单词背课文等等,都绝对是极好的提议,但由于时间原因我并没有进行。我相信严格按照这个计划有的人一定会有很大的收获的。
只可惜这么好的白老师不能留在我们的身边,白老师走时,是高三上学期刚刚开学。支教一年回来,我们也就高中毕业了,这最后一年重要的时光,不能与白老师共享,实在是可惜!正如李煜所写的:剪不断,理还乱,是离愁。别是一般滋味在心头。
白老师给了我这么大的帮助,我生怕忘记了白老师,可是我又知道我是一定会忘记一些事情的,只祈求新的班主任来之后,我还能够记得白老师的好,永远不要忘记吧!
写于2017.04.16

Openjudge 画家问题

画家问题

总时间限制:
1000ms
内存限制:
65536kB
描述
有一个正方形的墙,由N*N个正方形的砖组成,其中一些砖是白色的,另外一些砖是黄色的。Bob是个画家,想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i, j)个位置的砖时, 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖,才能使所有砖的颜色都变成黄色。

输入
第一行是一个整数n (1≤n ≤15),表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖,“y”表示黄砖。
输出
一行,如果Bob能够将所有的砖都涂成黄色,则输出最少需要涂画的砖数,否则输出“inf”。
样例输入
5
wwwww
wwwww
wwwww
wwwww
wwwww
样例输出
15
来源
1681

继续阅读

Openjudge Calling Extraterrestrial Intelligence Again 题解

Calling Extraterrestrial Intelligence Again

总时间限制:
1000ms
内存限制:
65536kB
描述
A message from humans to extraterrestrial intelligence was sent through the Arecibo radio telescope in Puerto Rico on the afternoon of Saturday November 16, 1974. The message consisted of 1679 bits and was meant to be translated to a rectangular picture with 23 x 73 pixels. Since both 23 and 73 are prime numbers, 23 x 73 is the unique possible size of the translated rectangular picture each edge of which is longer than 1 pixel. Of course, there was no guarantee that the receivers would try to translate the message to a rectangular picture. Even if they would, they might put the pixels into the rectangle incorrectly. The senders of the Arecibo message were optimistic.

We are planning a similar project. Your task in the project is to find the most suitable width and height of the translated rectangular picture. The term “most suitable” is defined as follows. An integer m greater than 4 is given. A positive fraction a/b less than or equal to 1 is also given. The area of the picture should not be greater than m. Both of the width and the height of the translated picture should be prime numbers. The ratio of the width to the height should not be less than a/b nor greater than 1. You should maximize the area of the picture under these constraints.

In other words, you will receive an integer m and a fraction a/b. It holds that m > 4 and 0 < a/b <= 1. You should find the pair of prime numbers p, q such that pq <= m and a/b <= p/q <= 1, and furthermore, the product pq takes the maximum value among such pairs of two prime numbers. You should report p and q as the “most suitable” width and height of the translated picture.

输入
The input is a sequence of at most 2000 triplets of positive integers, delimited by a space character in between. Each line contains a single triplet. The sequence is followed by a triplet of zeros, 0 0 0, which indicates the end of the input and should not be treated as data to be processed.

The integers of each input triplet are the integer m, the numerator a, and the denominator b described above, in this order. You may assume 4 < m <= 100000 and 1 <= a <= b <= 1000.

输出
The output is a sequence of pairs of positive integers. The i-th output pair corresponds to the i-th input triplet. The integers of each output pair are the width p and the height q described above, in this order.

Each output line contains a single pair. A space character is put between the integers as a delimiter. No other characters should appear in the output.

样例输入
5 1 2
99999 999 999
1680 5 16
1970 1 1
2002 4 11
0 0 0
样例输出
2 2
313 313
23 73
43 43
37 53
来源
Japan 2002 Kanazawa

继续阅读