CF#512 div1

Source

CF#512div1

A

请先思考后再展开

画一画三角形,发现面积要么是整数,要么是整数/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
void main()
{
ll n=qread(),m=qread(),k=qread();
ll d=gcd(n*m,k);ll b=k/d;
if(b==1)
{
puts("YES");
ll tmp=gcd(n,d);
ll x=n/tmp,y=m/(d/tmp);
if(x*2<=n) printf("0 0\n%lld %lld\n%lld %lld",x*2,0ll,0ll,y);
else printf("0 0\n%lld %lld\n%lld %lld",x,0ll,0ll,y*2);
}
else if(b==2)
{
puts("YES");
ll tmp=gcd(n,d);
n=n/tmp;m=m/(d/tmp);
printf("%lld %lld\n",0ll,0ll);
printf("%lld %lld\n",n,0ll);
printf("%lld %lld\n",0ll,m);
}
else
{
puts("NO");
}
}

B

请先思考后再展开

好难受啊看错数据($1e18->2^18$)到最后10min才过……
玩一玩样例,再随便举且情况,发现只需要满足以下限制:
【ln%2==0】,【2mx<=ln】,【ln>1】
证明不太会,也不太会写暴力……
实现的话,可以像我现在这样,往前枚举2log值域个,这样是 $O(nlog值域)$
更优秀复杂度的做法是分治,考虑跨过mid的区间,然后记录左右两边目前有多少奇偶位, $O(nlogn)$

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
int t0[MAX_N],t1[MAX_N],a[MAX_N],sum[MAX_N];
void main()
{
int n=qread();t0[0]=1;
for(int i=1;i<=n;i++)
{
ll num=qread();
for(int j=0;j<=62;j++) if(num&(1ll<<j)) a[i]++;
sum[i]=sum[i-1]+a[i];
t0[i]=t0[i-1]+( (sum[i]&1)==0 );
t1[i]=t1[i-1]+(sum[i]&1);
}
ll ans=0;
for(int r=2;r<=n;r++)
{
// if(r==n)
// puts("");
int mx=a[r];
for(int l=r-1;l>=r-150 and l>=1;l--)
{
chmax(mx,a[l]);
if(2*mx<=sum[r]-sum[l-1] and (sum[r]-sum[l-1])%2==0) ans++;
}
if(r-152>=0)
{
if(sum[r]&1) ans+=t1[r-152];
else ans+=t0[r-152];
}
}
write(ans);
}

C

请先思考后再展开

能独立做出div1的C让我感到很舒服,虽然清明一个人在家特别颓废……
一开始觉得很难做,后来决定把柿子写一下,在此过程中曾多次认为无法优化

其实我并没有意识到bi=ai-i这东西能转化为带权中位数……就自己推一推柿子,发现要用到,于是就用来化简了……
下面给出我的推导过程(具体化简过程略):

注意$w_i \leq 0,且单调不减$
先考虑移动为 $[A_l,A_l+(r-l)]$
$$
\begin{aligned}
l \leq x(题意中的x),设T=x-l\\
ans=
\sum_{b_i \geq T} b_iw_i
-\sum_{b_i < T} b_iw_i
+(\sum_{b_i < T} w_i
-\sum_{b_i \geq T} w_i)T
\end{aligned}
$$

然后考虑T->T+1,则变化为
$\sum_{b_i \leq T} w_i-\sum_{b_i>T} w_i$
注意到右边的增量总是在变大,则二分到最小的那个负数位置T
那么现在T已经确定了,统计答案,则总增量为
$\sum_{b_i \leq T} (T-2b_i+b_l+1) w_i+\sum_{bi > T} (T-b_l+1)w_i$

于是树状数组维护 $w_i$和$b_iw_i$ 即可
我写的是log方的,树状数组上二分时间复杂度可达 $O(qlogn)$

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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
void chmax(ll &x,const ll y) {x=x>y?x:y;}
void chmin(ll &x,const ll y) {x=x<y?x:y;}
const int MAX_N=2e5+10;
const ll MOD=1e9+7;
void add(ll &x,ll y) {x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
struct BIT
{
ll bit[MAX_N];BIT(){memset(bit,0,sizeof bit);}
int lowbit(int x) {return x&-x;}
void add(int x,int c) {while(x<MAX_N) bit[x]+=c,x+=lowbit(x);}
ll sum(int x){ll ans=0;while(x>=1) ans+=bit[x],x-=lowbit(x);return ans;}
ll ask(int l,int r) {return (l>r)?0:sum(r)-sum(l-1);}
}bit,bit2;//不取模
ll a[MAX_N],b[MAX_N],w[MAX_N];
void main()
{
int n=qread(),q=qread();
for(int i=1;i<=n;i++) a[i]=qread(),b[i]=a[i]-i;
for(int i=1;i<=n;i++)
{
w[i]=qread(),bit.add(i,w[i]);
bit2.add(i,w[i]*b[i]%MOD);
}
while(q--)
{
int x=qread(),y=qread();
if(x<0)
{
int id=-x,c=y;
bit.add(id,-w[id]);bit2.add(id,-w[id]*b[id]%MOD);
w[id]=c;
bit.add(id,w[id]);bit2.add(id,w[id]*b[id]%MOD);
}
else
{
int l=x,r=y;
ll now=0;int T0=a[l]-l;
int mid=lower_bound(b+l,b+r+1,T0)-b-1;
now-=bit2.ask(l,mid)%MOD-bit.ask(l,mid)%MOD*T0%MOD;
now+=bit2.ask(mid+1,r)%MOD-bit.ask(mid+1,r)%MOD*T0%MOD;
now%=MOD;
int fl=b[l],fr=b[r]-1,T=-1;
while(fl<=fr)
{
int mid=(fl+fr)>>1;
int tt=upper_bound(b+1,b+n+1,mid)-b-1;
if(bit.ask(l,tt)<bit.ask(tt+1,r)) T=mid,fl=mid+1;
else fr=mid-1;
}
if(T>=0)//no move
{
int tt=upper_bound(b+1,b+n+1,T)-b-1;
now+=-bit2.ask(l,tt)*2%MOD+bit.ask(l,tt)%MOD*(T+b[l]+1)%MOD;
now-=bit.ask(tt+1,r)%MOD*(T-b[l]+1)%MOD;
}
write2((now%MOD+MOD)%MOD);
}
}
}
};
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
srand(time(0));
mine::main();
}

咕咕咕

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/da7b.html
转载请注明出处,谢谢!