随机的100道题作为练习 ，争取在NOIP前做完。
update: NOIP前应该是做不完了，还是太菜了。
update: NOIP爆炸了，可能是因为没把这东西做完吧。。。
update: 摆了，练习题目都做不完，还是有空再来吧。。。
update on 2023.12.12: 我觉得应该结个尾，至少，在退役之前，不留遗憾。
设 $m=\frac{(n+1)}{2}$，容易得到要求的是 $Ans=\sum_{i=1}^{m}(2i-1)\cdot 26^i $
再用错位相减随便推一下得到：
$26Ans=\sum_{i=1}^{m}(2i-1)\cdot 26^{i+1} $
$25Ans=-26+(2m-1)\cdot 26^{m+1}+2\cdot \sum_{i=2}^{m}26^i $
最后运用等比数列求和公式就可以得到：
$Ans=\frac{-26+(2m-1)\cdot26^{m+1}+2\cdot \frac{26^{n+1}-26^2}{25} }{25}$
最后直接套式子，除法用逆元即可，时间复杂度 $\mathcal O(T\log n)$。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int mod=1e9+7;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int T,n,inv;
ll power(ll a,int k)
{
ll res=1;
while(k)
{
if(k&1)res=res*a%mod;
a=a*a%mod;
k>>=1;
}
return res;
}
int main()
{
inv=power(25,mod-2);
read(T);
while(T--)
{
read(n);
int m=(n+1)/2;
ll res=power(26,m+1);
ll ans=((2*m-1)*res%mod-26-2*((res-26*26+mod)%mod*inv%mod)%mod+mod)%mod*inv%mod;
printf("%lld\n",ans);
}
return 0;
}
|
很明显得到 $Ans=C_{n}^{k}\cdot f(q)$ 。
而求 $f(q)$ 也很简单的用一个秦九韶算法就完了。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=5e5+10,mod=1e9+7;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
ll n,m,k,q;
ll a[N],pre[N];
ll f(ll q)
{
ll res=a[m]%mod;
for(int i=m;i;i--)
res=(res*q%mod+a[i-1])%mod;
return res;
}
ll inv(ll x)
{
if(x<=1)return 1;
return (mod-mod/x)*inv(mod%x)%mod;
}
ll C(int n,int m)
{
if(m>n)return 0;
return pre[n]*inv(pre[m])%mod*inv(pre[n-m])%mod;
}
int main()
{
read(n,m,k,q);
q%=mod;
for(int i=0;i<=m;i++)
read(a[i]);
pre[0]=1;
for(int i=1;i<=n;i++)
pre[i]=pre[i-1]*i%mod;
printf("%lld\n",f(q)*C(n,k)%mod);
return 0;
}
|
不错的一道分治，也不算很难。
运用调整法很容易证明，将 $b$ 按照升序插入才可能得到最优解，于是我们先将 $b$ 排序。
考虑求出一个 $pos_i$ 为将 $b_i$ 插入到 $a_{pos_i}$ 前面（特别地 $pos_i=n+1$ 表示将 $b_i$ 插入到 $a$ 的最后面 ）。
有上面的结论可以得到，$b$ 中的元素各自的产生的逆序对数是互不影响的，但他们的位置又互相受到限制，都是因为 $b$ 是以升序插入的，于是我们可以知道：当若有 $l<mid<r$ ，那么 $b_{mid}$ 在 $[pos_l,pos_r]$中的最优解即为在全局 $[1,n]$ 中的最优解（微扰法可以证明，此处就不再赘述）。
其实这个贡献有关系式 $w(i,j)+w(i-1,j+1)=w(i,j+1)+w(i-1,j)$，这就是决策单调性的经典式子了。
有了这个新结论，我们利用决策单调性这一点进行分治，用 $solve(p,q,l,r)$，表示将 $b_l,b_{l+1},…,b_r$ 插入到 $a$ 的 $[p,q]$ 之间，每次递归只需要用 $\mathcal O(p-q)$ 求出 $pos_{mid}$。
随后根据求出的 $pos$ 将 $b$ 插入 $a$ 中再求逆序对即可。时间复杂度 $\mathcal O((n+m)\log(n+m))$。
实际上还有另外一种解法，就是先将 $a$ 离散化并计算逆序对，再建立一颗线段树，表示每个位置维护插入到位置 $i$ 新增加的逆序对数。新增加的逆序对数由两部分组成，前面比 $b_i$ 大的 $+$ 后面比 $b_i$ 小的。我们接着考虑当 $b_i$ 变为 $b_{i+1}$ 时对线段树的影响，同时 $a$ 也需要小到大考虑，得到：当 $a_x<b_i$ 时，应当使 $[1,x]+1$；而当 $a_y\le b_i$ 时，应当使 $[y+1,n+1]-1$，同时动态维护答案即可。时间复杂度 $\mathcal O(n\log n)$。
Code
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e6+10,INF=1e9;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int T,n,m;
int a[N],b[N],c[N<<1];
int pos[N];
int h[N];
int sum1[N],sum2[N];
ll ans;
void solve(int p,int q,int l,int r)
{
if(l>r)return;
int mid=l+r>>1;
sum1[p-1]=sum2[q-1]=0;
for(int i=p;i<=q;i++)
{
sum1[i]=a[i]>b[mid];
sum2[i]=a[i]<b[mid];
}
for(int i=p+1;i<=q;i++)
sum1[i]+=sum1[i-1];
for(int i=q-1;i>=p;i--)
sum2[i]+=sum2[i+1];
pos[mid]=0;
for(int i=p;i<=q;i++)
if(!pos[mid]||sum1[i-1]+sum2[i]<sum1[pos[mid]-1]+sum2[pos[mid]])
pos[mid]=i;
solve(p,pos[mid],l,mid-1);
solve(pos[mid],q,mid+1,r);
}
void merge(int *a,int l,int r)
{
if(l==r)
return ;
int mid=(l+r)/2;
merge(a,l,mid);
merge(a,mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j])
{
h[k]=a[i];
k++;
i++;
}
else
{
h[k]=a[j];
k++;
j++;
ans+=mid-i+1;
}
}
while(i<=mid)
h[k]=a[i],k++,i++;
while(j<=r)
h[k]=a[j],k++,j++;
for(int i=l;i<=r;i++)
a[i]=h[i];
}
int main()
{
read(T);
while(T--)
{
read(n,m);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<=m;i++)
read(b[i]);
sort(b+1,b+1+m);
solve(1,n+1,1,m);
int p=0,j=1;
for(int i=1;i<=n+1;i++)
{
while(j<=m&&pos[j]==i)
c[++p]=b[j++];
c[++p]=a[i];
}
ans=0;
merge(c,1,n+m);
printf("%lld\n",ans);
}
return 0;
}
|
树形背包裸题，状态和转移方程稍复杂，还需要滚动数组优化一下。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+10,K=100+10;
const int mod=1e9+7;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n,m;
int tot,head[N],ver[N<<1],ne[N<<1];
int si[N];
int f[N][K][2][2],g[K][2][2];
void add(int u,int v)
{
ver[++tot]=v;
ne[tot]=head[u];
head[u]=tot;
}
void dp(int x,int fa)
{
si[x]=1;
f[x][0][0][0]=f[x][1][1][0]=1;
for(int i=head[x];i;i=ne[i])
{
int y=ver[i];
if(fa==y)continue;
dp(y,x);
for(int j=0;j<=min(si[x],m);j++)
{
g[j][0][0]=f[x][j][0][0];
g[j][0][1]=f[x][j][0][1];
g[j][1][0]=f[x][j][1][0];
g[j][1][1]=f[x][j][1][1];
f[x][j][0][0]=f[x][j][0][1]=f[x][j][1][0]=f[x][j][1][1]=0;
}
for(int j=0;j<=min(si[x],m);j++)
{
for(int k=0;k<=si[y]&&j+k<=m;k++)
{
f[x][j+k][0][0]=(f[x][j+k][0][0]+1ll*g[j][0][0]*f[y][k][0][1]%mod)%mod;
f[x][j+k][0][1]=(f[x][j+k][0][1]+1ll*g[j][0][1]*(f[y][k][0][1]+f[y][k][1][1])%mod)%mod;
f[x][j+k][0][1]=(f[x][j+k][0][1]+1ll*g[j][0][0]*f[y][k][1][1]%mod)%mod;
f[x][j+k][1][0]=(f[x][j+k][1][0]+1ll*g[j][1][0]*(f[y][k][0][0]+f[y][k][0][1])%mod)%mod;
f[x][j+k][1][1]=(f[x][j+k][1][1]+1ll*g[j][1][0]*(f[y][k][1][0]+f[y][k][1][1])%mod)%mod;
f[x][j+k][1][1]=(f[x][j+k][1][1]+1ll*g[j][1][1]*(1ll*f[y][k][0][0]+1ll*f[y][k][0][1]+1ll*f[y][k][1][0]+1ll*f[y][k][1][1])%mod)%mod;
}
}
si[x]+=si[y];
}
}
int main()
{
read(n,m);
for(int i=1;i<n;i++)
{
int u,v;
read(u,v);
add(u,v);
add(v,u);
}
dp(1,0);
printf("%d",(f[1][m][0][1]+f[1][m][1][1])%mod);
return 0;
}
|
题意简述：给你一个长度为 n 的数组 $A$ 和长度为 $m$ 的数组 $B$，你每次可以选择 $B$ 中的一个数 $b_i$，然后将 $A$ 中一段长度为 $b_i$ 的区间取反，求可能的 $\max{\sum_{i=1}^{n}a_i}$。
首先要转化问题，注意 $B$ 中的一个数 $b_i$ 可以重复选择，那么我们每一次都可以取反长度为 $|b_i-b_j|$ 的区间，容易由更相减损术转化为我们每次都选取一段长度为 $\gcd_{i=1}^{m}b_i$ 的区间。
那么问题就很简单了，用 $DP$ 将模 $\gcd_{i=1}^{m}b_i$ 的余数和其奇偶性记录进状态就可以很好转移了。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e6+10;
const ll INF=2e9;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int T,n,m,a[N],b[N];
ll f[N][2],ans1,ans2;
int gcd(int x,int y)
{
return x==0?y:gcd(y%x,x);
}
int main()
{
read(T);
while(T--)
{
read(n,m);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<=m;i++)
read(b[i]);
int g=0;
for(int i=1;i<=m;i++)
g=gcd(g,b[i]);
for(int i=0;i<g;i++)
f[i][0]=0,f[i][1]=-INF;
for(int i=1;i<=n;i++)
{
ll res1=f[i%g][0],res2=f[i%g][1];
f[i%g][0]=max(res1+a[i],res2-a[i]);
f[i%g][1]=max(res1-a[i],res2+a[i]);
}
ans1=ans2=0;
for(int i=0;i<g;i++)
ans1+=f[i][0],ans2+=f[i][1];
printf("%lld\n",max(ans1,ans2));
}
return 0;
}
|
容易想到以所选数的质因数的集合为状态进行 DP，设 $f_{s_1,s_2}$ 为小 G 和小 W 所选数的质因数的集合分别为 $s_1,s_2$ 的方案数。但 $\le 500$ 的质因数太多了，无法全部记录。
注意一个关键点，$\le 500$ 的数最多有一个 $p\ge 23$ 的质因数，我们可以按照质因数 $p$ 对所有数进行分类，那么我们只需要考虑 $p$ 对同类数之间的限制即可。
考虑 $f1_{s_1,s_2},f2_{s_1,s_2}$，分别为小 G 和 小 W 选 $p$ 的方案数，而 $f’_{s_1,s_2}=f1_{s_1,s_2}+f2_{s_1,s_2}-f_{s_1,s_2}$。
于是我们只需要记录前面 $8$ 个质数即可。DP 过程中枚举 $s_2$ 时枚举 $s_1$ 补集的子集即可，时间复杂度为 $\mathcal O(3^8n)$。
Code
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e2+10,S=(1<<8)-1;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
struct Num
{
int s,d;
bool operator<(const Num &t)const
{
return d<t.d;
}
}a[N];
int n,p;
int cnt,prime[N],vis[N];
int f[N][N],f1[N][N],f2[N][N];
void prework(int n)
{
for(int i=2;i<=n;i++)
{
if(!vis[i])
prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(!(i%prime[j]))break;
}
}
}
void get(int x)
{
int now=x;
for(int i=1;i<=8&&x>=prime[i];i++)
{
if(!(x%prime[i]))
{
a[now].s|=1<<(i-1);
while(x&&!(x%prime[i]))x/=prime[i];
}
}
a[now].d=x;
}
int main()
{
read(n,p);
prework(N-10);
for(int i=2;i<=n;i++)
get(i);
sort(a+2,a+1+n);
f[0][0]=1;
for(int i=2;i<=n;i++)
{
if(a[i].d==1||a[i].d!=a[i-1].d)
{
memcpy(f1,f,sizeof(f));
memcpy(f2,f,sizeof(f));
}
for(int s1=S;~s1;s1--)
{
int c=S^s1;
for(int s2=c;s2;s2=(s2-1)&c)
{
if(!(a[i].s&s2))f1[s1|a[i].s][s2]=(f1[s1|a[i].s][s2]+f1[s1][s2])%p;
if(!(a[i].s&s1))f2[s1][s2|a[i].s]=(f2[s1][s2|a[i].s]+f2[s1][s2])%p;
}
f1[s1|a[i].s][0]=(f1[s1|a[i].s][0]+f1[s1][0])%p;
if(!(a[i].s&s1))f2[s1][a[i].s]=(f2[s1][a[i].s]+f2[s1][0])%p;
}
if(a[i].d==1||a[i].d!=a[i+1].d)
{
for(int s1=0;s1<=S;s1++)
{
int c=S^s1;
for(int s2=c;s2;s2=(s2-1)&c)
f[s1][s2]=((f1[s1][s2]+f2[s1][s2])%p-f[s1][s2]+p)%p;
f[s1][0]=((f1[s1][0]+f2[s1][0])%p-f[s1][0]+p)%p;
}
}
}
int ans=0;
for(int s1=0;s1<=S;s1++)
{
int c=S^s1;
for(int s2=c;s2;s2=(s2-1)&c)
ans=(ans+f[s1][s2])%p;
ans=(ans+f[s1][0])%p;
}
printf("%d\n",ans);
return 0;
}
|
比较简单的题目，首先以外径为关键字进行排序，保证遍历时外径是有序的。再维护一个栈，直接模拟题意，当栈顶元素的内径 $\ge$ 当前元素的外径，将栈顶元素弹去。同时维护答案即可。
Code
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
#define ll long long
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
struct ring
{
int a,b;
ll h;
friend bool operator<(ring x,ring y)
{
if(x.b!=y.b)return x.b>y.b;
return x.a>y.a;
}
}k[N],sta[N];
int n,top;
ll f[N],ans;
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(k[i].a,k[i].b,k[i].h);
sort(k+1,k+1+n);
for(int i=1;i<=n;i++)
{
while(top&&k[i].b<=sta[top].a)top--;
sta[++top]=k[i];
sta[top].h+=sta[top-1].h;
ans=max(ans,sta[top].h);
}
printf("%lld",ans);
return 0;
}
|
在线算法不容易实现，我们直接考虑对全局暴力求出所有公约数，用一个 $\text{map}$ 存储答案。只需要考虑优化。
比较简单地有：若 $l\le r<n$，则有 $ \gcd_{i=l}^{r}\le \gcd_{i=l}^{r+1}$。这就意味当左端点固定时，随着右端点递增，$\gcd$ 单调递减。并且 $\gcd$ 种类数是 $\mathcal O(\log V)$ 的
这样就很简单了，我们只需要枚举左端点，对右端点进行二分或者倍增就可以了。ST 表查询 $\gcd$ 的时间是 $\mathcal O(\log V)$，其中 $V$ 为值域。
时间复杂度 $\mathcal O(n\log n\log^2 V+q\log n)$：
Code
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
| #include<iostream>
#include<cstdio>
#include<map>
#define ll long long
using namespace std;
const int N=1e5+10;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m;
int a[N];
int Log[N],st[N][25];
map<int,ll>ans;
int gcd(int x,int y)
{
return x?gcd(y%x,x):y;
}
void build()
{
for(int i=1;i<=n;i++)
st[i][0]=a[i];
for(int j=1;j<=Log[n];j++)
for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int query(int l,int r)
{
int k=Log[r-l+1];
return gcd(st[l][k],st[r-(1<<k)+1][k]);
}
int find(int x,int len,int g)
{
int l=x+len,r=n,res=x;
while(l<=r)
{
int mid=l+r>>1;
int now=query(x,mid);
if(now==g)res=mid,l=mid+1;
else r=mid-1;
}
return res-x+1;
}
void solve(int x)
{
int l=x,r=x;
while(r<=n)
{
int g=query(x,l);
r=x+find(x,l-x,g);
ans[g]+=r-l;
l=r;
}
}
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=2;i<=n;i++)
Log[i]=Log[i>>1]+1;
build();
for(int i=1;i<=n;i++)
solve(i);
read(m);
for(int i=1;i<=m;i++)
{
int x;
read(x);
printf("%lld\n",ans[x]);
}
return 0;
}
|
学会转化问题，与其考虑变，我们不如将目光放到哪些不变上。手动模拟，我们发现一个长度为 $n$ 的序列无论如何只需要最多 $n-1$ 次操作，我们考虑最优情况哪些数不会被操作。
这下就更简单了，我们只需要找到一条带重复元素的最长无缝上升子序列，设其长度为 $len$，因为穿插在这个子序列中的数总是能够被按一定顺序移到两端去从而变得有序。答案就是 $n-len$ 。
然而至今笔者未在网上找到靠谱的带重复元素的最长无缝上升子序列解法，现有有两组hack：
input1:
4
3 1 2 3
output1:
1
input2:
6
4 2 3 4 1 5
output2:
3
希望读者有新的思考，随时可以联系笔者。
Code1 100pts
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,ans;
int a[N],b[N],f[N];
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i]),b[i]=a[i];
sort(b+1,b+1+n);
int len=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+1+len,a[i])-b;
for(int i=1;i<=n;i++)
ans=max(ans,f[a[i]]=(f[a[i]]?f[a[i]]:f[a[i]-1])+1);
printf("%d",n-ans);
return 0;
}
|
Code2 90pts
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,ans;
int a[N],b[N],f[N];
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i]),b[i]=a[i];
sort(b+1,b+1+n);
int len=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+1+len,a[i])-b;
for(int i=1;i<=n;i++)
ans=max(ans,f[a[i]]=max(f[a[i]],f[a[i]-1])+1);
printf("%d",n-ans);
return 0;
}
|
注意到关键：有向无环图。这意味一条路径最多只会经过 $n-1$ 次。再者 $1\le n\le 50$，我们考虑直接跑一遍 Floyd，并且将走过的边数记录进状态就可以实现类似于背包的转移。稍想便知，我们并不需要枚举边的决策点，有状态转移方程：
$f_{t,i,j}=\min f_{t-1,i,j}+f_{1,k,j}$
最直接遍历一遍 $f$ 数组计算出所有答案即可。
Code
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
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=50+10,M=1e3+10,INF=1e9;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n,m,q;
int f[N][N][N];
double ans[N][N];
void init()
{
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans[i][j]=1e9;
}
int main()
{
read(n,m);
init();
for(int i=1;i<=m;i++)
{
int u,v,w;
read(u,v,w);
f[1][u][v]=min(f[1][u][v],w);
}
for(int t=2;t<=n;t++)
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(k!=i&&k!=j&&i!=j)
f[t][i][j]=min(f[t][i][j],f[t-1][i][k]+f[1][k][j]);
for(int t=1;t<=n;t++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(f[t][i][j]<INF)
ans[i][j]=min(ans[i][j],f[t][i][j]*1.0/t);
read(q);
for(int i=1;i<=q;i++)
{
int x,y;
read(x,y);
if(ans[x][y]<INF)
printf("%.3lf\n",ans[x][y]);
else printf("OMG!\n");
}
return 0;
}
|
很明显的二分，直接选择二分 $p$，重点在于如何写 $check(p)$ 函数。
首先考虑暴力，这样 $check(p)$ 时间复杂度是 $O(n^2)$ 的，尝试推一下性质。
很容易得到：
$\sum p-(i-j)^2=\sum p-\sum i^2+2\sum i\cdot j-\sum j^2=sum\cdot p-sum_{i^2}+2\cdot sum_i\cdot j-sum\cdot j$
我们只需要维护，$sum,sum_i,sum_{i^2}$ 就可以直接计算出前面对当前的影响。
Code
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
| #include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
const int N=5e5+10;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n,k;
ll a[N],c[N],h[N];
ll l,r=1e12;
bool check(ll p)
{
ll cnt=0,len=sqrt(p),s=0,si=0,si2=0;
for(int i=1;i<=n;i++)
c[i]=a[i],h[i]=0;
for(int i=1;i<=n;i++)
{
c[i]-=s*p-si2+2*si*i-s*i*i;
if(c[i]>=0)
h[i]=c[i]/p+1,cnt+=h[i];
s+=h[i];
si+=h[i]*i;
si2+=h[i]*i*i;
if(i-len>=1)
{
s-=h[i-len];
si-=h[i-len]*(i-len);
si2-=h[i-len]*(i-len)*(i-len);
}
if(cnt>k)
return 0;
}
return 1;
}
int main()
{
read(n,k);
for(int i=1;i<=n;i++)
read(a[n-i+1]);
while(l<r)
{
ll mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%lld",r);
return 0;
}
|
有难度的倍增题目，比较有趣。
首先用DP预处理出数组 $pr_x$ 为遍历节点 $x$ 的子树获得的最大权值。先考虑从节点向根走，尝试求出 $f_{x,i}$ 为从点 $x$ 出发走到它的第 $2^i$ 辈祖先。只不过不能想当然地进行转移，考虑一下容斥，得到：
$f_{x,i}=f_{x,i-1}+f_{fa_{x,i-1},i-1}-pr_{fa_{x,i-1}}$
同时需要注意 $f_{x,0}$ 的值，需要判断 $x$ 的父亲节点是否选取了 $x$ 作为答案。
我们接着就可以使用倍增向上跳并累加答案 $f_{x,i}-pr_x$。但需要注意的是，我们最后只是会跳到 $LCA$ 处，实际上从 $LCA$ 还可以往上跳继续寻找答案。为了累加这个答案，我们可以再用一个 $g_x$ 表示从 $x$ 向上走能够获得的最大权值，从 $x$ 的父节点就可以很好地转移。最后统计答案时加上 $g_{LCA}$ 就行了。记得最后加上原来端点的 $pr_x$。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=3e5+10,M=6e5+10,K=25;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n,q,rt=1;
int a[N];
ll pr[N],g[N];
int tot,head[N],ver[M],e[M],ne[M];
int fa[N][30],d[N];
ll f[N][30];
void add(int u,int v,int w)
{
ver[++tot]=v;
e[tot]=w;
ne[tot]=head[u];
head[u]=tot;
}
void dp(int x,int fa)
{
pr[x]+=a[x];
for(int i=head[x];i;i=ne[i])
{
if(ver[i]==fa)
continue;
dp(ver[i],x);
pr[x]+=max(0ll,pr[ver[i]]-2*e[i]);
}
}
void dfs(int x)
{
for(int i=1;i<=25;++i)
{
fa[x][i]=fa[fa[x][i-1]][i-1];
f[x][i]=f[x][i-1]+f[fa[x][i-1]][i-1]-pr[fa[x][i-1]];
}
for(int i=head[x];i;i=ne[i])
{
if(d[ver[i]])
continue;
d[ver[i]]=d[x]+1;
fa[ver[i]][0]=x;
f[ver[i]][0]=pr[ver[i]]+pr[x]-e[i]-(pr[ver[i]]-2*e[i]>0?pr[ver[i]]-2*e[i]:0);
g[ver[i]]=max(0ll,g[x]+f[ver[i]][0]-e[i]-pr[ver[i]]);
dfs(ver[i]);
}
}
ll query(int x,int y)
{
ll res=0;
if(d[x]<d[y])
swap(x,y);
int u=x,v=y;
for(int i=K;i>=0;i--)
if(d[fa[x][i]]>=d[y])
{
res+=f[x][i]-pr[x];
x=fa[x][i];
}
if(x==y)
return res+pr[u]+g[x];
for(int i=K;i>=0;i--)
if(fa[x][i]!=fa[y][i])
{
res+=f[x][i]-pr[x]+f[y][i]-pr[y];
x=fa[x][i],y=fa[y][i];
}
int lca=fa[x][0];
return res+f[x][0]-pr[x]+f[y][0]-pr[y]-pr[lca]+pr[u]+pr[v]+g[lca];
}
int main()
{
read(n,q);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<n;i++)
{
int u,v,w;
read(u,v,w);
add(u,v,w);
add(v,u,w);
}
dp(rt,0);
d[rt]=1;
dfs(rt);
for(int i=1;i<=q;i++)
{
int x,y;
read(x,y);
printf("%lld\n",query(x,y));
}
return 0;
}
|
推式子为主。
首先很明显应该贪心，先将 $C_i$ 进行排序。并很容易得出答案为：
$2^n\cdot (\sum_{i=1}^{n}2^{i-1}\cdot C_i\cdot \sum_{j=0}^{n-i}\begin{pmatrix} n-i\ j\end{pmatrix}\cdot(j+1))$
对后面这一坨尝试进行变换：$\sum_{j=0}^{n-i} \begin{pmatrix} n-i \ j \end{pmatrix} \cdot(j+1) = \sum_{j=0}^{n-i}\begin{pmatrix} n-i \ j \end{pmatrix} \cdot j+2^{n-i}$
运用吸收恒等式：$\begin{pmatrix} i \ j \end{pmatrix}\cdot j = \begin{pmatrix} i-1 \ j-1 \end{pmatrix} \cdot i$，对第一项进行变换：
$\sum_{j=0}^{n-i} \begin{pmatrix} n-i \ j\end{pmatrix} \cdot j = \sum_{j=0}^{n-i} \begin{pmatrix} n-i-1 \ j-1 \end{pmatrix} \cdot (n-i) = (n-i) \cdot2^{n-i-1}$
所以得到最终式子：
$2^n\cdot (\sum_{i=1}^{n}2^{i-1} \cdot C_i \cdot ((n-i) \cdot 2^{n-i-1}+2^{n-i}))$
直接计算即可。
Code
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n;
ll ans,c[N],p[N];
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(c[i]);
sort(c+1,c+1+n);
p[0]=1;
for(int i=1;i<=n;i++)
p[i]=(p[i-1]<<1)%mod;
for(int i=1;i<=n;i++)
ans=(ans+p[i-1]*c[i]%mod*((n-i)*p[n-i-1]%mod+p[n-i]))%mod;
printf("%lld\n",ans*p[n]%mod);
return 0;
}
|
容易得到：$f_{i,j}=f_{i-1,x-1}⊕f_{i-1,j+1}$。
然后稍加思索，便得到：$f_{i,j}=f_{i-2^k,x-2^k}⊕f_{i-2^k,j+2^k}$。
然后就直接将 $T$ 按照二进制拆开计算就可以了，时间复杂度 $\mathcal O(n\log T)$。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+10,K=60;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n;
ll t;
int p,f[2][N];
int main()
{
read(n,t);
for(int i=0;i<n;i++)
scanf("%1d",&f[p][i]);
for(int k=0;k<=K;k++)
{
if(t&(1ll<<k))
{
int r=(1ll<<k)%n,l=(n-r)%n;
for(int i=0;i<n;i++)
{
f[p^1][i]=f[p][l]^f[p][r];
if(++l>=n)l-=n;
if(++r>=n)r-=n;
}
p^=1;
}
}
for(int i=0;i<n;i++)
printf("%d",f[p][i]);
return 0;
}
|
单点修改求最大独立集。尝试使用线段树来维护，左右端点各自取或不取所得到的区间最大值就可以了。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+10,M=1e5+10;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
struct Node
{
int l,r;
ll v[2][2];
}tr[N<<2];
int n,m;
ll a[N];
ll ans;
void pushup(int x)
{
tr[x].v[0][0]=max(tr[x<<1].v[0][0]+tr[x<<1|1].v[0][0],max(tr[x<<1].v[0][1]+tr[x<<1|1].v[0][0],tr[x<<1].v[0][0]+tr[x<<1|1].v[1][0]));
tr[x].v[1][0]=max(tr[x<<1].v[1][0]+tr[x<<1|1].v[0][0],max(tr[x<<1].v[1][1]+tr[x<<1|1].v[0][0],tr[x<<1].v[1][0]+tr[x<<1|1].v[1][0]));
tr[x].v[0][1]=max(tr[x<<1].v[0][0]+tr[x<<1|1].v[0][1],max(tr[x<<1].v[0][1]+tr[x<<1|1].v[0][1],tr[x<<1].v[0][0]+tr[x<<1|1].v[1][1]));
tr[x].v[1][1]=max(tr[x<<1].v[1][0]+tr[x<<1|1].v[0][1],max(tr[x<<1].v[1][1]+tr[x<<1|1].v[0][1],tr[x<<1].v[1][0]+tr[x<<1|1].v[1][1]));
}
void build(int x,int l,int r)
{
tr[x].l=l,tr[x].r=r;
if(l==r)
{
tr[x].v[1][1]=a[l];
return ;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
void modify(int x,int pos,int k)
{
if(tr[x].l==tr[x].r)
{
tr[x].v[1][1]=k;
return ;
}
int mid=tr[x].l+tr[x].r>>1;
if(pos<=mid)modify(x<<1,pos,k);
else modify(x<<1|1,pos,k);
pushup(x);
}
int main()
{
read(n,m);
for(int i=1;i<=n;i++)
read(a[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int x,y;
read(x,y);
modify(1,x,y);
ans+=max(max(tr[1].v[0][0],tr[1].v[1][1]),max(tr[1].v[1][0],tr[1].v[0][1]));
}
printf("%lld\n",ans);
return 0;
}
|
单边修改求树上直径。很厉害的一道题，一开始根本没有思路，看题解也想了一会儿才弄懂。
先考虑把树上问题向区间问题转换。还记得我们如何将 LCA 问题进行转化的吗？对，这道题我们就是需要尝试用欧拉序进行转换。我们需要求的：$\max_{l,r\in [1,N]} {dep_l+dep_r-2*dep_{lca(l,r)}}$
就变为了：$\max_{1\le l \le r \le 2N-1}{dep_l+dep_r- 2\times\min_{l\le mid\le r}{dep_{mid}}$。
考虑怎么维护这个东西，考虑分多个值：
1.区间深度最大值（作为 $dep_l$ 或 $dep_r$）。
2.区间深度最小值（作为 $dep_{lca}$）。
3.左端点与 LCA 合并的最大值，和右端点与 LCA 合并的最大值。
4.区间内直径最大值。
而修改操作就是欧拉序上的一段区间修改，这道题就完美解决了。
Code
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
122
123
124
125
126
127
128
129
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+10,M=2e5+10;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n,q,rt=1;
int tot,head[N],ver[M],ne[M];
int cnt,num[N<<1],in[N],out[N],pos[N];
ll w,e[M],val[N],d[N];
struct Node
{
int l,r;
ll maxd,mind,lm,mr,lmr;
ll tag;
}tr[N<<3];
void add(int u,int v,ll w)
{
ver[++tot]=v;
e[tot]=w;
ne[tot]=head[u];
head[u]=tot;
}
void dfs(int x,int fa)
{
num[in[x]=++cnt]=x;
for(int i=head[x];i;i=ne[i])
{
if(ver[i]==fa)continue;
d[ver[i]]=d[x]+e[i];
pos[i+1>>1]=ver[i];
dfs(ver[i],x);
num[++cnt]=x;
}
out[x]=cnt;
}
void pushup(int x)
{
tr[x].maxd=max(tr[x<<1].maxd,tr[x<<1|1].maxd);
tr[x].mind=max(tr[x<<1].mind,tr[x<<1|1].mind);
tr[x].lm=max(max(tr[x<<1].lm,tr[x<<1|1].lm),tr[x<<1].maxd+tr[x<<1|1].mind);
tr[x].mr=max(max(tr[x<<1].mr,tr[x<<1|1].mr),tr[x<<1].mind+tr[x<<1|1].maxd);
tr[x].lmr=max(max(tr[x<<1].lmr,tr[x<<1|1].lmr),max(tr[x<<1].lm+tr[x<<1|1].maxd,tr[x<<1].maxd+tr[x<<1|1].mr));
}
void update(int x,ll k)
{
tr[x].maxd+=k;
tr[x].mind-=2*k;
tr[x].lm-=k;
tr[x].mr-=k;
tr[x].tag+=k;
}
void pushdown(int x)
{
update(x<<1,tr[x].tag);
update(x<<1|1,tr[x].tag);
tr[x].tag=0;
}
void build(int x,int l,int r)
{
tr[x].l=l,tr[x].r=r;
if(l==r)
{
tr[x].maxd=d[num[l]];
tr[x].mind=-2*d[num[l]];
tr[x].lm=tr[x].mr=-d[num[l]];
tr[x].lmr=0;
tr[x].tag=0;
return ;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
void modify(int x,int l,int r,ll k)
{
if(tr[x].l>=l&&tr[x].r<=r)
{
update(x,k);
return ;
}
if(tr[x].tag)
pushdown(x);
int mid=tr[x].l+tr[x].r>>1;
if(l<=mid)modify(x<<1,l,r,k);
if(r>mid)modify(x<<1|1,l,r,k);
pushup(x);
}
int main()
{
read(n,q,w);
for(int i=1;i<n;i++)
{
int u,v;
read(u,v,val[i]);
add(u,v,val[i]);
add(v,u,val[i]);
}
dfs(rt,0);
build(1,1,cnt);
ll ans=0;
for(int i=1;i<=q;i++)
{
int x;
ll k;
read(x,k);
x=(x+ans%(n-1))%(n-1)+1;
k=(k+ans%w)%w;
modify(1,in[pos[x]],out[pos[x]],k-val[x]);
val[x]=k;
printf("%lld\n",ans=tr[1].lmr);
}
return 0;
}
|
按照每一位来考虑，设 $sum$ 为其所有数的异或和，其中 $sum_i$ 表示其二进制下的第 $i$ 位，考虑其奇偶性，有：
1.$sum_i$ 为 $1$，则分为两组的异或和的贡献一定为 $2^i$。
2.$sum_i$ 为 $0$ ，则分为两组的异或和第 $i$ 位一定相同。
第一种情况可以直接累加上答案，于是我们只需要考虑第二种情况就可以了。由第二条性质可以得到：仅考虑 $sum_i=0$ 的情况下,分为两组的异或和一定是相等的，于是我们直接用线性基算之后将答案乘二即可。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+10;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n;
ll sum,ans,res,a[N],p[100];
void insert(ll x)
{
for(int i=60;i>=0;i--)
{
if(!(x>>i&1))continue;
if(!p[i])
{
p[i]=x;
break;
}
x^=p[i];
}
}
int main()
{
read(n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]),sum^=a[i];
for(int i=60;i>=0;i--)
{
if(sum>>i&1)
{
ans+=1ll<<i;
for(int j=1;j<=n;j++)
if(a[j]>>i&1)
a[j]^=1ll<<i;
}
}
for(int i=1;i<=n;i++)
insert(a[i]);
for(int i=60;i>=0;i--)
res=max(res,res^p[i]);
printf("%lld\n",ans+2ll*res);
return 0;
}
|
最小值最大，很明显考虑二分。$check(i)$ 用线段树修改查询就可以了。
看题解后，发现还是做复杂了，可以直接差分，做到 $\mathcal O(n)$ $check(i)$ 。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+10,INF=1e9;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
struct Node
{
int l,r;
ll val,tag;
}tr[N<<2];
int n,m,w;
ll a[N];
ll l=INF,r;
void pushdown(int x)
{
tr[x<<1].tag+=tr[x].tag;
tr[x<<1|1].tag+=tr[x].tag;
tr[x].tag=0;
}
void build(int x,int l,int r)
{
tr[x].l=l,tr[x].r=r;
if(l==r)
{
tr[x].val=a[l];
return ;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
}
void modify(int x,int l,int r,int k)
{
if(tr[x].l>=l&&tr[x].r<=r)
{
tr[x].tag+=k;
return;
}
if(tr[x].tag)pushdown(x);
int mid=tr[x].l+tr[x].r>>1;
if(l<=mid)modify(x<<1,l,r,k);
if(r>mid)modify(x<<1|1,l,r,k);
}
ll query(int x,int pos)
{
if(tr[x].l==tr[x].r)
return tr[x].val+tr[x].tag;
if(tr[x].tag)
pushdown(x);
int mid=tr[x].l+tr[x].r>>1;
if(pos<=mid)return query(x<<1,pos);
return query(x<<1|1,pos);
}
bool check(ll x)
{
for(int i=0;i<=(n<<2);i++)
tr[i].tag=0;
int cnt=0;
for(int i=1;i<=n;i++)
{
ll res=query(1,i);
if(res<x)
{
modify(1,i,i+w-1,x-res);
cnt+=x-res;
}
if(cnt>m)return 0;
}
return 1;
}
int main()
{
read(n,m,w);
for(int i=1;i<=n;i++)
read(a[i]),l=min(l,a[i]),r+=a[i];
r=(r+1ll*m*w)/n;
build(1,1,n);
ll ans=l;
while(l<=r)
{
ll mid=l+r>>1;
if(check(mid))
l=mid+1,ans=mid;
else r=mid-1;
}
printf("%lld\n",ans);
return 0;
}
|
直接将所有后缀异或和插入进 01Trie，再查询每个前缀异或和所能得到最大值就可以了。
还有 01Trie 记得将空间开大。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+10;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n,cnt,t[N<<5][2];
ll a[N],ans;
void insert(ll x)
{
int p=0;
for(int i=63;~i;i--)
{
int num=(x>>i&1);
if(!t[p][num])
t[p][num]=++cnt;
p=t[p][num];
}
}
ll query(ll x)
{
int p=0;
ll sum=0;
for(int i=63;~i;i--)
{
int num=(x>>i&1);
if(t[p][num^1])
sum+=1ll<<i,p=t[p][num^1];
else p=t[p][num];
}
return sum;
}
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i]);
ll res=0;
for(int i=n;i>=1;i--)
{
res^=a[i];
insert(res);
}
res=0;
for(int i=0;i<=n;i++)
{
res^=a[i];
ans=max(ans,query(res));
}
printf("%lld\n",ans);
return 0;
}
|
因为每次我们需要贪心地考虑选择获得价值最大的数字进行 配对，考虑使用费用流，我们来看看怎么建模。
一定要想到将其转化为二分图，它是我们最好解决的了。我们对每个数进行质因数分解，将 $i$ 其分解成 $cnt_i$ 个质因数。再考虑将这些点其按照 $cnt_i$ 的奇偶性分为左部和右部的点，再将能够配对的点连起来，剩下的建图就很显然了。
注意这里我们需要写的是最大费用最大流。但又有一些不一样，我们只有在费用大于0的情况下才能继续继续增广，改一下就好了。
Code
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
122
123
124
125
126
127
128
129
130
131
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int N=1e5+10,M=4e5+10,INF=1e9;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n,m,s,t,maxflow;
int a[N],b[N],cnt[N];
int tot=1,head[N],ver[M],e[M],ne[M];
int incf[N],pre[N],vis[N];
ll maxcost,c[N],cost[M],d[N];
void add_edge(int u,int v,int w,ll c)
{
ver[++tot]=v;
e[tot]=w;
cost[tot]=c;
ne[tot]=head[u];
head[u]=tot;
}
void add(int u,int v,int w,ll c)
{
add_edge(u,v,w,c);
add_edge(v,u,0,-c);
}
bool SPFA()
{
queue<int>q;
for(int i=0;i<=t;i++)
d[i]=-1e18,vis[i]=0;
q.push(s);
d[s]=0;
vis[s]=1;
incf[s]=INF;
while(!q.empty())
{
int x=q.front();
vis[x]=0;
q.pop();
for(int i=head[x];i;i=ne[i])
{
if(!e[i])continue;
int y=ver[i];
if(d[y]<d[x]+cost[i])
{
d[y]=d[x]+cost[i];
incf[y]=min(incf[x],e[i]);
pre[y]=i;
if(!vis[y])
vis[y]=1,q.push(y);
}
}
}
if(d[t]>-1e18)return 1;
return 0;
}
bool update()
{
ll now=d[t]*incf[t];
if(maxcost+now<0)
{
maxflow+=maxcost/(-d[t]);
return 0;
}
maxcost+=now;
maxflow+=incf[t];
int x=t;
while(x!=s)
{
int i=pre[x];
e[i]-=incf[t];
e[i^1]+=incf[t];
x=ver[i^1];
}
return 1;
}
int divide(int x)
{
int res=0;
for(int i=2;i<=x;i++)
{
while(!(x%i))
x/=i,res++;
}
return res;
}
int main()
{
read(n);
s=n+1,t=s+1;
for(int i=1;i<=n;i++)
read(a[i]),cnt[i]=divide(a[i]);
for(int i=1;i<=n;i++)
{
read(b[i]);
if(cnt[i]&1)
add(s,i,b[i],0);
else add(i,t,b[i],0);
}
for(int i=1;i<=n;i++)
read(c[i]);
for(int i=1;i<=n;i++)
{
if(cnt[i]&1)
{
for(int j=1;j<=n;j++)
{
if((a[i]%a[j]==0&&cnt[i]==cnt[j]+1)||(a[j]%a[i]==0&&cnt[j]==cnt[i]+1))
add(i,j,INF,1ll*c[i]*c[j]);
}
}
}
while(SPFA()&&update());
printf("%d\n",maxflow);
return 0;
}
|
第一眼是一个区间DP，但是数据范围很明显不能让我们通过，我们没法DP直接考虑贪心。
很明显，若 $a_i<a_{i-1}$ 且 $a_i<a_{i+1}$ ，我们一定会将 $a_i$ 删去。
我们直接将其放入一个单调栈中进行维护并统计，最后得到的序列一定是单峰的。然后我们直接在剩下的 $m$ 个数中取最小的 $m-2$ 个就可以得到答案（因为最大的两个数不可能被取到）。
Code
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=5e5+10;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n;
ll ans;
int top,sta[N];
int main()
{
read(n);
for(int i=1;i<=n;i++)
{
int x;
read(x);
while(top>=2&&sta[top]<=sta[top-1]&&sta[top]<=x)
ans+=min(sta[top-1],x),top--;
sta[++top]=x;
}
sort(sta+1,sta+1+top);
for(int i=1;i<=top-2;i++)
ans+=sta[i];
printf("%lld\n",ans);
return 0;
}
|
比较清新的构造题（？）。
我们尝试从每个点的 $D_i$ 之间的关系入手。很明显 $D_i$ 值最大的节点必定为叶子，$D_i$ 值最小的节点必定为树的重心（可似乎没什么用），还记得之前的换根DP吗？若 $v$ 为 $u$ 的子节点，我们很明显有：$D_v=D_u-2\times size_v+n$。变换一下得到 $D_u=D_v+2\times size_v-n$。我们把两者结合一下，尝试用叶子节点逐渐构造其祖先。我们先将其排序，从 $D_i$ 值最大的开始处理，大致分为这几步：
1、计算用当前节点计算父节点的 $D$ 值。 2、父节点的 $D$ 值在给定的 $D_i$ 中进行二分查找。找到了则新加一条边计入答案，并且计算父节点的 $size_u$；若未找到直接输出 $-1$ 。
Code
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+10;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
struct Node
{
int id;
ll d;
friend bool operator<(const Node x,const Node y)
{
return x.d<y.d;
}
}a[N];
int n,si[N];
int cnt,u[N],v[N];
ll dis;
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i].d),a[i].id=i,si[i]=1;
sort(a+1,a+1+n);
for(int i=n;i>1;i--)
{
ll d=a[i].d-n+(si[i]<<1);
int k=lower_bound(a+1,a+1+n,(Node){0,d})-a;
if(a[k].d!=d)
{
puts("-1");
return 0;
}
u[i]=a[i].id;
v[i]=a[k].id;
si[k]+=si[i];
dis+=si[i];
}
if(dis!=a[1].d)
puts("-1");
else
for(int i=2;i<=n;i++)
printf("%d %d\n",u[i],v[i]);
return 0;
}
|
直接枚举 $k$ 的正整数倍并不是明智之举，我们并不能找到较好的条件或方式来优化。我们考虑直接对其进行搜索，再判断其是否为 $k$ 的倍数。
在搜索过程中，很明显每次只有两种分支：$\times 10$ 或 $+1$。而其花费分别为 $0$ 和 $1$。很自然想到了双端队列 BFS。并且我们在搜索过程中直接对数进行取模就行。时间复杂度 $\mathcal O(k)$。
Code
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
| #include<iostream>
#include<cstdio>
#include<bitset>
#include<queue>
using namespace std;
const int N=1e5+10;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
struct Node
{
int num,val;
};
int k;
bitset<N>vis;
deque<Node>q;
void BFS()
{
q.push_back((Node){1,1});
while(!q.empty())
{
int x=q.front().num,y=q.front().val;
q.pop_front();
if(vis[x])
continue;
vis[x]=1;
if(!x)
{
printf("%d\n",y);
return ;
}
if(!vis[x*10%k])
q.push_front((Node){x*10%k,y});
if(!vis[(x+1)%k])
q.push_back((Node){(x+1)%k,y+1});
}
}
int main()
{
read(k);
BFS();
return 0;
}
|
很明显应当从低位向高位考虑。每次从后面枚举，得到它后缀 $\mod p$ 的余数，很明显用该后缀减去之前所枚举的所有满足 $\mod p$ 的余数与其相等的后缀，所得到的字串一定被 $p$ 整除。这就很好办了，直接拿一个数组 $f_i$ 来存 $\mod p$ 的余数为 $i$ 的后缀数量，并且在枚举后缀时累加答案即可。
注意特判 $p=2,5$ 时的情况。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=2e5+10,M=1e4+10;
template <class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x);
read(x1...);
}
int n,p;
ll ans;
int sum,t=1,a[N],f[M];
int main()
{
read(n,p);
for(int i=1;i<=n;i++)
scanf("%1d",a+i);
if(p==2||p==5)
{
for(int i=1;i<=n;i++)
ans+=a[i]%p?0:i;
printf("%lld\n",ans);
return 0;
}
f[0]=1;
for(int i=n;i>=1;i--)
{
sum=(sum+t*a[i])%p;
ans+=f[sum];
f[sum]++;
t=t*10%p;
}
printf("%lld\n",ans);
return 0;
}
|
开始本来以为是贪心，但发现并不能总是得到最优解。
有端联想，我们似乎可以直接上费用流，建图很显然，直接上最大费用最大流跑就可以了，确实可以过，但是效率并不高。
我们逐渐想到区间DP，但是直接搞的话 $\mathcal O(n^3)$ 的。我们每次只能考虑从端点转移。
于是我们尝试将区间DP与贪心结合，直觉告诉我们对于 $a_i$ 较大的，应当将它尽可能排在一段区间的两端，而非中间，这样产生的贡献才大。然后乱搞，现将数组按照 $a_i$ 为第一关键字排序，并记录其初始位置 $pos_i$。对于区间 $[l,r]$ 我们只需要将前 $r-l+1$ 个数填进去，这样来满足贪心即可。
Code
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<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e3+10;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
struct Node
{
int val,pos;
bool operator<(const Node &t)
{
return val<t.val;
}
}a[N];
int n;
ll f[N][N];
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i].val),a[i].pos=i;
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
f[i][i]=1ll*abs(a[1].pos-i)*a[1].val;
for(int i=2;i<=n;i++)
for(int l=1;l+i-1<=n;l++)
{
int r=l+i-1;
f[l][r]=max(f[l+1][r]+1ll*abs(a[i].pos-l)*a[i].val,f[l][r-1]+1ll*abs(a[i].pos-r)*a[i].val);
}
printf("%lld\n",f[1][n]);
return 0;
}
|
使最大值最小，直接二分答案。我们需要研究 $check$ 函数应该如何写，设二分答案为 $lim$。
容易看出来是个 DP。可是直接 DP 明显很难做到 $\mathcal O(n^2)$。这就很难搞了。我们必须转换思路进行 DP。
经典正难则反，我们直接考虑计算 $[1,i]$ 中最多有多少个可以不变。可是似乎还是不太好转移。又该怎么办？只有当满足 $mid\times (i-j)\ge |a_i-a_j|$ 时，才可能有 $a_j$ 不改变，通过改变 $(j,i]$ 得到合法方案。最后判断其中是否存在某个 $i$ 使得 $n-dp_i\le k$ 即可。
Code
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
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e3+10;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,k;
ll a[N];
ll l,r,f[N];
bool check(ll lim)
{
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++)
{
if(lim*(i-j)>=abs(a[i]-a[j]))
f[i]=max(f[i],f[j]+1);
}
if(f[i]+k>=n)
return 1;
}
return 0;
}
int main()
{
read(n,k);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<n;i++)
r=max(r,abs(a[i]-a[i+1]));
while(l<r)
{
ll mid=l+r>>1;
if(check(mid))
r=mid;
else l=mid+1;
}
printf("%lld\n",r);
return 0;
}
|
简单题，分别从左和从右模拟一次就可以了
Code
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,ans;
int h[N],f[N];
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(h[i]);
f[1]=1;
for(int i=2;i<=n;i++)
f[i]=min(f[i-1]+1,h[i]);
f[n]=1;
for(int i=n-1;i;i--)
f[i]=min(f[i+1]+1,f[i]);
for(int i=1;i<=n;i++)
ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}
|
又是简单题，两遍 dfs 即可
Code
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10,M=1e5+10;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m;
int tot,head[N],ver[M<<1],ne[M<<1];
int vis[N];
int cnt1,cnt2,ans1[N],ans2[N];
void add(int u,int v)
{
ver[++tot]=v;
ne[tot]=head[u];
head[u]=tot;
}
void dfs1(int x)
{
for(int i=head[x];i;i=ne[i])
{
if(!vis[ver[i]])
{
vis[ver[i]]=1;
ans1[++cnt1]=ver[i];
dfs1(ver[i]);
break;
}
}
}
void dfs2(int x)
{
for(int i=head[x];i;i=ne[i])
{
if(!vis[ver[i]])
{
vis[ver[i]]=1;
ans2[++cnt2]=ver[i];
dfs2(ver[i]);
break;
}
}
}
int main()
{
read(n,m);
for(int i=1;i<=m;i++)
{
int u,v;
read(u,v);
add(u,v),add(v,u);
}
vis[1]=1;
dfs1(1);
dfs2(1);
printf("%d\n",cnt1+cnt2+1);
for(int i=cnt1;i;i--)
printf("%d ",ans1[i]);
printf("1 ");
for(int i=1;i<=cnt2;i++)
printf("%d ",ans2[i]);
return 0;
}
|
还是简单题（大雾）。排序后直接 01背包 就可以了，然后注意细节。
Code
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=5e2+10,M=1e4+10,INF=1e9;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m;
int c[N],e[N];
ll p[M],f[M],ans;
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
read(m,n);
for(int i=1;i<=m;i++)
read(p[i]);
sort(p+1,p+1+m,cmp);
for(int i=2;i<=m;i++)
p[i]+=p[i-1];
for(int i=1;i<=n;i++)
read(c[i],e[i]),c[i]=min(c[i],m);
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=c[i];j--)
f[j]=min(f[j],f[j-c[i]]+e[i]);
for(int j=m-1;j>=1;j--)
f[j]=min(f[j],f[j+1]);
}
ll res=INF;
for(int i=1;i<=m;i++)
ans=max(ans,p[i]-f[i]);
printf("%lld\n",ans);
return 0;
}
|
小清新数据结构题，比较水。看到位运算很容易想到按位拆开来算，毕竟时限本来就很宽松（以至于暴力用循环展开都可以卡过去）。对于线段树中每个节点维护一个数组 $sum_i$，表示在此区间中有多少个数第 $i$ 位为 $1$。查询和修改大力维护就可以了。时间复杂度 $\mathcal O(m\log n\log V)$，其中 $V$ 为值域。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+10,K=20;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
struct Node
{
int l,r;
int sum[32],tag;
}tr[N<<2];
int n,m;
int a[N];
void pushup(int x)
{
for(int i=0;i<=K;i++)
tr[x].sum[i]=tr[x<<1].sum[i]+tr[x<<1|1].sum[i];
}
void update(int x,int k)
{
tr[x].tag^=k;
for(int i=0;i<=K;i++)
if(k>>i&1)
tr[x].sum[i]=(tr[x].r-tr[x].l+1-tr[x].sum[i]);
}
void pushdown(int x)
{
if(!tr[x].tag)
return ;
update(x<<1,tr[x].tag);
update(x<<1|1,tr[x].tag);
tr[x].tag=0;
}
void build(int x,int l,int r)
{
tr[x].l=l,tr[x].r=r;
if(l==r)
{
for(int i=0;i<=K;i++)
tr[x].sum[i]=(a[l]>>i&1);
return ;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
ll query(int x,int l,int r)
{
if(tr[x].l>=l&&tr[x].r<=r)
{
ll res=0;
for(int i=0;i<=K;i++)
res+=1ll*tr[x].sum[i]<<i;
return res;
}
pushdown(x);
int mid=tr[x].l+tr[x].r>>1;
ll res=0;
if(l<=mid)res+=query(x<<1,l,r);
if(r>mid)res+=query(x<<1|1,l,r);
return res;
}
void modify(int x,int l,int r,int k)
{
if(tr[x].l>=l&&tr[x].r<=r)
{
update(x,k);
return ;
}
pushdown(x);
int mid=tr[x].l+tr[x].r>>1;
if(l<=mid)modify(x<<1,l,r,k);
if(r>mid)modify(x<<1|1,l,r,k);
pushup(x);
}
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i]);
build(1,1,n);
read(m);
for(int i=1;i<=m;i++)
{
int op,l,r;
read(op,l,r);
if(op==1)
printf("%lld\n",query(1,l,r));
else
{
int x;
read(x);
modify(1,l,r,x);
}
}
return 0;
}
|
第一眼觉得很神秘。但是我们容易发现最优方案似乎只有一条边。因为加入选取一条密度最大的边后，选取其它边只会是密度变小。
然后就过了？
Code
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m;
int a[N];
double ans;
int main()
{
read(n,m);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<=m;i++)
{
int u,v,w;
read(u,v,w);
ans=max(ans,(a[u]+a[v])*1.0/w);
}
printf("%.10lf\n",ans);
return 0;
}
|
考虑假如每次将一个数拆成两半，最少会进行 $\lceil\log_2 n\rceil$ 次。一个贪心的想法是一次尽可能选尽量多的数进行操作。我们只用考虑一段单峰区间的最大操作次数就行了。每次只需要记录上一个数的操作次数就行了。
但是这样似乎很容易被 Hack：
1
2
3
4
5
6
| 3
3 3 3
out:2
ans:3
3 3 3 -> 1 2 2 1 3 -> 1 1 1 1 1 1 3 -> 1 1 1 1 1 1 1 2 ->
1 1 1 1 1 1 1 1 1
|
原因很显然，可能存在并不能将多个数一起操作的情况。但是没有关系，这种情况只可能存在于需要上取整的情况。对于此种情况，如果前面的操作次数比它小，我们就将其看做已经对其执行了一次操作，使它变成了较小的另一半。这样继续贪心就没有问题了。
这样看来似乎有一点奇怪，但仔细想想这确实是没有问题的。
Code
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
| #include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1e5+10;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,res,ans;
int main()
{
read(n);
for(int i=1;i<=n;i++)
{
int x,d;
read(x);
d=log2(x);
if((1<<d)<x&&d>=res)
d++;
if(d>res)ans+=d-res;
res=d;
}
printf("%d\n",ans);
return 0;
}
|
水题，暴力断开一条边，然后对剩下的两棵树分别求直径。最后求最大值就可以。时间复杂度 $\mathcal O(n^2)$。
难道就这样吗？
不如看看加强版 SP6717 TWOPATHS - Two Paths（但还是虚高题）。
我们考虑 $\mathcal O(n)$ 的做法。
update on 2022.11.13。原题解被 @zhanghenglei 所 Hack。现在已将解法修正，如果仍有问题，欢迎指出qwq。
不难想到用 $f_x,g_x$ 分别表示以 $x$ 为根的子树内和子树外最长链的长度。答案就是 $\max{f_x\times g_x}$。$f_x$ 很容易求，考虑 $g_x$ 怎么求。
$g_x$ 可以从父亲节点转移过来，这启发我们可以类似于换根 DP 的方法来求 $g_x$。
考虑怎么构成一条子树外的链。无非是从父节点往上延伸，或者从父节点往下延伸的链。再将他们最长的两段在父节点拼起来成为一个答案。
但是我们选取的两段链不能在 $x$ 的子树中。这就意味着我们需要先求出，从父节点往下延伸的链的最大值、亚大值和次大值，以及对应的子节点。转移时判断一下所选的链有没有在 $x$ 的子树中就行。
从该节点 $x$ 往上延伸的最长链也可以通过最大值和亚大值通过换根 DP 来求出，也比较简单。
但是这样解是有漏洞的，$g_x$ 求出来只是恰好经过其父节点的最长链，而不是整棵树中除去该子树的最长链，就像这样：
output : 30
answer : 36
所以我们需要再多记一个 $h_x$ 表示该节点的父节点的子树之外的最长链，转移与上面类似。
具体可看看代码，有一些注释。有点繁琐，但还是比较好写。
Code
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+10;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
ll ans;
int tot,head[N],ver[N<<1],ne[N<<1];
int d[N][3],l[N],t[N][3],f[N],g[N],h[N];
int res;
inline void add(int u,int v)
{
ver[++tot]=v;
ne[tot]=head[u];
head[u]=tot;
}
void dfs1(int x,int fa)
{
for(int i=head[x];i;i=ne[i])
{
int y=ver[i];
if(y==fa)continue;
dfs1(y,x);
if(d[y][0]+1>=d[x][0])
{
d[x][2]=d[x][1],t[x][2]=t[x][1];
d[x][1]=d[x][0],t[x][1]=t[x][0];
d[x][0]=d[y][0]+1,t[x][0]=y;
}
else if(d[y][0]+1>=d[x][1])
{
d[x][2]=d[x][1],t[x][2]=t[x][1];
d[x][1]=d[y][0]+1,t[x][1]=y;
}
else if(d[y][0]+1>=d[x][2])
d[x][2]=d[y][0]+1,t[x][2]=y;
f[x]=max(f[x],f[y]);
}
f[x]=max(f[x],d[x][0]+d[x][1]);
}
void dfs2(int x,int fa)
{
ans=max(ans,1ll*f[x]*max(g[x],h[x]));
for(int i=head[x];i;i=ne[i])
{
int y=ver[i];
if(y==fa)continue;
l[y]=l[x]+1;
if(t[x][0]&&t[x][0]!=y)
l[y]=max(l[x],d[x][0])+1;
else if(t[x][1])
l[y]=max(l[x],d[x][1])+1;
int res[4];
res[0]=t[x][0]!=y?d[x][0]:0;
res[1]=t[x][1]!=y?d[x][1]:0;
res[2]=t[x][2]!=y?d[x][2]:0;
res[3]=l[x];
sort(res,res+4);
g[y]=max(g[x],res[2]+res[3]);
h[y]=h[x];
dfs2(y,x);
res[0]=t[y][0]!=y?d[y][0]:0;
res[1]=t[y][1]!=y?d[y][1]:0;
res[2]=t[y][2]!=y?d[y][2]:0;
sort(res,res+3);
h[x]=max(h[x],res[1]+res[2]);
}
}
int main()
{
read(n);
for(int i=1;i<n;i++)
{
int u,v;
read(u,v);
add(u,v);
add(v,u);
}
dfs1(1,0);
dfs2(1,0);
printf("%lld\n",ans);
return 0;
}
|
考虑贪心。我们依次考虑，将每个点放在左端或者右端。
而是对于每个点，我们考虑拆贡献。设放在前面的点 $[1,l]$ 的和为 $sum_1$，放在后面的点 $ [r,n]$ 的和为 $sum_2$，所有点和为 $sum$，那么：
1.放在前面的点，对其后面的点贡献为 $sum-sum_1$。
2.放在后面的点，对其后面的点贡献为 $sum_2$。而他前面还有 $r-l+1$ 个点未计算贡献，而这部分贡献为 $a_i\times (r-l+1)$。
注意，我们直接统计贡献是会有重复的。但是这样贪心的话，我们能保证对于之后的决策都会是更优的。真正的的贡献直接统计就好了。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e6+10;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
int a[N];
int l,r,ans[N];
ll sum1,sum2;
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i]),sum1+=a[i];
l=1,r=n;
ll res=0;
for(int i=1;i<=n;i++)
{
if(sum1>=1ll*a[i]*(r-l+1)+sum2)
res+=1ll*a[i]*l,ans[l++]=a[i],sum1-=a[i];
else res+=1ll*a[i]*r,ans[r--]=a[i],sum2+=a[i];
}
printf("%lld\n",res);
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}
|
神秘题。随机化题目都没怎么做过，所以根本不会。。。
考虑两个结论：
1.操作次数 $< n$。
2.操作超过两次的数 $\le \frac{n}{2}$。
那么随机化做法就来了，我们每次随机选取一个数 $x$，并将 $x-1,x,x+1$ 都分解质因数，放入一个 set 里。我们一共选取 50 次，这样最多有约 600 个质数。
然后我们暴力枚举每个质因数 $p$，计算 $\gcd=p$ 时的操作次数是多少。取最小值就可以了。
我们每次都有至少 $\frac{1}{2}$ 的概率选中操作次数小于等于一次的数。所以错误的概率只为 $\frac{1}{2^{50}}$。
注意每个数不能为 $0$。
Code
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
| #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<set>
#include<ctime>
#define ll long long
using namespace std;
const int N=2e5+10,INF=1e9;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
ll ans;
ll a[N];
set<ll>prime;
inline void divide(ll x)
{
for(ll i=2;i*i<=x;i++)
{
if(!(x%i))
{
prime.insert(i);
while(!(x%i))x/=i;
}
}
if(x>1)prime.insert(x);
}
int main()
{
srand(time(0));
read(n);
ans=n;
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<=50;i++)
{
int pos=rand()*rand()%n+1;
divide(a[pos]-1),divide(a[pos]),divide(a[pos]+1);
}
set<ll>::iterator it;
for(it=prime.begin();it!=prime.end();it++)
{
ll res=0;
for(int i=1;i<=n;i++)
{
if(a[i]>*it)
res+=min(a[i]%*it,(*it-a[i]%*it));
else res+=*it-a[i];
}
ans=min(ans,res);
}
printf("%lld\n",ans);
return 0;
}
|
假如有 $cnt$ 个连通块，那么我们需要连 $cnt-1$ 条边，那么就要选取 $2\times cnt-2$ 个点。现在每个连通块里选一个最小的，再贪心地在所以里面再选 $cnt-2$ 个最小的即可。
Code
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1e5+10,INF=1<<30;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m,cnt;
ll ans;
int a[N],fa[N],v[N];
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
read(n,m);
for(int i=1;i<=n;i++)
read(a[i]),fa[i]=i,v[i]=a[i];
for(int i=1;i<=m;i++)
{
int u,v;
read(u,v);
fa[find(v+1)]=find(u+1);
}
for(int i=1;i<=n;i++)
v[find(i)]=min(v[find(i)],a[i]);
for(int i=1;i<=n;i++)
{
if(a[i]==v[find(i)])
{
ans+=a[i];
cnt++;
v[find(i)]=INF;
a[i]=INF;
}
}
if(cnt==1)
{
puts("0");
return 0;
}
sort(a+1,a+1+n);
for(int i=1;i<=cnt-2;i++)
{
if(a[i]==INF)
{
puts("Impossible");
return 0;
}
ans+=a[i];
}
printf("%lld\n",ans);
return 0;
}
|
如果没有整数的话，答案就是一定的。我们只需要枚举将多少个整数上取整即可。
Code
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
| #include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1e5+10;
const double eps=1e-4,INF=1e9;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
double a[N],sum,ans=INF;
int cnt;
int main()
{
read(n);
for(int i=1;i<=2*n;i++)
{
scanf("%lf",&a[i]);
a[i]=a[i]-int(a[i]);
if(a[i]<=eps)cnt++;
sum+=a[i];
}
for(int i=max(cnt-n,0);i<=min(cnt,n);i++)
ans=min(ans,abs(sum-n+i));
printf("%.3lf\n",ans);
return 0;
}
|
分治求解即可。每次考虑将区间内高度最小的横着刷，将其分成多个小区间再求解。
Code
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=5e3+10,INF=1e9;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
int a[N];
int solve(int l,int r,int h)
{
if(l>r)return 0;
if(l==r)return min(1,a[l]-h);
int minx=INF,cnt=0;
for(int i=l;i<=r;i++)
minx=min(minx,a[i]);
int pre=l,res=minx-h;
for(int i=l;i<=r;i++)
if(a[i]==minx)
res+=solve(pre,i-1,minx),pre=i+1;
res+=solve(pre,r,minx);
return min(res,r-l+1);
}
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i]);
printf("%d\n",solve(1,n,0));
return 0;
}
|
虽然这样已经做可以通过此题，但这并不影响我们对更优解的思考。我们发现时间都浪费在找最小值上，我们可以用笛卡尔树来做（本题的形式就是笛卡尔树的经典模型）。这样很容易做到 $\mathcal O(n)$。
Code
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+10,INF=1e9;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
struct Node
{
int l,r;
int val;
}tr[N];
int n;
int a[N];
int top,sta[N];
int solve(int l,int r,int pos,int h)
{
if(l>r)return 0;
int res=solve(l,pos-1,tr[pos].l,tr[pos].val)+
solve(pos+1,r,tr[pos].r,tr[pos].val)+tr[pos].val-h;
return min(res,r-l+1);
}
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(tr[i].val);
for(int i=1;i<=n;i++)
{
int p=top;
while(p&&tr[sta[p]].val>tr[i].val)
p--;
if(p)tr[sta[p]].r=i;
if(p<top)tr[i].l=sta[p+1];
sta[++p]=i;
top=p;
}
printf("%d\n",solve(1,n,sta[1],0));
return 0;
}
|
先考虑贪心，考虑微扰法，假设有 $i$ 与 $j$，他们的花费分别为 $(a_i+1)\times (a_j\times t+b_j+t+1)+b_i$ 与 $(a_j+1)\times (a_i\times t+b_i+t+1)+b_j$，两式相减即可得到 $a_i\times b_j +a_i- a_j\times b_i -a_j$，于是我们按照 $\frac{a_i}{b_i+1}<\frac{a_j}{b_j+1}$ 的顺序排序即可。
确定顺序后考虑 DP，$f_{i,j}$ 为考虑前 $i$ 个点选取 $j$ 个点，很容易有转移方程 $f_{i,j}=\min {f_{i-1,j},(f_{i-1,j-1}+1)*(a_i+1)+b_i}$。
这样状态已经是 $\mathcal O(n^2)$ 的。但是我们注意当 $a_i\ge 1$ 时，时间是按照指数级别增长，那么我们最多就只能选取 $\log t$ 个点，状态就变为 $\mathcal O(n\log t)$ 了。过程中还可以使用滚动数组优化。
Code
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2e5+10,K=40,INF=1e9;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
struct Line
{
ll k,b;
}a[N];
int n,t,ans,tot;
ll c[N],f[N][K];
bool cmp(Line x,Line y)
{
return y.k*(x.b+1)<x.k*(y.b+1);
}
int main()
{
read(n,t);
for(int i=1;i<=n;i++)
{
read(a[i].k,a[i].b);
if(a[i].k==0)
c[++tot]=a[i].b,a[i].k=INF;
}
sort(a+1,a+1+n,cmp);
sort(c+1,c+1+tot);
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++)
f[i][j]=INF;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j-1],(f[i-1][j-1]+1)*(a[j].k+1)+a[j].b);
for(int i=1;i<=tot;i++)
c[i]+=c[i-1];
int j=tot;
for(int i=1;i<=n&&f[i][n]<=t;i++)
{
while(j&&f[i][n]+c[j]>t)j--;
ans=max(ans,i+j);
}
printf("%d\n",ans);
return 0;
}
|
考虑每一次操作的本质就是断开该节点以外的所有叶子。于是考虑树的直径 $len$，简单博弈就可以得到当 $len \equiv 2\mod3$ 时才是 Second。
Code
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=2e5+10;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
int tot,head[N],ver[N<<1],ne[N<<1];
int len,d[N],f[N];
inline void add(int u,int v)
{
ver[++tot]=v;
ne[tot]=head[u];
head[u]=tot;
}
void dfs(int x,int fa)
{
for(int i=head[x];i;i=ne[i])
{
int y=ver[i];
if(y==fa)continue;
dfs(y,x);
len=max(len,d[x]+d[y]+1);
d[x]=max(d[x],d[y]+1);
}
}
int main()
{
read(n);
for(int i=1;i<n;i++)
{
int u,v;
read(u,v);
add(u,v),add(v,u);
}
dfs(1,0);
len++;
puts(len%3!=2?"First":"Second");
return 0;
}
|
简单题，前缀和然后 DP 就完了。
Code
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=2e5+10;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,ans;
int a[N],sum[N],f[N],pre[3];
int main()
{
while(scanf("%1d",&a[++n])!=EOF)
sum[n]=sum[n-1]+a[n];
n--;
for(int i=1;i<=n;i++)
{
f[i]=max(f[i-1],f[pre[sum[i]%3]]+(pre[sum[i]%3]||sum[i]%3==0));
pre[sum[i]%3]=i;
ans=max(ans,f[i]);
}
printf("%d\n",ans);
return 0;
}
|
考虑 $f_x$ 为从点 $x$ 走到 $x+1$ 的期望步数。$\deg_x$ 为 $x$ 的出度那么有：
$f_x=1+\frac{\sum_y \sum_{i=y}^{x} f_i}{\deg_x}$
使用对 $f$ 做前缀和得到：
$f_x=\frac{\deg_x+(\deg_x-1)\times sum_x-\sum sum_{y-1}}{\deg_x}$
将 $sum_x$ 替换为 $sum_{x-1}+f_x$ 得：
$f_x=\deg_x+(\deg_x-1)\times sum_{x-1}-\sum sum_{y-1}$
线性递推即可。
Code
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>
#define ll long long
using namespace std;
const int N=1e6+10,M=1e6+10,mod=998244353;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m,id;
int tot,head[N],ver[M],ne[M];
int deg[N];
ll f[N],sum[N];
inline void add(int u,int v)
{
ver[++tot]=v;
ne[tot]=head[u];
head[u]=tot;
}
int main()
{
read(id,n,m);
for(int i=1;i<=m;i++)
{
int u,v;
read(u,v);
add(u,v);
deg[u]++;
}
for(int x=1;x<=n;x++)
{
for(int i=head[x];i;i=ne[i])
f[x]=(f[x]+sum[ver[i]-1])%mod;
f[x]=((deg[x]+1+deg[x]*sum[x-1]%mod-f[x])%mod+mod)%mod;
sum[x]=(sum[x-1]+f[x])%mod;
}
printf("%lld\n",sum[n]);
return 0;
}
|
将问题转化为一维，等价于求 $max-min=r-l$ 的区间个数。
考虑枚举左端点 $l$，求出满足答案的右端点 $r$，并且用线段树维护 $max-min-r+l$ 的最小值及其个数。每次移动左端点 $l$ 时，用单调栈维护最小值和最大值，消除前面的影响即可。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=3e5+10;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
struct Node
{
int l,r;
int val,cnt,tag;
}tr[N<<2];
int n;
int a[N];
int top1,top2,sta1[N],sta2[N];
ll ans;
inline void pushup(int x)
{
tr[x].val=min(tr[x<<1].val,tr[x<<1|1].val);
tr[x].cnt=(tr[x<<1].val==tr[x].val)*tr[x<<1].cnt
+(tr[x<<1|1].val==tr[x].val)*tr[x<<1|1].cnt;
}
inline void update(int x,int k)
{
tr[x].val+=k;
tr[x].tag+=k;
}
inline void pushdown(int x)
{
if(!tr[x].tag)return ;
update(x<<1,tr[x].tag);
update(x<<1|1,tr[x].tag);
tr[x].tag=0;
}
void build(int x,int l,int r)
{
tr[x].l=l,tr[x].r=r;
if(l==r)
{
tr[x].val=l,tr[x].cnt=1;
return ;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
void modify(int x,int l,int r,int k)
{
if(tr[x].l>=l&&tr[x].r<=r)
{
update(x,k);
return ;
}
pushdown(x);
int mid=tr[x].l+tr[x].r>>1;
if(l<=mid)modify(x<<1,l,r,k);
if(r>mid)modify(x<<1|1,l,r,k);
pushup(x);
}
int main()
{
read(n);
for(int i=1;i<=n;i++)
{
int x,y;
read(x,y);
a[x]=y;
}
build(1,1,n);
for(int i=1;i<=n;i++)
{
while(top1&&a[i]<a[sta1[top1]])
{
modify(1,sta1[top1-1]+1,sta1[top1],-(a[i]-a[sta1[top1]]));
top1--;
}
sta1[++top1]=i;
while(top2&&a[i]>a[sta2[top2]])
{
modify(1,sta2[top2-1]+1,sta2[top2],a[i]-a[sta2[top2]]);
top2--;
}
sta2[++top2]=i;
ans+=tr[1].cnt;
}
printf("%lld\n",ans);
return 0;
}
|
直接DP。$f_{i,j,k}$ 表示到第 $i$ 轮变换 $j$ 次变成手势 $k$ 时最多赢的次数。时间复杂度 $\mathcal O(nk)$。
Code
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10,M=30;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m;
int a[N];
int f[N][M][3];
int h(int x,int y)
{
if((x==0&&y==1)||(x==1&&y==2)||(x==2&&y==0))
return 1;
return 0;
}
int main()
{
read(n,m);
for(int i=1;i<=n;i++)
{
char ch[10];
scanf("%s",ch);
if(ch[0]=='H')a[i]=0;
else if (ch[0]=='S')a[i]=1;
else a[i]=2;
}
for(int i=0;i<3;i++)
f[1][0][i]=h(i,a[1]);
for(int i=2;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<3;k++)
for(int l=0;l<3;l++)
f[i][j][k]=max(f[i][j][k],max(f[i-1][j][k],(j-(k!=l)>=0)?f[i-1][j-(k!=l)][l]:0)+h(k,a[i]));
int ans=0;
for(int i=0;i<=m;i++)
for(int j=0;j<3;j++)
ans=max(ans,f[n][i][j]);
printf("%d\n",ans);
return 0;
}
|
小清新构造题。
注意观察，其实我们只需要将边权按照 popcount 的奇偶全部转为 $0,1$ 即可。我们再通过边的限制维护两个点集，表示两个点集中的元素互相之间边权异或和为 $1$，而点集内部的点之间的边权异或和为 $0$。这个可以直接用扩展域并查集维护即可。
需要注意的是最后输出方案时也需要把新加的边权加进限制里面。
Code
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=2e5+10;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int T,n,m;
int u[N],v[N],w[N];
int fa[N<<1];
int get(int x){return (x==fa[x])?x:fa[x]=get(fa[x]);}
inline void merge(int x,int y)
{
x=get(x),y=get(y);
fa[y]=x;
}
inline void solve()
{
read(n,m);
for(int i=1;i<=(n<<1);i++)
fa[i]=i;
for(int i=1;i<n;i++)
{
read(u[i],v[i],w[i]);
if(!~w[i])continue;
int x=__builtin_popcount(w[i])&1;
if(x)merge(u[i]+n,v[i]),merge(u[i],v[i]+n);
else merge(u[i],v[i]),merge(u[i]+n,v[i]+n);
}
for(int i=1;i<=m;i++)
{
int u,v,w;
read(u,v,w);
if(w)merge(u+n,v),merge(u,v+n);
else merge(u,v),merge(u+n,v+n);
}
for(int i=1;i<=n;i++)
if(get(i)==get(i+n))
{
puts("NO");
return ;
}
puts("YES");
for(int i=1;i<n;i++)
{
if(!~w[i])
{
if(get(u[i])!=get(v[i]))w[i]=1,merge(u[i]+n,v[i]),merge(u[i],v[i]+n);
else w[i]=0,merge(u[i],v[i]),merge(u[i]+n,v[i]+n);
}
printf("%d %d %d\n",u[i],v[i],w[i]);
}
}
int main()
{
read(T);
while(T--)solve();
return 0;
}
|
感觉自己的人类智慧又不够用了。
通过简单动手画图，如果将每个点向所有和它同行或同列的点连边，我们发现只要形成连通块，那么可以按照这个连通块的最大长与宽把这个长方形填满。维护连通性？我们可以用并查集。
我们有一种比较巧妙的方法来维护。我们将一个点的坐标拆成 $x$ 和 $y$ 单独的两个点，并且将每个点的第 $x$ 行与第 $y$ 列合并。最后统计根节点的长与宽就行了，代码很简洁。
Code
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>
using namespace std;
const int N=1e5+10;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m=1e5;
long long ans;
int fa[N<<1];
int f[N<<1],g[N<<1];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
inline void merge(int x,int y)
{
x=get(x),y=get(y);
fa[y]=x;
}
int main()
{
read(n);
for(int i=1;i<=m<<1;i++)
fa[i]=i;
for(int i=1;i<=n;i++)
{
int x,y;
read(x,y);
merge(x,y+m);
}
for(int i=1;i<=m;i++)f[get(i)]++;
for(int i=1;i<=m;i++)g[get(i+m)]++;
for(int i=1;i<=m<<1;i++)
ans+=1ll*f[i]*g[i];
printf("%lld\n",ans-n);
return 0;
}
|
有点意思的结论题。
直接给结论，设 $a>b$，则 $a-b=a\oplus b$。
简单证明：
先考虑一个结论 $a-b\le a\oplus b$，
又因为 $\gcd(a,b)\ge a-b$。
就有了上面的结论。
剩下的直接枚举就行了，时间复杂度 $\mathcal O(n\ln n)$。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=3e7+10;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int T,n;
ll sum[N];
inline void prework(int n)
{
for(int i=1;i<=n;i++)
for(int j=2*i;j<=n;j+=i)
if(((j-i)^j)==i)
sum[j]++;
for(int i=2;i<=n;i++)
sum[i]+=sum[i-1];
}
int main()
{
prework(N-10);
read(T);
for(int t=1;t<=T;t++)
{
int x;
read(x);
printf("Case %d: %lld\n",t,sum[x]);
}
return 0;
}
|
有意思的一道题。
直接 DP，但是似乎不好设计出好转移的状态。这里就比较关键，直接设 $f_{i,j}$ 表示位置 $i$ 与 位置 $j$ 上的数满足偏序关系的期望。这样就对于每一个交换操作我们可以 $\mathcal O(n)$ 求出其贡献，而预处理和统计答案的时间为 $\mathcal O(n^2)$。总时间复杂度为 $\mathcal O(n^2+qn)$。
代码十分好写。
Code
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=1e3+10;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,q;
int a[N];
double f[N][N];
int main()
{
read(n,q);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i==j)continue;
f[i][j]=(a[i]<a[j]);
}
while(q--)
{
int x,y;
read(x,y);
for(int i=1;i<=n;i++)
{
if(i==x||i==y)continue;
f[x][i]=f[y][i]=f[x][i]*0.5+f[y][i]*0.5;
f[i][x]=f[i][y]=f[i][x]*0.5+f[i][y]*0.5;
}
f[x][y]=f[y][x]=f[x][y]*0.5+f[y][x]*0.5;
}
double ans=0;
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
ans+=f[j][i];
printf("%.9lf\n",ans);
return 0;
}
|
这次是真的要认真开始做了。
比较容易想复杂，但还是挺巧妙的经典题。
因为有 $n\le 20$，考虑对每一列进行状压，设第 $i$ 行的初始状态为 $g[i]$。接着考虑对行操作，也只有 $2^n$ 种。对行的操作为 $x$ 时，答案 $\displaystyle f[x]=\sum_{i=1}^m \min(\text{popcount} (g[i]\oplus x),\text{popcount}(\neg g[i]\oplus x))$。暴力计算是 $\mathcal O(m2^n)$。考虑将 $m$ 去掉，所有行的状态总数最多为 $2^n$，记 $\displaystyle a[x]=\sum_{i=1}^{m}[g[i]=x]$。关键的来了，这个转移成立满足的条件是 $g[i]\oplus x=y$ 或 $\neg g[i]\oplus x=y$，贡献与 $y$ 相关，要求的是对 $x$ 的贡献，于是将 $y$ 移至等式右侧，$x$ 移至等式右侧吗，得到 $g[i]\oplus y=x$ 或 $g[i]\oplus \neg y=x$。于是进一步得到下面的式子：
其中 $b[i]$ 代表 $\min(\text{popcount} (i),\text{popcount}(\neg x))$。转化为 FWT 板子，时间复杂度为 $\mathcal O(n 2^n)$。
注意 FWT 过程中需要开long long。
Code
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
| #include<iostream>
#include<cstdio>
#define ll long long
#define popcnt __builtin_popcount
using namespace std;
const int N=21,M=1e5+10,INF=1e9;
template<class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m;
int g[M];
ll a[1<<N],b[1<<N];
inline void FWT(int n,ll *a)
{
int tot=1<<n;
for(int mid=1;mid<tot;mid<<=1)
for(int i=0;i<tot;i+=mid<<1)
for(int j=0;j<mid;j++)
{
ll x=a[i+j],y=a[i+j+mid];
a[i+j]=x+y,a[i+j+mid]=x-y;
}
}
inline void IFWT(int x,ll *a)
{
int tot=1<<n;
for(int mid=1;mid<tot;mid<<=1)
for(int i=0;i<tot;i+=mid<<1)
for(int j=0;j<mid;j++)
{
ll x=a[i+j],y=a[i+j+mid];
a[i+j]=x+y>>1,a[i+j+mid]=x-y>>1;
}
}
int main()
{
read(n,m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
int x;
scanf("%1d",&x);
g[j]|=x<<i;
}
int tot=1<<n;
for(int i=0;i<m;i++)a[g[i]]++;
for(int i=0;i<tot;i++)b[i]=popcnt(i),b[i]=min(b[i],n-b[i]);
FWT(n,a),FWT(n,b);
for(int i=0;i<tot;i++)a[i]*=b[i];
IFWT(n,a);
ll ans=INF;
for(int i=0;i<tot;i++)ans=min(ans,a[i]);
printf("%lld\n",ans);
return 0;
}
|
手玩一下，发现最优情况下答案一定是一个回文串。
我们考虑 DP，设 $f(l,r,k)$ 表示对子串 $(l,r)$ 操作 $k$ 次后最长的的回文子序列的长度。直接转移即可。
Code
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
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=300+10;
int n,k;
char a[N];
int f[N][N][N];
inline void ckmax(int &x,int y){x=x>y?x:y;}
int main()
{
scanf("%s%d",a+1,&k);
n=strlen(a+1);
for(int t=0;t<=k;t++)
for(int i=1;i<=n;i++)f[t][i][i]=1;
for(int t=0;t<=k;t++)
{
for(int len=2;len<=n;len++)
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
ckmax(f[t][i][j],max(f[t][i+1][j],f[t][i][j-1]));
if(a[i]==a[j])ckmax(f[t][i][j],f[t][i+1][j-1]+2);
else if(t)ckmax(f[t][i][j],f[t-1][i+1][j-1]+2);
}
}
printf("%d\n",f[k][1][n]);
return 0;
}
|
发现与我之前做过的一个题 [ABC242Ex] Random Painting 简直一模一样。略有不同，但还是做出来了。
和那个题完全一样的套路，设 $i$ 是在第 $t_i$ 次第一次被选中，那么要求的答案就是 $\displaystyle E(\max_{i\in S}t_i)$，$S$ 为全集。考虑 min-max 容斥的式子，得到
容易知道 $\displaystyle E(\min_{i\in S} t_i)=\frac{n}{\sum_{i\in S} c_i}$，于是我们考虑对于每个 $\sum_{i\in S} c_i=k$ 求出对应的容斥系数。我们相当于要对于每个 $k$ 求 $\displaystyle \sum_{\sum_{i\in S} c_i=k} (-1)^{|T|+1}$，很容易看出来卷积的形式，转化为生成函数就是 $\displaystyle -\prod_{i} (1-x^{c_i})$，而这个式子就更经典了，我们可以直接分治 NTT 做到 $\mathcal O(n\log^2 n)$。更牛逼的是，这就是 P4389 付公主的背包 中非常经典的式子，直接用取 $\exp$ 之后再取 $\ln$ 的 trick 即可做到 $\mathcal O(n\log n)$。
Code
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=4e6+10,mod=998244353,G=3,Gi=(mod+1)/G;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
int a[N],b[N],c[N],d[N],e[N],f[N];
int bit,tot,rev[N];
inline int adj(int x){return x>=mod?x-mod:x;}
inline void upd(int &x,int y){x+=y,x=x>=mod?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
int res=1;
while(k)
{
if(k&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;
k>>=1;
}
return res;
}
inline void init(int len)
{
bit=0;
while((1<<bit)<len)bit++;
tot=1<<bit;
for(int i=0;i<tot;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<bit-1);
}
inline void NTT(int *a,int inv)
{
for(int i=0;i<tot;i++)if(rev[i]<i)swap(a[rev[i]],a[i]);
for(int mid=1;mid<tot;mid<<=1)
{
int g=qpow(inv==1?G:Gi,(mod-1)/(mid<<1));
for(int i=0;i<tot;i+=(mid<<1))
for(int j=0,cur=1;j<mid;j++,cur=1ll*cur*g%mod)
{
int x=a[i+j],y=1ll*cur*a[i+j+mid]%mod;
a[i+j]=adj(x+y),a[i+j+mid]=adj(x-y+mod);
}
}
if(inv==-1)
{
int inv=qpow(tot,mod-2);
for(int i=0;i<tot;i++)a[i]=adj(1ll*a[i]*inv%mod+mod);
}
}
void poly_inv(int *a,int *b,int len)
{
if(len==1)return b[0]=qpow(a[0]),void();
poly_inv(a,b,(len+1)>>1);
init(len<<1);
for(int i=0;i<tot;i++)c[i]=(i<len?a[i]:0);
NTT(b,1),NTT(c,1);
for(int i=0;i<tot;i++)b[i]=1ll*adj(2-1ll*b[i]*c[i]%mod+mod)*b[i]%mod;
NTT(b,-1);
for(int i=len;i<tot;i++)b[i]=0;
}
inline void derivative(int *a,int *b,int len)
{
for(int i=1;i<len;i++)b[i-1]=1ll*i*a[i]%mod;
b[len-1]=0;
}
inline void integrate(int *a,int *b,int len)
{
for(int i=len-1;i;i--)b[i]=1ll*qpow(i)*a[i-1]%mod;
b[0]=0;
}
inline void poly_ln(int *a,int *b,int len)
{
poly_inv(a,b,len);
derivative(a,d,len);
init(len<<1);
NTT(b,1),NTT(d,1);
for(int i=0;i<tot;i++)b[i]=1ll*b[i]*d[i]%mod;
NTT(b,-1);
integrate(b,b,len<<1);
}
inline void poly_exp(int *a,int *b,int len)
{
if(len==1)return b[0]=(a[0]==0),void();
poly_exp(a,b,(len+1)>>1);
for(int i=0;i<(len<<1);i++)e[i]=0;
poly_ln(b,e,len);
init(len<<1);
for(int i=0;i<tot;i++)f[i]=(i<len?a[i]:0);
f[0]++;
for(int i=0;i<len;i++)f[i]=adj(f[i]-e[i]+mod);
NTT(b,1),NTT(f,1);
for(int i=0;i<tot;i++)b[i]=1ll*b[i]*f[i]%mod;
NTT(b,-1);
for(int i=len;i<tot;i++)b[i]=0;
}
int m;
int cnt[N];
int inv[N];
int main()
{
read(m,n);
for(int i=1;i<=n;i++)
{
int x;
read(x);
cnt[x]++;
}
for(int i=1;i<=m;i++)inv[i]=qpow(i);
for(int i=1;i<=m;i++)
{
if(!cnt[i])continue;
for(int j=1;i*j<=m;j++)
upd(a[i*j],mod-1ll*cnt[i]*inv[j]%mod);
}
poly_exp(a,b,m+1);
int ans=0;
for(int i=1;i<=m;i++)upd(ans,1ll*m*inv[i]%mod*(mod-b[i])%mod);
printf("%d\n",ans);
return 0;
}
|
发现和 LOJ#2542. 「PKUWC2018」随机游走 很相似啊。但是我们尝试用那道题一样的方法，发现枚举终点 $f(i)=0$ 很难避免。似乎只能暴力做了。
方法一
考虑转变思路，我们尝试枚举终点作为根。设计状态 $g(u)$ 表示从 $u$ 的子树中的节点走到 $u$ 的期望步数之和。直接似乎不好求，再设计 $f(u)$ 表示从 $u$ 走到 $fa(u)$ 的期望步数。考虑两种情况：1.直接从 $u$ 走到 $fa(u)$；2.从 $u$ 先走到其子节点 $v$ 再返回 $u$，再走到 $fa(u)$。我们尝试列出状态转移方程：
化简一下，那么同时也可以得到 $g(u)$：
这注意到利用这个关系，我们很容易换根做到 $\mathcal O(n)$。
方法二
求 $f(u)$ 的过程是一样的。将答案拆到到根的每条边上，那就是
直接考虑终点是否在子树 $u$ 中即可，时间复杂度为 $\mathcal O(n)$。
Code
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10,mod=998244353;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n;
int tot,head[N],ver[N<<1],ne[N<<1];
int si[N],deg[N],fa[N];
inline void upd(int &x,int y){x+=y,x=x>=mod?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
int res=1;
while(k)
{
if(k&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;
k>>=1;
}
return res;
}
inline void add(int u,int v)
{
ver[++tot]=v;
ne[tot]=head[u];
head[u]=tot;
deg[v]++;
}
void dfs(int x)
{
si[x]=1;
for(int i=head[x];i;i=ne[i])
{
int y=ver[i];
if(y==fa[x])continue;
fa[y]=x;
dfs(y);
si[x]+=si[y],deg[x]+=deg[y];
}
}
int main()
{
read(n);
for(int i=1,u,v;i<n;i++)read(u,v),add(u,v),add(v,u);
dfs(1);
int ans=0;
for(int x=1;x<=n;x++)
{
upd(ans,1ll*(n-si[x])*si[x]*deg[x]%mod);
for(int i=head[x];i;i=ne[i])
{
int y=ver[i];
if(y==fa[x])continue;
upd(ans,1ll*si[y]*(n-si[y])*(deg[1]-deg[y])%mod);
}
}
printf("%d\n",1ll*ans*qpow(1ll*n*n%mod)%mod);
return 0;
}
|