很楠不爱3

这个屌丝很懒，什么也没留下！

热门标签

BZOJ刷题集_bzoj 题目和数据

作者：很楠不爱3 | 2024-03-09 10:49:36

踩

bzoj 题目和数据

1600: [Usaco2008 Oct]建造栅栏

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1348 Solved: 841
[ Submit][ Status][ Discuss]

Description

勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n（4<=n<=2500）的木板，他想把这块本板切成4块。这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意： *只要大木板的切割点不同就当成是不同的方案（像全排列那样），不要担心另外的特殊情况，go ahead。 *栅栏的面积要大于0. *输出保证答案在longint范围内。 *整块木板都要用完。

Input

*第一行：一个数n

Output

*第一行：合理的方案总数

Sample Input

Sample Output

6

输出详解：

Farmer John能够切出所有的情况为: (1, 1, 1,3); (1, 1, 2, 2); (1, 1, 3, 1); (1, 2, 1, 2); (1, 2, 2, 1); (1, 3,1, 1);
(2, 1, 1, 2); (2, 1, 2, 1); (2, 2, 1, 1); or (3, 1, 1, 1).
下面四种 -- (1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1), and (3,1, 1, 1) – 不能够组成一个四边形.

HINT

Source

资格赛

[ Submit][ Status][ Discuss]

HOME Back

该题利用DP,dp[i][j]表示前i个板子和为j,由 a+b+c>d -> n/2>a,每个板子长度都小于n/2


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =200005;
const int INF =1e9+5;
 
ll n;
ll dp[5][2505];
 
int main()
{
//    freopen("data.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    ios_base::sync_with_stdio(false);
 
    cin >>n;
    int m;
    if(n%2)
    {
        m = n/2;
    }
    else
    {
        m = n/2-1;
    }
 
    for(int i=1;i<=m;i++)
    {
        dp[1][i] = 1;
    }
 
 
    for(int i=1;i<=n;i++)
    {
        for(int j=max(i-m,1);j<i;j++)
        {
            dp[2][i] += dp[1][j];
        }
    }
 
    for(int i=1;i<=n;i++)
    {
        for(int j=max(i-m,1);j<i;j++)
        {
            dp[3][i] += dp[2][j];
        }
    }
 
 
    int x;
    for(int i=1;i<=n;i++)
    {
        for(int j=max(i-m,1);j<i;j++)
        {
            dp[4][i] += dp[3][j];
        }
    }
 
//    for(int i=1;i<=4;i++)
//    {
//        for(int j=1;j<=n;j++)
//        {
//            cout << dp[i][j]<<" ";
//        }
//        cout <<endl;
//    }
 
    cout << dp[4][n]<<endl;
 
    return 0;
}

1601: [Usaco2008 Oct]灌水

Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 2056 Solved: 1355
[ Submit][ Status][ Discuss]

Description

Farmer John已经决定把水灌到他的n(1<=n<=300)块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0). 计算Farmer John所需的最少代价。

Input

*第一行：一个数n

*第二行到第n+1行：第i+1行含有一个数wi

*第n+2行到第2n+1行：第n+1+i行有n个被空格分开的数，第j个数代表pij。

Output

*第一行：一个单独的数代表最小代价.

Sample Input

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

Sample Output

9

输出详解：

Farmer John在第四块土地上建立水库，然后把其他的都连向那一个，这样就要花费3+2+2+2=9

HINT

Source

资格赛

最小生成树,添加一个水源的节点


 
#include<bits/stdc++.h>
using namespace std;
 
 
const int MAXN=1110;//最大点数
const int MAXM=1001000;//最大边数
int F[MAXN];//并查集使用
 
struct Edge
{
    int u,v;
    int w;
}edge[MAXM];//储存边的信息，包括起点/终点/权值
 
int tol=0;//边数，加边前赋值为0
 
 
 
void addedge(int u,int v,int w)
{
    edge[tol].u=u;
    edge[tol].v=v;
    edge[tol++].w=w;
}
void init()
{
    tol=0;
}
 
bool cmp(Edge a,Edge b)//排序函数，边按照权值从小到大排序
{
    return a.w<b.w;
}
 
int Find(int x)
{
    if(F[x]==-1)
        return x;
    else
        return F[x]=Find(F[x]);
}
 
int Kruskal(int n)//传入点数，返回最小生成树的权值，如果不连通返回-1
{
    memset(F,-1,sizeof(F));
    sort(edge,edge+tol,cmp);
    int cnt=0;//计算加入的边数
    int ans=0;
    for(int i=0;i<tol;i++)
    {
        int    u=edge[i].u;
        int    v=edge[i].v;
        int w=edge[i].w;
        int t1=Find(u);
        int t2=Find(v);
        if(t1!=t2)
        {
 
            ans+=w;
            F[t1]=t2;
            cnt++;
        }
        if(cnt==n-1)
            break;
    }
    if(cnt<n-1)
        return -1;//不连通
    else
        return ans;
}
 
int n;
int w;
 
int main()
{
//    freopen("data.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin >> n;
    int ss = 0;
    init();
    for(int i=1;i<=n;i++)
    {
        cin >> w;
        addedge(ss,i,w);
    }
 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin >> w;
            if(i==j) continue;
            addedge(i,j,w);
        }
    }
 
    cout << Kruskal(n+1)<<endl;
    return 0;
}

1602: [Usaco2008 Oct]牧场行走

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 2096 Solved: 1108
[ Submit][ Status][ Discuss]

Description

N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。这n块土地被n-1条边连接。奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。

Input

*第一行：两个被空格隔开的整数：N和Q

*第二行到第n行：第i+1行有两个被空格隔开的整数：AI，BI，LI

*第n+1行到n+Q行：每一行有两个空格隔开的整数：P1，P2，表示两头奶牛的编号。

Output

*第1行到第Q行：每行输出一个数，表示那两头奶牛之间的距离。

Sample Input

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

Sample Output

2
7

HINT

Source

资格赛

LCA求树上两点距离


 
#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 40000 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
const double ee = exp(1.0);
 
int head[maxn];
int edgeNum;
struct Edge
{
    int fr, to, next;
    int val;
} e[maxn << 1];
 
void initEdge()
{
    memset(head, -1, sizeof(head));
    edgeNum = 0;
}
 
void addEdge(int fr, int to, int val)
{
    e[edgeNum].fr = fr;
    e[edgeNum].to = to;
    e[edgeNum].val = val;
    e[edgeNum].next = head[fr];
    head[fr] = edgeNum++;
 
    e[edgeNum].fr = to;
    e[edgeNum].to = fr;
    e[edgeNum].val = val;
    e[edgeNum].next = head[to];
    head[to] = edgeNum++;
}
 
bool vis[maxn];
int dis[maxn];          //根节点到当前点的距离
int ver[maxn << 1];     //dfs遍历时节点的编号
int dep[maxn << 1];     //dfs遍历时节点的深度
int R[maxn];            //dfs遍历时第一次出现当前节点时的遍历序号
int tot;                //下标计数器
 
void dfs(int u, int d)
{
    vis[u] = true;
    ver[++tot] = u;
    R[u] = tot;
    dep[tot] = d;
 
    for (int i = head[u]; i != -1; i = e[i].next)
    {
        if (!vis[e[i].to])
        {
            int v = e[i].to;
            int val = e[i].val;
            dis[v] = dis[u] + val;
            dfs(v, d + 1);
            ver[++tot] = u;
            dep[tot] = d;
        }
    }
}
 
 
int minDepVerIndex[maxn << 1][20];
void queryInit(int n)
{
    
    for (int i = 1; i <= n; i++)
    {
        minDepVerIndex[i][0] = i;
    }
    
 
    for (int j = 1; (1 << j) <= n; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            int p = (1 << (j - 1));
            int u = minDepVerIndex[i][j - 1];
            int v = minDepVerIndex[i + p][j - 1];
            minDepVerIndex[i][j] = dep[u] < dep[v] ? u : v;
        }
    }
}
 
int queryMin(int l, int r)
{
    int k = log2((double)(r - l + 1));
    int u = minDepVerIndex[l][k];
    int v = minDepVerIndex[r - (1 << k) + 1][k];
    return dep[u] < dep[v] ? u : v;
}
 
 
//先求出两个点的lca，然后他们之间的最短距离就是一个点走到他们的lca，然后再走向另一个点。
//对应的计算方法就是根节点到lca点的disLca，然后根节点到u点的disU，到v点的disV，
//他们呢间的距离就是disU + disV - 2 * disLCA。
 
 
int lca(int u, int v)
{
    int l = R[u];
    int r = R[v];
    if (l > r)
        swap(l, r);
    int index = queryMin(l, r);
    return ver[index];
}
 
int main()
{
//    freopen("data.txt", "r", stdin);
 
    int n, q;
    scanf("%d%d", &n, &q);
    initEdge();
    for (int i = 1; i < n; i++)
    {
        int fr, to, val;
        scanf("%d%d%d", &fr, &to, &val);
        addEdge(fr, to, val);
    }
 
    memset(vis, false, sizeof(vis));
    tot = 0;
    dis[1] = 0;
    dfs(1, 1);
 
    queryInit((n << 1) - 1);
    while (q--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        int rt = lca(u, v);
        printf("%d\n", dis[u] + dis[v] - 2 * dis[rt]);
    }
 
    return 0;
}

1603: [Usaco2008 Oct]打谷机

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1010 Solved: 775
[ Submit][ Status][ Discuss]

Description

Farmer John有一个过时的打谷机（收割小麦），它需要带子来带动。发动机驱动轮1总是顺时针旋转的，用来带动转轮2，转轮2来带动转轮3，等等。一共有n（2<=n<=1000）个转轮（n-1条带子）。上面的图解描述了转轮的两种连接方式，第一种方式使得两个轮子旋转的方向相同，第二种则相反。给出一串带子的信息： *Si—驱动轮 *Di—被动轮 *Ci—连接的类型（0=直接连接，1=交叉连接）不幸的是，列出的信息是随即的。作为样例，考虑上面的图解，n=4，转轮1是驱动轮，可以得知最后转轮4是逆时针旋转的。

Input

*第一行：一个数n *第二行到第n行：每一行有三个被空格隔开的数：Si，Di，Ci

Output

*第一行：一个单独的数，表示第n个转轮的方向，0表示顺时针，1表示逆时针。

Sample Input

4
2 3 0
3 4 1
1 2 0

Sample Output

HINT

Source

资格赛

直接正连价值为0的边,奇连价值为1的边,根据其奇偶性判断


 
#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 40000 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
const double ee = exp(1.0);
 
int head[maxn];
int edgeNum;
struct Edge
{
    int fr, to, next;
    int val;
} e[maxn << 1];
 
void initEdge()
{
    memset(head, -1, sizeof(head));
    edgeNum = 0;
}
 
void addEdge(int fr, int to, int val)
{
    e[edgeNum].fr = fr;
    e[edgeNum].to = to;
    e[edgeNum].val = val;
    e[edgeNum].next = head[fr];
    head[fr] = edgeNum++;
 
    e[edgeNum].fr = to;
    e[edgeNum].to = fr;
    e[edgeNum].val = val;
    e[edgeNum].next = head[to];
    head[to] = edgeNum++;
}
 
bool vis[maxn];
int dis[maxn];          //根节点到当前点的距离
int ver[maxn << 1];     //dfs遍历时节点的编号
int dep[maxn << 1];     //dfs遍历时节点的深度
int R[maxn];            //dfs遍历时第一次出现当前节点时的遍历序号
int tot;                //下标计数器
 
void dfs(int u, int d)
{
    vis[u] = true;
    ver[++tot] = u;
    R[u] = tot;
    dep[tot] = d;
 
    for (int i = head[u]; i != -1; i = e[i].next)
    {
        if (!vis[e[i].to])
        {
            int v = e[i].to;
            int val = e[i].val;
            dis[v] = dis[u] + val;
            dfs(v, d + 1);
            ver[++tot] = u;
            dep[tot] = d;
        }
    }
}
 
 
int minDepVerIndex[maxn << 1][20];
void queryInit(int n)
{
    
    for (int i = 1; i <= n; i++)
    {
        minDepVerIndex[i][0] = i;
    }
    
 
    for (int j = 1; (1 << j) <= n; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            int p = (1 << (j - 1));
            int u = minDepVerIndex[i][j - 1];
            int v = minDepVerIndex[i + p][j - 1];
            minDepVerIndex[i][j] = dep[u] < dep[v] ? u : v;
        }
    }
}
 
int queryMin(int l, int r)
{
    int k = log2((double)(r - l + 1));
    int u = minDepVerIndex[l][k];
    int v = minDepVerIndex[r - (1 << k) + 1][k];
    return dep[u] < dep[v] ? u : v;
}
 
 
//先求出两个点的lca，然后他们之间的最短距离就是一个点走到他们的lca，然后再走向另一个点。
//对应的计算方法就是根节点到lca点的disLca，然后根节点到u点的disU，到v点的disV，
//他们呢间的距离就是disU + disV - 2 * disLCA。
 
 
int lca(int u, int v)
{
    int l = R[u];
    int r = R[v];
    if (l > r)
        swap(l, r);
    int index = queryMin(l, r);
    return ver[index];
}
 
int main()
{
//    freopen("data.txt", "r", stdin);
 
    int n, q;
    scanf("%d", &n);
    initEdge();
    for (int i = 1; i < n; i++)
    {
        int fr, to, val;
        scanf("%d%d%d", &fr, &to, &val);
        addEdge(fr, to, val);
    }
 
    memset(vis, false, sizeof(vis));
    tot = 0;
    dis[1] = 0;
    dfs(1, 1);
    q=1;
    queryInit((n << 1) - 1);
    int u=1;
    int v=n;
    int rt = lca(u, v);
    printf("%d\n", (dis[u] + dis[v] - 2 * dis[rt])%2);
 
 
    return 0;
}

1606: [Usaco2008 Dec]Hay For Sale 购买干草

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1393 Solved: 1032
[ Submit][ Status][ Discuss]

Description

约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为C(1≤C≤50000)个单位的马车，去顿因家买一些干草．顿因有H(1≤H≤5000)包干草，每一包都有它的体积Vi(l≤Vi≤C).约翰只能整包购买，

他最多可以运回多少体积的干草呢？

Input

第1行输入C和H，之后H行一行输入一个Vi．

Output

最多的可买干草体积．

Sample Input

7 3 //总体积为7,用3个物品来背包
2
6
5

The wagon holds 7 volumetric units; three bales are offered for sale with
volumes of 2, 6, and 5 units, respectively.

Sample Output

7 //最大可以背出来的体积

HINT

Buying the two smaller bales fills the wagon.

Source

Silver

0-1背包


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
 
 
int c;
int h;
int v[5005];
int dp[2][50005];
 
 
int main()
{
//    freopen("data.txt", "r", stdin);
//    ios_base::sync_with_stdio(false);
    c = read();
    h = read();
    for(int i=1;i<=h;i++)
    {
        v[i] = read();
    }
 
    for(int i=1;i<=h;i++)
    {
 
        for(int j=0;j<=c;j++)
        {
            dp[i&1][j]=dp[(i-1)&1][j];
            if(j>=v[i])
                dp[i&1][j] = max(dp[(i-1)&1][j] , dp[(i-1)&1][ j-v[i] ] + v[i]);
        }
    }
    printf("%d\n",dp[h%2][c]);
//    cout <<dp[h%2][c]<<endl;
 
}

1607: [Usaco2008 Dec]Patting Heads 轻拍牛头

Time Limit: 3 Sec Memory Limit: 64 MB
Submit: 2657 Solved: 1397
[ Submit][ Status][ Discuss]

Description

今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏．

贝茜让N(1≤N≤100000)头奶牛坐成一个圈．除了1号与N号奶牛外，i号奶牛与i-l号和i+l号奶牛相邻．N号奶牛与1号奶牛相邻．农夫约翰用很多纸条装满了一个桶，每一张包含了一个独一无二的1到1,000,000的数字．

接着每一头奶牛i从柄中取出一张纸条Ai．每头奶牛轮流走上一圈，同时拍打所有编号能整除在纸条上的数字的牛的头，然后做回到原来的位置．牛们希望你帮助他们确定，每一头奶牛需要拍打的牛．

Input

第1行包含一个整数N，接下来第2到N+1行每行包含一个整数Ai．

Output

第1到N行，每行的输出表示第i头奶牛要拍打的牛数量．

Sample Input

5 //有五个数,对于任一个数来说,其它的数有多少个是它的约数
2
1
2
3
4

INPUT DETAILS:

The 5 cows are given the numbers 2, 1, 2, 3, and 4, respectively.

Sample Output

2
0
2
1
3

OUTPUT DETAILS:

The first cow pats the second and third cows; the second cows pats no cows;
etc.

HINT

Source

Silver

打表求解,可以被1整除的为1,2,3,4 ,,注意把重复的数优化掉


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int N = 1000000+5;
map<int,int> mp;
map<int,int>::iterator it;
int n;
int v[100005];
int num[N];
int maxx;
 
int main()
{
//    freopen("data.txt", "r", stdin);
//    ios_base::sync_with_stdio(false);
    n = read();
    for(int i=1;i<=n;i++)
    {
        v[i] = read();
        mp[v[i]]++;
        maxx = max(maxx,v[i]);
    }
 
    for(it = mp.begin();it!=mp.end();it++)
    {
        int x = it->first;
        int ct =it->second;
        for(int j=x;j<=maxx;j+=x)
        {
            num[j]+=ct;
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",num[ v[i] ]-1);
    }
 
}

1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1687 Solved: 1031
[ Submit][ Status][ Discuss]

Description

为了避免餐厅过分拥挤，FJ要求奶牛们分3批就餐。每天晚饭前，奶牛们都会在餐厅前排队入内，按FJ的设想所有第3批就餐的奶牛排在队尾，队伍的前端由设定为第1批就餐的奶牛占据，中间的位置就归第2批就餐的奶牛了。由于奶牛们不理解FJ的安排，晚饭前的排队成了一个大麻烦。第i头奶牛有一张标明她用餐批次D_i(1 <= D_i <= 3)的卡片。虽然所有N(1 <= N <= 30,000)头奶牛排成了很整齐的队伍但谁都看得出来，卡片上的号码是完全杂乱无章的。在若干次混乱的重新排队后，FJ找到了一种简单些的方法：奶牛们不动，他沿着队伍从头到尾走一遍把那些他认为排错队的奶牛卡片上的编号改掉，最终得到一个他想要的每个组中的奶牛都站在一起的队列，例如111222333或者333222111。哦，你也发现了，FJ不反对一条前后颠倒的队列，那样他可以让所有奶牛向后转，然后按正常顺序进入餐厅。你也晓得，FJ是个很懒的人。他想知道，如果他想达到目的，那么他最少得改多少头奶牛卡片上的编号。所有奶牛在FJ改卡片编号的时候，都不会挪位置。

Input

第1行: 1个整数：N 第2..N+1行: 第i+1行是1个整数，为第i头奶牛的用餐批次D_i

Output

第1行: 输出1个整数，为FJ最少要改几头奶牛卡片上的编号，才能让编号变成他设想中的样子

Sample Input

5
1
3
2
1
1
输入说明:

队列中共有5头奶牛，第1头以及最后2头奶牛被设定为第一批用餐，第2头奶牛的预设是第三批用餐，第3头则为第二批用餐。

Sample Output

1

输出说明:

如果FJ想把当前队列改成一个不下降序列，他至少要改2头奶牛的编号，一种可行的方案是：把队伍中2头编号不是1的奶牛的编号都改成1。不过，如果FJ选择把第1头奶牛的编号改成3就能把奶牛们的队伍改造成一个合法的不上升序列了。

HINT

Source

Silver

最长非递减子序列的变型


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int N = 30000+5;
const int INF = 1e9;
 
int n,t;
vector<int> num;
//int dp[N][4];
 
 
//最长非递减
//LIS O(n*log(n));
int getLISLength( int length)
{
    vector<ll> ivec;
    ivec.clear();
    for(int i = 0; i < length; ++i)
    {
        if (ivec.size() == 0 || ivec.back() <= num[i])
            ivec.push_back(num[i]);
        else
        {
            int low = upper_bound(ivec.begin(),ivec.end(),num[i])-ivec.begin();
            //找到大于等于num[i]的数
 
            ivec[low] =num[i];
        }
    }
    return ivec.size();
}
 
 
 
 
int main()
{
//    freopen("data.txt", "r", stdin);
//    ios_base::sync_with_stdio(false);
    n = read();
    for(int i=1;i<=n;i++)
    {
        t = read();
        num.push_back(t);
    }
    int ans = INF;
    ans = min(ans,n-getLISLength(n));
 
    reverse(num.begin(),num.end());
 
    ans = min(ans,n-getLISLength(n));
 
    printf("%d\n",ans);
}

1610: [Usaco2008 Feb]Line连线游戏

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 2324 Solved: 1045
[ Submit][ Status][ Discuss]

Description

Farmer John最近发明了一个游戏，来考验自命不凡的贝茜。游戏开始的时候，FJ会给贝茜一块画着N (2 <= N <= 200)个不重合的点的木板，其中第i个点的横、纵坐标分别为X_i和Y_i (-1,000 <= X_i <=1,000； -1,000 <= Y_i <= 1,000)。贝茜可以选两个点画一条过它们的直线，当且仅当平面上不存在与画出直线平行的直线。游戏结束时贝茜的得分，就是她画出的直线的总条数。为了在游戏中胜出，贝茜找到了你，希望你帮她计算一下最大可能得分。

Input

* 第1行: 输入1个正整数：N

* 第2..N+1行: 第i+1行用2个用空格隔开的整数X_i、Y_i，描述了点i的坐标

Output

第1行: 输出1个整数，表示贝茜的最大得分，即她能画出的互不平行的直线数

Sample Input

4
-1 1
-2 0
0 0
1 1

Sample Output

* 第1行: 输出1个整数，表示贝茜的最大得分，即她能画出的互不平行的直线数

HINT

4 输出说明: 贝茜能画出以下4种斜率的直线：-1，0，1/3以及1。

Source

Silver

暴力一下所有的斜率,set求一下斜率就好了


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int N = 30000+5;
const int INF = 1e9;
 
int n;
set<pair <int,int> > num;
int x[205];
int y[205];
int gcd(int p,int q){return q==0?p:gcd(q,p%q);}
 
 
int main()
{
//    freopen("data.txt", "r", stdin);
//    ios_base::sync_with_stdio(false);
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >>x[i]>>y[i];
    }
 
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
 
            int xx = x[i]-x[j];
            int yy = y[i]-y[j];
            if(xx==yy&&yy==0) continue;
            if(yy<0)
            {
                xx*=-1;
                yy*=-1;
            }
            int t;
            if(xx<0)
            {
                t=gcd(-xx,yy);
            }
            else
            {
                t=gcd(xx,yy);
            }
            xx/=t;
            yy/=t;
            if(xx==0) yy=1;
            if(yy==0) xx=1;
            num.insert(make_pair(xx,yy));
        }
    }
    cout << num.size()<<endl;;
}

1611: [Usaco2008 Feb]Meteor Shower流星雨

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1687 Solved: 724
[ Submit][ Status][ Discuss]

Description

去年偶们湖南遭受N年不遇到冰冻灾害，现在芙蓉哥哥则听说另一个骇人听闻的消息：一场流星雨即将袭击整个霸中，由于流星体积过大，它们无法在撞击到地面前燃烧殆尽，届时将会对它撞到的一切东西造成毁灭性的打击。很自然地，芙蓉哥哥开始担心自己的安全问题。以霸中至In型男名誉起誓，他一定要在被流星砸到前，到达一个安全的地方（也就是说，一块不会被任何流星砸到的土地）。如果将霸中放入一个直角坐标系中，芙蓉哥哥现在的位置是原点，并且，芙蓉哥哥不能踏上一块被流星砸过的土地。根据预报，一共有M颗流星(1 <= M <= 50,000)会坠落在霸中上，其中第i颗流星会在时刻 T_i (0 <= T_i <= 1,000)砸在坐标为(X_i, Y_i) (0 <= X_i <= 300；0 <= Y_i <= 300) 的格子里。流星的力量会将它所在的格子，以及周围4个相邻的格子都化为焦土，当然芙蓉哥哥也无法再在这些格子上行走。芙蓉哥哥在时刻0开始行动，它只能在第一象限中，平行于坐标轴行动，每1个时刻中，她能移动到相邻的（一般是4个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻t被流星撞击或烧焦，那么芙蓉哥哥只能在t之前的时刻在这个格子里出现。请你计算一下，芙蓉哥哥最少需要多少时间才能到达一个安全的格子。

Input

* 第1行: 1个正整数：M * 第2..M+1行: 第i+1行为3个用空格隔开的整数：X_i，Y_i，以及T_i

Output

输出1个整数，即芙蓉哥哥逃生所花的最少时间。如果芙蓉哥哥无论如何都无法在流星雨中存活下来，输出-1

Sample Input

4
0 0 2
2 1 2
1 1 2
0 3 5
输入说明:
一共有4颗流星将坠落在霸中，它们落地点的坐标分别是(0, 0)，(2, 1)，(1, 1)
以及(0, 3)，时刻分别为2，2，2，5。

Sample Output

BFS模拟


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int N = 30000+5;
const int INF = 1e9;
int dir[4][2] = {  {1,0},{-1,0},{0,1},{0,-1} };
 
struct node{
    int x;
    int y;
};
 
int m;
vector<node> a[1005];
int mm[305][305];
int vis1[305][305];
 
node nt ;
int t;
 
 
int vis[1000000];
 
struct nod{
    int x;
    int y;
    int step;
};
 
 
int bfs(int x,int y)
{
    nod cur,nex;
    cur.x = x;
    cur.y = y;
    cur.step = 0;
    queue<nod> q;
    q.push(cur);
 
 
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
 
        if( mm[cur.x][cur.y] == 2 )
        {
//            cout << cur.x<<cur.y<<endl;
            return cur.step;
        }
 
        if(!vis[cur.step])
        {
            int len = a[cur.step].size();
 
            for(int i=0;i<len;i++)
            {
                int tx = a[cur.step][i].x;
                int ty = a[cur.step][i].y;
                for(int j=0;j<4;j++)
                {
                    int xx = tx+dir[j][0];
                    int yy = ty+dir[j][1];
                    if(xx<0||yy<0) continue;
                    mm[xx][yy]=1;
                }
                mm[tx][ty]=1;
            }
            vis[cur.step] = 1;
        }
 
 
        if(mm[cur.x][cur.y]==1) continue;
 
        for(int i=0;i<4;i++)
        {
 
            int xx = cur.x+dir[i][0];
            int yy = cur.y+dir[i][1];
            if(xx<0||yy<0) continue;
            if(mm[xx][yy]==1) continue;
            if(vis1[xx][yy]==1) continue;
 
            nex.x = xx;
            nex.y = yy;
            nex.step = cur.step + 1;
 
            q.push(nex);
            vis1[xx][yy]=1;
        }
    }
    return -1;
}
 
 
 
 
int main()
{
//    freopen("data.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
 
    cin>>m;
    for(int i=0;i<m;i++)
    {
        cin >> nt.x >> nt.y >> t;
        for(int j=0;j<4;j++)
        {
            int xx = nt.x+dir[j][0];
            int yy = nt.y+dir[j][1];
            if(xx<0||yy<0) continue;
            mm[xx][yy]=1;
        }
        mm[nt.x][nt.y] = 1 ;
 
        a[t].push_back(nt);
    }
 
    for(int i=0;i<305;i++)
    {
        for(int j=0;j<305;j++)
        {
            if(mm[i][j])
            {
                mm[i][j]=0;
            }
            else
            {
                mm[i][j]=2;
            }
        }
    }
    cout <<bfs(0,0)<<endl;
}

1612: [Usaco2008 Jan]Cow Contest奶牛的比赛

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1218 Solved: 831
[ Submit][ Status][ Discuss]

Description

FJ的N(1 <= N <= 100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1 <= A <= N; 1 <= B <= N; A != B) ，那么她们的对决中，编号为A的奶牛总是能胜出。 FJ想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 M(1 <= M <= 4,500)轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

Input

* 第1行: 2个用空格隔开的整数：N 和 M

* 第2..M+1行: 每行为2个用空格隔开的整数A、B，描述了参加某一轮比赛的奶牛的编号，以及结果（编号为A，即为每行的第一个数的奶牛为胜者）

Output

* 第1行: 输出1个整数，表示排名可以确定的奶牛的数目

Sample Input

5 5
4 3
4 2
3 2
1 2
2 5

Sample Output

2

输出说明:

编号为2的奶牛输给了编号为1、3、4的奶牛，也就是说她的水平比这3头奶
牛都差。而编号为5的奶牛又输在了她的手下，也就是说，她的水平比编号为5的
奶牛强一些。于是，编号为2的奶牛的排名必然为第4，编号为5的奶牛的水平必
然最差。其他3头奶牛的排名仍无法确定。

HINT

Source

Silver

传递背包


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
 
 
int mm[305][305];
int n,m,u,v;
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    memset(mm,0,sizeof(mm));
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        mm[u][v]=1;
    }
    for(int k=1;k<=n;k++)
      for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(mm[i][k]&&mm[k][j]){
        //如果两个数之间有直接或间接关系，都能判断
            mm[i][j]=1;
        }
 
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int flag=0;
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;//自己和自己不需要比较
          if(mm[i][j]==0&&mm[j][i]==0)
          {
             flag=1;
             break;
          }
        }
        if(!flag) ans++;
 
    }
    cout<<ans<<endl;
    return 0;
}

1613: [Usaco2007 Jan]Running贝茜的晨练计划

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1880 Solved: 923
[ Submit][ Status][ Discuss]

Description

奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行N(1 <= N <= 10,000)分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第i分钟内跑步，她可以在这一分钟内跑D_i(1 <= D_i <= 1,000)米，并且她的疲劳度会增加 1。不过，无论何时贝茜的疲劳度都不能超过M(1 <= M <= 500)。如果贝茜选择休息，那么她的疲劳度就会每分钟减少1，但她必须休息到疲劳度恢复到0为止。在疲劳度为0时休息的话，疲劳度不会再变动。晨跑开始时，贝茜的疲劳度为0。还有，在N分钟的锻炼结束时，贝茜的疲劳度也必须恢复到0，否则她将没有足够的精力来对付这一整天中剩下的事情。请你计算一下，贝茜最多能跑多少米。

Input

* 第1行: 2个用空格隔开的整数：N 和 M

* 第2..N+1行: 第i+1为1个整数：D_i

Output

* 第1行: 输出1个整数，表示在满足所有限制条件的情况下，贝茜能跑的最大距离

Sample Input

5 2
5
3
4
2
10

Sample Output

9

输出说明:

贝茜在第1分钟内选择跑步（跑了5米），在第2分钟内休息，在第3分钟内跑
步（跑了4米），剩余的时间都用来休息。因为在晨跑结束时贝茜的疲劳度必须
为0，所以她不能在第5分钟内选择跑步。

HINT

Source

DP[前n分钟][疲劳度]


 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
int dp[10005][505];
 
int n,m;
int b[10005];
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin >> b[i];
    }
    for(int i=1;i<=n;i++)
    {
 
        for(int j=0;j<=m;j++)
        {
            if(j==0)
            {
                dp[i][0] = max( dp[i][0],dp[i-1][0]);//rest
 
                for(int k=1;k<=m;k++)
                {
                    if(i-k<0) break;
                    dp[i][0] = max( dp[i][0],dp[i-k][k] );
                }
            }
            else
            {
                dp[i][j] = dp[i-1][j-1]+b[i];
            }
        }
 
    }
    cout << dp[n][0] << endl;
    return 0;
}

1614: [Usaco2007 Jan]Telephone Lines架设电话线

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1875 Solved: 804
[ Submit][ Status][ Discuss]

Description

Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为 L_i (1 <= L_i <= 1,000,000)。数据中保证每对{A_i，B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。经过谈判，电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过 K对，那么FJ的总支出为0。请你计算一下，FJ最少需要在电话线上花多少钱。

Input

* 第1行: 3个用空格隔开的整数：N，P，以及K

* 第2..P+1行: 第i+1行为3个用空格隔开的整数：A_i，B_i，L_i

Output

* 第1行: 输出1个整数，为FJ在这项工程上的最小支出。如果任务不可能完成，输出-1

Sample Input

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

输入说明:

一共有5根废弃的电话线杆。电话线杆1不能直接与电话线杆4、5相连。电话
线杆5不能直接与电话线杆1、3相连。其余所有电话线杆间均可拉电话线。电信
公司可以免费为FJ连结一对电话线杆。

Sample Output

4

输出说明:

FJ选择如下的连结方案：1->3；3->2；2->5，这3对电话线杆间需要的
电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线，于是，
他所需要购买的电话线的最大长度为4。

HINT

Source

Silver

可以化为验证性题目,二分答案


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
//
const int INF = 1e9;
 
int m,n;//n is the node   m is the edge
const int MAXN=1e3+5;;
const int MAXM =1e5+5;
struct node{
    int x,d;
    node(){}
    node(int a,int b){x=a;d=b;}
    bool operator < (const node & a) const
    {
        if(d==a.d) return x<a.x;
        else return d > a.d;
    }
};
 
 
class Dijkstra_queue{
public:
    void init(){
        for(int i=0;i<=n;i++)
            eg[i].clear();
        for(int i=0;i<=n;i++)
            dist[i]=INF;
    }
    void Run(int s)
    {
        dist[s]=0;
        //用优先队列优化
        priority_queue<node> q;
        q.push(node(s,dist[s]));
        while(!q.empty())
        {
            node x=q.top();q.pop();
            for(int i=0;i<eg[x.x].size();i++)
            {
                node y=eg[x.x][i];
                if(dist[y.x]>x.d+y.d)
                {
                    dist[y.x]=x.d+y.d;
                    q.push(node(y.x,dist[y.x]));
                }
            }
        }
    }
    void addEdge(int u,int v,int w)
    {
        eg[u].push_back(node(v,w));
    }
public:
    int dist[MAXN];
private:
    vector<node> eg[MAXN];//如果MAXN非常大，就把其放到类的外面
};
 
int u[MAXM];
int v[MAXM];
int w[MAXM];
 
Dijkstra_queue di;
int k;
 
 
 
bool check(int num)
{
    di.init();
    for(int i=0;i<m;i++)
    {
        if(w[i]>num)
        {
            di.addEdge(u[i],v[i],1);
            di.addEdge(v[i],u[i],1);
        }
        else
        {
            di.addEdge(u[i],v[i],0);
            di.addEdge(v[i],u[i],0);
        }
    }
    di.Run(1);
 
    if(di.dist[n]>k)
    {
        return false;
    }
    else
    {
        return true;
    }
}
 
 
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m>>k;
    int maxx = 0;
    for(int i=0;i<m;i++)
    {
        cin >> u[i]>>v[i]>>w[i];
        maxx = max(maxx,w[i]);
    }
 
    int l = 0;
    int r = maxx;
 
    while(l<r)
    {
        int mid = (l+r)>>1;
        if(!check(mid))
        {
            l  = mid+1;
        }
        else
        {
            r  = mid;
        }
    }
    if(check(r))
    {
        cout <<r<<endl;
    }
    else if(check(r+1))
    {
        cout <<r+1<<endl;
    }
    else
    {
        cout << -1<<endl;
    }
 
 
    return 0;
}


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
//
const int INF = 1e9;
 
int m,n;//n is the node   m is the edge
const int MAXN=1e3+5;;
const int MAXM =1e5+5;
struct node{
    int x,d;
    node(){}
    node(int a,int b){x=a;d=b;}
    bool operator < (const node & a) const
    {
        if(d==a.d) return x<a.x;
        else return d > a.d;
    }
};
 
 
class Dijkstra_queue{
public:
    void init(){
        for(int i=0;i<=n;i++)
            eg[i].clear();
        for(int i=0;i<=n;i++)
            dist[i]=INF;
    }
    void Run(int s)
    {
        dist[s]=0;
        //用优先队列优化
        priority_queue<node> q;
        q.push(node(s,dist[s]));
        while(!q.empty())
        {
            node x=q.top();q.pop();
            for(int i=0;i<eg[x.x].size();i++)
            {
                node y=eg[x.x][i];
                if(dist[y.x]>x.d+y.d)
                {
                    dist[y.x]=x.d+y.d;
                    q.push(node(y.x,dist[y.x]));
                }
            }
        }
    }
    void addEdge(int u,int v,int w)
    {
        eg[u].push_back(node(v,w));
    }
public:
    int dist[MAXN];
private:
    vector<node> eg[MAXN];//如果MAXN非常大，就把其放到类的外面
};
 
int u[MAXM];
int v[MAXM];
int w[MAXM];
 
Dijkstra_queue di;
int k;
 
 
 
bool check(int num)
{
    di.init();
    for(int i=0;i<m;i++)
    {
        if(w[i]>num)
        {
            di.addEdge(u[i],v[i],1);
            di.addEdge(v[i],u[i],1);
        }
        else
        {
            di.addEdge(u[i],v[i],0);
            di.addEdge(v[i],u[i],0);
        }
    }
    di.Run(1);
 
    if(di.dist[n]>k)
    {
        return false;
    }
    else
    {
        return true;
    }
}
 
 
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m>>k;
    int maxx = 0;
    for(int i=0;i<m;i++)
    {
        cin >> u[i]>>v[i]>>w[i];
        maxx = max(maxx,w[i]);
    }
 
    int ans=-1;
    int l = 0;
    int r = maxx;
 
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
            ans=mid,r=mid-1;
        else
            l=mid+1;
    }
    cout << ans<<endl;
 
 
    return 0;
}

1615: [Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 998 Solved: 413
[ Submit][ Status][ Discuss]

Description

Farmer John新买的干草打包机的内部结构大概算世界上最混乱的了，它不象普通的机器一样有明确的内部传动装置，而是，N (2 <= N <= 1050)个齿轮互相作用，每个齿轮都可能驱动着多个齿轮。 FJ记录了对于每个齿轮i，记录了它的3个参数：X_i，Y_i表示齿轮中心的位置坐标(-5000 <= X_i <= 5000; -5000 <= Y_i <= 5000)；R_i表示该齿轮的半径(3 <= R_i <= 800)。驱动齿轮的位置为0,0，并且FJ也知道最终的工作齿轮位于X_t,Y_t。驱动齿轮顺时针转动，转速为10,000转/小时。你的任务是，确定传动序列中所有齿轮的转速。传动序列的定义为，能量由驱动齿轮传送到工作齿轮的过程中用到的所有齿轮的集合。对能量传送无意义的齿轮都应当被忽略。在一个半径为Rd，转速为S转/每小时的齿轮的带动下，与它相接的半径为Rx的齿轮的转速将为-S*Rd/Rx转/小时。S前的负号的意思是，一个齿轮带动的另一个齿轮的转向会与它的转向相反。 FJ只对整个传动序列中所有齿轮速度的绝对值之和感兴趣，你的任务也就相应转化成求这个值。机器中除了驱动齿轮以外的所有齿轮都被另外某个齿轮带动，并且不会出现2个不同的齿轮带动同一个齿轮的情况。相信你能轻易地写个程序来完成这些计算:)

Input

* 第1行: 3个用空格隔开的整数：N，X_t，Y_t

* 第2..N+1行: 第i+1描述了齿轮i的位置及半径：X_i，Y_i，以及R_i

Output

* 第1行: 输出所有在传动中起到作用的齿轮转速的绝对值，包括驱动齿轮和工作齿轮。只需要输出答案的整数部分

Sample Input

4 32 54
0 0 10
0 30 20
32 54 20
-40 30 20

机器里一共有4个齿轮，位于0,0的是半径为10的驱动齿轮，它带动了位于
0,30的，半径为20的某个齿轮。这个齿轮又间接带动了位于32,54，半径为20的
工作齿轮，以及一个位于-40,30，半径同样为20的冗余的齿轮。

Sample Output

20000

HINT

输出说明:

齿轮位置半径     转速

1 (0,0)     10     10,000

2 (0,30)    20     -5,000

3 (32,54)   20      5,000

                   ------

齿轮转速绝对值之和:20,000

Source

Silver

先BFS确定每个节点的父节点,然后从工作齿轮反向转


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
//
const int INF = 1e9;
struct node
{
    int x;
    int y;
    int r;
};
 
vector<int> mm;
vector<node> a;
node nt;
 
int n;
int sx,sy;
int ss;
int tt;
int f[200000];
int vis[200000];
 
 
void bfs(int ss)
{
    int cur,nex;
    queue<int> q;
    vis[ss] = 1;
    q.push(ss);
    while(!q.empty())
    {
        cur = q.front();
        q.pop();
        for(int j=0;j<n;j++)
        {
            if(vis[j]) continue;
 
            if( (a[cur].x - a[j].x)*(a[cur].x - a[j].x) + (a[cur].y - a[j].y)*(a[cur].y - a[j].y) == (a[cur].r+a[j].r)*(a[cur].r+a[j].r) )
            {
                f[j] = cur;
                q.push(j);
                vis[j] =1;
            }
        }
    }
    return ;
 
}
 
 
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    memset(f,-1,sizeof(f));
    cin >> n>>sx>>sy;
    for(int i=0;i<n;i++)
    {
        cin >> nt.x>>nt.y>>nt.r;
        a.push_back(nt);
        if(nt.x==0&&nt.y==0)
        {
            ss = a.size()-1;
        }
        else if(nt.x==sx&&nt.y==sy)
        {
            tt = a.size()-1;
        }
    }
 
 
    bfs(ss);
    vector<int> ans;
    ans.clear();
 
    int t = tt;
    ans.push_back(t);
    while(t!=ss)
    {
        t =f[t];
        ans.push_back(t);
//        cout << t <<endl;
    }
    reverse(ans.begin(),ans.end());
 
 
 
    double re = 0 ;
    double dt= 10000 ;
    re += dt;
    for(int i=1;i<ans.size();i++)
    {
        dt = dt*a[ans[i-1]].r/a[ans[i]].r;
        re += dt;
    }
    cout << (ll)re<<endl;
 
    return 0;
}

1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1357 Solved: 761
[ Submit][ Status][ Discuss]

Description

奶牛们在被划分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上游走，试图找到整块草地中最美味的牧草。Farmer John在某个时刻看见贝茜在位置 (R1, C1)，恰好T (0 < T <= 15)秒后，FJ又在位置(R2, C2)与贝茜撞了正着。 FJ并不知道在这T秒内贝茜是否曾经到过(R2, C2)，他能确定的只是，现在贝茜在那里。设S为奶牛在T秒内从(R1, C1)走到(R2, C2)所能选择的路径总数，FJ希望有一个程序来帮他计算这个值。每一秒内，奶牛会水平或垂直地移动1单位距离（奶牛总是在移动，不会在某秒内停在它上一秒所在的点）。草地上的某些地方有树，自然，奶牛不能走到树所在的位置，也不会走出草地。现在你拿到了一张整块草地的地形图，其中'.'表示平坦的草地，'*'表示挡路的树。你的任务是计算出，一头在T秒内从(R1, C1)移动到(R2, C2)的奶牛可能经过的路径有哪些。

Input

* 第1行: 3个用空格隔开的整数：N，M，T

* 第2..N+1行: 第i+1行为M个连续的字符，描述了草地第i行各点的情况，保证字符是'.'和'*'中的一个 * 第N+2行: 4个用空格隔开的整数：R1，C1，R2，以及C2

Output

* 第1行: 输出S，含义如题中所述

Sample Input

4 5 6
...*.
...*.
.....
.....
1 3 1 5

输入说明:

草地被划分成4行5列，奶牛在6秒内从第1行第3列走到了第1行第5列。

Sample Output

1

奶牛在6秒内从(1,3)走到(1,5)的方法只有一种（绕过她面前的树）。

HINT

Source

Silver

DP递推

dp[第t秒][i][j]

dp[k][i][j] += dp[k-1][xx][yy];


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
 
const int INF = 1e9;
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1}};
 
int n,m,t;
int sx,sy,ex,ey;
int mm[105][105];
string s;
int dp[20][105][105];
 
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >> n >> m >> t;
    for(int i=0;i<n;i++)
    {
        cin >> s;
        for(int j=0;j<m;j++)
        {
            if(s[j]=='*')
                mm[i][j] = 1;
        }
    }
    cin >> sx>>sy>>ex>>ey;
    sx--,sy--,ex--,ey--;
    dp[0][sx][sy] = 1;
    for(int k=1;k<=t;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(mm[i][j]) continue;
                for(int x=0;x<4;x++)
                {
                    int xx = i+dir[x][0];
                    int yy = j+dir[x][1];
                    if(xx<0 || xx>=n || yy<0 || yy>=m || mm[xx][yy]) continue;
                    dp[k][i][j] += dp[k-1][xx][yy];
                }
//                cout << dp[k][i][j]<<" ";
            }
//            cout <<endl;
        }
//        cout <<"&&&&&"<<endl;
    }
 
 
 
    cout <<dp[t][ex][ey] <<endl;
    return 0;
}

1617: [Usaco2008 Mar]River Crossing渡河问题

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1120 Solved: 817
[ Submit][ Status][ Discuss]

Description

Farmer John以及他的N(1 <= N <= 2,500)头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。由于奶牛不会划船，在整个渡河过程中，FJ必须始终在木筏上。在这个基础上，木筏上的奶牛数目每增加1，FJ把木筏划到对岸就得花更多的时间。当FJ一个人坐在木筏上，他把木筏划到对岸需要M(1 <= M <= 1000)分钟。当木筏搭载的奶牛数目从i-1增加到i时，FJ得多花M_i(1 <= M_i <= 1000)分钟才能把木筏划过河（也就是说，船上有1头奶牛时，FJ得花M+M_1分钟渡河；船上有2头奶牛时，时间就变成M+M_1+M_2分钟。后面的依此类推）。那么，FJ最少要花多少时间，才能把所有奶牛带到对岸呢？当然，这个时间得包括FJ一个人把木筏从对岸划回来接下一批的奶牛的时间。

Input

* 第1行: 2个用空格隔开的整数：N 和 M

* 第2..N+1行: 第i+1为1个整数：M_i

Output

* 第1行: 输出1个整数，为FJ把所有奶牛都载过河所需的最少时间

Sample Input

5 10
3
4
6
100
1

输入说明:

FJ带了5头奶牛出门。如果是单独把木筏划过河，FJ需要花10分钟，带上
1头奶牛的话，是13分钟，2头奶牛是17分钟，3头是23分钟，4头是123分钟，将
5头一次性载过去，花费的时间是124分钟。

Sample Output

HINT

输出说明:

Farmer John第一次带3头奶牛过河（23分钟），然后一个人划回来

（10分钟），最后带剩下的2头奶牛一起过河（17分钟），总共花费的时间是

23+10+17 = 50分钟。

Source

Silver

不同数量过河对应一个权值,且可以重复,直接利用完全背包


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
 
const int INF = 1e9;
int dp[2550];
 
int n,m;
int a[2550];
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        a[i] += a[i-1];
 
    }
    for(int i=1;i<=n;i++)
    {
        a[i] += (2*m);
    }
//    for(int i=0;i<=n;i++)
//    {
//        for(int j=0;j<=n;j++)
//        {
//            dp[i][j] = INF;
//        }
//    }
 
    dp[1] = a[1];
    for(int i=1;i<=n;i++)
    {
        dp[i] = a[i];
        for(int j=1;j<i;j++)
        {
            dp[i] = min(dp[i],dp[i-j]+a[j]);
        }
    }
//    for(int i=1;i<=n;i++)
//    {
//        cout << dp[i]<<" ";
//    }
//    cout <<endl;
    cout << dp[n]-m << endl;
    return 0;
}

1618: [Usaco2008 Nov]Buying Hay 购买干草

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1260 Solved: 657
[ Submit][ Status][ Discuss]

Description

约翰的干草库存已经告罄,他打算为奶牛们采购H(1≤H≤50000)磅干草,他知道N(1≤N≤100)个干草公司,现在用1到

N给它们编号。第i个公司卖的干草包重量为Pi(1≤Pi≤5000)磅,需要的开销为Ci(l≤Ci≤5000)美元．每个干草公

司的货源都十分充足,可以卖出无限多的干草包．帮助约翰找到最小的开销来满足需要,即采购到至少H磅干草

．

Input

第1行输入N和H，之后N行每行输入一个Pi和Ci．

Output

最小的开销．

Sample Input

2 15
3 2
5 3

Sample Output

9
FJ can buy three packages from the second supplier for a total cost of 9.

HINT

Source

Silver

类似于0-1背包,只是要往后多取些值


 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
 
const int INF = 1e9;
 
int n,m;
int p[105];
int c[105];
int dp[55010];
int maxx = 0;
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin >> p[i]>>c[i];
        maxx = max(maxx,p[i]);
    }
    int tt = m;
    m=m+maxx+5;
 
    for(int i=0;i<=m;i++)
    {
        dp[i] = INF;
    }
    dp[0] = 0;
    for(int i=1;i<=n;i++)
    {
        dp[ p[i] ] = c[i];
        for(int j=p[i];j<=m;j++)
        {
            dp[j] = min(dp[j],dp[ j-p[i] ] + c[i] );
        }
    }
    int ans = INF;
    for(int i=tt;i<=m;i++)
    {
        ans = min(ans,dp[i]);
    }
 
    cout << ans << endl;
    return 0;
}

1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 938 Solved: 423
[ Submit][ Status][ Discuss]

Description

The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows. He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns. Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000). Help him determine the number of hilltops on the map. A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.

农夫JOHN的农夫上有很多小山丘，他想要在那里布置一些保镖（……）去保卫他的那些相当值钱的奶牛们。他想知道如果在一座小山丘上布置一名保镖的话，他总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有N行（1 < N < = 100)和M列( 1 < M < = 70) 。矩阵中的每个元素都有一个值H_ij(0 < = H_ij < =10,000)来表示该地区的海拔高度。请你帮助他统计出地图上到底有多少个小山丘。小山丘的定义是：若地图中一个元素所邻接的所有元素都比这个元素高度要小（或它邻接的是地图的边界），则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是：若一个元素与另一个横坐标纵坐标和它的横纵坐标相差不超过1，则称这两个元素邻接。问题名称：guard 输入格式：第一行：两个由空格隔开的整数N和M 第二行到第N+1行：第I+1行描述了地图上的第I行，有M个由空格隔开的整数：H_ij. 输入样例：(guard.in): 8 7 4 3 2 2 1 0 1 3 3 3 2 1 0 1 2 2 2 2 1 0 0 2 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 2 2 1 1 0 0 1 1 1 2 1 0 输出格式: 第一行：小山丘的个数输出样例：(guard.out): 3 输出样例解释：地图上有三个小山丘：每个小山丘的山峰位置分别在左上角（高度为4），右上角（高度为1）和底部（高度为2）。

Input

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 describes row i of the matrix with M space-separated integers: H_ij

Output

* Line 1: A single integer that specifies the number of hilltops

Sample Input

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

Sample Output

HINT

三个山丘分别是：左上角的高度为4的方格，右上角的高度为1的方格，还有最后一行中高度为2的方格．

Source

Silver

从最高点灌水,,,灌水


 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
 
const int INF = 1e9;
int dir[8][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
int n,m;
int mm[1000][1000];
 
struct node{
    int x;
    int y;
    int w;
    bool operator<(const node x)const
    {
        return w>x.w;
    }
};
 
vector<node> a;
 
 
 
int vis[1000][1000];
 
void dfs(int x,int y)
{
    vis[x][y]=1;
    for(int i=0;i<8;i++)
    {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if(xx<=0||xx>n||yy<=0||yy>m||vis[xx][yy])
        {
            continue;
        }
        if(mm[xx][yy]<=mm[x][y])
        {
            dfs(xx,yy);
        }
    }
}
 
 
node nt;
 
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin >> mm[i][j];
            nt.x = i;
            nt.y = j;
            nt.w = mm[i][j];
            a.push_back(nt);
        }
    }
    sort(a.begin(),a.end());
 
    int ans = 0;
    for(int i=0;i<a.size();i++)
    {
        if(vis[a[i].x][a[i].y] ) continue;
        ans++;
        dfs(a[i].x,a[i].y);
    }
    cout << ans<<endl;
    return 0;
}

1620: [Usaco2008 Nov]Time Management 时间管理

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 867 Solved: 547
[ Submit][ Status][ Discuss]

Description

Ever the maturing businessman, Farmer John realizes that he must manage his time effectively. He has N jobs conveniently numbered 1..N (1 <= N <= 1,000) to accomplish (like milking the cows, cleaning the barn, mending the fences, and so on). To manage his time effectively, he has created a list of the jobs that must be finished. Job i requires a certain amount of time T_i (1 <= T_i <= 1,000) to complete and furthermore must be finished by time S_i (1 <= S_i <= 1,000,000). Farmer John starts his day at time t=0 and can only work on one job at a time until it is finished. Even a maturing businessman likes to sleep late; help Farmer John determine the latest he can start working and still finish all the jobs on time.

N个工作,每个工作其所需时间,及完成的Deadline,问要完成所有工作,最迟要什么时候开始.

Input

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: T_i and S_i

Output

* Line 1: The latest time Farmer John can start working or -1 if Farmer John cannot finish all the jobs on time.

Sample Input

4
3 5
8 14
5 20
1 16

INPUT DETAILS:

Farmer John has 4 jobs to do, which take 3, 8, 5, and 1 units of
time, respectively, and must be completed by time 5, 14, 20, and
16, respectively.

Sample Output

2

OUTPUT DETAILS:

Farmer John must start the first job at time 2. Then he can do
the second, fourth, and third jobs in that order to finish on time.

HINT

Source

Silver

从后往前贪心,假设工作都是在deadline紧挨着最后几天完成,这样可以防止时间浪费


 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
 
const int INF = 1e9;
//int dir[8][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
int n;
struct node
{
    int t;
    int s;
    bool operator < (const node x) const
    {
        return s>x.s;
    }
};
vector<node> a;
 
node nt;
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >>n;
    for(int i=0;i<n;i++)
    {
        cin >> nt.t>>nt.s;
        a.push_back(nt);
    }
 
    sort(a.begin(),a.end());
    int nd=0;
    for(int i=0;i<n-1;i++)
    {
        if(a[i].t>a[i].s-a[i+1].s)
        {
            nd += a[i].t-a[i].s+a[i+1].s;
        }
        else
        {
            nd -= a[i].s - a[i+1].s- a[i].t;
            if(nd<0) nd = 0;
        }
    }
 
    nd +=a[n-1].t;
//    cout <<nd<<endl;
    if(a[n-1].s -nd<0 )
    {
        cout <<-1<<endl;
    }
    else
    {
        cout <<a[n-1].s - nd<<endl;
    }
 
    return 0;
}

1621: [Usaco2008 Open]Roads Around The Farm分岔路口

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 914 Solved: 677
[ Submit][ Status][ Discuss]

Description

约翰的N(1≤N≤1,000,000,000)只奶牛要出发去探索牧场四周的土地．她们将沿着一条路走，一直走到三岔路口（可以认为所有的路口都是这样的）．这时候，这一群奶牛可能会分成两群，分别沿着接下来的两条路继续走．如果她们再次走到三岔路口，那么仍有可能继续分裂成两群继续走．奶牛的分裂方式十分古怪：如果这一群奶牛可以精确地分成两部分，这两部分的牛数恰好相差K(1≤K≤1000)，那么在三岔路口牛群就会分裂．否则，牛群不会分裂，她们都将在这里待下去，平静地吃草．请计算，最终将会有多少群奶牛在平静地吃草．

Input

两个整数N和K.

Output

最后的牛群数．

Sample Input

6 2

INPUT DETAILS:

There are 6 cows and the difference in group sizes is 2.

Sample Output

3

OUTPUT DETAILS:

There are 3 final groups (with 2, 1, and 3 cows in them).

6
/ \
2 4
/ \
1 3

HINT

6只奶牛先分成2只和4只．4只奶牛又分成1只和3只．最后有三群奶牛．

Source

Silver

DFS


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
 
const int INF = 1e9;
//int dir[8][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
int n,k;
int ans;
 
void dfs(int x)
{
//    cout << k<<endl;
    if(x<=k)
    {
        ans++;
        return ;
    }
 
    if((x-k)%2)
    {
        ans++;
        return ;
    }
 
    dfs((x-k)/2);
    dfs(x-(x-k)/2);
}
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >> n >> k;
    dfs(n);
    cout <<ans<<endl;
    return 0;
}

1622: [Usaco2008 Open]Word Power 名字的能量

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 630 Solved: 345
[ Submit][ Status][ Discuss]

Description

约翰想要计算他那N(1≤N≤1000)只奶牛的名字的能量．每只奶牛的名字由不超过1000个字待构成，没有一个名字是空字体串，约翰有一张“能量字符串表”，上面有M(1≤M≤100)个代表能量的字符串．每个字符串由不超过30个字体构成，同样不存在空字符串．一个奶牛的名字蕴含多少个能量字符串，这个名字就有多少能量．所谓“蕴含”，是指某个能量字符串的所有字符都在名字串中按顺序出现（不一定一个紧接着一个）．

所有的大写字母和小写字母都是等价的．比如，在贝茜的名字“Bessie”里，蕴含有“Be”

“sI”“EE”以及“Es”等等字符串，但不蕴含“lS”或“eB”．请帮约翰计算他的奶牛的名字的能量．

Input

第1行输入两个整数N和M，之后N行每行输入一个奶牛的名字，之后M行每行输入一个能量字符串．

Output

一共N行，每行一个整数，依次表示一个名字的能量．

Sample Input

5 3
Bessie
Jonathan
Montgomery
Alicia
Angola
se
nGo
Ont

INPUT DETAILS:

There are 5 cows, and their names are "Bessie", "Jonathan",
"Montgomery", "Alicia", and "Angola". The 3 good strings are "se",
"nGo", and "Ont".

Sample Output

1
1
2
0
1

OUTPUT DETAILS:

"Bessie" contains "se", "Jonathan" contains "Ont", "Montgomery" contains
both "nGo" and "Ont", Alicia contains none of the good strings, and
"Angola" contains "nGo".

HINT

Source

Silver

直接用栈开始暴力


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
 
const int INF = 1e9;
int n,m;
string a[1005];
string b[105];
string s;
 
 
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    int t = 'a'-'A';
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
        for(int j=0;j<a[i].size();j++)
        {
            if(a[i][j]>='a'&&a[i][j]<='z')
            {
                a[i][j] -= t;
            }
        }
    }
 
    for(int i=0;i<m;i++)
    {
        cin >> b[i];
 
        for(int j=0;j<b[i].size();j++)
        {
            if(b[i][j]>='a'&&b[i][j]<='z')
            {
                b[i][j] -= t;
            }
        }
    }
 
    stack<char> aa;
    for(int i=0;i<n;i++)
    {
        int ct = 0;
        int len1 = a[i].size();
        int len2;
        for(int j=0;j<m;j++)
        {
            int len2 = b[j].size();
 
            while(!aa.empty())  aa.pop();
 
            for(int k=len2-1;k>=0;k--)
            {
                aa.push(b[j][k]);
            }
 
            for(int k=0;k<len1;k++)
            {
                if(a[i][k]==aa.top())
                {
                    aa.pop();
                }
                if(aa.empty()) break;
            }
 
            if(aa.size()==0) ct++;
        }
        cout <<ct<<endl;
    }
 
    return 0;
}

1623: [Usaco2008 Open]Cow Cars 奶牛飞车

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 587 Solved: 410
[ Submit][ Status][ Discuss]

Description

编号为1到N的N只奶牛正各自驾着车打算在牛德比亚的高速公路上飞驰．高速公路有M(1≤M≤N)条车道．奶牛i有一个自己的车速上限Si(l≤Si≤1,000,000)．

在经历过糟糕的驾驶事故之后，奶牛们变得十分小心，避免碰撞的发生．每条车道上，如果某一只奶牛i的前面有K只奶牛驾车行驶，那奶牛i的速度上限就会下降K*D个单位，也就是说，她的速度不会超过Si - kD(O≤D≤5000)，当然如果这个数是负的，那她的速度将是0．牛德比亚的高速会路法规定，在高速公路上行驶的车辆时速不得低于/(1≤L≤1,000,000)．那么，请你计算有多少奶牛可以在高速公路上行驶呢？

Input

第1行输入N，M，D，L四个整数，之后N行每行一个整数输入Si．

N<=50000

Output

输出最多有多少奶牛可以在高速公路上行驶．

Sample Input

3 1 1 5//三头牛开车过一个通道.当一个牛进入通道时，它的速度V会变成V-D*X(X代表在它前面有多少牛),它减速后，速度不能小于L
5
7
5

INPUT DETAILS:

There are three cows with one lane to drive on, a speed decrease
of 1, and a minimum speed limit of 5.

Sample Output

2

OUTPUT DETAILS:

Two cows are possible, by putting either cow with speed 5 first and the cow
with speed 7 second.

HINT

Source

Silver

贪心,先计算出有奶牛前面最多可以多少奶牛,然后再挨个放,直到放满


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
 
const int INF = 1e9;
int n,m,d,l;
int s[100005];
int maxx[100005];
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >> n >> m >> d >> l;
    for(int i=0;i<n;i++)
    {
        cin >> s[i];
    }
    priority_queue<int, vector<int>, less<int> > q;
    for(int i=0;i<n;i++)
    {
        if(s[i]<l)
        {
            s[i]=-1;
        }
        else
        {
            s[i] = (s[i]-l) / d;
        }
        q.push(s[i]);
    }
 
    for(int i=0;i<m;i++)
    {
        maxx[i] = INF;
    }
    int ans = 0;
    while(!q.empty())
    {
        int f = 1;
        for(int i=0;i<m&&(!q.empty());i++)
        {
            int x = q.top();
            if(maxx[i]<=0||x==-1)  continue;
            q.pop();
            f = 0;
            ans++;
            maxx[i] =  min(maxx[i]-1,x);
        }
        if(f) break;
    }
    cout << ans<<endl;
    return 0;
}

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 799 Solved: 522
[ Submit][ Status][ Discuss]

Description

农夫约翰正驾驶一条小艇在牛勒比海上航行．

海上有N(1≤N≤100)个岛屿，用1到N编号．约翰从1号小岛出发，最后到达N号小岛．一

张藏宝图上说，如果他的路程上经过的小岛依次出现了Ai，A2，…，AM(2≤M≤10000)这样的序列（不一定相邻），那他最终就能找到古老的宝藏．但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数Dij(0≤Dij≤100000)来描述．他希望他的寻宝活动经过的航线危险指数之和最小．那么，在找到宝藏的前提下，这个最小的危险指数是多少呢？

Input

第1行输入N和M，之后M行一行一个整数表示A序列，之后输入一个NxN的方阵，表示两两岛屿之间航线的危险指数．数据保证Dij=Dji，Dii=0．

Output

最小的危险指数和．

Sample Input

3 4
1
2
1
3
0 5 1
5 0 2
1 2 0

INPUT DETAILS:

There are 3 islands and the treasure map requires Farmer John to
visit a sequence of 4 islands in order: island 1, island 2, island
1 again, and finally island 3. The danger ratings of the paths are
given: the paths (1, 2); (2, 3); (3, 1) and the reverse paths have
danger ratings of 5, 2, and 1, respectively.

Sample Output

7

OUTPUT DETAILS:

He can get the treasure with a total danger of 7 by traveling in
the sequence of islands 1, 3, 2, 3, 1, and 3. The cow map's requirement
(1, 2, 1, and 3) is satisfied by this route. We avoid the path
between islands 1 and 2 because it has a large danger rating.

HINT

Source

Silver

Flod求最短路跑一遍


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
 
const int INF = 1e9;
 
int n,t,m;
ll mm[105][105];
vector<int> a;
 
int main()
{
//        freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >> n >>m;
    for(int i=0;i<m;i++)
    {
        cin >> t;
        t--;
        a.push_back(t);
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin >> mm[i][j];
        }
    }
 
    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(mm[i][j]>mm[i][k]+mm[k][j])
                    mm[i][j]=mm[i][k]+mm[k][j];
            }
        }
    }
 
    ll ans = 0;
 
    ans += mm[    0   ][ a[0] ];
    ans += mm[ a[m-1] ][ n-1  ];
 
    for(int i=0;i<m-1;i++)
    {
        ans+= mm[ a[i]  ][  a[i+1] ];
    }
    cout << ans<<endl;
    return 0;
}

1625: [Usaco2007 Dec]宝石手镯

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1373 Solved: 975
[ Submit][ Status][ Discuss]

Description

贝茜在珠宝店闲逛时，买到了一个中意的手镯。很自然地，她想从她收集的 N(1 <= N <= 3,402)块宝石中选出最好的那些镶在手镯上。对于第i块宝石，它的重量为W_i(1 <= W_i <= 400)，并且贝茜知道它在镶上手镯后能为自己增加的魅力值D_i(1 <= D_i <= 100)。由于贝茜只能忍受重量不超过M(1 <= M <= 12,880)的手镯，她可能无法把所有喜欢的宝石都镶上。于是贝茜找到了你，告诉了你她所有宝石的属性以及她能忍受的重量，希望你能帮她计算一下，按照最合理的方案镶嵌宝石的话，她的魅力值最多能增加多少。

Input

* 第1行: 2个用空格隔开的整数：N 和 M

* 第2..N+1行: 第i+1行为2个用空格隔开的整数：W_i、D_i，分别为第i块宝石的重量与能为贝茜增加的魅力值

Output

* 第1行: 输出1个整数，表示按照镶嵌要求，贝茜最多能增加的魅力值

Sample Input

4 6
1 4
2 6
3 12
2 7

输入说明:

贝茜收集了4块宝石，她能忍受重量最大为6的手镯。

Sample Output

23

输出说明:

贝茜把除了第二块宝石的其余所有宝石都镶上手镯，这样她能增加
4+12+7=23的魅力值，并且所有宝石的重量为1+2+3 <= 6，同样符合要求。

HINT

Source

Silver

0-1背包


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
 
const int INF = 1e9;
 
int n,t,m;
int dp[2][13880];
int w[4000];
int v[4000];
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >> n >>m;
 
    for(int i=1;i<=n;i++)
    {
        cin >> w[i]>>v[i];
    }
 
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i&1][j] = dp[(i-1)&1][j];
            if(j>=w[i])
            {
                dp[i&1][j] = max(dp[i&1][j] , dp[(i-1)&1][j-w[i]]+v[i]);
            }
        }
    }
    cout <<dp[n&1][m]<<endl;
    return 0;
}

1626: [Usaco2007 Dec]Building Roads 修建道路

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1768 Solved: 745
[ Submit][ Status][ Discuss]

Description

Farmer John最近得到了一些新的农场，他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达（也就是说，从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场）。有些农场之间原本就有道路相连。所有N(1 <= N <= 1,000)个农场（用1..N顺次编号）在地图上都表示为坐标为(X_i, Y_i)的点(0 <= X_i <= 1,000,000；0 <= Y_i <= 1,000,000)，两个农场间道路的长度自然就是代表它们的点之间的距离。现在Farmer John也告诉了你农场间原有的M(1 <= M <= 1,000)条路分别连接了哪两个农场，他希望你计算一下，为了使得所有农场连通，他所需建造道路的最小总长是多少。

Input

* 第1行: 2个用空格隔开的整数：N 和 M

* 第2..N+1行: 第i+1行为2个用空格隔开的整数：X_i、Y_i * 第N+2..N+M+2行: 每行用2个以空格隔开的整数i、j描述了一条已有的道路，这条道路连接了农场i和农场j

Output

* 第1行: 输出使所有农场连通所需建设道路的最小总长，保留2位小数，不必做任何额外的取整操作。为了避免精度误差，计算农场间距离及答案时请使用64位实型变量

Sample Input

4 1
1 1
3 1
2 3
4 3
1 4

输入说明:

FJ一共有4个坐标分别为(1,1)，(3,1)，(2,3)，(4,3)的农场。农场1和农场
4之间原本就有道路相连。

Sample Output

4.00

输出说明:

FJ选择在农场1和农场2间建一条长度为2.00的道路，在农场3和农场4间建一
条长度为2.00的道路。这样，所建道路的总长为4.00，并且这是所有方案中道路
总长最小的一种。

HINT

Source

Silver

并查集确定有几个联通块,然后把连通块缩为一个点,然后最短路求解


 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
 
const int INF = 1e9;
 
int n,t,m;
double x[1005];
double y[1005];
int fa[1005];
vector<int> mm[1005];
int fi(int x)
{
    return fa[x]==x?x:fa[x]=fi(fa[x]);
}
void uni(int xx,int yy)
{
    xx = fi(xx);
    yy = fi(yy);
    fa[xx]=yy;
}
double getdis(int xx,int yy)
{
    return sqrt( (x[xx]-x[yy])*(x[xx]-x[yy])+(y[xx]-y[yy])*(y[xx]-y[yy]) );
}
 
 
const int MAXN=1100;//最大点数
const int MAXM=1001000;//最大边数
int F[MAXN];//并查集使用
 
struct Edge
{
    int u,v;
    double w;
}edge[MAXM];//储存边的信息，包括起点/终点/权值
 
int tol=0;//边数，加边前赋值为0
 
 
 
void addedge(int u,int v,double w)
{
    edge[tol].u=u;
    edge[tol].v=v;
    edge[tol++].w=w;
}
void init()
{
    tol=0;
}
 
bool cmp(Edge a,Edge b)//排序函数，边按照权值从小到大排序
{
    return a.w<b.w;
}
 
int Find(int x)
{
    if(F[x]==-1)
        return x;
    else
        return F[x]=Find(F[x]);
}
 
double Kruskal(int n)//传入点数，返回最小生成树的权值，如果不连通返回-1
{
    memset(F,-1,sizeof(F));
    sort(edge,edge+tol,cmp);
    int cnt=0;//计算加入的边数
    double ans=0;
    for(int i=0;i<tol;i++)
    {
        int    u=edge[i].u;
        int    v=edge[i].v;
        double w=edge[i].w;
        int t1=Find(u);
        int t2=Find(v);
        if(t1!=t2)
        {
 
            ans+=w;
            F[t1]=t2;
            cnt++;
        }
        if(cnt==n-1)
            break;
    }
    if(cnt<n-1)
        return -1;//不连通
    else
        return ans;
}
 
 
int main()
{
//    freopen("data.txt","r",stdin);
//    ios_base::sync_with_stdio(false);
    cin >> n >>m;
    for(int i=1;i<=n;i++)
    {
        fa[i] = i;
        cin >> x[i]>>y[i];
    }
    int u,v;
    for(int i=0;i<m;i++)
    {
        cin >> u>>v;
        uni(u,v);
    }
 
    for(int i=1;i<=n;i++)
    {
        fi(i);
    }
 
    set<int> ss;
    set<int>::iterator it;
    ss.clear();
 
    for(int i=1;i<=n;i++)
    {
        mm[fa[i]].push_back(i);
        ss.insert(fa[i]);
    }
 
    vector<int> a;
    a.clear();
 
    for(it = ss.begin();it!=ss.end();it++)
    {
        a.push_back(*it);
    }
 
    init();
    int len = a.size();
    for(int i=0;i<len;i++)
    {
        for(int j=i+1;j<len;j++)
        {
            int xx = a[i];
            int yy = a[j];
            double dis = 1e18;
            for(int k=0;k<mm[xx].size();k++)
            {
                for(int z=0;z<mm[yy].size();z++)
                {
                    dis = min(dis,getdis( mm[xx][k],mm[yy][z] ) );
                }
            }
            addedge(xx,yy,dis);
            addedge(yy,xx,dis);
        }
    }
 
    printf("%.2f\n",Kruskal(len)) ;
 
    return 0;
}

1627: [Usaco2007 Dec]穿越泥地

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 780 Solved: 526
[ Submit][ Status][ Discuss]

Description

清早6：00，Farmer John就离开了他的屋子，开始了他的例行工作：为贝茜挤奶。前一天晚上，整个农场刚经受过一场瓢泼大雨的洗礼，于是不难想见，FJ 现在面对的是一大片泥泞的土地。FJ的屋子在平面坐标(0, 0)的位置，贝茜所在的牛棚则位于坐标(X,Y) (-500 <= X <= 500; -500 <= Y <= 500)处。当然咯， FJ也看到了地上的所有N(1 <= N <= 10,000)个泥塘，第i个泥塘的坐标为 (A_i, B_i) (-500 <= A_i <= 500；-500 <= B_i <= 500)。每个泥塘都只占据了它所在的那个格子。 Farmer John自然不愿意弄脏他新买的靴子，但他同时想尽快到达贝茜所在的位置。为了数那些讨厌的泥塘，他已经耽搁了一些时间了。如果Farmer John 只能平行于坐标轴移动，并且只在x、y均为整数的坐标处转弯，那么他从屋子门口出发，最少要走多少路才能到贝茜所在的牛棚呢？你可以认为从FJ的屋子到牛棚总是存在至少一条不经过任何泥塘的路径。

Input

* 第1行: 3个用空格隔开的整数：X，Y 和 N

* 第2..N+1行: 第i+1行为2个用空格隔开的整数：A_i 和 B_i

Output

* 第1行: 输出1个整数，即FJ在不踏进泥塘的情况下，到达贝茜所在牛棚所需要走过的最小距离

Sample Input

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

输入说明:

贝茜所在牛棚的坐标为(1, 2)。Farmer John能看到7个泥塘，它们的坐标分
别为(0, 2)、(-1, 3)、(3, 1)、(1, 1)、(4, 2)、(-1, 1)以及(2, 2)。
以下为农场的简图：（*为FJ的屋子，B为贝茜呆的牛棚）

4 . . . . . . . .
3 . M . . . . . .
Y 2 . . M B M . M .
1 . M . M . M . .
0 . . * . . . . .
-1 . . . . . . . .
-2-1 0 1 2 3 4 5

X

Sample Output

HINT

约翰的最佳路线是：(0，0)，（一1，0），（一2，0），（一2，1），（一2，2），（一2，3），（一2，4），（一1，4），(0,4), (0,3), (1,3), (1,2).

Source

Silver

坐标都加上一个数
直接BFS求解


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
//const int MAXN=1100;//最大点数
//const int MAXM=100100;//最大边数
 
const int INF = 1e9;
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int n,x,y;
int mm[1010][1010];
int vis[1010][1010];
int xx,yy;
int m = 502;
 
struct node{
    int x;
    int y;
    int step;
};
 
int bfs()
{
    node cur,nex;
    queue<node> q;
    cur.x=m;
    cur.y=m;
    cur.step =0;
    vis[m][m]=1;
    q.push(cur);
    while(!q.empty())
    {
        cur = q.front();
        q.pop();
//        cout <<cur.x<<" "<<cur.y<<" "<<cur.step<<endl;
        if(cur.x==x&&cur.y==y)
            return cur.step;
        for(int i=0;i<4;i++)
        {
            int x1 = cur.x+dir[i][0];
            int y1 = cur.y+dir[i][1];
            if(x1<0||y1<0||x1>=1010||y1>=1010||vis[x1][y1]||mm[x1][y1])
            {
                continue;
            }
            nex.x = x1;
            nex.y = y1;
            nex.step = cur.step + 1;
            q.push(nex);
            vis[x1][y1]=1;
        }
    }
}
 
 
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >> x>>y >>n;
    x += m;
    y += m;
//    cout << x<<" "<<y<<endl;
    for(int i=0;i<n;i++)
    {
        cin >> xx>>yy;
        xx+=m;
        yy+=m;
        mm[xx][yy]=1;
    }
    cout <<bfs()<<endl;
 
 
    return 0;
}

1628: [Usaco2007 Demo]City skyline

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 576 Solved: 447
[ Submit][ Status][ Discuss]

Description

Input

第一行给出N，W

第二行到第N+1行:每行给出二个整数x,y，输入的x严格递增，并且第一个x总是1

Output

输出一个整数，表示城市中最少包含的建筑物数量

Sample Input

10 26
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1

INPUT DETAILS:

The case mentioned above

Sample Output

HINT

Source

Silver

维护一个优先队列,如果其出现了一个矮的方格,则把比矮方格大的数弹出

也可单调栈


 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int INF = 1e9;
 
 
 
int n;
int w;
int x,y;
int vis[500005];
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >> n>>w;
    priority_queue<int> q;
    int ans =0 ;
    q.push(0);
    vis[0]=1;
    for(int i=0;i<n;i++)
    {
        cin >> x >> y;
        if((!q.empty())&&q.top()>=y)
        {
            while((!q.empty())&&q.top()>y)
            {
                vis[q.top()]=0;
                q.pop();
            }
            if(vis[y]==0)
            {
//                cout << y<<endl;
                ans++;
                vis[y]=1;
                q.push(y);
            }
        }
        else
        {
            ans++;
            q.push(y);
            vis[y]=1;
        }
 
    }
    cout <<ans<<endl;
 
    return 0;
}


#include <bits/stdc++.h>
using namespace std;
 
const int maxn=50000+5;
int n,m,top,ans;
int a[maxn],s[maxn];
int main(){
    scanf("%d%d",&n,&m); ans=n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]), scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        while(s[top]>a[i]) top--;
        if(s[top]==a[i]) ans--;
        else s[++top]=a[i];
    }
    printf("%d\n",ans);
    return 0;
}

1629: [Usaco2007 Demo]Cow Acrobats

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1065 Solved: 545
[ Submit][ Status][ Discuss]

Description

Farmer John's N (1 <= N <= 50,000) cows (numbered 1..N) are planning to run away and join the circus. Their hoofed feet prevent them from tightrope walking and swinging from the trapeze (and their last attempt at firing a cow out of a cannon met with a dismal failure). Thus, they have decided to practice performing acrobatic stunts. The cows aren't terribly creative and have only come up with one acrobatic stunt: standing on top of each other to form a vertical stack of some height. The cows are trying to figure out the order in which they should arrange themselves within this stack. Each of the N cows has an associated weight (1 <= W_i <= 10,000) and strength (1 <= S_i <= 1,000,000,000). The risk of a cow collapsing is equal to the combined weight of all cows on top of her (not including her own weight, of course) minus her strength (so that a stronger cow has a lower risk). Your task is to determine an ordering of the cows that minimizes the greatest risk of collapse for any of the cows. //有三个头牛，下面三行二个数分别代表其体重及力量 //它们玩叠罗汉的游戏，每个牛的危险值等于它上面的牛的体重总和减去它的力量值，因为它要扛起上面所有的牛嘛. //求所有方案中危险值最大的最小

Input

* Line 1: A single line with the integer N. * Lines 2..N+1: Line i+1 describes cow i with two space-separated integers, W_i and S_i.

Output

* Line 1: A single integer, giving the largest risk of all the cows in any optimal ordering that minimizes the risk.

Sample Input

3
10 3
2 5
3 3

Sample Output

2

OUTPUT DETAILS:

Put the cow with weight 10 on the bottom. She will carry the other
two cows, so the risk of her collapsing is 2+3-3=2. The other cows
have lower risk of collapsing.

HINT

Source

Silver

贪心算法,感觉好难想

【分析】假设我们必须把A放在B的上面。设A的重量和力量是w1，a1，B的是w2，a2。如果A在上面，B的危险值就是S+w1-a2.（其中S是之前的奶牛重量和）。如果A在下面，A的危险值就是S+w2-a1.设A在B上面更优，所以S+w1-a2<=s+w2-a1,整理后可得：w1+a1<=w2+a2。因此，我们要把总和小的放在前面！


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int INF = 1e9;
 
int n,m;
 
struct node
{
    int w;
    int s;
    bool operator < (const node & x) const
    {
        return w+s<x.s+x.w;
    }
};
 
node nt;
vector<node> a;
int main()
{
//    freopen("data.txt","r",stdin);
//    ios_base::sync_with_stdio(false);
 
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin >>nt.w>>nt.s;
        a.push_back(nt);
    }
 
    sort(a.begin(),a.end());
    int ans = -a[0].s;
    int ss = a[0].w;
    for(int i=1;i<n;i++)
    {
        ans = max(ans,ss- a[i].s);
        ss+=a[i].w;
    }
    cout << ans<<endl;
    return 0;
}

1631: [Usaco2007 Feb]Cow Party

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 884 Solved: 639
[ Submit][ Status][ Discuss]

Description

农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共有M(1≤M≤100000)条单向路连接着牛棚，第i条踣需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？

Input

第1行:三个用空格隔开的整数.

第2行到第M+1行,每行三个用空格隔开的整数:Ai, Bi,以及Ti.表示一条道路的起点,终点和需要花费的时间.

Output

唯一一行:一个整数: 所有参加聚会的奶牛中,需要花费总时间的最大值.

Sample Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

Sample Output

HINT

样例说明:

共有4只奶牛参加聚会,有8条路,聚会位于第2个农场.

第4只奶牛可以直接到聚会所在地(花费3时间),然后返程路线经过第1和第3个农场(花费7时间),总共10时间.

Source

Silver

[ Submit][ Status][ Discuss] 最短路,

正着一次,然后把边逆置再跑一边


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int INF = 1e9;
 
int n,m;
const int MAXN = 1e5+5;
const int MAXM = 1e6+4;
struct node{
    int x,d;
    node(){}
    node(int a,int b){x=a;d=b;}
    bool operator < (const node &a) const
    {
        if(d==a.d) return x<a.x;
        else return     d>a.d;
 
    }
 
};
 
class Dijkstra_queue{
 
public:
    void init()
    {
        for(int i=0;i<=n;i++)
        {
            eg[i].clear();
        }
        for(int i=0;i<=n;i++)
        {
            dist[i] = INF;
        }
    }
    void Run(int s)
    {
        dist[s] = 0;
        priority_queue<node> q;
        q.push(node(s,dist[s]));
        while(!q.empty())
        {
            node x = q.top();
            q.pop();
            for(int i=0;i<eg[x.x].size();i++)
            {
                node y = eg[x.x][i];
                if(dist[y.x] >x.d+y.d )
                {
                    dist[y.x] = x.d + y.d;
                    q.push(node(y.x,dist[y.x]));
                }
            }
        }
    }
    void addEdge(int u,int v,int w)
    {
        eg[u].push_back(node(v,w));
    }
public:
    int dist[MAXN];
private:
    vector<node> eg[MAXN];
};
 
 
int u[MAXN],v[MAXN],w[MAXN];
int ans[MAXN];
int x;
 
 
Dijkstra_queue di;
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >> n>>m>>x;
    for(int i=1;i<=m;i++)
    {
        cin >> u[i] >>v[i] >>w[i];
    }
 
    di.init();
    for(int i=1;i<=m;i++)
    {
        di.addEdge(u[i],v[i],w[i]);
    }
    di.Run(x);
    for(int i=1;i<=n;i++)
    {
//        cout << di.dist[i]<<" ->"<<endl;
         ans[i]+=di.dist[i];
    }
 
 
 
    di.init();
    for(int i=1;i<=m;i++)
    {
        di.addEdge(v[i],u[i],w[i]);
    }
    di.Run(x);
    for(int i=1;i<=n;i++)
    {
//        cout << di.dist[i]<<endl;
        ans[i]+=di.dist[i];
    }
 
    cout << *max_element(ans+1,ans+n+1)<<endl;
    return 0;
}

1633: [Usaco2007 Feb]The Cow Lexicon 牛的词典

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 639 Solved: 362
[ Submit][ Status][ Discuss]

Description

没有几个人知道,奶牛有她们自己的字典,里面的有W (1 ≤ W ≤ 600)个词,每个词的长度不超过25,且由小写字母组成.她们在交流时,由于各种原因,用词总是不那么准确.比如,贝茜听到有人对她说"browndcodw",确切的意思是"browncow",多出了两个"d",这两个"d"大概是身边的噪音. 奶牛们发觉辨认那些奇怪的信息很费劲,所以她们就想让你帮忙辨认一条收到的消息,即一个只包含小写字母且长度为L (2 ≤ L ≤ 300)的字符串.有些时候,这个字符串里会有多余的字母,你的任务就是找出最少去掉几个字母就可以使这个字符串变成准确的"牛语"(即奶牛字典中某些词的一个排列).

Input

第1行:两个用空格隔开的整数,W和L.

第2行:一个长度为L的字符串,表示收到的信息. 第3行至第W+2行:奶牛的字典,每行一个词.

Output

唯一一行:一个整数,表示最少去掉几个字母就可以使之变成准确的"牛语".

Sample Input

6 10
browndcodw
cow
milk
white
black
brown
farmer

Sample Output

HINT

Source

Silver

动态规划：

dp[i]，表示前面i位需要去掉的最小的数目，

对当前i位，枚举每一个单词需要去掉的个数。


/**************************************************************
    Problem: 1633
    User: RoyYuan
    Language: C++
    Result: Accepted
    Time:196 ms
    Memory:1300 kb
****************************************************************/
 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int INF = 1e9;
 
string w[1000];
char s[1000];
int n,m;
int dp[500];
 
 
int main()
{
//    freopen("data.txt","r",stdin);
//    ios_base::sync_with_stdio(false);
    cin >> n>>m;
    cin >> s+1;
 
    for(int i=0;i<n;i++)
    {
        cin >>w[i];
    }
    for(int i=0;i<=m;i++)
    {
        dp[i] = i;
    }
 
    stack<char> ss;
    for(int i=1;i<=m;i++)
    {
        for(int k=0;k<n;k++)
        {
            int len = w[k].size();
 
            while(!ss.empty()) ss.pop();
 
            for(int j=0;j<len;j++)
            {
                ss.push(w[k][j]);
            }
 
            int cur = i;
            while(cur>0&&(!ss.empty()))
            {
                if(s[cur]==ss.top())
                {
                    ss.pop();
                }
                cur--;
            }
 
            if(ss.size()>0)
                continue;
 
            dp[i] = min( dp[i], dp[cur]+i-cur-len) ;
        }
//        cout <<dp[i]<<endl;
    }
 
    cout <<dp[m]<<endl;
    return 0;
}

1634: [Usaco2007 Jan]Protecting the Flowers 护花

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 865 Solved: 562
[ Submit][ Status][ Discuss]

Description

Farmer John went to cut some wood and left N (2 <= N <= 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cows were in his garden eating his beautiful flowers. Wanting to minimize the subsequent damage, FJ decided to take immediate action and transport the cows back to their barn. Each cow i is at a location that is Ti minutes (1 <= Ti <= 2,000,000) away from the barn. Furthermore, while waiting for transport, she destroys Di (1 <= Di <= 100) flowers per minute. No matter how hard he tries,FJ can only transport one cow at a time back to the barn. Moving cow i to the barn requires 2*Ti minutes (Ti to get there and Ti to return). Write a program to determine the order in which FJ should pick up the cows so that the total number of flowers destroyed is minimized.

约翰留下他的N只奶牛上山采木．他离开的时候，她们像往常一样悠闲地在草场里吃草．可是，当他回来的时候，他看到了一幕惨剧：牛们正躲在他的花园里，啃食着他心爱的美丽花朵！为了使接下来花朵的损失最小，约翰赶紧采取行动，把牛们送回牛棚．牛们从1到N编号．第i只牛所在的位置距离牛棚Ti(1≤Ti《2000000)分钟的路程，而在约翰开始送她回牛棚之前，她每分钟会啃食Di(1≤Di≤100)朵鲜花．无论多么努力，约翰一次只能送一只牛回棚．而运送第第i只牛事实上需要2Ti分钟，因为来回都需要时间．写一个程序来决定约翰运送奶牛的顺序，使最终被吞食的花朵数量最小．

Input

* Line 1: A single integer

N * Lines 2..N+1: Each line contains two space-separated integers, Ti and Di, that describe a single cow's characteristics

第1行输入N，之后N行每行输入两个整数Ti和Di．

Output

* Line 1: A single integer that is the minimum number of destroyed flowers

一个整数，表示最小数量的花朵被吞食．

Sample Input

6
3 1
2 5
2 3
3 2
4 1
1 6

Sample Output

HINT

约翰用6，2，3，4，1，5的顺序来运送他的奶牛．

Source

Silver

贪心，调换两个牛的位置，然后判断

(double)a[i]/b[i];

根据这个排序，贪心选择


/**************************************************************
    Problem: 1634
    User: RoyYuan
    Language: C++
    Result: Accepted
    Time:168 ms
    Memory:4380 kb
****************************************************************/
 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int INF = 1e9;
 
struct node
{
    double v;
    int ind;
    bool operator < (const node & x) const
    {
        return v < x.v;
    }
};
 
vector<node> aa;
int n;
node nt;
 
int a[100005];
int b[100005];
 
 
int main()
{
//    freopen("data.txt","r",stdin);
//    ios_base::sync_with_stdio(false);
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> a[i] >> b[i];
        nt.ind = i;
        nt.v = (double)a[i]/b[i];
        aa.push_back(nt);
    }
    sort(aa.begin(),aa.end());
    ll tt=0;
    ll ans = 0;
    for(int i=0;i<n;i++)
    {
        ans += b[ aa[i].ind  ]*2*tt;
        tt+=a[ aa[i].ind  ];
    }
 
    cout << ans<<endl;
 
    return 0;
}

1635: [Usaco2007 Jan]Tallest Cow 最高的牛

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 687 Solved: 425
[ Submit][ Status][ Discuss]

Description

FJ's N (1 <= N <= 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (which is a bit of secret). You are told only the height H (1 <= H <= 1,000,000) of the tallest cow along with the index I of that cow. FJ has made a list of R (0 <= R <= 10,000) lines of the form "cow 17 sees cow 34". This means that cow 34 is at least as tall as cow 17, and that every cow between 17 and 34 has a height that is strictly smaller than that of cow 17. For each cow from 1..N, determine its maximum possible height, such that all of the information given is still correct. It is guaranteed that it is possible to satisfy all the constraints.

有n(1 <= n <= 10000)头牛从１到n线性排列，每头牛的高度为h[i](1 <= i <= n),现在告诉你这里面的牛的最大高度为maxH,而且有r组关系，每组关系输入两个数字，假设为a和b,表示第a头牛能看到第b头牛，能看到的条件是a, b之间的其它牛的高度都严格小于min(h[a], h[b]),而h[b] >= h[a]

Input

* Line 1: Four space-separated integers: N, I, H and R

* Lines 2..R+1: Two distinct space-separated integers A and B (1 <= A, B <= N), indicating that cow A can see cow B.

Output

* Lines 1..N: Line i contains the maximum possible height of cow i.

Sample Input

9 3 5 5
1 3
5 3
4 3
3 7
9 8

INPUT DETAILS:

There are 9 cows, and the 3rd is the tallest with height 5.

Sample Output

5
4
5
3
4
4
5
5
5

HINT

Source

Silver

[ Submit][ Status][ Discuss]
HOME Back

结果初始化为最大的,对于每个区间减1


 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int INF = 1e9;
 
int n,h,m,ind;
struct node
{
    int l,r;
    bool operator < (const node &x) const
    {
        if(l==x.l)
            return r<x.r;
        return l < x.l;
    }
};
set<node> a;
set<node>::iterator it;
int ans[10005];
node nt;
 
 
int main()
{
//    freopen("data.txt","r",stdin);
//    ios_base::sync_with_stdio(false);
    cin >> n >> ind >>h>>m;
    for(int i=1;i<=n;i++)
    {
        ans[i] = h;
    }
 
    for(int i=0;i<m;i++)
    {
        cin >>nt.l>>nt.r;
        a.insert(nt);
    }
 
 
    for(it=a.begin();it!=a.end();it++)
    {
        int l = it->l ;
        int r = it->r;
        if(l>r)
            swap(l,r);
 
        for(int j = l+1;j<r;j++)
        {
            ans[j]--;
        }
    }
 
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

1636: [Usaco2007 Jan]Balanced Lineup

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 951 Solved: 673
[ Submit][ Status][ Discuss]

Description

For the daily milking, Farmer John's N cows (1 <= N <= 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height. Farmer John has made a list of Q (1 <= Q <= 200,000) potential groups of cows and their heights (1 <= height <= 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John
决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛.
但是为了避免水平悬殊,牛的身高不应该相差太大.
John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <=
身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别.
注意: 在最大数据上, 输入和输出将占用大部分运行时间.

Input

* Line 1: Two space-separated integers, N and Q. * Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i * Lines N+2..N+Q+1: Two integers A and B (1 <= A <= B <= N), representing the range of cows from A to B inclusive.

Output

6 3

1 5

4 6

2 2

Sample Input

* Lines 1..Q: Each line contains a single integer that is a response
to a reply and indicates the difference in height between the
tallest and shortest cow in the range.

Sample Output

6
3
0

HINT

Source

Silver

两次RMQ


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int INF = 1e9;
const int MAXN = 50010;
int dp[MAXN][20];
int mm[MAXN];
int xx[MAXN];
int dp1[MAXN][20];
int b[MAXN];
//初始化RMQ, b数组下标从1开始
void initRMQ(int n)
{
    mm[0] = -1;
    for(int i = 1; i <= n;i++)
    {
        mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1];
        dp[i][0] = b[i];
    }
    for(int j = 1; j <= mm[n];j++)
        for(int i = 1;i + (1<<j) -1 <= n;i++)
            dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
 
 
    xx[0] = -1;
    for(int i = 1; i <= n;i++)
    {
        xx[i] = ((i&(i-1)) == 0)?xx[i-1]+1:xx[i-1];
        dp1[i][0] = b[i];
    }
    for(int j = 1; j <= xx[n];j++)
        for(int i = 1;i + (1<<j) -1 <= n;i++)
            dp1[i][j] = min(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
 
}
 
//查询最大值
int rmq_max(int x,int y)
{
    int k = mm[y-x+1];
    return max(dp[x][k],dp[y-(1<<k)+1][k]);
}
 
 
int rmq_min(int x,int y)
{
    int k = xx[y-x+1];
    return min(dp1[x][k],dp1[y-(1<<k)+1][k]);
}
 
 
 
 
int n,q;
int l,r;
 
 
 
int main()
{
//    freopen("data.txt","r",stdin);
//    ios_base::sync_with_stdio(false);
    n = read();
    q = read();
    for(int i=1;i<=n;i++)
    {
        b[i] = read();
    }
    initRMQ(n);
    while(q--)
    {
        l = read();
        r = read();
        printf("%d\n",rmq_max(l,r)-rmq_min(l,r));
    }
    return 0;
}

1637: [Usaco2007 Mar]Balanced Lineup

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 724 Solved: 477
[ Submit][ Status][ Discuss]

Description

Farmer John 决定给他的奶牛们照一张合影，他让 N (1 ≤ N ≤ 50,000) 头奶牛站成一条直线，每头牛都有它的

坐标(范围: 0..1,000,000,000)和种族(0或1)。一直以来 Farmer John 总是喜欢做一些非凡的事，当然这次照相

也不例外。他只给一部分牛照相，并且这一组牛的阵容必须是“平衡的”。平衡的阵容，指的是在一组牛中，种族

0和种族1的牛的数量相等。请算出最广阔的区间，使这个区间内的牛阵容平衡。区间的大小为区间内最右边的牛

的坐标减去最做边的牛的坐标。输入中，每个种族至少有一头牛，没有两头牛的坐标相同。

Input

行 1: 一个整数: N 行 2..N + 1: 每行两个整数，为种族 ID 和 x 坐标。

Output

行 1: 一个整数，阵容平衡的最大的区间的大小。

Sample Input

7
0 11
1 10
1 25
1 12
1 4
0 13
1 22

Sample Output

HINT

输入说明

有7头牛，像这样在数轴上。

输出说明

牛 #1 (at 11), #4 (at 12), #6 (at 13), #7 (at 22) 组成一个平衡的最大的区间，大小为 22-11=11 个单位长度。

Source

Silver

先求0-1前缀,然后存储sum出现的第一次的位置,然后扫一遍


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int INF = 1e9;
const int MAXN = 50010;
 
int ind[100020];
 
 
int n;
struct node
{
    int tp;
    int pos;
    bool operator < (const node & x) const
    {
        return pos < x.pos;
    }
};
vector<node> a;
node nt;
int sum[MAXN];
 
int main()
{
//    freopen("data.txt","r",stdin);
//    ios_base::sync_with_stdio(false);
    n = read();
    a.push_back(nt);
    for(int i=1;i<=n;i++)
    {
        nt.tp = read();
        if(!nt.tp)
            nt.tp=-1;
        nt.pos = read();
        a.push_back(nt);
    }
 
    sort(a.begin()+1,a.end());
    for(int i=1;i<=n;i++)
    {
        sum[i] = a[i].tp+sum[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        sum[i] += 50005;
    }
    for(int i=n;i>=1;i--)
    {
        if(ind[ sum[i] ]==0)
        {
            ind[sum[i]] = i;
        }
    }
    int  ans = 0;
    for(int i=1;i<=n;i++)
    {
        if(ind[ sum[i-1] ]>i)
        {
            ans = max(ans,a[ ind[ sum[i-1] ] ].pos - a[ i ].pos );
        }
    }
    cout << ans<<endl;
 
    return 0;
}

1639: [Usaco2007 Mar]Monthly Expense 月度开支

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1100 Solved: 548
[ Submit][ Status][ Discuss]

Description

Farmer John是一个令人惊讶的会计学天才，他已经明白了他可能会花光他的钱，这些钱本来是要维持农场每个月的正常运转的。他已经计算了他以后N(1<=N<=100,000)个工作日中每一天的花费moneyi(1<=moneyi<=10,000)，他想要为他连续的M(1<=M<=N)个被叫做“清算月”的结帐时期做一个预算，每一个“清算月”包含一个工作日或更多连续的工作日，每一个工作日都仅被包含在一个“清算月”当中。 FJ的目标是安排这些“清算月”，使得每个清算月的花费中最大的那个花费达到最小，从而来决定他的月度支出限制。

Input

第一行：两个用空格隔开的整数：N和M

第2..N+1行：第i+1行包含FJ在他的第i个工作日的花费

Output

第一行：能够维持每个月农场正常运转的钱数

Sample Input

7 5
100
400
300
100
500
101
400

Sample Output

500
输入细节

这里有7个工作日来被5个“清算月”划分。他花费100，400，100，500，101，和400元在他的每个工作日。

输出细节

如果FJ安排他的月度预算，他将把前两天划分在一个月中，把第三天、第四天划分在一个月当中，最后的三个工作日各自在一个月当中，所以他一个月最多花费500元，其他的方法总是得出一个较大的结果。

100 400 300 100 500 101 400 每天花费
---1--- ---2--- -3- -4- -5- 月度标号
500 400 500 101 400 月度花费

HINT

Source

Silver

[ Submit][ Status][ Discuss]

二分答案


 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int INF = 0x3f3f3f3f;
 
int n,m;
int a[100005];
bool check(int num)
{
//    cout << num<<endl;
    int ct = 0;
    int cur=0;
    int sum = 0;
    while(cur<n)
    {
        sum=0;
        while(cur<n)
        {
            sum+=a[cur];
            if(sum>num) break;
            cur++;
        }
        ct++;
    }
    if(ct>m)
    {
        return false;
    }
    else
    {
//        cout <<num<<" **"<<endl;
        return true;
    }
}
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    int maxx = 0;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin >>a[i];
        maxx = max(maxx,a[i]);
    }
 
    int ans = 0;
    int l = maxx;
    int r =1000000000;
    while(l<=r)
    {
        int mid = (l+r)>>1;
        if(check(mid))
        {
            ans=mid,r=mid-1;
        }
        else
        {
            l = mid+1;
        }
    }
    cout << ans<<endl;
 
 
    return 0;
}

1640: [Usaco2007 Nov]Best Cow Line 队列变换

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1033 Solved: 537
[ Submit][ Status][ Discuss]

Description

FJ打算带着他可爱的N (1 ≤ N ≤ 2,000)头奶牛去参加”年度最佳老农”的比赛.在比赛中,每个农夫把他的奶牛排成一列,然后准备经过评委检验. 比赛中简单地将奶牛的名字缩写为其头字母(the initial letter of every cow),举个例子,FJ带了Bessie, Sylvia,和Dora,那么就可以缩写为BSD. FJ只需将奶牛的一个序列重新排列,然后参加比赛.他可以让序列中的第一头奶牛,或者最后一头走出来,站到新队列的队尾. 利欲熏心的FJ为了取得冠军,他就必须使新队列的字典序尽量小. 给你初始奶牛序列(用头字母)表示,然后按照上述的规则组成新序列,并使新序列的字典序尽量小.

Input

第1行:一个整数N.

第2行至第N+1行:每行一个大写字母,表示初始序列中该奶牛的头字母.

Output

得到的最小字典序的序列.每输出80个字母需要一个换行!

Sample Input

6
A
C
D
B
C
B

Sample Output

ABCBCD

HINT

直接模拟,注意判断两端一样时选择哪个


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int INF = 0x3f3f3f3f;
 
int n,m;
char a[20005];
int head,tail;
char ch;
string s;
 
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    head=tail=0;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> ch;
        a[tail++]=ch;
    }
    tail--;
    while(head<=tail)
    {
        s.clear();
        for(int i=0;i<80&&head<=tail;i++)
        {
            if(a[head]>a[tail])
            {
                s+=a[tail--];
            }
            else if(a[head]==a[tail])
            {
                if(head==tail)
                {
                    s+=a[head++];
                }
                else
                {
                    int st=1;
                    while(a[head+st]==a[tail-st] && head+st<tail-st) st++;
                    if(a[head+st]>a[tail-st])
                    {
                        s+=a[tail--];
                    }
                    else
                    {
                        s+=a[head++];
                    }
                }
            }
            else
            {
                s+=a[head++];
            }
        }
        cout << s<<endl;
    }
 
 
    return 0;
}

1641: [Usaco2007 Nov]Cow Hurdles 奶牛跨栏

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 763 Solved: 499
[ Submit][ Status][ Discuss]

Description

Farmer John 想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。奶牛的训练场中有 N (1 ≤ N ≤ 300) 个站台，分别标记为1..N。所有站台之间有M (1 ≤ M ≤ 25,000)条单向路径，第i条路经是从站台Si开始，到站台Ei，其中最高的栏的高度为Hi (1 ≤ Hi ≤ 1,000,000)。无论如何跑，奶牛们都要跨栏。奶牛们有 T (1 ≤ T ≤ 40,000) 个训练任务要完成。第 i 个任务包含两个数字 Ai 和 Bi (1 ≤ Ai ≤ N; 1 ≤ Bi ≤ N)，表示奶牛必须从站台Ai跑到站台Bi，可以路过别的站台。奶牛们想找一条路径从站台Ai到站台Bi，使路径上最高的栏的高度最小。你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。

Input

行 1: 两个整数 N, M, T 行

2..M+1: 行 i+1 包含三个整数 Si , Ei , Hi 行 M+2..M+T+1: 行 i+M+1 包含两个整数，表示任务i的起始站台和目标站台: Ai , Bi

Output

行 1..T: 行 i 为一个整数，表示任务i路径上最高的栏的高度的最小值。如果无法到达，输出 -1。

Sample Input

5 6 3
1 2 12
3 2 8
1 3 5
2 5 3
3 4 4
2 4 8
3 4
1 2
5 1

Sample Output

4
8
-1

HINT

Source

Silver

[ Submit][ Status][ Discuss]

Floy计算最小高度注意不要用cin cout 会 RE


 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int INF = 0x3f3f3f3f;
 
int n,m,q;
int mm[305][305];
 
 
int main()
{
//    freopen("data.txt","r",stdin);
//    ios_base::sync_with_stdio(false);
    int u,v,w;
    scanf("%d %d %d",&n,&m,&q);
//    cin >> n>>m>>q;
 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            mm[i][j] = INF;
        }
    }
 
 
    for(int i=0;i<m;i++)
    {
//        cin >> u>>v>>w;
        scanf("%d %d %d",&u,&v,&w);
        mm[u][v] = w;
    }
 
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(max(mm[i][k],mm[k][j] ) < mm[i][j] )
                {
                    mm[i][j] =max(mm[i][k],mm[k][j]);
                }
            }
        }
    }
    while(q--)
    {
//        cin >> u>>v;
        scanf("%d%d",&u,&v);
        if(u==v)
        {
            printf("0\n");
//            cout <<0<<endl;
            continue;
        }
        if(mm[u][v]==INF)
        {
            printf("-1\n");
//            cout << -1<<endl;
        }
        else
        {
            printf("%d\n",mm[u][v]);
//            cout << mm[u][v]<<endl;
        }
    }
 
 
 
    return 0;
}

1642: [Usaco2007 Nov]Milking Time 挤奶时间

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 899 Solved: 520
[ Submit][ Status][ Discuss]

Description

贝茜是一只非常努力工作的奶牛，她总是专注于提高自己的产量。为了产更多的奶，她预计好了接下来的N (1 ≤ N ≤ 1,000,000)个小时，标记为0..N-1。 Farmer John 计划好了 M (1 ≤ M ≤ 1,000) 个可以挤奶的时间段。每个时间段有一个开始时间(0 ≤ 开始时间 ≤ N), 和一个结束时间 (开始时间 < 结束时间 ≤ N), 和一个产量 (1 ≤ 产量 ≤ 1,000,000) 表示可以从贝茜挤奶的数量。Farmer John 从分别从开始时间挤奶，到结束时间为止。每次挤奶必须使用整个时间段。但即使是贝茜也有她的产量限制。每次挤奶以后，她必须休息 R (1 ≤ R ≤ N) 个小时才能下次挤奶。给定Farmer John 计划的时间段，请你算出在 N 个小时内，最大的挤奶的量。

Input

第1行三个整数N，M，R.接下来M行，每行三个整数Si，Ei，Pi．

Output

最大产奶量．

Sample Input

12 4 2
1 2 8
10 12 19
3 6 24
7 10 31

Sample Output

HINT

注意：结束时间不挤奶

Source

[ Submit][ Status][ Discuss]

DP问题,只是把点换成了区间

DP[i]表示当前时间段挤奶的最大值


#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
 
const int INF = 0x3f3f3f3f;
 
int n,m,v;
 
struct node
{
    int l,r;
    int w;
    bool operator < (const node & x) const
    {
        if(l==x.l)
        {
            return r < x.r;
        }
        else
        {
            return l<x.l;
        }
    }
};
 
node nt;
vector<node> a;
int dp[1005];
 
 
 
 
 
int maxx =0;
int main()
{
//    freopen("data.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin >> n >> m >> v;
    for(int i=0;i<m;i++)
    {
        cin >> nt.l >> nt.r >> nt.w;
        a.push_back(nt);
    }
 
    sort(a.begin(),a.end());
 
    for(int i=0;i<m;i++)
    {
        dp[i] = a[i].w;
    }
 
    for(int i=1;i<m;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(a[j].r+v<=a[i].l)
                dp[i] = max(dp[i],dp[j]+a[i].w);
//            dp[i] = a[i].w;
        }
 
    }
 
 
    cout << *max_element(dp,dp+m)<<endl;
    return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/214784