2020-9-16 ACM Contest

字数统计: 3.2k字   |   阅读时长: 15分
训练题解
solved A B C D E F G H I J K L M
6 / 13 Ø Ø Ø O · · · Ø · · Ø ! ·
  • O：比赛时通过
  • Ø：赛后通过
  • !：比赛时尝试了未通过
  • ·：比赛时未尝试

  
总结：

  • 知识储备不够。暑假集训了一个月，自己又学习了一个月的图论。但是几乎没用上学过的内容。所掌握的算法与比赛内容不匹配。应多做一些CF的比赛熟悉题型，补上知识空缺.
  • 思考问题不够全面，有时候打完代码才发现有bug，浪费了很多时间，导致别的题目思考时间不够，开题也开得少。dp一点不会，直接爆炸。

比赛链接

A. A simple problem

solved by Sstee1XD

题意： 给你nn和mm，问你以0−n0 - n的全排列组成的新数字中，不含前导零且能被mm整除的数字有多少个。

题解： 想不到什么好的办法，再看数字范围比较小，就可以用状压dpdp来写，dp[S][i]dp[S][i]表示已经用了的数字状态为SS，若当前位为11则已用，为00没用。ii表示剩下的余数，参考大整数取余的方法，同时注意当数字>=10>=10的情况。最后算一下发现最大的数量会爆intint，所以开longlonglong long。

AC代码 
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<cstdio> 
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<ctime> 
 
using namespace std;
 
#define outtime() cerr<<"User Time = "<<(double)clock()/CLOCKS_PER_SEC<<endl
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define bug printf("bug**")
#define coutlf(x) cout << fixed << setprecision(x)
#define uncoutlf  cout.unsetf(ios::fixed)
#define S_IT set<Node>::iterator
#define endl "\n"
#define fi first
#define se second
#define mp(a,b) make_pair(a,b)
 
int gcd(int a,int b) { return b?gcd(b,a%b):a;}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pII;
const double eps = 1e-7;
 
template<class T> inline void read(T &x){
    int f=0;x=0;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    if(f)x=-x;
}
 
int n, m;
ll dp[1 << 16][107];
 
void solve() {
    ++n;//自加后-1即可得到二进制下所有位都为1的情况
    int L = 1 << n;
    dp[0][0] = 1;
    for (int S = 0; S < L; ++S) {
        for (int i = 0; i < n; ++i) {//枚举数字
            if (S & 1 << i) continue;//这位已经用过了，就跳到下一个数字
            if (S == 0 && i == 0) continue;//所有数字都还没用时不能用0，即避免出现前导零的情况
            int nxt = S | 1 << i;//用了第i个后的状态为nxt，由S向nxt转移
            for (int j = 0; j < m; ++j) {
                if (i >= 10) dp[nxt][(j * 100 + i) % m] += dp[S][j];
                else dp[nxt][(j * 10 + i) % m] += dp[S][j];
            }
        }
    }
    printf("%lld\n", dp[L - 1][0]);
}
 
int main() {
    read(n), read(m);
    solve();
    return 0;
}

B. Hsueh- play balls

solved by lllllan

题意： 有n个白球和m个黑球在盒子里，每次从中取出一个球到盒子外，问取球过程中将所有球取出的过程中盒子外的球中，白球个数和黑球个数至少有一次相等的概率是多少？要求逆元 （刚学）

题解： 可以转化为图形的思想，问题变成在一个n*m的矩阵中，有n*m个单位方格。从左下角的顶点走到右上角的顶点的路线总数，就是原本问题的取球方案个数。
   令矩阵的长为n，宽为m。将矩阵放在一个二维坐标轴上，左下角的顶点对应坐标轴原点，长边在X轴上，宽边在Y轴上。题目中合法的方案为所有能经过y = x上的点的路线。
   从原点走到右上角顶点的路线总数为$$\begin{pmatrix}n\n+m\end{pmatrix} $$
   从（0，0）先走到（0，1）时，因为长宽的原因，所以此后的所有路线都会经过y = x 这条线，此时的合法方案数为$$\begin{pmatrix}n\n+m-1\end{pmatrix} $$
   从（0，0）先走到（1，0）时，可通过（0，1）的镜像得到，经过y = x的路线数量也是$$\begin{pmatrix}n\n+m-1\end{pmatrix} $$
   则合法的概率为$$2\begin{pmatrix}n\n+m-1\end{pmatrix} /\begin{pmatrix}n\n+m\end{pmatrix} $$

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 2e6 + 10;

int n, m, fac[N], inv[N];

inline int nextInt(){ int x; cin >> x; return x; }
ll qpow(ll a, ll b){
	if (b < 0) return 0;
	ll ans = 1;
	while(b){
		if(b & 1)
			ans = ans * a % mod;
		a  = a * a % mod;
		b >>= 1;
	}
	return ans;
}

ll C(ll n, ll m){
	if(n < m)	return 0;
	return 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
}

void run(){
	cin >> n >> m;
	if(n == m){	printf("1\n");	return;}
	if(n < m)	swap(n, m);
	ll tot = C(n + m, n);
	ll cur = 2 * C(n + m - 1, n) % mod;
	ll ans = cur * qpow(tot, mod - 2) % mod;
	printf("%d\n", ans);
}

int main(){
	ios :: sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	fac[1] = 1;
	for(int i = 2; i < N; i++)	fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[N - 1] = qpow(fac[N - 1], mod - 2);
	for(int i = N - 1; i >= 1; i--)	inv[i - 1] = 1ll * inv[i] * i % mod;
	
	int _T = nextInt();
	while(_T--)	run();
	
	return 0;
}

C. Hoogle Machine Translation

solved by Sstee1XD

题意： 给你nn个单词，你每次可以向机器询问一个或多个单词的翻译，当存在多个单词时给你的翻译会乱序，最多只能询问25次，最后输出正确顺序的翻译。

题解： nn最多能到10510^5，但是最多只能询问25次，数量差距很大，所以想到了询问lognlog_n次，由此想到了二进制。枚举位数，再找1−n1 - n在当前位数下为1的数字，每次询问这些位置下的单词，然后读入翻译出来的答案，用map来把这些单词出现过的位置加起来，最后就找到了每个翻译对应的正确位置。

AC代码 
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 <bits/stdc++.h>

using namespace std;

#define endl "\n"

int n;
const int maxn = 1e5 + 7;
string s[maxn], ans[maxn];
map<string, int> mp;
vector<string> v;

void query() {
	cout << "? " << v.size();
	for (auto ss : v) {
		cout << " " << ss;
	}
	cout << endl << endl;
	cout.flush();
}

void find(int q) {
	string a;
	for (int i = 0; i < v.size(); ++i) {
		cin >> a;
		mp[a] |= 1 << q;
	}
}

void out() {
	for (auto t : mp) {
		ans[t.second] = t.first;
	}
	cout << "!";
	for (int i = 1; i <= n; ++i) {
		cout << " " << ans[i];
	}
	cout << endl << endl;
	cout.flush();
}

void solve() {
	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
	}
	for (int i = 0; i < 20; ++i) {
		if (1 << i > n) {
			break;
		}
		for (int j = 1; j <= n; ++j) {
			if (1 << i & j) {//在1-n中找第i位为1的数字
				v.push_back(s[j]);
			}
		}
		query();//询问
		find(i);//维护翻译出现的位置
		v.clear();//初始化需要翻译的单词
	}
	out();//输出答案
}

int main() {
	ios :: sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin >> n;
	solve();
	return 0;
}

D. Dup4 and pebble pile

solved by lllllan

题意： 有一些鹅卵石，编号为a到b，刚开始每个鹅卵石各自属于一堆。接下来，每次可以选择两个属于不同堆的鹅卵石x和y，如果x和y有公共质因数t并且t≥p，那么合并x和y所在的两堆鹅卵石。问直到不能再合并为止，最终有多少堆鹅卵石。

题解： 直接枚举大于等于p的质因数，然后枚举质因数的倍数，这些质因数的倍数之间相邻两个之间连边即可。最终答案是联通块个数。

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int a, b, p;
int s[N], f[N];
int find(int x){	return s[x] == x ? x : s[x] = find(s[x]);}
void merge(int a, int b){
	int sa = find(a), sb = find(b);
	if(sa != sb)		
		s[sa] = sb;
}
int main(){
	scanf("%d%d%d", &a, &b, &p);
	for(int i = 1; i < N; i++)	s[i] = i, f[i] = 0;
	for(int i = 2; i <= b; i++){
		if(f[i])	continue;
		int pre = i;
		for(int j = i; j <= b; j += i){
			f[j] = 1;
			if(i >= p && pre >= a)	
				merge(pre, j);
			pre = j;
		}
	}
	int ans = 0;
	for(int i = a; i <= b; i++){
		if(find(i) == i)	ans++;
	}
	printf("%d\n", ans);
	return 0;
}

H. Hsueh- and keyboard

solved by Sstee1XD

题意： 文本框里刚开始有一个长度为xx的字符串，现在要求得到一个长度为nn的字符串。0<=x,n<=1060<=x, n<=10^6。
你可以通过以下操作达成目标：

  • 按下键盘一次，输入一个字符。
  • 按下键盘两次(Ctrl + A), 选中文本框中的所有字符。
  • 按下键盘两次(Ctrl + C), 复制选中的字符到剪贴板。
  • 按下键盘两次(Ctrl + V), 将剪贴板中的字符粘贴到文本框。
  • 按下键盘一次(Backspace), 删除文本框中的最后一个字符或者删除选中的字符，如果在这之前你按下了(Ctrl + A)选中了一些字符的话。
    此处的操作和传统认知有所不同的是，如果你先按下了(Ctrl + A)选中了所有字符，再输入一个字符，或者粘贴剪贴板中的文字到文本框，那么它不会产生替换选中文字的效果，而是会直接当前字符串追加在后面。
    或者你可以认为(Ctrl + A)只会对复制操作有效。

题解： 我们要由xx到nn，并且要操作数最少，由此想到了最短路。
每次有4种情况建边：

  • ii向(i+1)(i+1)建边
  • ii向00建边
  • ii向(i−1)(i-1)建边
  • ii一直向ii的倍数建边
    注意到字符串的长度可能会超出我们想要的nn，所以边界要比nn大一些。刚开始直接取了2n2n，发现如果xx超过2n2n时会出bug。取大后发现会MLE，这时发现边界只要取稍微大一点就好了，字符串会超出很多的情况时，是在我们接近n时取了两倍，而此时只要一个个输入就可以取到一个很小的值。这样了之后又TLE了，此时要么用一个visvis数组来减小时间复杂度，要么当你在nn点进行松弛操作时直接breakbreak。
AC代码 
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 <bits/stdc++.h>
 
using namespace std;
 
#define endl "\n"
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 7;
int dis[maxn << 1], head[maxn << 1];
int x, n, cnt;
 
struct Edge{
	int nxt, to, w;
	Edge () {}
	Edge (int nxt, int to, int w) : nxt(nxt), to(to), w(w) {}
}edge[maxn * 20];
 
void addedge(int u, int v, int w) {
	edge[cnt] = Edge(head[u], v, w);
	head[u] = cnt++;
}
 
struct qnode{
	int len, w;
	qnode () {}
	qnode (int len, int w) : len(len), w(w) {}
	bool operator <(const qnode &a) const{
		return w > a.w;
	}
};
 
int Dijkstra(int S) {
	memset(dis, 0x3f, sizeof(dis));
	dis[S] = 0;
	priority_queue<qnode> Q;
	Q.push(qnode(S, 0));
	while (!Q.empty()) {
		qnode tt = Q.top();
		Q.pop();
		int u = tt.len;
		if (u == n) break;
		for (int i = head[u]; ~i; i = edge[i].nxt) {
			int w = edge[i].w, v = edge[i].to;
			if (dis[v] > w + dis[u]) {
				dis[v] = w + dis[u];
				Q.push(qnode(v, dis[v]));
			}
		}
	}
	return dis[n];
}
 
void getmap(int T) {
	memset(head, -1, sizeof(head));
	for (int i = 0; i < T + 100; ++i) {
		addedge(i, i + 1, 1);
		addedge(i + 1, i, 1);
		addedge(i + 1, 0, 3);
		for (int j = 2; j * i <= T + 100 && i; ++j) {
			addedge(i, j * i, 2 + 2 * j);
		}
	}
}
 
void solve() {
	getmap(max(n, x));
	cout << Dijkstra(x) << endl;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin >> x >> n;
	solve();
	return 0;
}

K. LTS buy wine

solved by lllllan

题意： 给出n瓶红酒, 从左至右依次排列，标号为1到n, 第i瓶红酒的初始价值为vi，第t天可以从最左边或者最右边取一瓶红酒，假设取到标号为j的红酒，得到的价值为 t·vi。问取完所有红酒后，得到的最大总价值是多少？

题解： 定义dp[i][j]表示取光区间[i,j]范围内红酒所能获得的最大价值。每次可以向dp[i-1][j]或dp[i][j+1]转移。

AC代码 
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;
typedef long long ll;
const int N = 2020;

int n;
ll a[N], dp[N][N];
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%lld", a + i);
		dp[i][i] = a[i] * n;
	}
	for(int len = 1; len < n; len ++)
		for(int i = 1; i <= n - len; i++){
			int j = i + len;
			ll x = dp[i + 1][j] + a[i] * (n - (j - i));
			ll y = dp[i][j - 1] + a[j] * (n - (j - i));
			dp[i][j] = max(x, y);
		}
	printf("%lld\n", dp[1][n]);
	return 0;
}
文章目录
  1. A. A simple problem
  2. B. Hsueh- play balls
  3. C. Hoogle Machine Translation
  4. D. Dup4 and pebble pile
  5. H. Hsueh- and keyboard
  6. K. LTS buy wine
|