首页 > 代码库 > 2016年9月25日四校联考
2016年9月25日四校联考
·前言：啊f**k今天早上体检，但是并不影响做题2333因为题目真的好 NOIP 啊
啊对了附中评测姬好坑啊正解强行T 23333
第一题《萝卜种子》
简要题意：小姑娘看了看狐狸的萝卜田，发现田里最多只能生长7个萝卜(多余的种子不会发芽)，且4种萝卜发芽的概率是完全相同的。它们的效果分别是：
普通萝卜：生产2kg兔粮
超能萝卜：生产2kg兔粮，每种植一个其他萝卜额外产生1kg兔粮
固氮萝卜：不能用于生产兔粮，但能使每个普通萝卜和超能萝卜生产的兔粮+1kg
金坷垃萝卜：不能用于生产兔粮，但能使每个普通萝卜和超能萝卜生产的兔粮+2kg
【输入数据】
一行，四个正整数，表示Npt，Ncn，Ngd，Njkl
【输出数据】
一行，一个数表示生产兔粮的期望值(保留2位小数)
【样例输入1】
1 1 1 1
【样例输出1】
13.00
【样例输入2】
2 2 2 2
【样例输出2】
35.50 //(36+40+30+36)/4=35.50
【数据范围】
对于50%的数据，Npt+Ncn+Ngd+Njkl<=7
对于100%的数据，Npt，Ncn，Ngd，Njkl<=10
题解：这一题来源于炉石传说圣骑士的斩杀
这题我们写个暴力就能过了，记住做的时候写组合数算方案。。。QAQ
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #include <cmath> 5 #include <string> 6 using namespace std; 7 long double C(int a,int b) 8 { 9 if (a<b) return 0;10 int i;11 long double kk=1;12 for (i=a;i>=a-b+1;i--) kk=kk*i;13 for (i=b;i>=1;i--) kk=kk/i;14 return kk;15 }16 int main()17 {18 int a,b,c,d;19 freopen("seed.in","r",stdin);20 freopen("seed.out","w",stdout);21 cin>>a>>b>>c>>d;22 int minkeng=min(7,a+b+c+d);23 double zy=1.0/C(a+b+c+d,minkeng);24 double ans=0;25 for (int i=0;i<=a;i++)26 for (int j=0;j<=b;j++)27 for (int k=0;k<=c;k++)28 for (int p=0;p<=d;p++)29 {30 if (i+j+k+p!=minkeng)31 continue;32 long double wwd=C(a,i)*C(b,j)*C(c,k)*C(d,p)*zy;33 int aa;34 aa=k*(i+j)+2*p*(i+j);35 aa+=i*2+(minkeng+1)*j;36 ans+=wwd*aa;37 }38 printf("%.2lf",ans);39 return 0;40 }
第二题《击败黑熊》
简要题意：凶恶的黑熊的陷阱一共有N+1个机关，机关分为3种，它们分别是：
守卫机关(d)：该机关有一个守卫，守卫不会主动攻击，小兔可以选择无视守卫直接通过机关或者杀死该守卫，杀死守卫会使自身的罪恶值+1，并获得一定数量的战斗力
审判机关(p)：该机关有一个守卫，不能被杀死，如果小兔的罪恶值大于或等于守卫的触发上限，守卫就会主动攻击小兔，小兔直接阵亡
黑熊机关：前N个机关均不是黑熊机关，第N+1个机关一定是黑熊机关，只有小兔的罪恶值大于或等于M才能通过，否则小兔直接阵亡
小兔希望在通关的基础上获得最大的战斗力以便和黑熊硬碰硬。
【输入数据】
第一行两个整数N,M
接下来N行描述第1~N个机关，每行一个字符和一个数值
字符为d：该机关是守卫机关，后面的数值表示击杀守卫获得的战斗力
字符为p：该机关是审判机关，后面的数值表示守卫的触发上限
【输出数据】
小兔一定会阵亡输出“Rabbit can not beat bear.”(不含引号)，否则输出一个整数表示小兔所能获得的最大战斗力
【样例输入】
4 2
d 1
d 2
p 2
d 1
【样例输出】
3
【数据范围】
对于10%的数据，N=0
对于20%的数据，N<=500
对于40%的数据，N<=8000
另有20%的数据，没有审判机关
对于100%的数据，N<=500000
答案保证不超过2147483647
题解：啊，这题的话我们可以脑补一下，我们会发现在遇到审判机关时，它只审判罪恶值而不是战斗力，所以我们可以维护一个小根堆，把战斗力小的都删除掉，一遍遍模拟就好了
1 #include <iostream> 2 #include <algorithm> 3 #include <stdio.h> 4 #include <cmath> 5 #include <string> 6 #include <string.h> 7 #include <numeric> 8 #include <queue> 9 #define gc getchar()10 #define REM main11 using namespace std;12 priority_queue<int,vector<int>, greater<int> >q;13 int read()14 {15 int xxxx=0,fuh=1;char ch=gc;16 while(!isdigit(ch)){17 if(ch==‘-‘)fuh=-1;18 ch=gc;19 }20 while(isdigit(ch)){21 xxxx=(xxxx<<3)+(xxxx<<1)+ch-‘0‘;ch=gc;22 }23 return xxxx*fuh;24 }25 /*int pow4(int a,int b)26 {27 int r=1,base=a;28 while(b!=0)29 {30 if(b&1)31 r*=base;32 base*=base;33 b>>=1;34 }35 return r;36 }*/37 int REM()38 {39 cin.sync_with_stdio(false);40 int n,m;41 freopen("beatbear.in","r",stdin);42 freopen("beatbear.out","w",stdout);43 n=read();m=read();int cnt=0;44 for (int i=1;i<=n;i++)45 {46 char ch;47 ch=gc;48 if (ch==‘d‘)49 {50 int k=read();51 q.push(k);52 cnt++;53 }54 else55 {56 int k=read();57 while(cnt>=k)58 {59 cnt--;60 q.pop();61 }62 }63 }64 if (cnt<m)65 {66 cout<<"Rabbit can not beat bear.";67 return 0;68 }69 int ans=0;70 while(cnt>0)71 {72 ans+=q.top();73 q.pop();74 cnt--;75 }76 cout<<ans;77 return 0;78 }
第三题：《种萝卜2》
简要题意：在嫦娥的帮助下，狐狸将土地拓成了M个坑排成一排，从左到右按1~M编号，每个坑里可以种一个胡萝卜，在N天小兔都会凭心情选择一个坑，狐狸会到那个坑种胡萝卜，如果已经被占用，则会种在前一个坑里，如果依然被占用，狐狸会再往前找空的坑，直到找到空的坑或者发现前面没有可用的坑为止。你本来需要输出N行，每一行表示当天的胡萝卜将种在哪一个坑里(无法种下输出0)，但为了避免输出占用过多的时间，你只需要输出(1*第一天+2*第二天+……+N*第N天)%1000000007的结果即可
【输入数据】
第一行两个整数N,M
接下来一个N个整数，表示当天小兔选择的坑
【输出数据】
一行，一个整数，意义如题目描述
【样例输入】
5 8
7 7 1 6 1
【样例输出】
42 //1*7+2*6+3*1+4*5+5*0=42
【数据范围】
对于30%的数据，N，M<=1000
对于70%的数据，N，M<=200000
对于100%的数据，N，M<=3000000
题解：啊f**k我们写个并查集维护点i左边的最右是哪个点就好了。。
1 #include <iostream> 2 #include <algorithm> 3 #include <stdio.h> 4 #include <cmath> 5 #include <string> 6 #include <string.h> 7 #include <numeric> 8 #define gc getchar() 9 #define REM main10 using namespace std;11 int f[5000000+1];12 const long long mod=1000000007;13 int read()14 {15 int xxxx=0,fuh=1;char ch=gc;16 while(!isdigit(ch)){17 if(ch==‘-‘)fuh=-1;18 ch=gc;19 }20 while(isdigit(ch)){21 xxxx=(xxxx<<3)+(xxxx<<1)+ch-‘0‘;ch=gc;22 }23 return xxxx*fuh;24 }25 int find(int x)26 {27 if (x!=f[x])28 return f[x]=find(f[x]);29 return x;30 31 }32 int REM()33 {34 cin.sync_with_stdio(false);35 freopen("carrot.in","r",stdin);36 freopen("carrot.out","w",stdout);37 int n,m,i,j;38 n=read();m=read();39 for (i=1;i<=m;i++) f[i]=i;40 long long ans=0;41 for (i=1;i<=n;i++)42 {43 int x=read();44 int fa=find(x);45 if (fa==0) continue;46 f[fa]=fa-1;47 ans=(ans+(long long)fa%mod*(long long)i%mod)%mod;48 }49 cout<<ans;50 return 0;51 }
论体检插队...
2016年9月25日四校联考