咕bye 2018,因为我这场又咕咕咕了

无谓地感慨一句:时间过得真快啊(有毒

A.New Year and the Christmas Ornament

分类讨论后等差数列求和

又在凑字数了

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a,b,c;
int main()
{
scanf("%d%d%d",&a,&b,&c);
printf("%d",min(min((a+)*,b*),(c-)*));
return ;
}

B.New Year and the Treasure Geolocation

坐标分别加起来除个$n$,没了

凑字数++

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,a,b,t1,t2;
int main()
{
scanf("%lld",&n);
for(int i=;i<=n;i++) scanf("%lld%lld",&t1,&t2),a+=t1,b+=t2;
for(int i=;i<=n;i++) scanf("%lld%lld",&t1,&t2),a+=t1,b+=t2;
printf("%lld %lld",a/n,b/n);
return ;
}

C.New Year and the Sphere Transmission

分解因数后变成了等差数列求和

凑字数停不下来了?

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,cnt,facs[N];
long long ans[N];
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
scanf("%d",&n);
for(int i=;i*i<=n;i++)
if(n%i==)
{
facs[++cnt]=i;
if(i*i!=n)
facs[++cnt]=n/i;
}
for(int i=;i<=cnt;i++)
{
int g=gcd(facs[i],n),tot=n/g;
ans[i]=1ll*(n-g+)*tot/;
}
sort(ans+,ans++cnt);
for(int i=;i<=cnt;i++)
printf("%lld ",ans[i]);
return ;
}

D.New Year and the Permutation Concatenation

不错的题 终于不在凑字数了

考虑容斥,计算不合法的方案数,这里我们要讲一讲如何实现next_permutation,是这样的:

以 1 3 5 4 2 为例

1.从序列末尾向前扫,直到一个位置pos序列开始下降 1 3 5 4 2

2.从后面这段递减的序列里找到第一个大于*pos的数,将pos位置的数与它交换 1 4 5 3 2

3.排序— —即翻转后面这段原来递减的序列 1 4 2 3 5

这样我们发现后面原来长度为n-pos的这段递减的序列被破坏了,而它原来是可以跟后面的一个排列配对的

那么显然对每个长度$len$统计有长度为$len$的递减序列的排列去掉即可(除了一种情况— —len==n,这时候没有排列能和它配对)

这样一来对每个$len$前$n-len$个可以随便排,后面$len$个又有$C_n^{len}$种选法,所以总方案数就是$\sum\limits_{len=1}^{n-1}\frac{n!}{len!}$,然后从总数里把这个容斥掉即可

 #include<cstdio>
const int N=,mod=;
int n,x,y,ans,fac[N],inv[N];
void exGCD(int &x,int &y,int a,int b)
{
if(!b) x=,y=;
else exGCD(y,x,b,a%b),y-=a/b*x;
}
int Inv(int nm,int md)
{
exGCD(x,y,nm,md);
return (x%md+md)%md;
}
int main()
{
scanf("%d",&n),fac[]=inv[]=;
for(int i=;i<=n;i++) fac[i]=1ll*fac[i-]*i%mod;
inv[n]=Inv(fac[n],mod),ans=1ll*n*fac[n]%mod;
for(int i=n-;i;i--) inv[i]=1ll*inv[i+]*(i+)%mod;
for(int i=;i<=n-;i++) ans-=1ll*fac[n]*inv[i]%mod,ans=(ans+mod)%mod;
printf("%d",ans);
return ;
}

E.New Year and the Acquaintance Estimation

观察样例/仔细分析/动手推理可以发现答案是一段隔2连续的区间!(我是第一种

所以只要求上下界就好了,怎么求呢?二分

怎么想到二分的呢?没想到,但是题目贴心地给了一个wiki的链接,里面有这样一个东西

这个定理可以在图的度数降序排好序的情况下检查图是否可行,这明摆着是告诉我们二分啊=。=

我们发现这个式子别的都好说,就是这个

$\sum\limits_{i=k+1}^{n}min(d_i,k)$

很麻烦啊,好像需要什么主席树/multiset?

并不需要,边扫边维护还未出现过的度数小于当前的$k$的点数的和sum即可,说白了就是前缀和,然后每次用$n-i-sum$更新。为什么?因为这就是后面那个式子里$k$的的贡献的增加量(未出现过的大于等于$k$的数)

注意二分+检查之后偏移的方向

 #include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int mem[N],tmp[N],bkt[N];
int n,l,r,rd,ld,hd,sum,odd;
bool cmp(int a,int b)
{
return a>b;
}
int check(int x)
{
int p=,pos=;
memset(bkt,,sizeof bkt);
for(int i=;i<=n;i++)
{
if(mem[i]<x&&p<i)
pos=++p,tmp[pos]=x;
tmp[++p]=mem[i];
}
if(!pos) pos=++p,tmp[pos]=x;
for(int i=;i<=p;i++) bkt[tmp[i]]++;
long long lsum=,rsum=,fsum=;
for(int i=;i<=p;i++)
{
lsum+=tmp[i],bkt[tmp[i]]--;
rsum+=*(i-),rsum-=min(tmp[i],i-);
fsum+=bkt[i-],rsum+=n-i+-fsum;
if(lsum>rsum) return i>=pos?:-;
}
return ;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&mem[i]),sum+=mem[i];
odd=sum%,sort(mem+,mem++n,cmp);
l=,r=(n-odd)/,ld=rd=-;
while(l<=r)
{
int mid=(l+r)/;
if(check(*mid+odd)<) l=mid+;
else ld=mid,r=mid-;
}
l=ld,r=(n-odd)/;
while(l<=r)
{
int mid=(l+r)/;
if(check(*mid+odd)>) r=mid-;
else rd=mid,l=mid+;
}
if(ld==-||rd==-) printf("-1");
else for(int i=ld;i<=rd;i++) printf("%d ",*i+odd);
return ;
}

F.New Year and the Mallard Expedition

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
char mapp[N]; long long len[N];
long long n,wat,spa,ans,sta;
int main()
{
scanf("%lld",&n);
for(int i=;i<=n;i++)
scanf("%lld",&len[i]);
scanf("%s",mapp+);
for(int i=;i<=n;i++)
{
if(mapp[i]=='G')
{
ans+=len[i]*;
spa+=len[i]*;
sta+=len[i];
}
else if(mapp[i]=='W')
{
wat=true;
ans+=len[i]*;
sta+=len[i];
}
else if(mapp[i]=='L')
{
if(sta<len[i])
{
ans+=(wat?:)*(len[i]-sta);
sta=len[i];
}
ans+=len[i];
sta-=len[i];
}
spa=min(spa,sta);
}
if(sta) ans-=sta+spa;//ans-=(5-1)*spa/2,ans-=(3-1)*(sta-spa)/2;
printf("%lld",ans);
return ;
}

首先模拟,草地先走路,水里游泳,岩浆飞过去。在这个过程中我们记录一下是否遇到了水,因为如果遇到岩浆飞不过去的情况,需要在之间走来走去/游来游去积攒体力。模拟的同时记录一个“可以用飞行代替行走”的路程的消耗,这个东西步步和你的耐力取min,最后如果它小于耐力就把它代表的行走换成飞行,如果还剩下一些就把一些游泳也换成飞行

最新文章

  1. Wine——在Linux上运行Windows软件
  2. js 阻止事件冒泡和默认行为 preventDefault、stopPropagation、return false
  3. 超详细的java反射教程
  4. delphi 弹出选择目录窗口
  5. Linux 命令 find
  6. Java和Ibatis调用存储过程并取得返回值详解
  7. PHP基础示例:用PHP+Mysql编写简易新闻管理系统
  8. 中国天气网API
  9. MySQL的C语言编程(一)
  10. 浅谈html入门
  11. 怎样让外界无法改变自定义view的尺寸大小
  12. java web 导出Excel 的工具类公用实现
  13. ES6入门2
  14. Linux多线程编程——线程的创建与退出
  15. 关于HTML5中的sessionStorage的会话级缓存使用
  16. 如果IBM再给我一次实习机会
  17. 【C/C++】实现牛顿迭代
  18. 【学习】pandas 基础介绍说明 【pandas】
  19. canvas-star7.html
  20. innobackupex per table

热门文章

  1. ionic 使用
  2. Linux下的文本编辑工具
  3. jqgrid 设置单元格编辑/不可编辑
  4. 基于memcached的单机轻量级通用缓存库minicached的实现
  5. HTML5的Server-Sent Events (SSE)
  6. 如何写一个数据库How do you build a database?(转载)
  7. myEclipse快捷键及其常用设置
  8. MySQL事务-ROLLBACK,COMMIT用法详解
  9. 2018-2019-2 《网络对抗技术》Exp0 Kali安装 Week1 20165321
  10. 教你如何修改运行中的docker容器的端口映射
  11. 炸金花游戏(4)--炸金花AI基准测试评估
  12. Discuz 论坛 (LAMP环境)
  13. Linux Shell自动交互/人机交互的三种方法
  14. XML文件处理
  15. c#继承中的函数调用实例
  16. java基础-day12
  17. 关于建立MySQL数据库,中文出现乱码问题
  18. C简介与环境配置
  19. 360随身wifi隐藏ssid方法
  20. vi作者:Bill Joy