UOJ Logo z2512690268的博客

博客

标签

学弟学妹也可加我啊

2020-12-04 22:47:33 By z2512690268

学弟学妹们好啊!!!!

我是17级OIer张柯尧,现在在浙江大学读计算机大一。

从两年前退役以来,居然这么久才想起来到lfyzoj 逛逛,实在是羞愧难当。

但不管怎么说,很高兴能看到lfyzoj还在继续正常运行。

发这个贴子主要是捞一捞人,各位学弟学妹如果遇到什么问题的话可以喊我,我可以尽力提供一些帮助。

我的QQ:2512690268。

另外我当初的博客园里写的一些模板和题解还在,学弟学妹们可以去看看。https://www.cnblogs.com/junk-yao-blog/

欢迎骚扰!!!!

小A的题解(高一考试T4题解)

2018-08-28 12:00:01 By z2512690268

小A是很守信用滴!为了感谢你的帮助,他决定将“secret”的题解通过z2512690268的账号发到博客里。

算法一

最简单的搜索与回溯,看一眼就应该有的想法,良心出题人实力送分。预期得分:50~70分(不像T5的某人,出的题用暴力只给40。。。至于正解,我坚决怀疑你们没学!!!)

dfs_without_optimize.cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1100;
int n, money, val[maxn], cost[maxn], ans;
void dfs(int x, int pay, int gain){
    if(pay > money)    return ;
    if(x == n + 1){
        ans = max(ans, gain);
        return ;
    }
    dfs(x + 1, pay + cost[x], gain + val[x]);
    dfs(x + 1, pay, gain);
}
int main(void){
//    freopen("secret.in", "r", stdin);
//    freopen("secret.out", "w", stdout);
    scanf("%d%d", &n, &money);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", val + i, cost + i);
    dfs(1, 0, 0);
    printf("%d\n", ans);
}

算法二

不加优化的dfs不是好暴力!可以观察算法一中的剪枝条件(pay>money),可以发现,只要让pay超过money更早,就可以裁剪大量分支,起到更好的剪枝效果。而pay是已选择的文件的总花费时间,要令它尽量变大,就要让程序先选择耗时较多的文件,改变搜索顺序,效率可以得到很大提高,可以A过这道题。预期得分:100分

dfs_with_optimize.cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1100;
int n, money, ans;
struct sec{
    int val;
    int cost;
}secs[maxn];
bool cmp(const sec& A, const sec& B){
    return A.cost > B.cost;
}
void dfs(int x, int pay, int gain){
    if(pay > money)    return ;
    if(x == n + 1){
        ans = max(ans, gain);
        return ;
    }
    dfs(x + 1, pay + secs[x].cost, gain + secs[x].val);
    dfs(x + 1, pay, gain);
}
int main(void){
//    freopen("secret.in", "r", stdin);
//    freopen("secret.out", "w", stdout);
    scanf("%d%d", &n, &money);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", &secs[i].val, &secs[i].cost);
    sort(secs + 1, secs + n + 1, cmp);
    dfs(1, 0, 0);
    printf("%d\n", ans);
}

算法三

超前学习的同学们有福了,赤果果的背包dp有木有!如果你会背包,这道题送分没毛病。预期得分100分

dp.cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1100;
const int maxm = 500010;
int n, money, val[maxn], cost[maxn], dp[maxm];
void DP(){
    for(int i = 1; i <= n; ++i)
        for(int j = money; j >= cost[i]; --j)
            dp[j] = max(dp[j], dp[j - cost[i]] + val[i]);
}
int main(void){
//    freopen("secret.in", "r", stdin);
//    freopen("secret.out", "w", stdout);
    scanf("%d%d", &n, &money);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", val + i, cost + i);
    DP();    
    printf("%d\n", dp[money]);
}

算法四

虽说算法二成功AC了,但我们发现它的耗时是算法3的70倍!这在数据较大时是简直无法忍受的。因此,我们要考虑考虑更多的剪枝条件。我们考虑搜索到第x个的情况,如果我们已经预处理出了从第x个到最后一个文件中价值最大的一个的价值,那么如果我们将后面的所有文件都用最大价值取得还没有超过当前已经搜索到的最大值,再搜索下去就没有任何意义了,也就是说,一旦出现这种情况立刻返回上一层,就能够节省大量的无用功,加快速度。这样优化后,用时就只有dp的三到四倍了。

dfs_with_more_optimize.cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 35;
int n, money, ans, maxx[maxn], minn[maxn];
struct sec{
    int val;
    int cost;
}secs[maxn];
bool cmp(const sec& A, const sec& B){
    return A.cost > B.cost;
}
void dfs(int x, int pay, int gain){
    if(pay > money)    return ;
    if(gain + maxx[x] * (n - x + 1) <= ans)            return ;
    if(x == n + 1){
        ans = max(ans, gain);
        return ;
    }
    dfs(x + 1, pay + secs[x].cost, gain + secs[x].val);
    dfs(x + 1, pay, gain);
}
int main(void){
//    freopen("secret.in", "r", stdin);
//    freopen("secret.out", "w", stdout);
    scanf("%d%d", &n, &money);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", &secs[i].val, &secs[i].cost);
    sort(secs + 1, secs + n + 1, cmp);
    for(int i = n; i >= 1; --i)
        maxx[i] = max(secs[i].val, maxx[i + 1]);
    dfs(1, 0, 0);
    printf("%d\n", ans);
}

算法5~正无穷

其实深搜还有几种优化的方法在这篇题解里就不再赘述了。要知道,dfs优化的方法是十分灵活而种类繁多的,通过大量做题与学习还有更多的剪枝技巧可以用在这道题上。所以说,不会算法并不一定解决不了问题,只要善于剪枝,暴力也能轻松AC。

最后附上数据生成器,大家自己探索更优的dfs优化或其他算法吧。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
int main(void){
    freopen("secret.in", "w", stdout);
    long long n = 30;
    cout << n << " ";
    srand(time(NULL));
    cout << rand() * (n >> 1) << endl;
    for(int i = 1; i <= n; ++i)
        cout << rand() << " " << rand() << endl;
}

#210 最短路径问题显示路径方法

2018-05-10 17:57:35 By z2512690268

这道题显然是上周老师讲课时提到的问题,当时由于时间问题老师没来得及讲清显示最短路径的方法。 对于这个问题,我的思路是在主函数中输出开头和结尾的节点,而由递归遍历中间节点,因为在路径数组中存储着路径中任意两点间的中间节点,而除首尾节点外其余节点均可通过遍历中间节点输出,故只需单独输出首位节点即可解决问题; 也就是像下面这样的:

        void showpath(int a, int b){
        if(path[a][b]){
            showpath(a, path[a][b]);
            cout << path[a][b] << " ";
            showpath(path[a][b], b);
        }
      }

主函数里是这样的:


       cout << l <<" ";//l是起点;

        showpath(l, p);

        cout << p << endl;//p是终点;

全部代码如下:

     #include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    struct VV{
        int x;
        int y;
    }v[110];
    int k, path[110][110];
    double g[110][110];
     void showpath(int a, int b);
    int main(){
        int n, m;
        cin >> n;
        for(int i=1; i<=n; i++)    cin >> v[i].x >> v[i].y;
        cin >> m;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++)
                g[i][j]=99999999;
            g[i][i]=0;
        }
        for(int i=1; i<=m; i++){
            int a, b;
            cin >> a >> b;
            g[a][b]=g[b][a]=hypot(v[a].x-v[b].x, v[a].y-v[b].y);
        }
        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    if(g[i][k]+g[k][j]<g[i][j]){
                         g[i][j]=g[i][k]+g[k][j];
                        path[i][j]=k;
                    }
        int l, p;
        cin >> l >> p;
        printf("%.2lf\n", g[l][p]);
        cout << l <<" ";
        showpath(l, p);
        cout << p << endl;
        return 0;
    }
    void showpath(int a, int b){
        if(path[a][b]){
            showpath(a, path[a][b]);
            cout << path[a][b] << " ";
            showpath(path[a][b], b);
        }
    }

最后附上个人测试时的数据(虽然是胡编的):

INPUT

10
0 0
2 2
4 4
6 6 
8 8
1 1
3 3
5 5
7 7
9 9

9
1 6
6 2
2 7
7 3
3 8
8 4
4 9
9 5
5 10

1 10

OUTPUT

12.73
1 6 2 7 3 8 4 9 5 10

显然是成立的

#98 求这个错误的解释

2018-03-14 18:28:49 By z2512690268

问题描述在注释里 代码如下:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
int cnt=0;
int num[50];
int sum[1010];
int mitime=0x7fffffff;
void ans(int k=1, int masum=0)
{
    if(masum>mitime)/*此处若改为masum>=mitime,问题解决,否则会有某些数据出现死循环,只能过80,为什么?*/
        return ;
    if(k==n+1)
    {
        if(masum<mitime)
            mitime=masum;
        return ;
    }
    for(int i=1; i<=m; i++)
    {
        if(sum[i]+num[k]<mitime)
        {
            sum[i]+=num[k];
            ans(k+1, max(masum, sum[i]));
            sum[i]-=num[k];
        }
    }
}
bool cmp(int a, int b)
{
    return a>b;
}
int main(void)
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        scanf("%d", &num[i]);
    sort(num+1, num+n+1,cmp);
    ans();
    cout << mitime << endl;
}
共 4 篇博客