CF#512 div1

Source

CF#512div1
神仙的题解:xyx,dzy
好题:C

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();
}

D

请先思考后再展开

$$
\begin{aligned}
& 先讨论一下数列 A_{n}=(aA_{n-1}+b)\%p 的循环情况 \\
& A_n=a^n (x_0+\frac{b}{a-1})-\frac{b}{a-1} \\
& a=0,若b=x_0则T=1否则T=1且进入链长=1 \\
& a=1,若b=0则T=1否则T=P \\
& a>1,若a=p的原根则T=p-1否则T为p-1的因子
\end{aligned}
$$
证明:
$g^n x0+b(g^n-1)/(g-1)=x0 (\% p)$
$(g^n-1) x0+b(g^n-1)/(g-1)=0 (\% p)$
$(g^n-1)(x0+\frac{b}{g-1})=0 (\% p)$
p是质数所以两者必有一个是0而右边与n无关,总有一个b满足非0,而左边的循环节为p-1

综上所述,可以随心所欲选择p、p-1、1且链长=1三种,ans=lcm+max链长
不考虑第三种的话按p排序从大到小贪心,因为 $lcm(P-1,p)<=lcm(p-1,P)$ 而lcm是满足结合律的
至于第3中,因为max<=1,如果存在一个无贡献的家伙(必须最后重新遍历),改为链长=1即可

时间复杂度 $O(nlogn+P)$

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
using namespace std;
namespace mine
{
typedef long long ll;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
void chmax(int &x,const ll y) {x=(x>y?x:y);}
void chmin(int &x,const ll y) {x=(x<y?x:y);}
ll qread()
{
ll ans=0,f=1;char c=getchar();
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) putchar('-'),num=-num;
if(num>=10) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);putchar('\n');}
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
void add(ll &a,ll b){a+=b;if(a>=MOD)a-=MOD;if(a<=-MOD)a+=MOD;}
ll qpower(ll x,int e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll invm(ll x){return qpower(x,MOD-2);}
const int MAX_N=2e6+10;

bool gg[MAX_N];
int pp=0,prm[MAX_N],mip[MAX_N];
void pre()
{
for(int i=2;i<MAX_N;i++)
{
if(!gg[i]) prm[++pp]=i,mip[i]=pp;
for(int j=1;j<=pp and (ll)prm[j]*i<MAX_N;j++)
{
int to=prm[j]*i;gg[to]=1;mip[to]=j;
if(i%prm[j]==0) break;
}
}
}
int p[MAX_N];
pr cnt[MAX_N];
void insert(int id,int num)
{
if(num>=cnt[id].FR) cnt[id].SE=cnt[id].FR,cnt[id].FR=num;
else if(num>cnt[id].SE) cnt[id].SE=num;
}
bool fine(int now)
{
if(now<=0) return 0;
while(now>1)
{
int t=0,id=mip[now];
while(now%prm[id]==0) now/=prm[id],t++;
if(cnt[id].FR!=cnt[id].SE and cnt[id].FR==t) return 0;
}
return 1;
}
void main()
{
pre();
int n=qread();for(int i=1;i<=n;i++) p[i]=qread();
sort(p+1,p+n+1);
for(int i=n;i>=1;i--)
{
if(!cnt[ mip[p[i]] ].FR) {cnt[ mip[p[i]] ].FR=1;p[i]=0;continue;}
int now=p[i]-1;
while(now>1)
{
int t=0,id=mip[now];
while(now%prm[id]==0) now/=prm[id],t++;
insert(id,t);
}
}
bool bk=0;for(int i=1;i<=n;i++) if(fine(p[i]-1)) {bk=1;break;}
ll ans=1;
for(int i=1;i<=pp;i++) {while(cnt[i].FR--) ans=ans*prm[i]%MOD;}
write((ans+bk)%MOD);
}
};
int main()
{
freopen("a.in","r",stdin);
// freopen("jump.in","r",stdin);
// freopen("jump.out","w",stdout);
srand(time(0));
mine::main();
}

E

请先思考后再展开

构造题
要求:
将相同的数作为一组,则同组内位置奇偶性相同
两个不同的组,不可能交叉
思路:
i xxx i 可以缩为i

实现有疑问可膜xyx

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