CFGR19

发表于 分类于
CFGR19

题面。

我只是贴个代码。。。

发现自己在思维题上容易吃大亏。。。

CF 比赛，Div2 的题实际上不会有什么难度。。。唯一的区分度就是手速和不吃扣分。。。

而且比赛实际上只有 2 个小时左右。。。对于这种题量来说，稍微思考一下很有可能时间就会比较紧张。。。所以 Div2 需要做的就是切题而不是想题。。。

Div1 似乎考到一些 CNOI 的考点必然成堆的人不会做，即便只是初涉省选级别的东西。。。这个时候就是练习熟练度的时候。。。

A.

Trivial 题。。。莽了个线段树吃了五发扣分。。。

只要判个是否不降就完了。。。

代码：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll inf=1e9+7,N=1e4,M=1e2;

ll T,amt;
ll n[M+5],a[M+5][N+5],uq[N+5];

struct Sgt{
  ll dat,mi,ma;
  #define dat1(x) tree1[x].dat
  #define dat2(x) tree2[x].dat
  #define ma1(x) tree1[x].ma
  #define ma2(x) tree2[x].ma
  #define mi1(x) tree1[x].mi
  #define mi2(x) tree2[x].mi
}tree1[N*4+5],tree2[N*4+5];

inline void Build(ll p,ll l,ll r) {
  if(l==r) {mi1(p)=mi2(p)=inf;return;}
  ll mid=(l+r)>>1;
  Build(p<<1,l,mid);Build(p<<1|1,mid+1,r);
  mi1(p)=inf;
  mi2(p)=inf;
}

inline void Clear(ll p,ll l,ll r) {
  if(l==r) {ma1(p)=ma2(p)=0;mi1(p)=mi2(p)=inf;dat1(p)=dat2(p)=0;return;}
  ll mid=(l+r)>>1;
  Clear(p<<1,l,mid);Clear(p<<1|1,mid+1,r);
  mi1(p)=inf;mi2(p)=inf;ma1(p)=0;ma2(p)=0;
}

inline void Add1(ll p,ll l,ll r,ll x,ll k) {
  if(l==r) {
    dat1(p)+=k;
    if(dat1(p)>0) {mi1(p)=l;ma1(p)=l;}
    else {mi1(p)=inf;ma1(p)=0;}
    return;
  }
  ll mid=(l+r)>>1;
  if(x<=mid) Add1(p<<1,l,mid,x,k);
  if(x>mid) Add1(p<<1|1,mid+1,r,x,k);
  ma1(p)=max(ma1(p<<1),ma1(p<<1|1));
  mi1(p)=min(mi1(p<<1),mi1(p<<1|1));
}

inline void Add2(ll p,ll l,ll r,ll x,ll k) {
  if(l==r) {
    dat2(p)+=k;
    if(dat2(p)>0) {mi2(p)=l;ma2(p)=l;}
    else {mi2(p)=inf;ma2(p)=0;}
    return;
  }
  ll mid=(l+r)>>1;
  if(x<=mid) Add2(p<<1,l,mid,x,k);
  if(x>mid) Add2(p<<1|1,mid+1,r,x,k);
  ma2(p)=max(ma2(p<<1),ma2(p<<1|1));
  mi2(p)=min(mi2(p<<1),mi2(p<<1|1));
}

inline ll Askma1(ll p,ll l,ll r) {return ma1(p);}
inline ll Askma2(ll p,ll l,ll r) {return ma2(p);}
inline ll Askmi1(ll p,ll l,ll r) {return mi1(p);}
inline ll Askmi2(ll p,ll l,ll r) {return mi2(p);}

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

int main() {

  T=read();

  for(ll i=1;i<=T;i++) {
    n[i]=read();
    for(ll j=1;j<=n[i];j++) {
      a[i][j]=read();uq[++amt]=a[i][j];
    }
  }

  sort(uq+1,uq+amt+1);amt=unique(uq+1,uq+amt+1)-uq-1;

  for(ll i=1;i<=T;i++) {
    for(ll j=1;j<=n[i];j++) {
      a[i][j]=lower_bound(uq+1,uq+amt+1,a[i][j])-uq;
    }
  }

  Build(1,1,amt);
  for(ll i=1;i<=T;i++) {
    for(ll j=1;j<=n[i];j++) {Add2(1,1,amt,a[i][j],1);}
    ll flg=0;
    for(ll len=1;len<=n[i]-1;len++) {
    //  printf("ma1=%lld mi2=%lld\n",Askma1(1,1,amt),Askmi2(1,1,amt));
      Add2(1,1,amt,a[i][len],-1);Add1(1,1,amt,a[i][len],1);
    //  printf("ma1=%lld mi2=%lld\n",Askma1(1,1,amt),Askmi2(1,1,amt));
      if(Askma1(1,1,amt)>Askmi2(1,1,amt)) {
        flg=1;break;
      }
    }
    Clear(1,1,amt);
    if(flg) printf("YES\n");
    else printf("NO\n");
  }

  return 0;
}

B.

Trivial 题。

仔细观察后发现是个直接计数。因为取长区间 $\operatorname{mex}$ 不会比直接一个一个取 $\operatorname{mex}$ 更优。

然后做完了。

代码：

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
45
46
47
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=1e5;

ll T,ans,n;

ll a[N+5];

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {write(x);putchar(10);}

int main() {

  T=read();

  while(T--) {
    n=read();ll ans=0;
    for(ll i=1;i<=n;i++) {
      a[i]=read();
      if(a[i]==0) {ans+=i*(n-i+1);}
    }
    for(ll i=1;i<=n;i++) {
      ans+=i*(n-i+1);
    }
    writeln(ans);
  }

  
  return 0;
}

C.

Trivial 题。特判一下不能取完的。剩下的肯定是元素除以二的上取整之和。

代码：

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
45
46
47
48
49
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=1e5;

ll T,ans,n;

ll a[N+5];

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {write(x);putchar(10);}

int main() {

  T=read();

  while(T--) {
    n=read();ans=0;
    for(ll i=1;i<=n;i++) {
      a[i]=read();
    }
    ll flg1=0;
    for(ll i=2;i<n;i++) {
      ans+=(a[i]+1)/2;
      if(a[i]>=2) flg1=1;
    }
    if(!flg1||(n==3&&a[2]%2==1)) writeln(-1);
    else writeln(ans);
  }

  
  return 0;
}

D.

因为 A 题吃了五发的问题导致后面没有时间了。。。

于是不拆式子直接瞪样例。

发现把两个数组的和之差调到最小就完了。

然后莽了个 DP 一发过掉。。。

剩下十分钟写不动了，睡觉去了。。。

实际上拆完式子后唯一有影响的部分就是 $(\sum_{i=1}^na_i)^2+(\sum_{i=1}^nb_i)^2$。

所以上面那个东西就可以解释了（均值不等式）。

代码：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e2,M=2e4;

ll T,ans,n,m;

ll a[N+5],b[N+5],f[N+5][M+5],from[N+5][M+5];

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {write(x);putchar(10);}

int main() {

  T=read();m=1e4;

  while(T--) {
    memset(f,0,sizeof(f));memset(from,0,sizeof(from));
    n=read();
    for(ll i=1;i<=n;i++) a[i]=read();
    for(ll i=1;i<=n;i++) b[i]=read();
    f[0][m]=1;
    for(ll i=1;i<=n;i++) {
      for(ll j=0;j<=m+m;j++) {
        if(f[i-1][j]) {
          if(j+a[i]-b[i]>0&&j+a[i]-b[i]<=m+m)
          {f[i][j+a[i]-b[i]]=1;from[i][j+a[i]-b[i]]=1;}
          if(j-a[i]+b[i]>0&&j-a[i]+b[i]<=m+m)
          {f[i][j-a[i]+b[i]]=1;from[i][j-a[i]+b[i]]=0;}
        }
      }
    }
    ll st=0;
    for(ll j=0;j<=m;j++) {
      if(f[n][m+j]) {st=m+j;break;}
      if(f[n][m-j]) {st=m-j;break;}
    }
    for(ll i=n;i>=1;i--) {
      if(from[i][st]) {st=st-(a[i]-b[i]);}
      else {st=st+(a[i]-b[i]);swap(a[i],b[i]);}
    }
    ll ans=0;
    for(ll i=1;i<=n;i++) {
      for(ll j=i+1;j<=n;j++) {
        ans=(ans+(a[i]+a[j])*(a[i]+a[j]));
        ans=(ans+(b[i]+b[j])*(b[i]+b[j]));
      }
    }
    writeln(ans);
  }

  
  return 0;
}

E.

咕。

F.

咕。

G.

咕。

H.

咕。