2017-11-7离线赛总结

题目

3814,3815,3816

失分小结

估分

100+100+?≈210

实际分数

0+100+10=110
第一题输出调试没关啊啊啊爆零

题解

T1

P100

玄学贪心.

CODE

#include<cstdio>
#include<iostream>
using namespace std;
#define N 100005
int A[N];
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",A+i);
long long num=A[2]>A[1]?A[2]-A[1]:A[1]-A[2];
for(int i=3;i<=n;i++){
if(A[i]>=A[i-1]&&A[i-1]>=A[i-2])
num+=A[i]-A[i-1];
else if(A[i]<=A[i-1]&&A[i-1]<=A[i-2]){
num+=A[i-1]-A[i];
}
else if(A[i]<=A[i-1]&&A[i-1]>=A[i-2]){
A[i-1]=max(A[i],A[i-2]);
num+=A[i-1]-A[i];
}
else if(A[i]>=A[i-1]&&A[i-1]<=A[i-2]){
A[i-1]=min(A[i],A[i-2]);
num+=A[i]-A[i-1];
}
}
/*
for(int i=1;i<=n;i++)printf("%d ",A[i]);
puts("");
*///输出调试啊啊啊
printf("%lldn",num);
return 0;
}

T2

保存所有的点的子树大小 size 。

P95

CODE

//注意会炸long long!!!网站上95.当然本地测试还是有100的啦
#include<cstdio>
#include<memory.h>
#define N 500005
struct node2 {int to,len,nxt;} edge[N<<1];
int head[N],tot;
int fa[N],sz[N];
void dfs1(int x,int f) {
fa[x]=f;
sz[x]=1;
for(int i=head[x]; ~i; i=edge[i].nxt) {
node2 y=edge[i];
if(y.to==f)continue;
dfs1(y.to,x);
sz[x]+=sz[y.to];
}
}
int n,m;
long long ans=0;
void dfs(int x) {
for(int i=head[x]; ~i; i=edge[i].nxt) {
int y=edge[i].to;
if(y==fa[x])continue;
long long t=1ll*sz[y]*(n-sz[y]);
ans+=t*edge[i].len;
dfs(y);
}
}
int main() {
int a,b,c;
scanf("%d",&n);
memset(head,-1,sizeof head);
for(int i=1; i<n; i++) {
scanf("%d %d %d",&a,&b,&c);
edge[tot]=(node2) {b,c,head[a]},head[a]=tot++;
edge[tot]=(node2) {a,c,head[b]},head[b]=tot++;
}
dfs1(1,-1);
dfs(1);
printf("%.2lfn",6.0*ans/n/(n-1));
return 0;
}

P100

long long 改成 double ，顺便把一些累赘的代码去掉.

CODE

#include<cstdio>
#include<memory.h>
#define N 500005
struct node {int to,len,nxt;} edge[N<<1];
int head[N],tot;
int n,m;
int sz[N];
double ans=0;
void dfs(int x,int f) {
sz[x]=1;
for(int i=head[x]; ~i; i=edge[i].nxt) {
int y=edge[i].to;
if(y==f)continue;
dfs(y,x);
sz[x]+=sz[y];
ans+=(double)sz[y]*(n-sz[y])*edge[i].len;
}
}
int main() {
int a,b,c;
scanf("%d",&n);
memset(head,-1,sizeof head);
for(int i=1; i<n; i++) {
scanf("%d %d %d",&a,&b,&c);
edge[tot]=(node) {b,c,head[a]},head[a]=tot++;
edge[tot]=(node) {a,c,head[b]},head[b]=tot++;
}
dfs(1,-1);
printf("%.2lfn",6.0*ans/n/(n-1));
return 0;
}

T3

P100

玄学高精.常数优化!!!万进制可能卡不过去…亿进制600ms左右，十亿进制500ms左右（很多同学都只有300ms~400ms，一定是我太弱了）
当然 n=3 时由于长度一直为3按正常方法会超时于是特判改用快速幂.

CODE

#include<iostream>
#include<cstring>
#include<cstdio>
#define P 1000000000//1e9
#define reg register
#define FOR(i,a,b) for(reg int i=(a),i##_END_=(b);i<=i##_END_;i++)
#define ROF(i,a,b) for(reg int i=(a),i##_END_=(b);i>=i##_END_;i--)
typedef long long ll;
using namespace std;
int n;
struct Bignum {
int len;
ll num[10086];
Bignum() {len=1;memset(num,0,sizeof num);}
void Rd() {
char C[1005];
scanf("%s",C+1);
int n=strlen(C+1);
len=0;
for(int i=n; i>=1; i-=9) {
len++;
num[len]=0;
for(int j=max(1,i-8); j<=i; j++) {
num[len]=(num[len]<<3)+(num[len]<<1)+(C[j]^48);
}
}
while(!num[len])len--;
}
void print() {
printf("%lld",num[len]);
for(int i=len-1; i>=1; i--)printf("%09lld",num[i]);
puts("");
}
Bignum operator +(const Bignum &_)const {
Bignum Ans;
Ans.len=max(_.len,len);
for(reg int i=1; i<=Ans.len; i++) {
Ans.num[i]+=num[i]+_.num[i];
if(Ans.num[i]>=P) {
Ans.num[i]-=P;
Ans.num[i+1]++;
}
}
if(Ans.num[Ans.len+1])Ans.len++;
return Ans;
}
Bignum operator -(const Bignum &_)const {
Bignum Ans;
Ans.len=max(_.len,len);
FOR(i,1,Ans.len) {
Ans.num[i]+=num[i]-_.num[i];
if(Ans.num[i]<0) {
Ans.num[i]+=P;
Ans.num[i+1]--;
}
}
while(!Ans.num[Ans.len]&&len>1)Ans.len--;
return Ans;
}
void operator++ () {
num[1]++;
FOR(i,1,len) {
if(num[i]>=P) {
num[i]-=P;
num[i+1]++;
} else break;
}
if(num[len+1])len++;
}
void operator-- () {
num[1]--;
FOR(i,1,len) {
if(num[i]<0) {
num[i]+=P;
num[i+1]--;
} else break;
}
while(!num[len]&&len>1)len--;
}
Bignum operator *(const Bignum &_)const {
Bignum Ans;
Ans.len=_.len+len-1;
FOR(i,1,len)FOR(j,1,_.len) {
Ans.num[i+j-1]+=num[i]*_.num[j];
if(Ans.num[i+j-1]>=P) {
Ans.num[i+j]+=Ans.num[i+j-1]/P;
Ans.num[i+j-1]%=P;
}
}
while(Ans.num[Ans.len+1])Ans.len++;
return Ans;
}
bool operator <=(const Bignum &_)const {
if(_.len!=len)return len<_.len;
ROF(i,len,1)if(num[i]!=_.num[i])
return num[i]<_.num[i];
return 1;
}
} k;
struct P100 {
void solve() {
k.Rd();
Bignum mi,mx,c;
mi.num[1]=1,mx.num[1]=n;
c=mx-mi;++c;
if(k<=c) {
Bignum ans;
ans=mi+k;--ans;
ans.print();
} else {
k=k-c;
while(1) {
mi=mi+mi;++mi;
mx=mx+mx;--mx;
c=mx-mi;++c;
if(k<=c)break;
else k=k-c;
}
Bignum ans;
ans=mi+k;
--ans;
ans.print();
}
}
} pother;
struct Pn3 {
void solve() {
int k;
Bignum a;
a.num[1]=2;
Bignum ans;
ans.num[1]=1;
scanf("%d",&k);
int tmp=(k-1)/3+1;
while(tmp) {
if(tmp&1)ans=ans*a;
tmp>>=1;
if(!tmp)break;
a=a*a;
}
if(k%3==1)--ans;
else if(!(k%3))++ans;
ans.print();
}
} nequ3;
int main() {
scanf("%d",&n);
if(n==3)nequ3.solve();
else if(n<=2) {
k.Rd();
if(n==2&&k.len==1&&k.num[1]==1)puts("1");
else if(n==2&&k.len==1&&k.num[1]==2)puts("2");
else if(n==2&&k.len==1&&k.num[1]==3)puts("3");
else puts("-1");
} else pother.solve();
return 0;
}

最后

以上就是震动狗为你收集整理的2017-11-7离线赛总结的全部内容，希望文章能够帮你解决2017-11-7离线赛总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。