1297: A 房间安排
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 426 Solved: 150
[Submit][Status][Web Board]
Description
2010年上海世界博览会(Expo2010),是第41届世界博览会。于2010年5月1日至10月31日期间，在中国上海市举行。本次世博会也是由中国举办的首届世界博览会。上海世博会以“城市，让生活更美好”(Better City,Better Life)为主题，将充分探索21世纪城市生活.
这次世博会总投资达450亿人民币，创造了世界博览会史上的最大规模记录。吸引200个国家和国际组织参展。预计有7000万人次的参观者。
为了更好地接待在这期间来自世界各地的参观者，如何合理安排各宾馆的住房问题提到了日程。组委会已接到了大量的客户住宿定单，每张定单的内容包括要住宿的房间数，开始住宿时间和要住的天数。为了便于整个城市各宾馆的管理，组委会希望对这些定单进行安排，目的是用尽可能少的房间来满足这些定单，以便空出更多的房间用于安排流动游客。
组委会请求DR.Kong来完成这个任务，对这些定单进行合理安排，使得满足这些定单要求的房间数最少。
假设：某个定单上的游客一旦被安排到某房间，在他预定住宿的期间内是不换房间的。为了简化描述，定单上的开始住宿时间为距离现在的第几天。例如，定单为（10，30，5）表示游客要求使用10个房间，第30天开始连住5天。
Input
第一行：T 表示有T组测试数据
每组测试数据第一行：N 表示定单数
每组测试数据接下来有N行，每行有三个整数 A B C 表示房间数，开始住宿时间和天数
1<=T<=100
1<=N<=10000 1<=A<=10 1<=B<=180 1<=c<=10
Output
输出一个整数，为满足所有定单要求的最少房间数。
Sample Input
1
3
3 10 4
4 9 3
3 12 6
Sample Output
7
#include<bits/stdc++.h>
using namespace std;
const int maxn=190;
int T;
int n,a,b,c;
int ans[maxn];
int main()
{
freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
memset(ans,0,sizeof(ans));
scanf("%d",&n);
for(int i=0;i!=n;i++)
{
scanf("%d %d %d",&a,&b,&c);
for(int j=0;j<c;j++)
{
ans[b+j]+=a;
}
}
sort(ans,ans+181);
printf("%d\n",ans[180]);
}
return 0;
}
Problem B: B 素数
Time Limit: 1 Sec Memory Limit: 512 MB
Submit: 18 Solved: 12
[Submit][Status][Web Board]
Description
走进世博园某信息通信馆，参观者将获得前所未有的尖端互动体验，一场充满创想和喜悦的信息通信互动体验秀将以全新形式呈现，从观众踏入展馆的第一步起，就将与手持终端密不可分，人类未来梦想的惊喜从参观者的掌上展开。
在等候区的梦想花园中，参观者便开始了他们奇妙的体验之旅，等待中的游客可利用手机等终端参与互动小游戏，与梦想剧场内的虚拟人物Kr. Kong 进行猜数比赛。当屏幕出现一个整数X时，若你能比Kr. Kong更快的发出最接近它的素数答案，你将会获得一个意想不到的礼物。
例如：当屏幕出现22时，你的回答应是23；当屏幕出现8时，你的回答应是7；若X本身是素数，则回答X;若最接近X的素数有两个时，则回答大于它的素数。
Input
第一行：N 要竞猜的整数个数
接下来有N行，每行有一个正整数X
1<=N<=5 1<=X<=1000
Output
输出有N行，每行是对应X的最接近它的素数
Sample Input
4
22
5
18
8
Sample Output
23
5
19
7
#include<bits/stdc++.h>
using namespace std;
int n,x;
int isPrime(int a)
{
if(a<2)return 0;
if(a==2)return 1;
if(a%2==0)return 0;
for(int i=3;i<=sqrt(a);i+=2)
{
if(a%i==0)return 0;
}
return 1;
}
int calc(int x)
{
if(isPrime(x))return x;
for(int i=1;i!=1000;i++)
{
if(isPrime(x+i))
{
return x+i;
}
if(isPrime(x-i))
{
return x-i;
}
}
return 1;
}
int main()
{
freopen("in.txt","r",stdin);
scanf("%d",&n);
while(n--)
{
scanf("%d",&x);
cout<<calc(x)<<endl;
}
return 0;
}
1299: C 网络的可靠性
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 27 Solved: 13
[Submit][Status][Web Board]
Description
A公司是全球依靠的互联网解决方案提供商，也是2010年世博会的高级赞助商。它将提供先进的网络协作技术，展示其”智能+互联“的生活概念，同时为参观者提供高品质的个人体验和互动，以”信息通信，尽情城市梦想”为主题贯穿。借助奇幻的剧场大屏幕和特效，展现信息通信技术的应用前景，通过生动形象的故事，向观众展示沟通无限制的未来社会前景。
为此，A公司为世博园的N个区域建立了视频通信系统，其中每个区域建立一个基站，编号依次为1，2，3…,N。通过基站之间的通信线路为各区域的参观者提供视频服务。
已知在各基站之间已铺设了一些光纤通讯线路，这些线路覆盖了所有的区域，即任意两个区域都可以进行视频传递。但为了节约成本开支，目前只铺设了N-1条线路，同时为了减轻各基站的信息传递负载，每个基站最多有三条光纤通讯线路与之连接。
但在通信系统试运行期间，A公司发现当某个基站发生故障时，会导致其它区域之间无法进行信息传递。为了提高该通信网络的可靠性，A公司准备在基站之间再新铺设一些光纤线路，使得任意一个基站故障后，其它基站之间仍然可以通讯。
由于铺设线路的成本昂贵，A公司希望新增设的光纤线路越少越好。A公司请求Dr. Kong来完成这个任务
Input
有多组测试数据，以EOF为结束标志。
第一行： N 表示有N个基站
接下来有N-1行：X Y 表示第X个基站与第Y个基站直连
Output
输出一个整数，表示至少需新铺设的光纤线路数
Sample Input
8
1 3
3 2
5 3
5 4
5 6
2 7
2 8
Sample Output
3
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000;
int n,a,b;
int d[maxn];
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&n))
{
memset(d,0,sizeof(d));
for(int i=0;i!=n-1;i++)
{
scanf("%d %d",&a,&b);
d[a]++;
d[b]++;
}
int ans=0;
// for(int i=1;i<=n;i++)
// {
// cout<<d[i]<<" ";
// }
// cout<<endl;
for(int i=1;i<=n;i++)
{
if(d[i]==1)
{
ans++;
}
}
if(ans%2==0)
{
ans/=2;
}
else
{
ans/=2;
ans++;
}
cout<<ans<<endl;
}
return 0;
}
Problem D: D 虚拟城市之旅
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 19 Solved: 6
[Submit][Status][Web Board]
Description
展馆是未来城市的缩影，个人体验和互动是不变的主题。在A国展馆通过多维模式和高科技手段，引领参观者在展示空间踏上一段虚拟的城市之旅。
梦幻国有N个城市和M条道路，每条道路连接某两个城市。任意两个城市之间最多只有一条道路直接相连。这M条道路中有一部分为单向通行的道路，一部分为双向通行的道路。
梦幻国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
现在你已踏上一段虚拟的城市之旅。为了给你一个意外收获，允许你在旅游的同时，利用 X 商品在不同城市中的差价赚回一点旅费，但最多只能交易一次。即,在某个城市买入X 商品，可以走到另外一个城市买掉来获得旅费。当然，在赚不到差价的情况下，你也可以不进行贸易活动。
设梦幻国N个城市的标号从1~ N，你只能从1 号城市出发，并最终在N 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有N个城市。
例如：梦幻国有5个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。假设 X 商品在1~5 号城市的价格分别为 4，3，5，6，1。
你可以选择如下一条线路：1235，并在2 号城市以3 的价格买入X 商品，在3号城市以5 的价格卖出X 商品，赚取的旅费数为2。
你也可以选择如下一条线路14545，并在第1次到达5号城市时以1的价格买入X 商品，在第2次到达4号城市时以6 的价格卖出X 商品，赚取的旅费数为5。
现在给出N个城市的X 商品价格，M条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请问你能赚取尽可能多的旅费吗。
Input
第一行：N M 分别表示城市的数目和道路的数目。
第二行：N个正整数，每两个整数之间用一个空格隔开，分别表示1到N个城市的商品价格。
接下来 M行，每行有3个正整数，X，Y，Z，每两个整数之间用一个空格隔开。
如果 Z=1，表示这条道路是城市X到城市Y之间的单向道路；
如果Z=2，表示这条道路为城市X 和城市Y之间的双向道路。
1≤N≤100000，1≤M≤500000，
1≤X，Y≤N，1≤Z≤2，1≤商品价格≤100。
Output
输出1个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出0。
Sample Input
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
Sample Output
5
你别看他没说有多组数据，省赛都是的多组数据的ORZ
解题思路时从前往后搜一遍从起点能到达那些点，到达这些点时能买到的最低价格是多少。
然后从后往前扫一遍，看从终点出发能到达哪些点，记录一下达到这些点的时候能卖出的最大价格是多大。
最后扫描一遍所有能到达的点的最大价格与最低价格差，即为他能赚取的最大利润。
#include<bits/stdc++.h>
using namespace std;
const int maxn=100001;
int n,m;
int x,y,z;
vector<int> s[maxn],e[maxn];
int dismin[maxn],dismax[maxn];
bool vis1[maxn],vis2[maxn];
void dijkstra_s()
{
memset(vis1,0,sizeof(vis1));
stack<int> sta;
sta.push(1);
while(sta.size())
{
int p = sta.top();
sta.pop();
vis1[p]=1;
vector<int>::iterator it;
//cout<<p<<" "<<s[p].size()<<endl;
for(it=s[p].begin();it!=s[p].end();it++)
{
//cout<<p<<" -> "<<*it<<endl;
if(dismin[*it]>dismin[p])
{
dismin[*it]=dismin[p];
sta.push(*it);
}
else
if(!vis1[*it])sta.push(*it);
}
}
// for(int i=1;i<=n;i++)
// {
// cout<<i<<" "<<dismin[i]<<endl;
// }
}
void dijkstra_e()
{
memset(vis2,0,sizeof(vis2));
stack<int> sta;
sta.push(n);
while(sta.size())
{
int p = sta.top();
sta.pop();
vis2[p]=1;
vector<int>::iterator it;
for(it=e[p].begin();it!=e[p].end();it++)
{
if(dismax[*it]<dismax[p])
{
dismax[*it]=dismax[p];
sta.push(*it);
}
else
if(!vis2[*it])
{
sta.push(*it);
}
}
}
// for(int i=1;i<=n;i++)
// {
// cout<<i<<" "<<dismax[i]<<endl;
// }
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d %d",&n,&m))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&dismin[i]);
dismax[i]=dismin[i];
}
for(int i=0;i!=m;i++)
{
scanf("%d %d %d",&x,&y,&z);
s[x].push_back(y);
e[y].push_back(x);
if(z==2)
{
s[y].push_back(x);
e[x].push_back(y);
}
}
dijkstra_s();
dijkstra_e();
int ans=0;
for(int i=1;i<=n;i++)
{
if(vis1[i]&&vis2[i])
ans=max(dismax[i]-dismin[i],ans);
}
cout<<ans<<endl;
}
return 0;
}
Problem E: E 聪明的“KK”
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 155 Solved: 22
[Submit][Status][Web Board]
Description
非洲某国展馆的设计灵感源于富有传奇色彩的沙漠中陡然起伏的沙丘，体现出本国不断变换和绚丽多彩的自然风光与城市风貌。展馆由五部分组成，馆内影院播放名为《一眨眼的瞬间》的宽银幕短片，反映了建国以来人民生活水平和城市居住环境的惊人巨变。可移动“沙丘”变戏法 的灵感源于其独特而雄伟的自然景观——富于传奇色彩的险峻沙丘。宏伟的结构、可循环的建材，与大自然相得益彰。环绕一周，发现它正是从沙丘那不断变换的形态中汲取灵感的。外形逼真到无论从哪个角度去观察，都能清楚地辨识出沙丘的特征。它“坡面”高达20米，微风吹来，你是否感觉到沙的流动？用手去触碰，却发现原来是“魔术戏法”。它表面的不锈钢面板呈现出一种富于变幻的色彩，从不同角度观察，呈现不同色泽，由此来模仿流动沙丘的光感。走进第三展厅有一个超大的屏幕，通过奇妙的特效，让观众犹如亲身来到浩瀚的沙漠。更为奇妙的是，只见一个小动物“KK”正从沙漠区域（矩形）的左上角沿着向右或向下的方向往右下角跑去。KK太聪明了，它居然能在跑的过程中会选择吃掉尽可能多的虫子线路。你知道它吃掉多少虫子吗？
Input
第一行：N M (1≤N M≤20 0≤Xij≤500(i=1,2„.N, j=1,2„,M) )表示沙漠是一个N*M的矩形区域接下来有N行：每行有M个正整数，Xi1 Xi2 ……Xim 表示各位置中的虫子数（单个空格隔开）假设“KK”只能向右走或向下走
Output
输出有一个整数， 表示“KK”吃掉最多的虫子数。
Sample Input
3 4
3 1 2 8
5 3 4 6
1 0 2 3
Sample Output
24
简单的递推
#include<bits/stdc++.h>
using namespace std;
const int maxn=21;
int n,m;
int dp[maxn][maxn];
int main()
{
while(~scanf("%d %d",&n,&m))
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&dp[i][j]);
dp[i][j]+=max(dp[i-1][j],dp[i][j-1]);
}
}
cout<<dp[n][m]<<endl;
}
return 0;
}
1310: F BUYING FEED
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 12 Solved: 6
[Submit][Status][Web Board]
Description
Farmer John needs to travel to town to pick up K (1 <= K <= 100)pounds of feed. Driving D miles with K pounds of feed in his truck costs D*K cents.
The county feed lot has N (1 <= N <= 100) stores (conveniently numbered 1…N) that sell feed. Each store is located on a segment of the X axis whose length is E (1 <= E <= 350). Store i is at
location X_i (0 < X_i < E) on the number line and can sell John as much as F_i (1 <= F_i <= 100) pounds of feed at a cost of C_i (1 <= C_i <= 1,000,000) cents per pound. Amazingly, a given point on the X axis might have more than one store.
Farmer John starts at location 0 on this number line and can drive only in the positive direction, ultimately arriving at location E, with at least K pounds of feed. He can stop at any of the feed stores along the way and buy any amount of feed up to the the store’s limit.
What is the minimum amount Farmer John has to pay to buy and transport the K pounds of feed? Farmer John knows there is a solution.
Consider a sample where Farmer John needs two pounds of feed from three stores (locations: 1, 3, and 4) on a number line whose range is 0…5:
0 1 2 3 4 5
1 1 1 Available pounds of feed
1 2 2 Cents per pound
It is best for John to buy one pound of feed from both the second and third stores. He must pay two cents to buy each pound of feed for a total cost of 4. When John travels from 3 to 4 he is moving 1 unit of length and he has 1 pound of feed so he must pay 11 = 1 cents.
When John travels from 4 to 5 he is moving one unit and he has 2 pounds of feed so he must pay 12 = 2 cents. The total cost is 4+1+2 = 7 cents.
Input
Line 1: Three space-separated integers: K, E, and N Lines 2…N+1: Line i+1 contains three space-separated integers: Xi Fi Ci
Output
A single integer that is the minimum cost for FJ to buy and transport the feed
Sample Input
2 5 3
3 1 2
4 1 2
1 1 1
Sample Output
7
可知价格低并不一定就买，因为带着他们走也是需要花费的，
那么我们就把走的花费也都加到这个物品的价格上，就是我们实际想要的性价比了
然后从小到大拿就好
#include<bits/stdc++.h>
using namespace std;
const int maxn=21;
int n,k,e;
int x,f,p;
class F
{
public:
int f,p;
};
bool operator <(const F a,const F b)
{
return a.p<b.p;
}
F store[110];
int main()
{
while(~scanf("%d %d %d",&k,&e,&n))
{
for(int i=0;i!=n;i++)
{
scanf("%d %d %d",&x,&f,&p);
store[i].f=f;
store[i].p=e-x+p;
}
sort(store,store+n);
int sum=0;
for(int i=0;i!=n;i++)
{
if(k>=store[i].f)
{
sum+=store[i].f*store[i].p;
k-=store[i].f;
}
else
{
sum+=k*store[i].p;
k=0;
}
if(k<=0)break;
}
cout<<sum<<endl;
}
return 0;
}
Problem G: G AMAZING AUCTION
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 11 Solved: 8
[Submit][Status][Web Board]
Description
Recently the auction house has introduced a new type of auction, the lowest price auction. In this new system, people compete for the lowest bid price, as opposed to what they did in the past. What an amazing thing! Now you could buy cool stuff with one penny. Your task is to write the software to automate this auction system.
First the auctioneer puts an upper limit on bid price for each item. Only positive price less than or equal to this price limit is a valid bid. For example, if the price limit is 100, then 1 to 100, inclusive, are all valid bid prices. Bidder can not put more than one bid for the same price on a same item. However they can put many bids on a same item, as long as the prices are different.
After all bids are set, the auctioneer chooses the winner according to the following rules:
(1). If any valid price comes from only one bidder, the price is a “unique bid”. If there are unique bids, then the unique bid with the lowest price wins. This price is the winning price and the only bidder is the winning bidder.
(2). If there are no unique bids, then the price with fewest bids is the winning bid. If there are more than one price which has the same lowest bid count, choose the lowest one. This price is the winning price. The bidder who puts this bid first is the winning bidder.
Given the price limit and all the bids that happen in order, you will determine the winning bidder and the winning price.
Input
The first line contains two integers: U (1 <= U <= 1000), the price upper limit and M (1 <= M <= 100), the total number of bids. M lines follow, each of which presents a single bid. The bid contains the bidder’s name (consecutive non-whitespace characters<=5) and the price P (1 <= P <= U), separated with a single space. All bids in the input are guaranteed to be valid ones.
Output
Print the sentence “The winner is W” on the first line, and “The price is P” on the second.
Sample Input
30 7
Mary 10
Mary 20
Mary 30
Bob 10
Bob 30
Carl 30
Alice 23
Sample Output
The winner is Mary
The price is 20
题目意思就是对一个商品进行竞标，
价格低的胜
如果只有一个人竞标，那么获胜者就是这个人，并且最终价格是最低的价格
如果有多个人竞标，那么获胜者是竞标的价格出现的次数最少，并且最低，并且先竞标的那个人
#include<bits/stdc++.h>
using namespace std;
int maxp;
class B
{
public:
string name;
int p;
int no;
B()
{
name="";
p=0;
}
};
bool operator < (const B a,const B b)
{
if(a.p==b.p)return a.no<b.no;
return a.p<b.p;
}
vector<B> v;
int n;
string name;
int p;
B t;
set<string> nameset;
map<int,int> map1;
int main()
{
while(~scanf("%d %d",&maxp,&n))
{
v.clear();
nameset.clear();
map1.clear();
for(int i=0;i!=n;i++)
{
cin>>name>>p;
if(p<=maxp&&p>0)
{
t.name=name;
nameset.insert(name);
t.p=p;
map1[p]++;
t.no=i;
v.push_back(t);
}
}
sort(v.begin(),v.end());
if(nameset.size()==1)
{
name=v[0].name;
p = v[0].p;
}
else
{
int minp=0x3f3f3f3f;
int mincnt=0x3f3f3f3f;
map<int,int>::iterator it;
for(it=map1.begin();it!=map1.end();it++)
{
if(mincnt>it->second)
{
mincnt=it->second;
minp=it->first;
}
}
for(int i=0;i!=n;i++)
{
if(v[i].p==minp)
{
name=v[i].name;
p = v[i].p;
break;
}
}
}
cout<<"The winner is "<<name<<endl;
cout<<"The price is "<<p<<endl;
}
return 0;
}
Problem H: H ROOM ASSIGNATION
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 0 Solved: 0
[Submit][Status][Web Board]
Description
The “cows” are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 <= N <= 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).
The “cows” and other visitors arrive in groups of size D_i (1 <= D_i <= N) and approach the front desk to check in. Each group i requests a set of D_i contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r…r+D_i-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.
Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters X_i and D_i which specify the vacating of rooms X_i…X_i+D_i-1 (1 <= X_i <= N-D_i+1). Some (or all) of those rooms might be empty before the checkout.
Your job is to assist Canmuu by processing M (1 <= M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.
Input
Line 1: Two space-separated integers: N and M
Lines 2…M+1: Line i+1 contains request expressed as one of two possible formats:
(a) Two space separated integers representing a check-in request: 1 and D_i
(b) Three space-separated integers representing a check-out: 2, X_i, and D_i
Output
Lines 1…: For each check-in request, output a single line with a single integer r, the
first room in the contiguous sequence of rooms to be occupied. If the request
cannot be satisfied, output 0.
Sample Input
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
Sample Output
1
4
7
0
5
就是个模拟而已，可是他在退房的时候可以退一段有可能本来就没人住的房子。
呵呵，本来还想着就写个结构体，仅仅保存空闲房间段就行，但是人家退房可能跨好几段，合并起来代码真实太复杂了，吐血。
大佬们用的应该都是线段树吧，麻烦的一笔，谁爱写谁写吧。
京公网安备 11010502036488号