2014-6-28 NOIP模拟赛
【今天我出的三道题目全部是图论哦,请大家轻虐】
1.魔术球问题弱化版(ball.c/.cpp/.pas)
题目描述
假设有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 1,2,3,…的球。
(1)每次只能在某根柱子的最上面放球。
(2)在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。
试设计一个算法,计算出在 n 根柱子上最多能放多少个球。例如,在 4 根柱子上最多可放 11 个球。
对于给定的 n,计算在 n 根柱子上最多能放多少个球。
输入描述
第 1 行有 1 个正整数 n,表示柱子数。
输出描述
一行表示可以放的最大球数
4
样例输出。
样例输入
11
题目限制(为什么说弱化版就在这里)
N<=60,时限为3s;比起原题还有弱化在不用打出方案,方案太坑了
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[],sum[],A[],Sum[];//a[i]记录第i个柱子顶端元素
int ans;
bool check(int x){
int s=(int)(sqrt(x));
if(s*s==x)return ;
return ;
}
void dfs(int x){//讨论把x放在哪里好
for(int i=;i<=n;i++){
if(!a[i]||check(a[i]+x)){
int pre=a[i];
a[i]=x;
sum[i]++;
if(x>ans){
ans=x;
A[i]=a[i];
Sum[i]=sum[i];
}
dfs(x+);
sum[i]--;
a[i]=pre;
}
}
}
int main(){
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
scanf("%d",&n);
ans=n;
for(int i=;i<=n;i++){
A[i]=a[i]=i;
Sum[i]=sum[i]=;
}
dfs(n+);
for(int i=;i<=n;i++){
if(Sum[i]==&&!check(A[i])){
ans--;
}
}
printf("%d",ans);
}
20分 暴力
/*
网络流经典题??贪心就能过??
刚开始把题目理解错了,只有一个球的柱子这个球不一定是完全平方数
所以贪心就可以咧
样例是
10
6 9 11
3 7 5
1 2 4 8
*/
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[],sum[],A[],Sum[];//a[i]记录第i个柱子顶端元素
int ans;
bool check(int x){
int s=(int)(sqrt(x));
if(s*s==x)return ;
return ;
}
void dfs(int x){//讨论把x放在哪里好
for(int i=;i<=n;i++){
if(!a[i]||check(a[i]+x)){
int pre=a[i];
a[i]=x;
sum[i]++;
if(x>ans){
ans=x;
A[i]=a[i];
Sum[i]=sum[i];
}
dfs(x+);
break;
}
}
}
int main(){
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
scanf("%d",&n);
A[]=a[]=;
Sum[]=sum[]=;
dfs();
printf("%d",ans);
}
100分 贪心
2.征兵(conscription.c/.cpp/.pas)
一个国王,他拥有一个国家。最近他因为国库里钱太多了,闲着蛋疼要征集一只部队要保卫国家。他选定了N个女兵和M个男兵,但事实上每征集一个兵他就要花10000RMB,即使国库里钱再多也伤不起啊。他发现,某男兵和某女兵之间有某种关系(往正常方面想,一共R种关系),这种关系可以使KING少花一些钱就可以征集到兵,不过国王也知道,在征兵的时候,每一个兵只能使用一种关系来少花钱。这时国王向你求助,问他最少要花多少的钱。
读入(conscription.in)
第一行:T,一共T组数据。
接下来T组数据,
第一行包括N,M,R
接下来的R行 包括Xi,Yi,Vi 表示如果招了第Xi个女兵,再招第Yi个男兵能省Vi元(同样表示如果招了第Yi个男兵,再招第Xi个女兵能也省Vi元)
输出(conscription.out)
共T行,表示每组数据的最终花费是多少(因为国库里的钱只有2^31-1,所以保证最终花费在maxlongint范围内)
样例输入
2
5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781
5 5 10
2 4 9820
3 2 6236
3 1 8864
2 4 8326
2 0 5156
2 0 1463
4 1 2439
0 4 4373
3 4 8889
2 4 3133
样例输出
71071
54223
数据范围
数据保证T<=5 ,m,n<=10000,r<=50000,Xi<=m,Yi<=n,Vi<=10000,结果<=2^31-1
【来源】
这道题我叫老师放在9018上了,原题是POJ 3723。
/*
最大生成树
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int T,n,m,r,fa[];
struct node{
int v,a,b;
}e[];
int cmp(node x,node y){return x.v>y.v;}
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
bool connect(int x,int y){
int f1=find(x),f2=find(y);
if(f1==f2)return ;
fa[f1]=f2;
return ;
}
int main(){
freopen("conscription.in","r",stdin);
freopen("conscription.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&r);
memset(fa,,sizeof(fa));
memset(e,,sizeof(e));
for(int i=;i<=n+m;i++)fa[i]=i;
int x,y,z;
for(int i=;i<=r;i++){
scanf("%d%d%d",&x,&y,&z);
e[i].a=x+;e[i].b=y+n+;e[i].v=z;
}
sort(e+,e+r+,cmp);
int ans=;
for(int i=;i<=r;i++){
int f1=find(e[i].a),f2=find(e[i].b);
if(f1!=f2){
fa[f1]=f2;
ans+=e[i].v;
}
}
printf("%d\n",(n+m)*-ans);
}
}
3.坑爹的GPS(gpsduel.c/.cpp/.pas)
有一天,FJ买了一辆车,但是,他一手下载了两个GPS系统。好了现在麻烦的事情来了,GPS有一个功能大概大家也知道,如果FJ没有按照GPS内置地图的最短路走,GPS就会报错来骚扰你。现在FJ准备从他的农舍(在1这个点)开车到他的谷屋(n这个点)。FJ给了你两个GPS系统内置地图的信息,他想知道,他最少会听到多少次报错(如果FJ走的路同时不满足两个GPS,报错次数+2)
读入:第一行:n,k;n表示有FJ的谷屋在哪,同时保证GPS内置地图里的点没有超过n的点。K表示GPS内置地图里的路有多少条,如果两个点没有连接则表明这不是一条通路。
接下来k行,每行4个数X,Y,A,B分别表示从X到Y在第一个GPS地图里的距离是A,在第二个GPS地图里的是B。注意由于地形的其他因素GPS给出的边是有向边。
输出:一个值,表示FJ最少听到的报错次数。
样例输入:
5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5
样例输出:
1
解释
FJ选择的路线是1 2 4 5,但是GPS 1认为的最短路是1到3,所以报错一次,对于剩下的2 4 5,两个GPS都不会报错。
数据范围
N<=10000,至于路有多少条自己算吧。数据保证所有的距离都在2^31-1以内。
来源
USACO 2014年 全美公开赛银组第二题(各位轻虐银组题)
最新文章
- HttpResponseMessage和HttpResponseException (转)
- png,jpg,gif格式的图片的选择
- linux进阶
- CS小分队第一阶段冲刺站立会议(5月9日)
- [ionic开源项目教程] - 第14讲 ionic解决跨域问题
- Excel 窗体控件属性
- 当前位置: 银光首页 >; WPF >; WPF学习教程 >; WPF: ShowDialog() 切换到其他应用窗口后,再切换回来无法让子窗口总在最上方
- N3292系列资料之RTC介绍
- CentOS下JAVA WEB 环境搭建
- Quartz任务调度器及与Spring的整合使用
- Caffe可视化之VisualDL
- Ubuntu16.04下安装Hive
- 『随笔』.Net 底层 数组[] 的 基本设计探秘 512 子数组
- Flask与mysql数据库字段类型的区别以及基本用法
- Ubuntu12.04下解决sudo apt-get update警告Duplicate sources.list entry
- Java知多少(9) import及Java类的搜索路径
- rest-framework之分页器
- 分析Ajax请求并抓取今日头条街拍美图
- StanFord ML 笔记 第八部分
- 安装mysql时启动服务出错问题
热门文章
- 让EasyDarwin只支持RTP over TCP传输
- ";Installing Software"; has encountered a problem---pydev on ubuntu
- Timing breakdown phases explained
- Java类加载器( 死磕 6)
- 15款创建美丽幻灯片的 jQuery 插件
- Windows10搭建FTP服务器
- [RK3288][Android6.0] 调试笔记 --- 软硬键盘同时使用【转】
- BZOJ 1619 [Usaco2008 Nov]Guarding the Farm 保卫牧场:dfs【灌水】
- codeforces B. Marathon 解题报告
- the art of seo(chapter three)