首页 › 题库 › 信息学奥赛 › 综合练习

信息学奥赛-提高级 题库

共 511 道题 ,第 26 / 26 页 · 按题型筛选,点「查看答案」核对解析
501 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

解方程

【问题描述】

已知多项式方程:

【输入】

输入文件名为 equation.in。

输入共 n+2 行。

第一行包含 2 个整数 n、m,每两个整数之间用一个空格隔开。

接下来的 n+1 行每行包含一个整数,依次为

【输出】

输出文件名为 equation.out。

第一行输出方程在[1, m]内的整数解的个数。

接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。

【输入输出样例 1】

【输入输出样例 2】

【输入输出样例 3】

【数据说明】

答案与解析
参考答案

#include<bits/stdc++.h>

#define LL long long

#define mod 1000000007

using namespace std;


inline LL read() {

    LL x = 0; int t = 1; char ch = getchar();

    while(ch > '9' || ch < '0')    { if(ch == '-') t = -1; ch = getchar(); }

    while(ch >= '0' && ch <= '9') { x = ((x << 1) % mod + (x << 3) % mod + ch - '0') % mod;    ch = getchar(); }

    return x * t;

}


LL a[105];

int n, m, ans[1000005], tot;

inline bool cal(int x) {

    LL res = a[n];

    for(int i = n - 1; i >= 0; i --)

        res = (res * x % mod + a[i]);

    return res == 0;

}


int main() {

    n = read(); m = read();

    for(int i = 0; i <= n; i ++)    a[i] = read();

    for(int i = 1; i <= m; i ++)

        if(cal(i))    ans[++tot] = i;

    printf("%d\n", tot);

    for(int i = 1; i <= tot; i ++)

        printf("%d\n", ans[i]);

    return 0;

}

题目详情
502 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

转圈游戏

【问题描述】

n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏。按照顺时针方向给 n 个位置编号,从0 到 n-1。最初,第 0 号小伙伴在第 0 号位置,第 1 号小伙伴在第 1 号位置,……,依此类推。

游戏规则如下:每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置,第 1 号位置小伙伴走到第 m+1 号位置,……,依此类推,第n − m号位置上的小伙伴走到第 0 号位置,第n-m+1 号位置上的小伙伴走到第 1 号位置,……,第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。

现在,一共进行了 10k 轮,请问 x 号小伙伴最后走到了第几号位置。

【输入】

输入文件名为 circle.in。

输入共 1 行,包含 4 个整数 n、m、k、x,每两个整数之间用一个空格隔开。

【输出】

输出文件名为 circle.out。

输出共 1 行,包含 1 个整数,表示 10k 轮后 x 号小伙伴所在的位置编号。

【输入输出样例】

【数据说明】

对于 30%的数据,0 < k < 7;

对于 80%的数据,0 < k < 10^7;

对于 100%的数据,1 < n < 1,000,000,0 < m < n,1 ≤ x ≤ n,0 < k < 10^9。

答案与解析
参考答案

import java.util.Scanner;



public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int m = sc.nextInt();

int k = sc.nextInt();

int x = sc.nextInt();

sc.close();


System.out.println((x + m * f(10, k, n)) % n);


}

public static int f(int y, int k, int n) {

int pingfangshu = y;

int result = 1;

while (k != 0) {

if ((k & 1) == 1) {

result *= pingfangshu;

}

k >>= 1;

pingfangshu = (pingfangshu * pingfangshu) % n;

result %= n;

}

return result;

}

}

题目详情
503 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

货车运输

【问题描述】

A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

【输入】

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路。

接下来 m 行每行 3 个整数 x、y、z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意:x 不等于 y,两座城市之间可能有多条道路。

接下来一行有一个整数 q,表示有 q 辆货车需要运货。

接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意:x 不等于 y。

【输出】

输出文件名为 truck.out。

输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能到达目的地,输出-1。

【输入输出样例】

【数据说明】

对于 30%的数据,0 < n < 1,000,0 < m < 10,000,0 < q < 1,000;

对于 60%的数据,0 < n < 1,000,0 < m < 50,000,0 < q < 1,000;

对于 100%的数据,0 < n < 10,000,0 < m < 50,000,0 < q < 30,000,0 ≤ z ≤ 100,000。

答案与解析
参考答案

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define _for(i,a,b) for (int i=a;i<=b;i++)

using namespace std;

const int N=1e4+5,M=5e4+5;//g[u][j]表示u到f[u][j]这条链上边权的最大值。

int n,m,fa[N],h[N],e[M],ne[M],w[M],idx,d[N],f[N][20],g[N][20];

struct node{

    int a,b,w;

    bool operator <(const node& rhs) const{

        return w>rhs.w;

    }

}a[M];

inline void c_plus(){//可以忽略

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

}

inline void init_list(){//单链表

    idx=0;

    memset(h,-1,sizeof(h));

}

inline void add(int a,int b,int c){//同上

    e[idx]=b;

    w[idx]=c;

    ne[idx]=h[a];

    h[a]=idx++;

}

inline void init_set(){//并查集

    _for(i,1,n){

        fa[i]=i;

    }

}

int get(int x){//同上

    if (x==fa[x]){

        return x;

    }

    return fa[x]=get(fa[x]);

}

void kruskal(){//kruskal算法

    sort(a+1,a+m+1);

    _for(i,1,m){

        int x=get(a[i].a);

        int y=get(a[i].b);

        if (x!=y){

            fa[y]=x;

            add(a[i].a,a[i].b,a[i].w);

            add(a[i].b,a[i].a,a[i].w);

        }

    }

}

void dfs(int u){

d[u]=d[f[u][0]]+1;

for (int i=h[u];i!=-1;i=ne[i]){

int j=e[i];

if (j==f[u][0]){

continue;

        }

f[j][0]=u;

        g[j][0]=w[i];//我们需要在dfs函数里给g[v][0]赋初值,为每个结点v上面那条边的权值。

dfs(j);

}

}

int lca(int x,int y){//LCA算法

    if (get(x)!=get(y)){//判断是否合法,在不在一个连通块内

        return -1;

    }

if (d[x]<d[y]){

swap(x,y);

}

int k=(int)(log2(d[x])),ans=0x7fffffff;//ans存答案

for (int j=k;j>=0;j--){

if (d[f[x][j]]>=d[y]){

            ans=min(ans,g[x][j]);//维护最大值

x=f[x][j];

}

}

if (x==y){/

goto output;

}

k=(int)(log2(d[x]));

for (int j=k;j>=0;j--){

if (f[x][j]!=f[y][j]){

            ans=min(ans,min(g[x][j],g[y][j]));//维护最大值

x=f[x][j];

y=f[y][j];

}

}

    ans=min(ans,min(g[x][0],g[y][0]));//最后还差一步才到达lca,因此还要算上最后两条边的最大值

    output:

return ans;

}

int main(){

    freopen("truck.in","r",stdin);

    freopen("truck.out","w",stdout);

    c_plus();

    int q,x,y;

    cin>>n>>m;

    init_list();

    init_set();

    _for(i,1,m){

        cin>>a[i].a>>a[i].b>>a[i].w;

    }

    kruskal();

    _for(i,1,n){

        if (d[i]==0){//每个连通块都要遍历

            dfs(i);

        }

    }

    for (int j=1;(1<<j)<=n;j++){

        _for(i,1,n){

            f[i][j]=f[f[i][j-1]][j-1];

            g[i][j]=min(g[i][j-1],g[f[i][j-1]][j-1]);//通过动态规划计算g数组剩余的值。

//转移方程很显然,就是把从i到f[i][j]这条链,拆成i到f[i][j-1]和f[i][j-1]到f[i][j]两条链,

//然后取最大值

        }

    }

    cin>>q;

    while (q--){

        cin>>x>>y;

        cout<<lca(x,y)<<endl;

    }

    return 0;

}

题目详情
504 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

借教室

【问题描述】

在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。

面对海量租借教室的信息,我们自然希望编程解决这个问题。

我们需要处理接下来n天的借教室信息,其中第i天学校有ri个教室可供租借。共有m份订单,每份订单用三个正整数描述,分别为dj, sj,tj,表示某租借者需要从第sj天到第tj天租借教室(包括第sj天和第tj天),每天需要租借dj个教室。

我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提供dj个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。

借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。

现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改订单。

【输入】

输入文件为 classroom.in。

第一行包含两个正整数n, m,表示天数和订单的数量。

第二行包含n个正整数,其中第i个数为ri,表示第i天可用于租借的教室数量。

接下来有m行,每行包含三个正整数dj, sj,tj,表示租借的数量,租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。

【输出】

输出文件为 classroom.out。

如果所有订单均可满足,则输出只有一行,包含一个整数 0。否则(订单无法完全满足)输出两行,第一行输出一个负整数-1,第二行输出需要修改订单的申请人编号。

【输入输出样例】

【输入输出样例说明】

第 1 份订单满足后,4 天剩余的教室数分别为 0,3,2,3。第 2 份订单要求第 2 天到

第 4 天每天提供 3 个教室,而第 3 天剩余的教室数为 2,因此无法满足。分配停止,通知第2 个申请人修改订单。

【数据范围】

答案与解析
参考答案

#include <bits/stdc++.h>

using namespace std;

const int SIZE=2000005;

 

bool check(int t);

 

struct node{

    int d,s,t;

}a[SIZE];

int r[SIZE],c[SIZE]; 

 

int n,m,ans=0;

 

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=1;i<=n;i++) scanf("%d",&r[i]);

    for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].d,&a[i].s,&a[i].t);

    

    int L=1,R=m,mid;

    while (L<=R){

        mid=(L+R)/2;

        if (!check(mid)){  //二分搜索

            ans=mid;

            R=mid-1;

        }

        else L=mid+1;

    }

    

    if (!ans) printf("0");

    else   printf("-1\n%d",ans);

    

    return 0;

}

 

bool check(int t)

{

    memset(c,0,sizeof(c));

    int sum=0;

    bool flag=true;

    for (int i=1;i<=t;i++){

        c[a[i].s]+=a[i].d;

        c[a[i].t+1]-=a[i].d; //进行差分检查 

    }

    for (int i=1;i<=n;i++){

        sum+=c[i];

        if (sum>r[i]){

            flag=false;

            break;

        }

    }

    return flag;

}

题目详情
505 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

聪明的质监员

【问题描述】

小 T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 n 个矿石,从 1到 n 逐一编号,每个矿石都有自己的重量 wi 以及价值 vi。检验矿产的流程是:

1、给定 m 个区间[Li,Ri];

2、选出一个参数 W;

3、对于一个区间[Li,Ri],计算矿石在这个区间上的检验值 Yi :

这批矿产的检验结果 Y 为各个区间的检验值之和。即:

若这批矿产的检验结果与所给标准值 S 相差太多,就需要再去检验另一批矿产。小 T不想费时间去检验另一批矿产,所以他想通过调整参数 W 的值,让检验结果尽可能的靠近标准值 S,即使得 S-Y 的绝对值最小。请你帮忙求出这个最小值。

【输入】

输入文件 qc.in。

第一行包含三个整数 n,m,S,分别表示矿石的个数、区间的个数和标准值。

接下来的 n 行,每行 2 个整数,中间用空格隔开,第 i+1 行表示 i 号矿石的重量 wi 和价值 vi 。

接下来的 m 行,表示区间,每行 2 个整数,中间用空格隔开,第 i+n+1 行表示区间[Li, Ri]的两个端点 Li 和 Ri。注意:不同区间可能重合或相互重叠。

【输出】

输出文件名为 qc.out。

输出只有一行,包含一个整数,表示所求的最小值。

【输入输出样例】

【输入输出样例说明】

当 W 选 4 的时候,三个区间上检验值分别为 20、5、0,这批矿产的检验结果为 25,此时与标准值 S 相差最小为 10。

【数据范围】

对于 10%的数据,有 1≤n,m≤10;

对于 30%的数据,有 1≤n,m≤500;

对于 50%的数据,有 1≤n,m≤5,000;

对于 70%的数据,有 1≤n,m≤10,000;

对于 100%的数据,有 1≤n,m≤200,000,0 < wi, vi≤10^6,0 < S≤10^12,1≤Li≤Ri≤n。

答案与解析
参考答案

#include <bits/stdc++.h>

#define int long long

using namespace std;

 

const int Max=200005;

int n,m,s,l,r,mid,maxx,ans=1e18,v;

int w[Max],c[Max],sum1[Max],sum2[Max],L[Max],R[Max];

 

inline int get_int()

{

int x=0,f=1;

char c;

for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());

if(c=='-') f=-1,c=getchar();

for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';

return x*f;

}

 

inline int check(int W)

{

int ans=0;

for(int i=1;i<=n;i++)

{

  sum1[i]=sum1[i-1],sum2[i]=sum2[i-1];

  if(w[i]>=W) sum1[i]+=c[i],sum2[i]++;

}

for(int i=1;i<=m;i++) ans+=(sum2[R[i]]-sum2[L[i]-1])*(sum1[R[i]]-sum1[L[i]-1]);

return ans;

}

 

signed main()

{

n=get_int(),m=get_int(),s=get_int();

for(int i=1;i<=n;i++) w[i]=get_int(),c[i]=get_int(),maxx=max(maxx,w[i]);

for(int i=1;i<=m;i++) L[i]=get_int(),R[i]=get_int();

l=1,r=maxx;

while(l<r)

{

   mid=(l+r)>>1,v=check(mid);

   if(v<=s) ans=min(s-v,ans),r=mid;

   else l=mid+1;

}

l=1,r=maxx;

while(l<r)

{

  mid=(l+r+1)>>1,v=check(mid);

  if(v>=s) ans=min(ans,v-s),l=mid;

  else r=mid-1;

}

cout<<ans;

return 0;

}

题目详情
506 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

观光公交

【问题描述】

风景迷人的小城 Y 市,拥有 n 个美丽的景点。由于慕名而来的游客越来越多,Y 市特意安排了一辆观光公交车,为游客提供更便捷的交通服务。观光公交车在第 0 分钟出现在 1号景点,随后依次前往 2、3、4……n 号景点。从第 i 号景点开到第 i+1 号景点需要 Di 分钟。任意时刻,公交车只能往前开,或在景点处等待。

设共有 m 个游客,每位游客需要乘车 1 次从一个景点到达另一个景点,第 i 位游客在Ti 分钟来到景点 Ai,希望乘车前往景点 Bi(Ai<Bi)。为了使所有乘客都能顺利到达目的地,公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。 

一个乘客的旅行时间,等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车,有时候还要停下来等其他乘客,乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 ZZ 给公交车安装了 k 个氮气加速器,每使用一个加速器,可以使其中一个 Di 减 1。对于同一个 Di 可以重复使用加速器,但是必须保证使用后 Di 大于等于 0。

那么 ZZ 该如何安排使用加速器,才能使所有乘客的旅行时间总和最小?

【输入】

输入文件名为 bus.in。

第 1 行是 3 个整数 n, m, k,每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。

第 2 行是 n-1 个整数,每两个整数之间用一个空格隔开,第 i 个数表示从第 i 个景点开往第 i+1 个景点所需要的时间,即 Di。

第 3 行至 m+2 行每行 3 个整数 Ti, Ai, Bi,每两个整数之间用一个空格隔开。第 i+2 行表示第 i 位乘客来到出发景点的时刻,出发的景点编号和到达的景点编号。

【输出】

输出文件名为 bus.out。共一行,包含一个整数,表示最小的总旅行时间。

【输入输出样例】 

【输入输出样例说明】

对 D2 使用 2 个加速器,从 2 号景点到 3 号景点时间变为 2 分钟。

公交车在第 1 分钟从 1 号景点出发,第 2 分钟到达 2 号景点,第 5 分钟从 2 号景点出发,

第 7 分钟到达 3 号景点。

第 1 个旅客旅行时间 7-0 = 7 分钟。

第 2 个旅客旅行时间 2-1 = 1 分钟。

第 3 个旅客旅行时间 7-5 = 2 分钟。

总时间 7+1+2 = 10 分钟。

【数据范围】

对于 10%的数据,k=0;

对于 20%的数据,k=1;

对于 40%的数据,2 ≤ n ≤ 50,1 ≤ m ≤ 1,000,0 ≤ k ≤ 20,0 ≤ Di ≤ 10,0 ≤ Ti ≤ 500;

对于 60%的数据,1 ≤ n ≤ 100,1 ≤ m ≤ 1,000,0 ≤ k ≤ 100,0 ≤ Di ≤ 100,0 ≤ Ti ≤ 10,000;

对于 100%的数据,1 ≤ n ≤ 1,000,1 ≤ m ≤ 10,000,0 ≤ k ≤ 100,000,0 ≤ Di ≤ 100,0 ≤ Ti ≤ 100,000。

答案与解析
参考答案

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn=1010;

const int maxm=10010;

int d[maxn];//en[maxn];

int dis[maxn];

int a[maxm],b[maxm],t[maxm];

int tim[maxn];

int c[maxn];

int g[maxn];

int main(){

freopen("bus.in","r",stdin);

freopen("bus.out","w",stdout);

int n,m,k;

scanf("%d %d %d",&n,&m,&k);

for(int i=1;i<n;i++)

scanf("%d",&d[i]);

for(int i=1;i<=m;i++){

scanf("%d %d %d",&t[i],&a[i],&b[i]);

//en[b[i]]++;

tim[a[i]]=max(tim[a[i]],t[i]);

c[b[i]]++;

}

for(int i=1;i<n;i++)

dis[i+1]=max(tim[i],dis[i])+d[i];

int ans=0;

for(int i=1;i<=m;i++)

ans+=dis[b[i]]-t[i];

for(int i=2;i<=n;i++)

c[i]=c[i-1]+c[i];

while(k--){

g[n]=n;

g[n-1]=n;

for(int i=n-2;i;i--){

if(dis[i+1]>tim[i+1])

g[i]=g[i+1];

else g[i]=i+1;

}

int maxx=0,u;

for(int i=1;i<=n;i++)

if(c[g[i]]-c[i]>maxx&&d[i]>0){

maxx=c[g[i]]-c[i];

u=i;

}

if(!maxx)

break;

d[u]--;

ans-=maxx;

dis[1]=0;

for(int i=1;i<n;i++)

dis[i+1]=max(tim[i],dis[i])+d[i];

}

printf("%d\n",ans);

return 0;

}

题目详情
507 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

乌龟棋

【问题描述】

小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘是一行 N 个格子,每个格子上一个分数(非负整数)。棋盘第 1 格是唯一的起点,第 N 格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 M 张爬行卡片,分成 4 种不同的类型(M 张卡片中不一定包含所有 4 种类型的卡片,见样例),每种类型的卡片上分别标有 1、2、3、4 四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次。游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?

【输入】

输入文件名 tortoise.in。输入文件的每行中两个数之间用一个空格隔开。

第 1 行 2 个正整数 N 和 M,分别表示棋盘格子数和爬行卡片数。

第 2 行 N 个非负整数,a1, a2, ……, aN,其中 ai 表示棋盘第 i 个格子上的分数。

第 3 行 M 个整数,b1,b2, ……, bM,表示 M 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 M 张爬行卡片,即

【输出】

输出文件名 tortoise.out。

输出只有 1 行,1 个整数,表示小明最多能得到的分数。

【输入输出样例 1】

【输入输出样例 1 说明】

小明使用爬行卡片顺序为 1,1,3,1,2,得到的分数为 6+10+14+8+18+17=73。注意,

由于起点是 1,所以自动获得第 1 格的分数 6。

【输入输出样例 2】

【数据范围】

对于 30%的数据有 1 ≤ N ≤ 30,1 ≤ M ≤ 12。

对于 50%的数据有 1 ≤ N ≤ 120,1 ≤ M ≤ 50,且 4 种爬行卡片,每种卡片的张数不会超

过 20。

对于 100%的数据有 1 ≤ N ≤ 350,1 ≤ M ≤ 120,且 4 种爬行卡片,每种卡片的张数不会

超过 40;0 ≤ ai ≤ 100,1 ≤ i ≤ N;1 ≤ bi ≤ 4,1 ≤ i ≤ M。输入数据保证

答案与解析
参考答案

#include <bits/stdc++.h>

#define LL long long

using namespace std;

const int maxs=41;

int f[maxs][maxs][maxs][maxs],a[5],q[352];

int main(){

int n,m,x;

scanf("%d %d",&n,&m);

for(int i=0;i<n;i++)scanf("%d",q+i);

for(int i=0;i<m;i++){

scanf("%d",&x);

a[x]++;

}

f[0][0][0][0]=q[0];

for(int i=0;i<=a[1];i++){

for(int j=0;j<=a[2];j++){

for(int k=0;k<=a[3];k++){

for(int l=0;l<=a[4];l++){

x=i+j*2+k*3+l*4;

if(i!=0)f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+q[x]);

if(j!=0)f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+q[x]);

if(k!=0)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+q[x]);

if(l!=0)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+q[x]);

}

}

}

}

cout<<f[a[1]][a[2]][a[3]][a[4]];

return 0;

}

题目详情
508 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

Hankson 的趣味题

【问题描述】

Hanks 博士是 BT (Bio-Tech,生物技术) 领域的知名专家,他的儿子名叫 Hankson。现在,刚刚放学回家的 Hankson 正在思考一个有趣的问题。

今天在课堂上,老师讲解了如何求两个正整数 c1 和 c2 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识,他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”,这个问题是这样的:已知正整数 a0,a1,b0,b1,设某未知正整数 x 满足:

1. x 和 a0 的最大公约数是 a1;

2. x 和 b0 的最小公倍数是 b1。

Hankson 的“逆问题”就是求出满足条件的正整数 x。但稍加思索之后,他发现这样的x 并不唯一,甚至可能不存在。因此他转而开始考虑如何求解满足条件的 x 的个数。请你帮助他编程求解这个问题。

【输入】

输入文件名为 son.in。第一行为一个正整数 n,表示有 n 组输入数据。接下来的 n 行每行一组输入数据,为四个正整数 a0,a1,b0,b1,每两个整数之间用一个空格隔开。输入数据保证 a0 能被 a1 整除,b1 能被 b0 整除。

【输出】

输出文件 son.out 共 n 行。每组输入数据的输出结果占一行,为一个整数。

对于每组数据:若不存在这样的 x,请输出 0;

若存在这样的 x,请输出满足条件的 x 的个数

【输入输出样例】

【说明】

第一组输入数据,x 可以是 9、18、36、72、144、288,共有 6 个。

第二组输入数据,x 可以是 48、1776,共有 2 个。

【数据范围】

对于 50%的数据,保证有 1≤a0,a1,b0,b1≤10000 且 n≤100。

对于 100%的数据,保证有 1≤a0,a1,b0,b1≤2,000,000,000 且 n≤2000。

答案与解析
参考答案

#include<iostream>

#include<cstdio>

#define LL long long

using namespace std;

LL n,a0,a1,b0,b1,a,b,ans,c,d,t;

LL gcd(LL a,LL b)

{

    if(b==0)return a;

    return gcd(b,a%b);

}

int main()

{

    //freopen("son.in","r",stdin);

    //freopen("son.out","w",stdout);

    scanf("%d",&n);

    while(n--)

    {

        ans=0;

        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);

        for(int i=1;i*i<=b1;i++)

        {

            if(b1%i!=0)continue;

            t=b1/i;

            a=gcd(i,a0);

            b=b0*i/gcd(i,b0);

            if(a1==a&&b1==b)ans++;

            c=gcd(t,a0);

            d=b0*t/gcd(t,b0);

            if(a1==c&&b1==d&&t!=i)ans++;

        }

        cout<<ans<<endl;

    }

    return 0;

}

题目详情
509 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

统计数字

【问题描述】

某次科研调查时得到了 n 个自然数,每个数均不超过 1500000000(1.5*109)。已知不相同的数

不超过 10000 个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输出统

计结果。

【输入】

 输入文件 count.in 包含 n+1 行:

 第 1 行是整数 n,表示自然数的个数。

 第 2~n+1 行每行一个自然数。

【输出】

 输出文件 count.out 包含 m 行(m 为 n 个自然数中不相同数的个数),按照自然数从小到大

的顺序输出。每行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格隔开。

【输入输出样例】

【限制】

 40%的数据满足:1<=n<=1000

 80%的数据满足:1<=n<=50000

 100%的数据满足:1<=n<=200000,每个数均不超过 1 500 000 000(1.5*10^9)

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

const int N=1e5;

long long a[N];

struct s

{

long long num;

long long sum;

}s[100001];

bool cmp(struct s a,struct s b)

{

return a.num<b.num;

}

long long n,m,i;

int main()

{

map<long long,int>mp;

    cin>>n;

    for(i=1;i<=n;i++)

    {

    cin>>a[i];

    mp[a[i]]++;

}

sort(a+1,a+n+1); 

n=unique(a+1,a+1+ n)-(a+1);

for(i=1;i<=n;i++)

{

s[i].num=a[i];

s[i].sum=mp[a[i]];

}

sort(s+1,s+1+n,cmp);

for(i=1;i<=n;i++)

{

cout<<s[i].num<<" "<<s[i].sum<<endl;

}

return 0;

} 

题目详情
510 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

矩阵取数游戏

【问题描述】

 帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的 n*m 的矩阵,矩阵中的每个元素 aij均为非负整数。游戏规则如下:

1. 每次取数时须从每行各取走一个元素,共 n 个。m 次后取完矩阵所有元素;

2. 每次取走的各个元素只能是该元素所在行的行首或行尾;

3. 每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的元素值*2i,其中 i 表示第 i 次取数(从 1 开始编号);

4. 游戏结束总得分为 m 次取数得分之和。

帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。

【输入】

 输入文件 game.in 包括 n+1 行:

 第 1 行为两个用空格隔开的整数 n 和 m。

 第 2~n+1 行为 n*m 矩阵,其中每行有 m 个用单个空格隔开的非负整数。

【输出】

 输出文件 game.out 仅包含 1 行,为一个整数,即输入矩阵取数后的最大得分。

【输入输出样例 1】

【输入输出样例 1 解释】

第 1 次:第 1 行取行首元素,第 2 行取行尾元素,本次得分为 1*21+2*21=6

第 2 次:两行均取行首元素,本次得分为 2*22+3*22=20

第 3 次:得分为 3*23+4*23=56。总得分为 6+20+56=82

【输入输出样例 2】

【输入输出样例 3】

【限制】

 60%的数据满足:1<=n, m<=30, 答案不超过 10^16

 100%的数据满足:1<=n, m<=80, 0<=aij<=1000

答案与解析
参考答案

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <iomanip>

using namespace std;

const int maxnum = 35;

const int M = 100000000;

typedef unsigned long long ll;

int n, m, map[81][81];

struct highNum

{

    ll num[maxnum];

    highNum(int length = 1)

    {

        memset(num, 0, sizeof(num));

        num[0] = length;

    }

    highNum operator = (highNum b)

    {

        memcpy(num, b.num, sizeof(b.num));

        return *this;

    }

    highNum operator = (int b)

    {

        *this = highNum();

        num[num[0]] = b;

        return *this;

    }

    bool operator < (const highNum& b) const

    {

        if(num[0] < b.num[0]) return true;

        if(num[0] == b.num[0])

        {

            for(int i = num[0]; i >= 1; --i)

            {

                if(num[i] > b.num[i]) return false;

                if(num[i] < b.num[i]) return true;

            }

        }

        return false;

    }

    highNum operator + (const highNum& b) const

    {

        highNum c = highNum(max(num[0], b.num[0]));

        for(int i = 1; i <= c.num[0]; ++i)

        {

            c.num[i] += num[i] + b.num[i];

            c.num[i + 1] += c.num[i] / M;

            c.num[i] %= M;

        }

        while(c.num[c.num[0] + 1] > 0)

        {

            ++c.num[0];

            c.num[c.num[0] + 1] += c.num[c.num[0]] / M;

            c.num[c.num[0]] %= M; 

        }

        return c;

    }

    highNum operator * (const int b) const

    {

        highNum c = highNum(num[0]);

        for(int i = 1; i <= c.num[0]; ++i)

        {

            c.num[i] += num[i] * b;

            c.num[i + 1] += c.num[i] / M;

            c.num[i] %= M;

        }

        while(c.num[c.num[0] + 1] > 0)

        {

            ++c.num[0];

            c.num[c.num[0] + 1] += c.num[c.num[0]] / M;

            c.num[c.num[0]] %= M;

        }

        while(c.num[c.num[0]] == 0 && c.num[0] > 1) --c.num[0];

        return c;

    }

    highNum operator * (const highNum& b) const

    {

        highNum c = highNum(num[0] + b.num[0]);

        for(int i = 1; i <= num[0]; ++i) for(int j = 1; j <= b.num[0]; ++j)

        {

            c.num[i + j - 1] += num[i] * b.num[j];

            c.num[i + j] += c.num[i + j - 1] / M;

            c.num[i + j - 1] %= M;

        }

        while(c.num[c.num[0] + 1] > 0)

        {

            ++c.num[0];

            c.num[c.num[0] + 1] += c.num[c.num[0]] / M;

            c.num[c.num[0]] %= M;

        }

        while(c.num[c.num[0]] == 0 && c.num[0] > 1) --c.num[0];

        return c;

    }

};

ostream& operator << (ostream& o, highNum& b)

{

    o << b.num[b.num[0]];

    o.setf(ios::fixed);

    o.width(8);

    o.fill('0');

    for(int i = b.num[0] - 1; i >= 1; --i) o << b.num[i];

    return o;

}

highNum ans, f[81][81], pw[81];

void init()

{

    cin >> n >> m;

    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j)

        cin >> map[i][j];

    pw[1] = 2;

    for(int i = 2; i <= m; ++i) pw[i] = pw[i - 1] * 2;

}

void work(int row)

{

    for(int i = 1; i <= m; ++i) for(int j = 1; j <= m; ++j)

        f[i][j] = highNum();

    for(int i = 1; i <= m; ++i) f[i][i] = pw[m] * map[row][i];

    for(int p = 1; p < m; ++p) for(int i = 1; i <= m - p; ++i)

    {

        int j = i + p;

        f[i][j] = max(f[i + 1][j] + pw[m - p] * map[row][i], f[i][j - 1] + pw[m - p] * map[row][j]);

    }

    ans = ans + f[1][m];

}

int main()

{

    init();

    for(int i = 1; i <= n; ++i) work(i);

    cout << ans;

    return 0;

}

题目详情
511 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

能量项链

【问题描述】

在 Mars 星球上,每个 Mars 人都随身佩带着一串能量项链。在项链上有 N 颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样,通过吸盘(吸盘是 Mars 人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 m,尾标记为 r,后一颗能量珠的头标记为 r,尾标记为 n,则聚合后释放的能量为(Mars 单位),新产生的珠子的头标记为 m,尾标记为 n。

需要时,Mars 人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释

放出的总能量最大。

例如:设 N=4,4 颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。我们用记号⊕表示两颗珠子的聚合操作,(j⊕k)表示第 j,k 两颗珠子聚合后所释放的能量。则第 4、1 两颗珠子聚合后释放的能量为:

(4⊕1)=10*2*3=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为

((4⊕1)⊕2)⊕3)=10*2*3+10*3*5+10*5*10=710。

【输入文件】

输入文件 energy.in 的第一行是一个正整数 N(4≤N≤100),表示项链上珠子的个数。第二行是 N 个用空格隔开的正整数,所有的数均不超过 1000。第 i 个数为第 i 颗珠子的头标记(1≤i≤N),当 i<N 时,第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记。第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。

至于珠子的顺序,你可以这样确定:将项链放到桌面上,不要出现交叉,随意指定第一颗珠子,然后按顺时针方向确定其他珠子的顺序。

【输出文件】

输出文件 energy.out 只有一行,是一个正整数 E(E≤2.1*),为一个最优聚合顺序所释放的总能量。

【输入样例】

 4

 2 3 5 10

【输出样例】

710

答案与解析
参考答案

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

long long head[220],tail[220];

long long f[220][220];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=1; i<=n; i++)   //环转为链 变为2倍长度

    {

        scanf("%lld",&head[i]);

        head[i+n]=head[i];

    }

    for(int i=1; i<=2*n-1; i++) //计算出每个珠子的尾标记

        tail[i]=head[i+1];

    tail[2*n]=head[1];

    for(int i=1; i<=2*n-1; i++) //初始化

        f[i][i]=0;

    int j;

    for(int t=1; t<=n-1; t++)//阶段 合并次数

    {

        for(int i=1; i<=2*n-t; i++)//状态 起始位置

        {

            j=i+t;//计算结束位置

            for(int k=i; k<=j-1; k++)

                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+head[i]*tail[k]*tail[j]);

        }

    }

    long long maxx=0;

    for(int i=1; i<=n; i++)

        maxx=max(maxx,f[i][i+n-1]);

    printf("%lld\n",maxx);

    return 0;

}

题目详情