套题T6

过节（festival.cpp/c/pas）

Dxy帮老师们过教师节的时候需要购买礼物。货架上有n 种礼物，每种礼物有不同的个数。每种礼物有价值和花费两种属性，帮他算出最大可以得到的价值。M是带的钱数有多少

Input:

第一行两个数n,m

第2到n+1行：每行三个数a,b,c，表示一种礼物的个数，花费和价值。

Output:

最大可得价值。

样例输入：

1 1

1 1 1

样例输出：

多重背包也可以拆开做01背包QAQ

背包教程百度背包九讲 || 阅读

http://transcoder.baidu.com/from=844b/bd_page_type=1/ssid=d6c350616c6164696e3130303130302d71/uid=0/pu=usm%401%2Csz%401320_1001%2Cta%40iphone_2_4.4_3_537/baiduid=864138CF7B44F345487B864DC214C0DF/w=0_10_/t=iphone/l=3/tc?ref=www_iphone&lid=1744986806270038500&order=2&fm=alop&tj=www_normal_2_0_10_title&vit=osres&m=8&srd=1&cltj=cloud_title&asres=1&title=%E8%83%8C%E5%8C%85%E4%B9%8B01%E8%83%8C%E5%8C%85%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85%E8%AF%A6%E8%A7%A3-Tan..._%E5%8D%9A%E5%AE%A2%E5%9B%AD&dict=30&w_qd=IlPT2AEptyoA_yk574oovA75HCdSjoS&sec=15106&di=95beeae6623de50a&bdenc=1&tch=124.0.0.0.0.0&nsrc=IlPT2AEptyoA_yixCFOxXnANedT62v3IEQGG_ytK1DK6mlrte4viZQRAVj06K7_dFEb7gTCcg2tSaC8hOnEobxB0r_x6sVsf8Gjb9fvtdhPsHBEZhgNmOhz_XC5o&eqid=18377041457812001000000157d3e2a9&wd=&clk_info=%7B%22srcid%22%3A%221599%22%2C%22tplname%22%3A%22www_normal%22%2C%22t%22%3A1473504051781%2C%22xpath%22%3A%22div-a-h3%22%7D

//楼上网址很长对吗我也觉得QAQ

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#define MOD 99999997

#define tips 100004

using namespace std;

int f[],n,m,cnt=;

int a[],b[];

int main()

{

    freopen("festival.in","r",stdin);freopen("festival.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&z,&y);

        for(int j=;j<=x;j++)a[++cnt]=y,b[cnt]=z;

    }

    for(int i=;i<=cnt;i++)

        for(int j=m;j>=a[i];j--)

            f[j]=max(f[j],f[j-a[i]]+b[i]);

    int ans=;

    for(int i=;i<=m;i++)ans=max(ans,f[i]);

    cout<<ans<<endl;

    fclose(stdin);fclose(stdout);

    return ;

}

搞成01背包

a*b(mod.cpp/c/pas)

没错dxy的题目就是这么简单。

输入：

第一行一个数t，表示有t个数据

第2到第t+1行，每行三个正整数a,b,c （a,b,c<=10^18）

输出：对于每组数据输出（a*b）%c

样例输入：

1 2 3

样例输出：

思想大概就是把两个数分成几个数的和然后就能乘了

压行写的话三行搞定QAQ

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn

using namespace std;

int n;

long long mul(long long a, long long b, long long p)

{ // a * b % p;

    long long ret = ;

    for (int i = ; ~ i; -- i)//~ >=0

    ret = (ret + ret) % p, b & (1ll << i) ? ret = (ret + a) % p : ;

    return ret % p;

}

int main()

{

    freopen("mod.in","r",stdin);

    freopen("mod.out","w",stdout);

    cin>>n;

    long long a,b,c;

    for(int i=;i<=n;++i)

    {

        scanf("%lld%lld%lld",&a,&b,&c);

        printf("%lld",mul(a,b,c));

        puts("");

    }

    fclose(stdin);fclose(stdout);

    return ;

}

%%%YJL

扫描(scan.cpp/c/pas)

【题目描述】

有一个 1 ∗ n 的矩阵，有 n 个正整数。

现在给你一个可以盖住连续的 k 的数的木板。

一开始木板盖住了矩阵的第 1 ∼ k 个数，每次将木板向右移动一个单位，直到右端与

第 n 个数重合。

每次移动前输出被覆盖住的最大的数是多少。

【输入格式】

从 scan.in 中输入数据

第一行两个数，n，k，表示共有 n 个数，木板可以盖住 k 个数。

第二行 n 个数，表示矩阵中的元素。

【输出格式】

输出到 scan.out 中

共 n − k + 1 行，每行一个正整数。

第 i 行表示第 i ∼ i + k − 1 个数中最大值是多少。

【样例输入】

5 3

1 5 3 4 2

【样例输出】

【数据规模与约定】

对于 20% 的数据保证：1 ≤ n ≤ 10^3，1 ≤ k ≤ n

对于 50% 的数据保证：1 ≤ n ≤ 10^4，1 ≤ k ≤ n

对于 100% 的数据保证：1 ≤ n ≤ 2 ∗ 10^5，1 ≤ k ≤ n

矩阵中元素大小不超过 104。

线段树

笔记见分类：算法学习->线段树笔记√

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 800005

#define inf 2000022800

using namespace std;

int n,k;

int a[];

int ll[maxn],rr[maxn];

int max1[maxn];

int MAX(int a,int b)

{

    if(a>b)return a;

    else return b;

}

int MIN(int a,int b)

{

    if(a<b)return a;

    else return b;

}

void build(int pos,int l,int r)

{

    ll[pos]=l,rr[pos]=r;

    if(l==r)

    {

        max1[pos]=a[l];

        return;

    }

    int mid=l+r>>;

    build(pos<<,l,mid);

    build(pos<<|,mid+,r);

    max1[pos]=MAX(max1[pos<<],max1[pos<<|]);

}

int query(int pos,int l,int r)

{

    l=MAX(ll[pos],l),r=MIN(rr[pos],r);

    if(l>r)return -*inf;//²éÑ¯max¾Í-inf£¬min¾Íinf£¬sum¾Í0

    if(l==ll[pos]&&r==rr[pos]) return max1[pos];

    int mid=l+r>>;

    return MAX(query(pos<< , l , r) , query(pos<<| , l , r));

}

int main()

{

//    freopen("disappear.in","r",stdin);

//    freopen("disappear.out","w",stdout);

    cin>>n>>k;

    for(int i=;i<=n;++i)

    {

        scanf("%d",&a[i]);

    }

    build(,,n);

    for(int i=;i<=n-k+;++i)

    {

        printf("%d",query(,i,i+k-));

        puts("");

    }

    puts("");

    fclose(stdin);fclose(stdout);

    return ;

}

DXY的消失

题目描述

给出 N 个点，M 条边的有向图，对于每个点 v，求 D(v) 表示从点 v 出发，能到达的编号最大的点。

输入格式

第 1 行，2 个整数 N,M。接下来 M 行，每行 2 个整数 Ui,Vi，表示边 ⟨Ui,Vi⟩。点用 1,2,...,N 编号。

输出格式

N 个整数 D(1),D(2),...,D(N)

样例输入

4 3

1 2

2 4

4 3

样例输出

4 4 3 4

数据范围

对于 60% 的数据，1 ≤ N,M ≤ 1000

对于 100% 的数据，1 ≤ N,M ≤ 100000。

① 学习tarjan

②把图变成反图，从最大的点开始走，走过的点就不要走了。比如编号最大的点是5，那就把能走到5的点都标记成5，然后把这些点删掉。

是《挑战程序设计竞赛》上的例题，详解见P320

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<vector>

#define MAX 100005

using namespace std;

vector<int> G[MAX],rG[MAX],vs;

int used[MAX],cmp[MAX],ans[MAX];

int V,m;

void add(int from,int to)

{//·´ÏòµÄ·´Ïò±ß

     G[from].push_back(to);

     rG[to].push_back(from);

}

void dfs(int v)

{

     used[v]=;

     for(int i=;i<G[v].size();i++)

     {

         if(!used[G[v][i]]) dfs(G[v][i]);

     }

     vs.push_back(v);

}

void rdfs(int v,int k)

{

     used[v]=;

     cmp[v]=k;

     for(int i=;i<rG[v].size();i++)

     {

         if(!used[rG[v][i]]) rdfs(rG[v][i],k);

     }

     ans[k]=max(ans[k],v);

     for(int i=;i<rG[v].size();i++)

     {

         ans[k]=max(ans[k],ans[cmp[rG[v][i]]]);

     }

}

int scc()

{

     memset(used,,sizeof(used));

     vs.clear();

     for(int v=;v<=V;v++)

     {

         if(!used[v]) dfs(v);

     }

     memset(used,,sizeof(used));

     int k=;

     for(int i=vs.size()-;i>=;i--)

     {

         if(!used[vs[i]]) rdfs(vs[i],k++);

     }

}

int main()

{

     freopen("disappear.in","r",stdin);

     freopen("disappear.out","w",stdout);

     scanf("%d%d",&V,&m);

     for(int i=;i<=m;i++)

     {

         int from,to;

         scanf("%d%d",&from,&to);

         add(to,from);//·´Ïò

     }

     scc();

     for(int i=;i<=V;i++)printf("%d ",ans[cmp[i]]);

     puts("");

     return ;

}

巴特西

套题T6

最新文章

热门文章