2019 北京理工大学程序设计竞赛

rank solved A B C D E F G H I J K L
10 8 O . O . O O . O . O O O

A 两只脑斧

Solved by Rainstar.

C 赛尔逵传说

Solved by Rainstar(+2).

每个人的受伤次数是上取整的怪物血量除攻击力,得到不使用强化的血量消耗。

贪心,对怪物按照攻击力排序,依次尽量不受伤。

E 只有一端开口的瓶子

Solved by XLor.

栈混洗。

如果可以栈混洗,那么只需要 $1$ 个栈即可,否则需要 $2$ 个。

构造方法,感觉可以两个栈轮流操作即可。

F 风王之瞳

Solved by Rainstar and wb.

考虑每一个沿着 $x$ 轴和 $y$ 轴方向的正方形,他算上内部斜着的正方形,一共有边长个。

H 目标是成为数论大师

Solved by Rainstar and XLor(+1).

J 金色传说

Solved by Rainstar, wb and XLor.

记 $g(n)$ 表示 $n$ 位数,全部都是数字的和,$g(n)={ 10^n(10^n-1) \over 2 }$。

考虑 $dp[i]$ 表示长度 $i$ 的式子的值的和。

发现枚举符号的位置,后一部分正负抵消了,实际上只有长度为 $0$ 到 $i-2$ 的有贡献,第 $j$ 位贡献实际上是 $dp[j] \cdot 10^{i-j-1}$。

转移时,维护乘上 $10$,维护前缀和即可。

K 多项式求导

Solved by wb.

L 旅行的意义

Solved by XLor(+2).

记 $dp[u]$ 表示以 $u$ 为根的旅行时间期望。

记 $u$ 有 $k$ 个儿子 $v_i$,转移就是 $1+{1 \over k+1}+\sum_{i=1}^k {1 \over k} dp[v_i]$。

DAG 上 DP。

代码

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
map<string,char> mp;
int main(){
int n; cin>>n;
string s[105];
char ans[105];
for(int i=1;i<=n;i++){
cin>>s[i];
int k=s[i][0]-'0';
if(k==1||k==3||k==5)ans[i]='E';
else if(k)ans[i]='I';
else ans[i]='X';
}
for(int i=1;i<=n;i++)cout<<ans[i];
}

C

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
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
ll n,k,c,m[100005],x[100005],d[100005];
bool cmp(ll i,ll j){
return x[i]>x[j];
}
int main(){
cin>>n>>k>>c;
ll sum=0;
for(ll i=1;i<=n;i++){
cin>>m[i]>>x[i],d[i]=i;
ll t=m[i]/k;
if(m[i]%k)t++;
t--;
sum+=t*x[i];
}
sort(d+1,d+n+1,cmp);
int i=1;
while(c>0&&i<=n){
ll t=m[d[i]]/k;
if(m[d[i]]%k)t++;
t--;
sum-=x[d[i]]*min(t,c);
c-=t;
i++;
}
cout<<sum;
}

F

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
ll ans=0;
for(int i=1;i<=min(n,m);i++)
{
ll res=1ll*(n-i+1)*(m-i+1)*i;
ans+=res;
}
printf("%lld\n",ans);
}
return 0;
}

H

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>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <cassert>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 100000 + 5;

int a, b;

int main() {
int T; scanf("%d", &T);
while (T--) {
scanf("%d%d", &a, &b);
int d = (int)sqrt(4 * a * b + a * a);
vector<int> v, ans;
v.push_back((2 * b + a - d) / 2);
v.push_back((2 * b + a + d) / 2);
if (v[0] == v[1]) v.pop_back();
for (int& x: v) {
if (x >= b && a * x >= 0) ans.push_back(x);
}
if ((int)ans.size() == 1) {
puts("1");
printf("%d\n", ans[0]);
} else if ((int)ans.size() == 2) {
puts("2");
printf("%d %d\n", ans[0], ans[1]);
} else {
assert(0);
}
}
return 0;
}

J

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>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 500000 + 5;

ll qpow(ll x, ll n) {
ll r = 1;
while (n > 0) {
if (n & 1) r = r * x % mod;
n >>= 1; x = x * x % mod;
}
return r;
}
void add(ll& x, ll y) {
x += y; if (x >= mod) x -= mod;
}

int n;
ll g[maxn], f[maxn], pre[maxn];

int main() {
g[1] = 45;
for (int i = 2; i < maxn; i++) {
ll x = qpow(10, i);
g[i] = x * (x - 1) / 2; g[i] %= mod;
}
f[1] = g[1]; f[2] = g[2];
pre[1] = f[1]; pre[2] = 10 * f[1] + f[2];
for (int i = 3; i < maxn; i++) {
f[i] = g[i];
add(f[i], 20ll * pre[i - 2] % mod);
pre[i] = f[i];
add(pre[i], 10ll * pre[i - 1] % mod);
}
// for (int i = 1; i <= 5; i++) cout << g[i] << endl;
int T; scanf("%d", &T);
while (T--) {
scanf("%d", &n);
printf("%I64d\n", f[n]);
}
return 0;
}

K

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=105;
const int mod=998244353;
int n,k;
int a[max_n];
int b[max_n];
int main()
{
scanf("%d%d",&n,&k);
for(int i=n;i>=0;i--)scanf("%d",a+i);
while(k)
{
for(int i=0;i<=n;i++)b[i]=0;
for(int i=1;i<=n;i++)
{
b[i-1]=1ll*i*a[i]%mod;
}
for(int i=0;i<=n;i++)a[i]=b[i];
k--;
}
for(int i=n;i>=0;i--)printf("%d%c",a[i],i==0?'\n':' ');
return 0;
}

L

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#ifdef XLor
#define dbg(args...) do {cout << #args << " -> "; err(args);} while (0)
#else
#define dbg(...)
#endif
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 100000 + 5;

ll inv[maxn];
ll qpow(ll x, ll n) {
ll r = 1;
while (n > 0) {
if (n & 1) r = r * x % mod;
n >>= 1; x = x * x % mod;
}
return r;
}

int n, m;
vector<int> edge[maxn];

ll dp[maxn];
ll dfs(int u) {
if (dp[u]) return dp[u];
ll ans = 1 + inv[(int)edge[u].size() + 1];
for (int& v: edge[u]) {
ans += inv[(int)edge[u].size()] * (dfs(v) + 1) % mod;
ans %= mod;
}
// dbg(u, ans);
return dp[u] = ans;
}

int main() {
for (int i = 1; i < maxn; i++) inv[i] = qpow(i, mod - 2);
int T; scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
edge[i].clear(); dp[i] = 0;
}
for (int i = 1, u, v; i <= m; i++) {
scanf("%d%d", &u, &v);
edge[u].push_back(v);
}
printf("%lld\n", dfs(1));
}
return 0;
}