0%

[MSSCTF2019-Final] PPC 题解

群里面说能评测了所以写了个简单的题解。

奇数

题目大意

给定长度为 $n$ 的序列 $s$,保证 $s_i$ 为数字。

求出 $s$ 中奇数子序列的个数,结果对 $998244353$ 取模。

$1 \le n \le 10^5$。

思路

签到题,估计人人过了。

考虑以 $i$ 结尾的子序列个数,显然为 $2^{i - 1}$ 个。

分类讨论更新答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

typedef long long LL;

const LL mod = 998244353;

std::string s;
LL f[100010];
LL ans, n;

int main()
{
std::cin >> n >> s;
f[0] = 1;
for (int i = 1; s[i]; ++i) f[i] = f[i - 1] * 2, f[i] %= mod;
for (int i = 0; s[i]; ++i) ans += s[i] % 2 == 1 ? f[i] : 0, ans %= mod;
printf("%lld\n", ans % mod);
return 0;
}

移动石子

题目大意

给定长度为 $n$ 的序列 $a$,每次操作可以选择 $i, j$ 并使 $a_i$ 减一,$a_j$ 加一,或者选择 $i$ 使 $a_i$ 减一。计算出使所有 $a_i$ 相同需要的最少操作次数。

$1 \le n \le 10^7, 1 \le a_i \le 10^9$。

思路

考虑贪心,将大的数多余的部分加到小的数的上。

如果最后还有剩余就删掉。

显然最优时最后序列中的数为原序列的平均数。

所以先对序列排序,然后从大往小一个个删,这样保证了不会不够用并且一定最优。计算时会自动加上那些单独删掉的数。

注意开 long long。

代码

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 <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

template <class T>
inline void read(T &x)
{
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return;
}

typedef long long LL;

LL a[10000010];
LL n, sum, ans;

int main()
{
read(n);
for (int i = 1; i <= n; ++i) read(a[i]), sum += a[i]; sum /= n;
std::sort(a + 1, a + n + 1);
for (int i = n; i >= 1; --i) ans += a[i] > sum ? a[i] - sum : 0;
printf("%lld\n", ans);
return 0;
}

星门

题目大意

给出一个 $n$ 个点和 $m$ 条边的无向图,所有边权为 $1$,给定起点和终点 $s, t$,你可以任选两个点连接一条边权为 $1$ 的边,统计有多少种方法使得新的最短路小于原最短路。题目保证给出的图无自环。

$2 \le n \le 2000, 2 \le m \le 5 \cdot 10^5$。

思路

我记得全场只有两个人切掉?

图论入门题。

分别以 $s$ 和 $t$ 为起点求出最短路,然后枚举点,更新答案。

代码

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>

template <class T>
inline void read(T &x)
{
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return;
}

struct Node
{
int pos, dis;
friend bool operator < (const Node &a, const Node &b)
{
return a.dis > b.dis;
}
} ;

std::vector<int> edge[2010];
int dis1[2010], dis2[2010];
int n, m, s, t, max, ans;
bool vis[2010];

void dijkstra(int s, int *dis)
{
dis[s] = 0;
std::priority_queue<Node> que;
que.push((Node){s, 0});
while (!que.empty())
{
Node top = que.top();
que.pop();
if (vis[top.pos]) continue;
vis[top.pos] = true;
for (auto i : edge[top.pos])
{
if (dis[i] > dis[top.pos] + 1)
{
dis[i] = dis[top.pos] + 1;
if (!vis[i]) que.push((Node){i, dis[i]});
}
}
}
}

int main()
{
read(n), read(m), read(s), read(t);
memset(dis1, 0x3f3f3f3f, sizeof(dis1));
memset(dis2, 0x3f3f3f3f, sizeof(dis2));
for (int i = 1, u, v; i <= m; ++i)
{
read(u), read(v);
edge[u].push_back(v), edge[v].push_back(u);
}
dijkstra(s, dis1);
memset(vis, false, sizeof(vis));
dijkstra(t, dis2);
max = dis1[t];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (dis1[i] + dis2[j] + 1 < max) ++ans;
printf("%d\n", ans);
return 0;
}

魔法使帕秋莉

题目大意

给出物品数 $n$ 和背包容量 $m$,求出选择某些物品使得 $\prod a_i \le m$ 的方案数。答案对 $10^9 + 7$ 取模。

$1 \le n \le 3000, 1 \le m \le 10^8, 1 \le a_i \le m$。

思路

全场没人切掉的神仙题。

考虑 dp。

利用 01 背包,状态转移方程:$f(i, j) = f(i - 1, j) + f(i - 1, \frac{j}{a_i})(j \bmod a_i = 0)$。

这样复杂度是 $O(nm)$ 的,会超时。

发现乘积的增长速度过快,我们可以压缩一下状态。

显然,$\frac{n}{x}$ 不同的结果最多有 $\sqrt{n} + 1$ 个,且 ${\frac{\frac{a}{b}}{c}} = \frac{a}{bc}$。以上运算均取整,实在太难打不打了。

所以可以将复杂度优化到 $O(n\sqrt{m})$。

就可以通过啦。

还涉及到取模问题……感觉是道比较神仙的题。

代码

放一下官方的 std。

其实是我懒得写了

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
/*
*         ┏┓    ┏┓
*         ┏┛┗━━━━━━━┛┗━━━┓
*         ┃       ┃  
*         ┃   ━    ┃
*         ┃ >   < ┃
*         ┃       ┃
*         ┃... ⌒ ...  ┃
*         ┃ ┃
*         ┗━┓ ┏━┛
*          ┃ ┃ Code is far away from bug with the animal protecting          
*          ┃ ┃ 神兽保佑,代码无bug
*          ┃ ┃           
*          ┃ ┃       
*          ┃ ┃
*          ┃ ┃           
*          ┃ ┗━━━┓
*          ┃ ┣┓
*          ┃ ┏┛
*          ┗┓┓┏━━━━━━━━┳┓┏┛
*           ┃┫┫ ┃┫┫
*           ┗┻┛ ┗┻┛
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<cstdlib>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define mid (x+y>>1)
#define sqr(x) ((x)*(x))
#define NM 100005
#define nm 400005
using namespace std;
const double pi=acos(-1);
const ll inf=1e9+7;
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}


inline void reduce(ll&x){x+=x>>63&inf;}

int n,m,_t,a[NM],w[NM];
ll d[NM],ans;

int id(int x){return x<=m/2?m-x:_t/x;}

void init(){
m=sqrt(_t);
inc(i,1,m)w[i]=_t/i;
while(w[m])w[m+1]=w[m]-1,m++;
}

int main(){
assert(scanf("%d%d",&n,&_t)==2);
inc(i,1,n)assert(scanf("%d",a+i)==1);
init();
d[1]=1;
inc(i,1,n){
dec(j,m,1)reduce(d[id(w[j]/a[i])]+=d[j]-inf);
}
ans=-1;
inc(i,1,m-1)reduce(ans+=d[i]-inf);
printf("%lld\n",ans);
return 0;
}

引用

https://mssctf.xidian.edu.cn/