【比赛】羊村的OIの题解

目录

• $$t1喜羊羊与灰太狼--仓库管理$$
  • $code$
• $$t2喜羊羊与灰太狼--破译密码$$
  • $code$
• $$t3喜羊羊与灰太狼--烦恼的礼物$$
  • $code$

---

$$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;
}

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