洛谷 金明的预算方案

发表评论

题号：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_;
}

20180730更新：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<functional>
using namespace std;
int r,c;
int arr[105][105];
int f[105][105];
struct node{
    int x,y;
    int v;
    bool operator < (const node& n2){
        return v<n2.v;
    }
}narr[10005];
int narrptr=0;
int main() {
    ios::sync_with_stdio(false);
    memset(arr,0x7f,sizeof(arr));
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>arr[i][j];
            narr[++narrptr].v=arr[i][j];
            narr[narrptr].x=i;
            narr[narrptr].y=j;
        }
    }
    sort(narr+1,narr+r*c+1);
    for(int i=1;i<=narrptr;i++){
        if(narr[i].v>arr[narr[i].x-1][narr[i].y])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x-1][narr[i].y]+1);
        if(narr[i].v>arr[narr[i].x+1][narr[i].y])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x+1][narr[i].y]+1);
        if(narr[i].v>arr[narr[i].x][narr[i].y-1])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x][narr[i].y-1]+1);
        if(narr[i].v>arr[narr[i].x][narr[i].y+1])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x][narr[i].y+1]+1);
    }
    int mmax=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            mmax=max(mmax,f[i][j]);
        }
    }
    cout<<mmax+1;
}

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

20180730更新：都忘了杨辉三角了……

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,sum;
bool visited[15];
int ansarr[15];
int triangle[15][15];
void triangle_init(){
    for(int i=0;i<15;i++){
        triangle[i][0]=1;
        triangle[i][i]=1;  
    }
    for(int i=2;i<15;i++){
        for(int j=1;j<i;j++){
            triangle[i][j]=triangle[i-1][j]+triangle[i-1][j-1];
        }
    }
}
bool dfs(int pos,int s){
    if(pos==n+1)return s==sum;
    if(s>sum)return false;
    for(int i=1;i<=n;i++){
        if(visited[i])continue;
        visited[i]=true;
        ansarr[pos]=i;
        if(dfs(pos+1,s+i*triangle[n-1][pos-1]))return true;
        visited[i]=false;
    }
    return false;
}
int main() {
    triangle_init();
    cin>>n>>sum;
    if(dfs(1,0))for(int i=1;i<=n;i++)cout<<ansarr[i]<<" ";
}

洛谷 拼数

发表评论

题号：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

数据结构 邓俊辉 PA#4 循环移位(Cycle) 题解

发表评论

循环移位(Cycle)

Description

Cycle shifting refers to following operation on the sting. Moving first letter to the end and keeping rest part of the string. For example, apply cycle shifting on ABCD will generate BCDA. Given any two strings, to judge if arbitrary times of cycle shifting on one string can generate the other one.

Input

There m lines in the input, while each one consists of two strings separated by space. Each string only contains uppercase letter ‘A’~’Z’.

Output

For each line in input, output YES in case one string can be transformed into the other by cycle shifting, otherwise output NO.

Example

Input

AACD CDAA
ABCDEFG EFGABCD
ABCD ACBD
ABCDEFEG ABCDEE

Output

YES
YES
NO
NO

Restrictions

0 <= m <= 5000

1 <= |S1|, |S2| <= 10^5

Time: 2 sec

Memory: 256 MB

描述

所谓循环移位是指。一个字符串的首字母移到末尾, 其他字符的次序保持不变。比如ABCD经过一次循环移位后变成BCDA

给定两个字符串，判断它们是不是可以通过若干次循环移位得到彼此

输入

由m行组成，每行包含两个由大写字母’A’~’Z’组成的字符串，中间由空格隔开

输出

对于每行输入，输出这两个字符串是否可以通过循环移位得到彼此：YES表示是，NO表示否

样例

见英文题面

限制

0 ≤ m ≤ 5000

1 ≤ |S1|, |S2| ≤ 10^5

时间：2 sec

内存：256 MB

开心死啦！本来就觉得这道题必须写KMP来着，结果搞了个c++stl糊弄过去了……还好THUOJ没有删掉头文件 /笑，倒是其他的map list queue还有什么 algorithm 都删啦！ /偷笑 /捂脸
继续阅读 →

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

继续阅读 →