1600: [Usaco2008 Oct]建造栅栏
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 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
输出详解：
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
该题利用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 MBSubmit: 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
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
Sample Output
输出详解：
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 MBSubmit: 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
2 1 2
4 3 2
1 4 3
1 2
3 2
Sample Output
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 MBSubmit: 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
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 MBSubmit: 1393 Solved: 1032
[ Submit][ Status][ Discuss]
Description
Input
Output
Sample Input
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
HINT
Buying the two smaller bales fills the wagon.
Source
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 MBSubmit: 2657 Solved: 1397
[ Submit][ Status][ Discuss]
Description
Input
Output
Sample Input
2
1
2
3
4
INPUT DETAILS:
The 5 cows are given the numbers 2, 1, 2, 3, and 4, respectively.
Sample Output
0
2
1
3
OUTPUT DETAILS:
The first cow pats the second and third cows; the second cows pats no cows;
etc.
HINT
Source
打表求解,可以被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 MBSubmit: 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
1
3
2
1
1
输入说明:
队列中共有5头奶牛，第1头以及最后2头奶牛被设定为第一批用餐，第2头奶牛的预设是第三批用餐，第3头则为第二批用餐。
Sample Output
输出说明:
如果FJ想把当前队列改成一个不下降序列，他至少要改2头奶牛的编号，一种可行的方案是：把队伍中2头编号不是1的奶牛的编号都改成1。不过，如果FJ选择把第1头奶牛的编号改成3就能把奶牛们的队伍改造成一个合法的不上升序列了。
HINT
Source
最长非递减子序列的变型
#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 MBSubmit: 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
-1 1
-2 0
0 0
1 1
Sample Output
HINT
4 输出说明: 贝茜能画出以下4种斜率的直线：-1，0，1/3以及1。
Source
暴力一下所有的斜率,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 MBSubmit: 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
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 MBSubmit: 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
4 3
4 2
3 2
1 2
2 5
Sample Output
输出说明:
编号为2的奶牛输给了编号为1、3、4的奶牛，也就是说她的水平比这3头奶
牛都差。而编号为5的奶牛又输在了她的手下，也就是说，她的水平比编号为5的
奶牛强一些。于是，编号为2的奶牛的排名必然为第4，编号为5的奶牛的水平必
然最差。其他3头奶牛的排名仍无法确定。
HINT
Source
#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 MBSubmit: 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
3
4
2
10
Sample Output
输出说明:
贝茜在第1分钟内选择跑步（跑了5米），在第2分钟内休息，在第3分钟内跑
步（跑了4米），剩余的时间都用来休息。因为在晨跑结束时贝茜的疲劳度必须
为0，所以她不能在第5分钟内选择跑步。
HINT
Source
#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 MBSubmit: 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
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
输出说明:
FJ选择如下的连结方案：1->3；3->2；2->5，这3对电话线杆间需要的
电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线，于是，
他所需要购买的电话线的最大长度为4。
HINT
Source
#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 MBSubmit: 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
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
HINT
输出说明:
齿轮 位置 半径 转速
1 (0,0) 10 10,000
2 (0,30) 20 -5,000
3 (32,54) 20 5,000
------
齿轮转速绝对值之和:20,000
Source
#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 MBSubmit: 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
...*.
...*.
.....
.....
1 3 1 5
输入说明:
草地被划分成4行5列，奶牛在6秒内从第1行第3列走到了第1行第5列。
Sample Output
奶牛在6秒内从(1,3)走到(1,5)的方法只有一种（绕过她面前的树）。
HINT
Source
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 MBSubmit: 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
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
不同数量过河对应一个权值,且可以重复,直接利用完全背包
#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 MBSubmit: 1260 Solved: 657
[ Submit][ Status][ Discuss]
Description
Input
Output
Sample Input
3 2
5 3
Sample Output
FJ can buy three packages from the second supplier for a total cost of 9.
HINT
Source
类似于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 MBSubmit: 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
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
Source
从最高点灌水,,,灌水
#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 MBSubmit: 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
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
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
从后往前贪心,假设工作都是在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 MBSubmit: 914 Solved: 677
[ Submit][ Status][ Discuss]
Description
Input
两个整数N和K.
Output
最后的牛群数．
Sample Input
INPUT DETAILS:
There are 6 cows and the difference in group sizes is 2.
Sample Output
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
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 MBSubmit: 630 Solved: 345
[ Submit][ Status][ Discuss]
Description
Input
Output
Sample Input
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
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
直接用栈开始暴力
#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 MBSubmit: 587 Solved: 410
[ Submit][ Status][ Discuss]
Description
Input
Output
Sample Input
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
OUTPUT DETAILS:
Two cows are possible, by putting either cow with speed 5 first and the cow
with speed 7 second.
HINT
Source
贪心,先计算出有奶牛前面最多可以多少奶牛,然后再挨个放,直到放满
#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 MBSubmit: 799 Solved: 522
[ Submit][ Status][ Discuss]
Description
Input
Output
Sample Input
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
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
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 MBSubmit: 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
1 4
2 6
3 12
2 7
输入说明:
贝茜收集了4块宝石，她能忍受重量最大为6的手镯。
Sample Output
输出说明:
贝茜把除了第二块宝石的其余所有宝石都镶上手镯，这样她能增加
4+12+7=23的魅力值，并且所有宝石的重量为1+2+3 <= 6，同样符合要求。
HINT
Source
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 MBSubmit: 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
1 1
3 1
2 3
4 3
1 4
输入说明:
FJ一共有4个坐标分别为(1,1)，(3,1)，(2,3)，(4,3)的农场。农场1和农场
4之间原本就有道路相连。
Sample Output
输出说明:
FJ选择在农场1和农场2间建一条长度为2.00的道路，在农场3和农场4间建一
条长度为2.00的道路。这样，所建道路的总长为4.00，并且这是所有方案中道路
总长最小的一种。
HINT
Source
并查集确定有几个联通块,然后把连通块缩为一个点,然后最短路求解
#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 MBSubmit: 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
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
Source
坐标都加上一个数
直接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 MBSubmit: 576 Solved: 447
[ Submit][ Status][ Discuss]
Description
Input
Output
输出一个整数，表示城市中最少包含的建筑物数量
Sample Input
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
维护一个优先队列,如果其出现了一个矮的方格,则把比矮方格大的数弹出
也可单调栈
#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 MBSubmit: 1065 Solved: 545
[ Submit][ Status][ Discuss]
Description
Input
Output
Sample Input
10 3
2 5
3 3
Sample Output
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
贪心算法,感觉好难想
【分析】假设我们必须把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 MBSubmit: 884 Solved: 639
[ Submit][ Status][ Discuss]
Description
Input
第1行:三个用空格隔开的整数.
第2行到第M+1行,每行三个用空格隔开的整数:Ai, Bi,以及Ti.表示一条道路的起点,终点和需要花费的时间.
Output
唯一一行:一个整数: 所有参加聚会的奶牛中,需要花费总时间的最大值.
Sample Input
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
正着一次,然后把边逆置再跑一边
#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 MBSubmit: 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
browndcodw
cow
milk
white
black
brown
farmer
Sample Output
HINT
Source
动态规划：
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 MBSubmit: 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.
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
3 1
2 5
2 3
3 2
4 1
1 6
Sample Output
HINT
约翰用6，2，3，4，1，5的顺序来运送他的奶牛．
Source
贪心，调换两个牛的位置，然后判断
(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 MBSubmit: 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
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
4
5
3
4
4
5
5
5
HINT
Source
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 MBSubmit: 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
Sample Input
to a reply and indicates the difference in height between the
tallest and shortest cow in the range.
Sample Output
3
0
HINT
Source
两次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 MBSubmit: 724 Solved: 477
[ Submit][ Status][ Discuss]
Description
Input
行 1: 一个整数: N 行 2..N + 1: 每行两个整数，为种族 ID 和 x 坐标。
Output
行 1: 一个整数，阵容平衡的最大的区间的大小。
Sample Input
0 11
1 10
1 25
1 12
1 4
0 13
1 22
Sample Output
HINT
输入说明
Source
先求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 MBSubmit: 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
100
400
300
100
500
101
400
Sample Output
输入细节
这里有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
二分答案
#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 MBSubmit: 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
A
C
D
B
C
B
Sample Output
HINT
.jpg)
直接模拟,注意判断两端一样时选择哪个
#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 MBSubmit: 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
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
8
-1
HINT
Source
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 MBSubmit: 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
1 2 8
10 12 19
3 6 24
7 10 31
Sample Output
HINT
注意：结束时间不挤奶
Source
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;
}