Fork me on GitHub

CodeForces Round #592

我好菜啊

Pens and Pencils

发现直接除一下,算出来分别需要多少铅笔和钢笔,最后看一下加起来是不是大于$k$即可.
注意一个细节,假如我们有$8$个工作需求,然后一支铅笔可以解决$3$个的话,那么我们需要$3$支铅笔.
所以我们不能直接算$a/x$,而是要算$(a+(x-1))/x$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
int a,b,c,d,k;
cin>>a>>b>>c>>d>>k;
int ll=(a+(c-1))/c;
int rr=(b+(d-1))/d;
if(ll+rr>k)
puts("-1");
else
cout<<ll<< " "<<rr<<endl;
}
return 0;
}

Rooms and Staircases

首先考虑一下走楼梯对答案有什么好处.
如果不走楼梯的话,那么答案一定就是$n$.
我们设一个楼梯在房间$i$的位置,那么我们从$1$走到$i$时,如果选择从$i$这个点走下去的话.那么如果我们向右走,显然和直接不走楼梯没区别.
而且根据题目中的限定,我们向初始走的位置的反方向走的时候就一定不能再回来了,所以我们的决策就是在每个楼梯的地方,判断一下是继续走的答案更优秀,还是走回去的答案更优秀,取最大值即可.

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
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while (T--){
cin>>n>>s;
int ans=-1;
for(int i=0;i<n;i++)
if(s[i]=='1')
ans=max(ans,2*(i+1));
int now=1;
for(int i=n-1;i>=0;i--){
if(s[i]=='1')
ans=max(ans,2*(now));
now++;
}
if(ans==-1)
ans=n;
cout<<ans<<endl;
}
return 0;
}

The Football Season

现在不会x.

Paint the Tree

首先考虑判断一下无解的情况,由于每相邻的三个点都不能同色,而我们只能把这些点染成三种颜色.
那么考虑某个节点$i$,如果和$i$直接相邻的点多于$2$个,那么无论如何都会有两个节点同色的.
pic1
发现在上图(样例二)中,因为与节点$3$直接相邻的点为$3$个.所以这个情况是无解的.
所以发现有解的情况只有是链的情况.
而在一条链的情况下,如果我们确定了前两个节点的颜色的话,那么这条链的颜色也是一定可以被确定下来的.
又因为前两个点的颜色只有$3 \times 2=6$种情况,所以我们可以直接暴力统计答案即可.
时间复杂度为$O(6 \times 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
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, tot, rt, len, ansx, ansy;
ll f[N][5][5], ans;
int fr[N][5][5];
int c[5][N];
int head[N], deg[N], sen[N], res[N];
struct Edge {
int u;
int v;
int next;
} e[N << 1];

inline void addedge(int u, int v) {
e[++tot] = (Edge) {u, v, head[u]};
head[u] = tot;
e[++tot] = (Edge) {v, u, head[v]};
head[v] = tot;
return;
}

void dfs1(int u, int fa) {
sen[++len] = u;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == fa) continue;
dfs1(v, u);
}
return;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=0;i<=n;i++)
for(int j=0;j<=4;j++)
for(int k=0;k<=4;k++)
f[i][j][k]=1e16;
for(int i = 1; i <= 3; i++)
for(int j = 1; j <= n; j++)
cin>>c[i][j];
for(int i = 1; i < n; i++) {
int u, v;
cin>>u>>v;
deg[u]++;
deg[v]++;
addedge(u, v);
}
for(int i = 1; i <= n; i++)
if(deg[i] >= 3) {
puts("-1");
return 0;
}
for(int i = 1; i <= n; i++)
if(deg[i] == 1) {
rt = i;
break;
}
dfs1(rt, 0);
for(int i = 1; i <= 3; i++)
for(int j = 1; j <= 3; j++) {
if(i == j) continue;
f[2][i][j] = min(f[2][i][j], (ll)c[i][sen[1]] + c[j][sen[2]]);
}
for(int i = 3; i <= n; i++)
for(int j = 1; j <= 3; j++)
for(int k = 1; k <= 3; k++)
for(int t = 1; t <= 3; t++) {
if(j == k || j == t || k == t) continue;
if(f[i][k][t] > f[i - 1][j][k] + c[t][sen[i]]) {
f[i][k][t] = f[i - 1][j][k] + c[t][sen[i]];
fr[i][k][t] = j;
}
}
ans = f[0][0][0];
for(int i = 1; i <= 3; i++)
for(int j = 1; j <= 3; j++)
if(f[n][i][j] < ans) {
ans = f[n][i][j];
ansx = i; ansy = j;
}
res[sen[n - 1]] = ansx; res[sen[n]] = ansy;
for(int i = n; i >= 3; i--) {
int go = fr[i][ansx][ansy];
ansy = ansx;
ansx = go;
res[sen[i - 2]] = go;
}
cout<<ans<<endl;
for(int i = 1; i <= n; i++)
cout<<res[i]<<" ";
return 0;
}

Minimizing Difference

这不是一眼题吗为什么要放到E上,放到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
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e18 + 7;
const int N = 1e5 + 10;
int n, k,ans;
int a[N], sum[N], cnt[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++ i){
cin >> a[i];
cnt[i] = 1;
}
sort(a + 1, a + n + 1);
ans = a[n] - a[1];
for (int i = 0; i < n; ++ i){
int l = 1 + i;
int r = n - i;
if (l >= r) break;
if (l + 1 != r){
int can = k / (i+1);
if (can == 0) break;
int lim = a[l+1]-a[l] + a[r]-a[r-1];
ans -= min(lim, can);
k -= min(lim, can) * (i+1);
if (lim > can) break;
}
if (l + 1 == r){
int can = k / (i+1);
if (can == 0) break;
int lim = a[r]-a[l];
ans -= min(lim, can);
k -= min(lim, can) * (i+1);
}
}
cout << ans << endl;
return 0;
}

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:CodeForces Round #592

文章作者:KRrrrrrrrr

发布时间:2019年10月15日 - 18:10

最后更新:2019年11月05日 - 08:11

原始链接:http://krrrr.xyz/2019/10/15/Round-592/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。