16级第一次周末赛题解

由于个人水平比较菜,第一次写题解,如果有分析不到位或者错误,敬请谅解!

A.csl的签到题

  • 这的的确确是一个签到题0.0,作为出这题(坑你们)的人,我也没想到签到成功率这么低。
  • 仔细看一下题目的数据$T,n$都可以到$10^5$,如果让你算$99999$个$99999!$,你每个都用for循环去算一遍显然是会超时的。
  • 正确做法就是在$O(n)$时间内预处理出$10^5$内的阶乘,保存在数组内。
    然后全部$O(1)$读即可。
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;

long long a[100001];
const int mod = 1e9 + 7;

int main()
{
a[0] = 1;
for (int i = 1; i < 100000; i++)
a[i] = i * a[i - 1] % mod;
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
cout << a[n] << endl;
}
return 0;
}

B. csl的填数游戏

  • 考虑$a$($a$为$Sum$的一个因数)作为答案,则填数字时最少要填以$a$为公差的等差数列,于是$\frac{n(1+n)}{2}a≤Sum$即可。
  • $O(\sqrt n)$时间可以得到$Sum$所有因数。
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;

int main()
{
ll s, n;
while (cin >> s >> n)
{
ll limit = (1 + n) * n / 2;
ll ans = -1;
for (ll i = 1; i * i <= s; i++)
if (s % i == 0)
{
if (i >= limit)
ans = max(ans, s / i);
if (s / i >= limit)
ans = max(ans, i);
}
cout << ans << endl;
}
return 0;
}

C. csl写OJ

  • 来神的大(fang)模(A)拟(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
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int inf = 0x3f3f3f3f;
const int maxn = 100000;
set<string> prob;
map<string, set<int> > cont;
map<int, vector<string> > contest_list;
map<int, int> isopen;

int main()
{
int n, q;
while(cin >> n >> q)
{
string tmp;
for (int i = 0; i < n; i++)
{
cin >> tmp;
//1 refer pub
prob.insert(tmp);
}
int cmd;
int tot = 0;
for (int i = 0; i < q; i++)
{
cin >> cmd;
if (cmd == 1)
{
cin >> tmp;
if (cont.find(tmp) == cont.end())
{
cout << "DoNotExist" << endl;
}
else
{
int cnt = cont[tmp].size();
for (int x: cont[tmp])
{
if (--cnt)
{
cout << x << " ";
}
else
{
cout << x << endl;
}
}
}
}
else if (cmd == 2)
{
cin >> tmp;
if (prob.find(tmp) == prob.end())
{
cout << "DoNotExist" << endl;
}
else
{
cout << "Response" << endl;
}
}
else if (cmd == 3)
{
isopen[++tot] = 1;
}
else if (cmd == 4)
{
int id;
cin >> id;
if (isopen[id])
{
isopen[id] = 0;
for (string x : contest_list[id])
{
cont[x].erase(id);
if (cont[x].size() == 0)
{
prob.insert(x);
cont.erase(x);
}
}
contest_list.erase(id);
}
else
{
cout << "Invalid" << endl;
}
}
else if (cmd == 5)
{
int id;
cin >> tmp >> id;
if (!isopen[id])
{
cout << "Invalid" << endl;
}
else
{
cont[tmp].insert(id);
contest_list[id].push_back(tmp);
if (prob.find(tmp) != prob.end())
{
prob.erase(tmp);
}
}
}
}
}
}

D. csl和喵神的困惑

  • 裸背包题,只是价值和体积是一个东西啦~注意多重背包的优化(没试过直接暴力会不会TLE),这里给大家参考一下二进制优化多重背包的方法(eg: $9$件物品变成$1,2,4,2$四件物品做01背包)
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
#include <bits/stdc++.h>
using namespace std;

int n, m;
int c[102], v[102];
int b[100000];
int dp[102];

int main()
{
while (cin >> n >> m)
{
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++)
cin >> v[i] >> c[i];
int id = 0;
for (int i = 0; i < n; i++)
{
int k = 1;
while (c[i] > k)
{
b[id++] = k * v[i];
c[i] -= k, k <<= 1;
}
b[id++] = c[i] * v[i];
}
for (int i = 0; i < id; i++)
for (int j = m; j >= b[i]; j--)
dp[j] = max(dp[j], dp[j - b[i]] + b[i]);
cout << dp[m] << endl;
}
return 0;
}

E. csl的简单数学题

  • 看到数学题做的人就少0.0
  • 我们知道$n$个元素的集合的子集为 $2^n$ 个,把数组从小到大排序后,对于每一个$a[i]$其在答案中作为最大值会出现 $2^i$ 次,作为最小值会出现 $2^{n-1-i}$ 次。这样我们就得到了公式:$$\sum F(a)=\sum_{i=0}^{n-1} a[i]·(2^i - 2^{n-i-1} )$$
  • 至于$2^n$随便你预处理一下,或者快速幂去算,都是可以的。
  • 时间复杂度$O(n)$
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 3e5 + 5;
const int mod = 1e9 + 7;
ll a[maxn];
ll fastpow(ll b)
{
ll r = 1, base = 2;
while (b)
{
if (b & 1)
r = r * base % mod;
base = base * base % mod;
b >>= 1;
}
return r;
}

int main()
{
int n;
while (cin >> n)
{
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
ll ans = 0;
for (int i = 0; i < n; i++)
ans = (ans + a[i] * (fastpow(i) - fastpow(n - 1 - i))) % mod;
cout << (ans + mod) % mod << endl;
}
return 0;
}

F. csl的字符诱惑

  • 这是一道正版签到题,没啥好说的orz
  • 恭喜第一个AC这题的同学23333
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int main()
{
char s[3];
int t;
while (cin >> t)
{
int cnt = 0;
while (t--)
{
cin >> s;
if (s[0] == 'X')
cnt++;
else
cnt--;
}
cout << cnt << endl;
}
return 0;
}

G. csl的萌妹数

  • 首先,我们证明$x$是萌妹数的话,$x+1$也是萌妹数。
  • 因为$sum(x+1)≤sum(x)+1$,所以$x+1-sum(x+1)≥x-sum(x)$。如果$x-sum(x)≥m$,则必有$x+1-sum(x+1)≥m$
  • 由上述单调性,可以考虑二分答案(最小萌妹数)。
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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, m;
bool check(ll x)
{
ll tmp = x;
int sumd = 0;
while (x)
{
sumd += x % 10;
x /= 10;
}
return tmp - sumd >= m;
}

int main()
{
while (cin >> n >> m)
{
ll l = 0, r = n + 1;
while (l < r)
{
ll mid = l + (r - l) / 2;
if (check(mid))
r = mid;
else
l = mid + 1;
}
ll ans = n - l + 1;
ans = ans > 0 ? ans : 0;
cout << ans << endl;
}
return 0;
}

H. csl的ACM之路

  • 模拟一下两个过程所需要的时间就好啦~
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;

int main()
{
int n, t, m, c;
while (cin >> n >> t >> m >> c)
{
int no = ceil(1.0 * n / m) * t;
int yes = 0;
int cnt = 0;
while (cnt < n)
{
yes += t;
cnt += m;
if (yes > c)
cnt += m;
}
if (yes < no)
cout << "yes" << endl;
else
cout << "no" << endl;
}
return 0;
}

I. csl不小气

  • 记录数组的前$n$项和$S(n)$,对于每个查询输出$S( r )-S(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
#include <bits/stdc++.h>
using namespace std;

int a[100005];

int main()
{
int n, q;
while (cin >> n >> q)
{
for (int i = 1; i <= n; i++)
{
int num;
cin >> num;
a[i] = a[i - 1] + num;
}
while (q--)
{
int l, r;
cin >> l >> r;
cout << a[r] - a[l - 1] << endl;
}
}
return 0;
}
捐助作者
0%