跃迁引擎启动

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