欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【比赛】羊村的OIの题解

程序员文章站 2022-09-27 23:12:23
[TOC] $$T1喜羊羊与灰太狼 仓库管理$$ 题目背景 这是一道送分题 可以开o2 题目描述 懒羊羊当上了羊村的仓库管理员。仓库里有很多很多筐的青草然而众所周知,懒羊羊是所有小羊里最贪吃的只。每当他想吃草时,就会从仓库里找出数量最少的一筐草,把它吃掉。(吃多了就会被喜羊羊惩罚) 输入输出格式 输 ......

$$t1喜羊羊与灰太狼--仓库管理$$

题目背景

这是一道送分题
可以开o2

题目描述

懒羊羊当上了羊村的仓库管理员。仓库里有很多很多筐的青草然而众所周知,懒羊羊是所有小羊里最贪吃的只。每当他想吃草时,就会从仓库里找出数量最少的一筐草,把它吃掉。(吃多了就会被喜羊羊惩罚)

输入输出格式

输入格式:

第$1$行$1$个正整数$n$,下面$n$行 当这行形式为q时,表示要吃掉仓库里当前数量最少的那筐青草; 当这行形式为一个字符i和一个整数$k$时,表示筐数量为$k$的青草存入了仓库数据保证一定饿的时候有草可以吃,(仓库不会空)

输出格式:

每行输出一行一个数,表示懒羊羊当前吃掉的那份青草的数量是多少

输入输出样例

输入样例#1:
5
i 5
i 2
q
i 9
q
输出样例#1:
2
5
说明
$1\le n \le 1000000$,$1\le k \le2000000000$
注意$k$可能比$2000000000$大一些($k \le 2200000000$),数据出了点小锅,见谅

思路:

$stl$大法好啊
priority_queue<int,vector<int>,greater<int> > q;相当于小根堆

$code$

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
int n;
priority_queue<int,vector<int>,greater<int> > q;
inline long long read(){
    long long x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f?-x:x;
}
int main(){
    n=read();
    char c;
    long long x;
    while(n--){
        cin>>c;
        if(c=='i'){
            x=read();
            if(x<=0x7fffffff)q.push(x);//数据水??
        }else {
            cout<<q.top()<<endl;
            q.pop();
        }
    }
    return 0;
}

$$t2喜羊羊与灰太狼--破译密码$$

题目背景

羊羊们因为仓库里的食物莫名变少,只能去狼堡偷吃的........可是灰太狼把羊羊们抓到了

题目描述

想要逃出狼堡很简单只需要破解密码就可以了

狼堡安装了$ai$管家傻强来看住小羊们可是聪明的喜羊羊黑入了管家傻强,傻强告诉了他们$n$个数,有任意个数出现了奇数次,有任意个数出现了偶数次,大门的密码就是分别输入出现了奇数次的数的所有正因数的个数。

输入输出格式

输入格式:
第 $1$ 行,一个正整数 $n$。 接下来$n$行,每行一个正整数 p($p \le 100000$) 。

输出格式:

每行输出两个数分别是出现了奇数次的数和它正因数的个数。按第一个数从小到大输出

输入输出样例

输入样例#1:
10
1
2
2
3
3
3
4
4
4
4
输出样例#1:
1 1
3 2
说明
30%的数据满足:$n \le 500$
50%的数据满足:$n \le 1000$
100%的数据满足:$n \le 10000$

思路

枚举

$code$

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n;
int pd[100001];
inline int read(){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f?-x:x;
}
inline void write(int x){
    if(x<0){putchar('-');write(-x);}
    else {if(x/10)write(x/10);putchar(x%10+'0');}
}

int main(){
    n=read();
    int x;
    int maxx=0;
    for(register int i=1;i<=n;++i){
        x=read();
        pd[x]++;
        maxx=maxx>x?maxx:x;
    }
    for(register int i=1;i<=maxx;++i){
        if(pd[i]!=0&&pd[i]%2!=0){
            int bz=sqrt(i),sum=0;
            for(register int j=1;j<=bz;++j){
                if(i%j==0) sum++;
            }
            write(i);
            printf(" ");
            if(bz*bz==i) write(sum*2-1);//当时少了这个判断零分
            else write(sum*2);
            puts("");
            //printf("%d %d\n",i,sum*2);
        }
    }
    return 0;
}

$$t3喜羊羊与灰太狼--烦恼的礼物$$

题目背景

就在千钧一发之际,刀羊爷爷开了鬼刀救出了羊羊们......
t3请按照样例说明写代码,必须每个人挨个借,借下一个人的必须花完或者扔完上一个人的

题目描述

羊羊们决定送给刀羊爷爷 $m$件礼物,决定顺序购买并赠送(注意是按顺序购买),但是羊羊们没有钱所以只能向 $n$位坑爹的建筑工人借钱,然而他们都是高利贷 为了减少最高的借款量,请你帮帮羊羊们.

输入输出格式

输入格式:

第一行输入两个用空格隔开的正整数 $m$ 和 $n$。 接下来 $m$ 行依次表示礼物的价格。

价格一定小于等于$10000$

输出格式:

一个数$money$表示最高借款量

输入输出样例

输入样例#1:
7 5
100
400
300
100
500
101
400
输出样例#1:
500
说明
看不懂的多看几遍
借第一个 $500$,够 $1,2$个人, 然后借第二个 $500$,够 $3,4$ 个人,下来不够第五个人,余下的钱全丢失。 借第三个 $500$,够第 $5$ 个人。 借第四个 $500$,够第 $6$个人,余下的钱全丢失。 借第五个 $500$,够第 $7$ 个人,全都发到礼物,任务完成。

30%的数据满足:$m \le 10$
60%的数据满足:$m \le 1000$
100%的数据满足:$m \le 100000$
$n \le 15000$

思路

二分答案

$code$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n,m,a[100001];
int l,r;
inline int read(){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f?-x:x;
}
bool check(int x,int tot=1){
    int flag=x;
    for(int i=1;i<=m;++i){
        if(a[i]<=flag) flag-=a[i];
        else flag=x-a[i],tot++;
        if(tot>n) return false;
    }
    return true;
}

int main(){
    m=read(),n=read();
    for(int i=1;i<=m;++i){
        a[i]=read();
        if(a[i]>l) l=a[i];
    }
    r=100000001;
    while(l<=r){
        int mid=(l+r)>>1;
        if(mid==0) break;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}

出题人说这场比赛太失败了,数据都很水