就写了四题
前面两题没啥好讲的。
F The Pool for Lucky Ones
定义unlucky pool指没有pool中人比它更多的pool，在unlucky pool中的人会不开心，现在给你初始每个pool中的人数，你有一次机会（可以不用）把一个pool中的一个人转移到它相邻的一个pool里（首尾不相邻），求最小不开心人数
大特判题，判的要死了。显然假如我们不操作的话最终答案就是max*s,我们有两种办法使得答案变优，第一种是把一组max中的人往旁边挪一个，答案为max*(s-1)，假如s=1，而且不存在ai=max-1那么显然我们这么操作假如有效的话答案是max-1，第二种是当s>1时，我们可以通过让一个max变大，使得答案从max*s变成max+1。反正特判多的我要吐了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include<cstdio>using namespace std;int max,s,n;int a[100005];long long sum;inline long long min(long long x,long long y){return x<y?x:y;}int main(){ scanf("%d",&n); max=-1; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(max==a[i])s++; if(max<a[i]){ max=a[i]; s=1; } } bool b=false,B=false; for(int i=2;i<=n;i++)if(((a[i]==max)&&(a[i-1]<max-1))||((a[i-1]==max)&&(a[i]<max-1)))b=true; for(int i=1;i<=n;i++)if(a[i]==max-1)B=true; if(s==1){ bool f=false; for(int i=1;i<=n;i++)if(a[i]==max){ if(i>1)if(a[i-1]<max-2)f=true; if(i<n)if(a[i+1]<max-2)f=true; } if(B)printf("%d",max); else if(f)printf("%d",max-1); else printf("%d",max); }else{ bool f=false; for(int i=2;i<=n;i++)if(((a[i]==max)&&(a[i-1]>0))||((a[i-1]==max)&&(a[i]>0)))f=true; if(f){ f=false; for(int i=2;i<=n;i++)if(((a[i]==max)&&(a[i-1]>0))||((a[i-1]==max)&&(a[i]>0)))f=true; } if(f)if(b){ if(s==2)printf("%I64d",1LL*(s-1)*max); else printf("%d",max+1); }else printf("%d",max+1); else if(b)printf("%I64d",1LL*(s-1)*max); else printf("%I64d",1LL*max*s); }} |
K Microcircuits
现在在圆上有依次n个互不相同的点，我们要在它们之间连若干条线，使得线与线不相交而且没有公共顶点，求方案数。
一开始往polya定理想的我还是太年轻，摆渡了一下然后发现是卡特兰数裸题。。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include<cstdio>using namespace std;long long ca[45];int n,m;long long c(int x,int y){ if(x-y>y)y=x-y; long double ans=1; for(int i=y+1;i<=x;i++)ans*=i,ans/=i-y; return (long long)ans;}int main(){ scanf("%d%d",&n,&m); if(m*2>n){ printf("0"); return 0; } ca[0]=1; for(int i=1;i<=m;i++)ca[i]=ca[i-1]*(4*i-2)/(i+1); printf("%I64d",c(n,m*2)*ca[m]);} |
B lunch
现在你是一只蛤，有两种移动方式：1、跳1格2、跳2格。从左到右有N片荷叶，现在你要从S点出发，到达T点结束，每片都要经过且只经过1次，求最少要使用移动方式1几次。
显然起始点和终点可以交换所以我们可以强制S≤T，然后最优方案显然是从S开始一直2格2格向左跳，然后跳回来一直跳到N为止，然后再跳回来直到跳到T。
手撸了几个发现细节好多，然后就想看代码。
然后就深深的意识到了自己的TOO YOUNG TOO SIMPLE
然后我就生气地不打了来表达我的生气
MGJ人NAIVE有什么办法
填坑去了
评论 (0)
