7.16
A
解法
设 $f_{i,j}$ 为当前在 $i$ 节点，用了 $j$ 条线段。
然后我们可以枚举新的不相交线段的右端点，假设为 $k$，则我们的左端点可以是 $i+1,i+2…k$，然后此时对答案的贡献就是 $2^{k-i}-1$（不选的情况舍去），这些线段可以选与不选，都会让总的选数增加 $1$。
而其他线段，其右端点需要大于 $k$（不然和贪心策略矛盾），左端点需要大于 $i$ （避免重复）。那么选与不选就有 $2^{(n-k)\times (k-i)}$ 个方案
综上所述，由 $f_{i,j}$ 转移到 $f_{k,j+1}$ 可得到 $f_{k,j+1} = f_{i,j} \times (2^{k-i} - 1) \times 2^{(k-i)\times({n-k})}$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <bits/stdc++.h>
using namespace std;
const long long inf = 1e9 + 7;
long long f[123123][123];
int n,k;
int main()
{
scanf("%d%d",&n,&k);
f[0][0]=1;
for(int i=0;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
for(int r=i+1;r<=n;r++) f[r][j]+=f[i][j-1]*((1<<(r-i))-1)*(1<<((n-r)*(r-i))),f[r][j]%=inf;
}
}
long long sum=0;
for(int i=1;i<=n;i++) sum+=f[i][k],sum%=inf;
printf("%lld",sum);
}
|
B
解法
设 $f_{i,j}$ 为 $[1,i]$ 中被 $a_{1…j}$ 整除的个数。
那么转移式就为 $f_{i,j}= \lfloor \frac {i}{a_j} \rfloor + f_{i,j-1} - f_{\lfloor \frac {i}{a_j} \rfloor , j-1}$
最后减去是为了去重， 因为他的去重可能出现 $a_k \times ..a_j$ 被重复计算。
而我们确定 $a_j \times … a_k \le i$ 那么移项得到 $a_k\times … \le \lfloor \frac {i}{a_j}\rfloor$
而式子的左边就相当于 $f_{\lfloor \frac {i}{a_j} \rfloor , j-1}$
而直接转移的复杂度和暴力差不多，所以不能直接转移。
我们发现 $\lfloor \frac {i}{a_j}\rfloor$ 其实并不是很大，所以我们可以只考虑 $\sqrt{n}$ 个状态。
用记忆化搜索可以实现。
然后由于数组空间不够，可以加个玄学优化：如果 $i$ 大于某个数，就重新算一遍。
代码
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
| #include <bits/stdc++.h>
using namespace std;
long long n;
int k;
int a[123];
long long dp[223132][123];
long long inf = 200010;
long long dfs(long long x,int y)
{
if(y==0) return 0;
if(x==0) return 0;
if(x<=inf && dp[x][y]) return dp[x][y];
long long ans=0;
ans=x/a[y]+dfs(x,y-1)-dfs(x/a[y],y-1);
if(x<=inf) return dp[x][y]=ans;
else return ans;
}
int main()
{
freopen("calc.in","r",stdin);
freopen("calc.out","w",stdout);
scanf("%lld%d",&n,&k);
for(int i=1;i<=k;i++) scanf("%lld",&a[i]);
cout<<n-dfs(n,k);
}
|
7.17
D
解法
首先，如果问题为一维，我们可以取中位数。
而扩展到二维，我们可以知道，最后取的中点肯定是取某个点的 $x$ 和某个点的 $y$。
那么我们可以“固定”住 $x$，也就是枚举每个点的 $x$ 轴，然后再排序后枚举每个点的 $y$ 轴。
那么就形成了一条线，线的上下侧有许多点：
那么根据目前我们固定的 $x$，枚举的 $y$ 。此时的代价是$\sum\limits_{i=1}^n |x-x_i|+|y-y_i|$。
我们把 $|x-x_i|$ 设为 $d_i$，则等于 $\sum\limits_{i=1}^n d_i+|y-y_i|$
那么现在我们只考虑在 $y$ 左边的，则上面的式子可以转化成 $\sum\limits_{i=1}^n d_i-y_i+y$
由于 $y$ 是个不变量，所以我们可以在维护的时候把 $d_i-y_i$ 扔进堆里，维护 $y$ 的下侧。
而可以观察到，由于答案是中位数，所以我们可以维护前 $\frac{k}{2}$ 小的数，用堆解决。
上侧同理，最后我们枚举y的时候可以记录答案，最后左扫右扫合并答案.
代码
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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
#define int long long
int n,k;
struct node
{
int x,y,id;
bool operator < (const node&cmp) const
{
return y<cmp.y;
}
};
node d[1501];
int la[1501],ra[1501];
signed main()
{
freopen("dating.in","r",stdin);
freopen("dating.out","w",stdout);
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++) scanf("%lld%lld",&d[i].x,&d[i].y),d[i].id=i;
sort(d+1,d+n+1);
int ans=(int)1e18;
for(int i=1;i<=n;i++)
{
int sum=0;
priority_queue<int> q;
for(int j=1;j<=n;j++)
{
q.push(abs(d[i].x-d[j].x)-d[j].y);
sum+=abs(d[i].x-d[j].x)-d[j].y;
if(q.size()>k/2+k%2)
{
sum-=q.top();
q.pop();
}
if(q.size()==k/2+k%2) la[j]=sum;
else la[j]=(int)1e18;
}
while(!q.empty()) q.pop();
sum=0;
ra[n+1]=1e18;
for(int j=n;j>=1;j--)
{
q.push(abs(d[i].x-d[j].x)+d[j].y);
sum+=abs(d[i].x-d[j].x)+d[j].y;
if(q.size()>k/2)
{
sum-=q.top();
q.pop();
}
if(q.size()==k/2) ra[j]=sum;
else ra[j]=(int)1e18;
}
for(int j=1;j<=n;j++){
ans=min(ans,(k/2+k%2)*d[j].y+la[j]+ra[j+1]-(k/2)*d[j].y);
}
}
printf("%lld",ans);
}
|
7.19
A
解法
7.22
A
解法
被这道题的思路震撼到了，听说这道题是NOI20204原题，所有的400多名选手只有周康阳做了出来。
首先由于 $2$ 可以由 $\frac {1}{2}$ 一次翻转得到，所以我们设 $2$ 为初始值。
那么我们可以先画出转移的图片。
而我们可以依靠这个关系图来直接搜索，这样的复杂度十分大。
我们可以猜一个结论，当分数 $\ge 2$ 时 $\frac {p+2q}{q}$ 的前驱一定是 $\frac {p}{q}$。
因为 $+2$ 操作直接成正无穷了，而反转操作只会让原本正无穷数越来越小。
而当分数 $\le \frac {1}{2}$ 时，首先 $+2$ 不可能，不然直接成负数了，而只有翻转操作没用使用过，而翻转操作不可能没用，所以前驱为翻转操作。
那么假设我们从 $2$ 开始画出我们的搜索图：
我们可以按照这个树进行搜索，搜索到的每个点都是答案。
而我们发现，每个链的链头都不一样，所以他们加二，翻转自然都不会重复。
那么这道题就做完了。从来没有接触过这种思维的题，太奇妙了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
using namespace std;
int n,m;
int ans=0;
void dfs(int a,int b,int op)
{
if(a<=n && b<=m) ans++;
if(a>max(n,m) || b>max(n,m)) return;
if(!op)dfs(b,a,1);
dfs(a+2*b,b,0);
}
int main()
{
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
scanf("%d%d",&n,&m);
dfs(2,1,0);
printf("%d",ans);
}
|
7.25
E
解法
这道题我们可以设 $f_{i,j}$ 为选到前 $i$ 个数列删除了 $j$ 个数的最大价值，也就是 $b_i = i$ 的数量。
那么我们有这个数选和不选两个选择。
首先不选，那么 $f_{i,j} = f_{i-1,j-1}$，也就是我们使用了一次删除的操作，然后价值就等于前 $i-1$ 的价值。
其次是选，那么 $f_{i,j} = f{i-1,j} + (i-j == a_i)$，也就是我们相当于在前 $i-1$ 个数的基础上添加了一个数，而由于我们使用了 $j$ 次删除，那么我们就看这前 $i$ 个数删除了 $j$ 个数，也就是一个一个地往前递补后这个数的位置会不会刚好等于 $a_i$。
所以直接转移，这道题就做完了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <bits/stdc++.h>
using namespace std;
int a[5010];
int dp[5010][5010];
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
int mx=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
if(j>=1)dp[i][j]=dp[i-1][j-1];
dp[i][j]=max(dp[i][j],dp[i-1][j]+(i-j==a[i]));
mx=max(mx,dp[i][j]);
}
}
printf("%d",mx);
}
|
F
解法
这道题我们其实不关心数组中的每个数是什么，只关心他们的差。
那么我们就设 $c_i = a_i - b_i$ ，那么在 $a$ 数组上的操作对于 $c$ 就是 $+1$，$b$ 数组上的则是 $-1$。
而如果对 $c_i$ 做一遍前缀和，我们更能发现，这一个操作其实就是相当于给前缀和数组加上了连续的一段 $1$。
而我们可以知道的是，我们需要把整个数组变成 $0$，也就是让 $a=b$。
所以问题就变成了给定一个数组，每次选择一段区间 $+1$，问让数组全为 $0$ 的操作数。
那么答案自然就是最小的那个数去绝对值了。
因为操作只支持加，所以如果数组中出现了大于 $0$ 的数，就说明无解。
而如果加的操作在数组末尾，那么就没有办法把他减回来，所以末尾不能操作，所以如果区间末尾不为 $0$，同样无解。
而判断无解和求方案数就是求最大和最小，直接 $ST$ 表就好了。
注意，我们的前缀和是从 $l$ 开始的，所以每个求得的数应该减去前缀和数 $sum_{l-1}$。
代码
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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
int a[200010],b[200010],d[200010];
int mx[200010][20],mi[200010][20],lg[200010],pr[20];
signed main()
{
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
for(int i=1;i<=n;i++) d[i]=d[i-1]+a[i]-b[i],mx[i][0]=d[i],mi[i][0]=d[i];
pr[0]=1;
lg[0]=-1;
for(int i=1;i<=19;i++)
{
pr[i]=pr[i-1]*2;
for(int j=1;j<=n;j++)
{
if(i+pr[i]-1>n) break;
mx[j][i]=max(mx[j][i-1],mx[j+pr[i-1]][i-1]);
mi[j][i]=min(mi[j][i-1],mi[j+pr[i-1]][i-1]);
}
}
for(int i=1;i<=100000;i++) lg[i]=lg[i>>1]+1;
while(q--)
{
int l,r;
scanf("%lld%lld",&l,&r);
int k=lg[r-l+1];
int mxn=max(mx[l][k],mx[r-pr[k]+1][k])-d[l-1];
int mnn=min(mi[l][k],mi[r-pr[k]+1][k])-d[l-1];
if(d[r]-d[l-1]!=0)
{
puts("-1");
continue;
}
if(mxn>0)
{
puts("-1");
continue;
}
printf("%lld\n",abs(mnn));
}
}
|
G
解法
首先我们可以发现，任意两段区间其实都可以使用一次翻转操作让他们相邻。
那么我们可以先找出有多少个没有相同字母的子串，然后使用高维前缀和更新最大值，最后判断一个集合和他的补集的和是什么就好了。
代码
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
| #include <bits/stdc++.h>
using namespace std;
char s[1000010];
int dp[(1<<20)+5];
int n;
signed main()
{
scanf("%s",s);
n=strlen(s);
for(int i=0;i<n;i++)
{
int mask=0,cnt=0;
for(int j=i;j<n;j++)
{
if(mask&(1<<(s[j]-'a'))) break;
mask|=(1<<(s[j]-'a'));
dp[mask]=max(dp[mask],(j-i+1));
}
}
for(int i=0;i<20;i++)
{
for(int j=0;j<1<<20;j++)
{
if(j&(1<<i)) dp[j]=max(dp[j],dp[j^(1<<i)]);
}
}
int ans=0;
for(int i=0;i<1<<20;i++) ans=max(ans,dp[i]+dp[i^((1<<20)-1)]);
printf("%d",ans);
}
|
