首页 > 代码库 > 9.26 noip模拟试题

9.26 noip模拟试题

魔术球问题弱化版(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>using namespace std;int a[61];int main(){    freopen("ball.in","r",stdin);    freopen("ball.out","w",stdout);    a[1]=1;a[2]=3;a[3]=7;a[4]=11;a[5]=17;a[6]=23;a[7]=31;a[8]=39;a[9]=49;a[10]=59;    a[11]=71;a[12]=83;a[13]=97;a[14]=111;a[15]=127;a[16]=143;a[17]=161;a[18]=179;a[19]=199;a[20]=219;    a[21]=241;a[22]=263;a[23]=287;a[24]=311;a[25]=337;a[26]=363;a[27]=391;a[28]=419;a[29]=449;a[30]=479;    a[31]=511;a[32]=543;a[33]=577;a[34]=611;a[35]=647;a[36]=683;a[37]=721;a[38]=759;a[39]=799;a[40]=839;    a[41]=881;a[42]=923;a[43]=967;a[44]=1011;a[45]=1057;a[46]=1103;a[47]=1151;a[48]=1199;a[49]=1249;a[50]=1299;    a[51]=1351;a[52]=1403;a[53]=1457;a[54]=1511;a[55]=1567;a[56]=1623;a[57]=1681;a[58]=1739;a[59]=1799;a[60]=1859;    int n;    scanf("%d",&n);    printf("%d\n",a[n]);    return 0;}
View Code

 

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

最大生成树

技术分享
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 50010using namespace std;int T,n,m,k,fa[maxn],tot,cost;struct node{    int u,v,t;}e[maxn];int init(){    int x=0,f=1;char s=getchar();    while(s<0||s>9){if(s==-)f=-1;s=getchar();}    while(s>=0&&s<=9){x=x*10+s-0;s=getchar();}    return x*f;}int cmp(const node &x,const node &y){    return x.t>y.t;}void Clear(){    tot=0;cost=(n+m)*10000;    for(int i=0;i<=m+n;i++)        fa[i]=i;}int find(int x){    if(x!=fa[x])fa[x]=find(fa[x]);    return fa[x];}int main(){    freopen("conscription.in","r",stdin);    freopen("conscription.out","w",stdout);    T=init();    while(T--){        n=init();m=init();k=init();        Clear();        int u,v,t;        for(int i=1;i<=k;i++){            u=init();v=init();t=init();            e[i].u=u;e[i].v=v+n;e[i].t=t;        }        sort(e+1,e+1+k,cmp);        for(int i=1;i<=k;i++){            int r1=find(e[i].u);            int r2=find(e[i].v);            if(r1!=r2){                tot++;cost-=e[i].t;fa[r2]=r1;            }            if(tot==n+m-1)break;        }        printf("%d\n",cost);    }    return 0;}
View Code

 

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以内。

来源

bzoj3538

技术分享
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#define maxn 10010#define ll long longusing namespace std;ll n,m,num1,num2,num,head1[maxn],head2[maxn],head[maxn],dis1[maxn],dis2[maxn],dis[maxn],f[maxn];ll u[maxn*10],v[maxn*10],t1[maxn*10],t2[maxn*10];queue<ll>q;struct node{    ll u,v,t,pre;}e1[maxn*10],e2[maxn*10],e[maxn*10];ll init(){    ll x=0,f=1;char s=getchar();    while(s<0||s>9){if(s==-)f=-1;s=getchar();}    while(s>=0&&s<=9){x=x*10+s-0;s=getchar();}    return x*f;}void Add1(ll from,ll to,ll dis){    num1++;e1[num1].u=from;    e1[num1].t=dis;    e1[num1].v=to;    e1[num1].pre=head1[from];    head1[from]=num1;}void Add2(ll from,ll to,ll dis){    num2++;e2[num2].u=from;    e2[num2].t=dis;    e2[num2].v=to;    e2[num2].pre=head2[from];    head2[from]=num2;}void SPFA1(){    memset(dis1,127/3,sizeof(dis));    q.push(n);f[n]=1;dis1[n]=0;    while(!q.empty()){        int k=q.front();        q.pop();f[k]=0;        for(int i=head1[k];i;i=e1[i].pre){            int v=e1[i].v;            if(dis1[v]>dis1[k]+e1[i].t){                dis1[v]=dis1[k]+e1[i].t;                if(f[v]==0){                    f[v]=1;q.push(v);                }            }        }    }}void SPFA2(){    memset(f,0,sizeof(f));    memset(dis2,127/3,sizeof(dis));    while(!q.empty())q.pop();    q.push(n);f[n]=1;dis2[n]=0;    while(!q.empty()){        int k=q.front();        q.pop();f[k]=0;        for(int i=head2[k];i;i=e2[i].pre){            int v=e2[i].v;            if(dis2[v]>dis2[k]+e2[i].t){                dis2[v]=dis2[k]+e2[i].t;                if(f[v]==0){                    f[v]=1;q.push(v);                }            }        }    }}ll Solve(){    memset(f,0,sizeof(f));    memset(dis,127/3,sizeof(dis));    while(!q.empty())q.pop();    q.push(1);f[1]=1;dis[1]=0;    while(!q.empty()){        int k=q.front();        q.pop();f[k]=0;        for(int i=head[k];i;i=e[i].pre){            int v=e[i].v;            if(dis[v]>dis[k]+e[i].t){                dis[v]=dis[k]+e[i].t;                if(f[v]==0){                    f[v]=1;q.push(v);                }            }        }    }    return dis[n];}int main(){    freopen("gpsduel.in","r",stdin);    freopen("gpsduel.out","w",stdout);    n=init();m=init();    for(ll i=1;i<=m;i++){        u[i]=init();v[i]=init();t1[i]=init();t2[i]=init();        Add1(v[i],u[i],t1[i]);Add2(v[i],u[i],t2[i]);    }    SPFA1();    SPFA2();    for(ll i=1;i<=m;i++){        e[i].v=v[i];e[i].pre=head[u[i]];head[u[i]]=i;        if(dis1[v[i]]+t1[i]>dis1[u[i]])e[i].t++;        if(dis2[v[i]]+t2[i]>dis2[u[i]])e[i].t++;    }    cout<<Solve()<<endl;    return 0;}
View Code

 

9.26 noip模拟试题