2019NERC部分题解

​ 一套偏简单的题目。

A.Berstagram

​ 题目大意:按顺序从1到$n$的$n$篇文章,每点赞一篇文章这篇文章就会和前面的那篇文章互换位置,问每篇文章的最靠前的位置和最靠后的位置分别为多少。

​ 开两个数组,第一个数组$a[i]$表示第$i$篇文章当前所在的位置,$b[i]$表示当前的第$i$篇文章是哪一篇。每当一篇文章被点赞一次,这篇文章的位置信息就通过$a[i]$得到了,然后就能够根据$b[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
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
int a[maxn];
int b[maxn];
int ans1[maxn];
int ans2[maxn];
void change(int x){
int pos=a[x];
if(pos==1) return ;
int y=b[pos-1];//前一篇是哪篇文章
a[x]--;
a[y]++;
swap(b[pos],b[pos-1]);//两篇文章位置互换
ans1[y]=max(ans1[y],a[y]);
ans2[x]=min(ans2[x],a[x]);
}
int main()
{
int n,m,x;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
a[i]=b[i]=ans1[i]=ans2[i]=i;
}
for(int i=0;i<m;i++){
scanf("%d",&x);
change(x);
}
for(int i=1;i<=n;i++){
printf("%d %d\n",ans2[i],ans1[i]);
}
return 0;
}
B.The Feast and the Bus

​ 题目大意:$n$个人分为$k$组,每组至少有一个人,现在你可以租一辆容量为$s$的车,这辆车每次只能够运输一组或两组人。总共的花费为$s*r$,其中$r$为运输次数,问最少花费为多少。

​ 从题目中可以看出,运输次数$r\in [\frac{k}{2},k]$,因此我们可以根据运输次数计算出此时的最小花费为多少。对于一个数$r$,我们可以计算出一次运输一组的次数为$r*2-k$,一次运输两组的次数为$k-r$。

​ 运输一组时,我们要挑选人数最多的小组进行运输,剩下的再按大小分别挑选当前人数最多的和人数最少的两组一起运输,这样就能够求出来此时需要的最小花费。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=100000+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll num[maxn];
int main()
{
ll n,k,x;
scanf("%lld %lld",&n,&k);
for(int i=1;i<=n;i++){
scanf("%lld",&x);
num[x]++;
}
sort(num+1,num+k+1);
ll ans=INF;
for(ll i=(k+1)/2;i<=k;i++){
ll cur=0;
ll q=k-i;
for(ll j=1;j<=q;j++){
cur=max(cur,num[j]+num[q*2+1-j]);
}
//剩下的有一次运输一组的
if(q*2!=k) cur=max(cur,num[k]);
ans=min(ans,cur*i);
}
printf("%lld\n",ans);
return 0;
}
C.Trip to Saint Petersburg
D.Conference Problem
E.The Coronation
F.Data Center

题目大意:用最短的栏杆围成一个面积为$n$的矩阵,并且每条边的长度均为整数,问最少需要多长的栏杆。

签到题。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int l=1;
for(int i=2;i*i<=n;i++){
if(n%i==0) l=i;
}
printf("%d\n",l*2+n/l*2);
return 0;
}
G.Discarding Game
H.Happy Birthday

题目大意:找出用给定数量的1到9不能拼成的最小的整数。

solved by Dicer.

首先找到数量最少的那个数,如果有多个选取最小的

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>

using namespace std;

int a[233];
int main() {
int T;
cin >> T;
while(T--){
int pos = 0;
for(int i = 0; i <= 9; ++i) {
cin >> a[i];
if(a[pos] > a[i]) pos = i;
}
int p = 1;
for(int i = 1; i <= 9; ++i) if(a[p] > a[i]) p = i;
if(pos == 0 && a[p] != a[pos]) {
int pos2 = -1;
for(int i = 1; i <= 9; ++i) {
if(a[i] != 0){
pos2 = i;
break;
}
}
if(pos2 == -1) cout << 1 << endl;
else {
cout << pos2;
for(int i = 1; i <= a[0] + 1; ++i) cout << 0;
cout << endl;
}
} else if(a[p] == a[pos]){
for(int i = 1; i <= a[p] + 1; ++i) cout << p;
cout << endl;
} else {
for(int i = 1; i <= a[pos] + 1; ++i) cout << pos;
cout << endl;
}
}
return 0;
}
I.Show Must Go On
J.The Parade

题目大意:将$n$种高度的士兵分散到$k$行中,使得每行人数相等,且任意两个人的身高差不超过1。问最多能安排多少人分散在$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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000000+10;
ll n,k;
ll c[maxn],cc[maxn];
bool check(ll x){
ll num=0;
for(ll i=1;i<=n;i++) cc[i]=c[i];
cc[n+1]=0;
for(ll i=1;i<=n;i++){
num+=cc[i]/x;//此行全为同一种身高
cc[i]%=x;
if(cc[i]+cc[i+1]>=x){可以和其他身高一起在同一行
cc[i+1]-=x-cc[i];
cc[i]=0;
num++;
}
}
return num>=k;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%lld %lld",&n,&k);
for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
ll l=1,r=2000000000000ll;
while(l<=r){
ll m=(l+r)/2;
if(check(m)) l=m+1;
else r=m-1;
}
printf("%lld\n",(l-1)*k);
}
return 0;
}
K.Projectors
L.Divede The Students

题目大意:有三种程序员:汇编程序员,Basic程序员,c++程序员,其中汇编程序员和c++程序员之间有矛盾,不能分在一组。现在你要将其分成三组,使得人数最多的那一组人数尽可能的少。问最少为多少。

有三种分配方法:①:汇编所在的有1组,c++所在的有1组。②:汇编所在的有1组,c++所在的有2组。③:汇编所在的有2组,c++所在的有1组。对每种情况求一个最小值即可。

都只在一组的直接确定汇编和c++的分配情况;若有一种在两组中,将其平均分配到两组,确定汇编和c++的分配情况。接下来分配剩余的Basic即可。

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
//以下为Dicer代码,思路为二分。
#include<bits/stdc++.h>

using namespace std;

int a, b, c;
int ta, tb, tc;
int m(){
return max(ta, max(tb, tc));
}
bool ok(int x) {
ta = a; tb = b; tc = c;
if(m() <= x) return 1;
if(ta > x) return 0;
if(tc <= x) {
int tmp = tb - x;
tb = x;
tmp -= x - ta;
ta = x;
if(tmp <= 0) return 1;
tmp -= x - tc;
tc = x;
if(tmp <= 0) return 1;
return 0;
} else {
int b1 = tb;
int b2 = tc - x;
tc = x;
tb = b1 + b2;
if(m() <= x) return 1;
if(b2 > x) return 0;
ta += b1 + b2 - x;
if(ta > x) return 0;
else return 1;
}
}
int main() {
int T;
cin >> T;
while(T--){
cin >> a >> b >> c;
if(a > c) swap(a, c);
int l = 1, r = 1000, mid;
while(l <= r) {
mid = l + r >> 1;
if(ok(mid)) r = mid - 1;
else l = mid + 1;
}
cout << l << endl;
}
return 0;
}
M.SmartGardan
N.Wires

题目大意:给出$n$条连线,每个连线连接两个节点。现在可以移动这些线段。将其中一端移到其他节点,另一个节点保持不变,问最少操作多少次能够使得所有的线段互相连通,并输出操作方案。

并查集。操作的次数为连通块个数 - 1 ,首先定义一个主连通块,对于剩下的每个连通块,如果有度数为1的节点(即只有一条边与之相连),那么就将这个节点连接到主连通块上任意一个节点;对于没有节点度数为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
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
#include<bits/stdc++.h>

using namespace std;
const int N = 2e5+100;
//ind:度数 edgeid:第几条边 par:并查集父亲节点 vis:连通块标记 res: 保存无用的边
unordered_map<int,int> ind,edgeid,par,vis,res;
int x[N],y[N];
//储存答案
vector<int> Point;
//所有出现过的点
set<int> all;
void init(){
res.clear();
par.clear();
ind.clear();
edgeid.clear();
vis.clear();
Point.clear();
all.clear();
}
int find(int x){
return x==par[x]?x:par[x]=find(par[x]);
}
void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y) return ;
par[x]=y;
}
bool same(int x,int y){
return find(x)==find(y);
}
int main(){
int T,n;scanf("%d",&T);
while(T--){
scanf("%d",&n);
init();
for(int i=1;i<=n;i++){
scanf("%d %d",&x[i],&y[i]);
par[x[i]]=x[i];//初始化并查集
par[y[i]]=y[i];
ind[x[i]]++;//记录度数
ind[y[i]]++;
edgeid[x[i]]=i;//记录属于哪条边
edgeid[y[i]]=i;
all.insert(x[i]);
all.insert(y[i]);
}
for(int i=1;i<=n;i++){
if(!same(x[i],y[i])) unite(x[i],y[i]);
else{//已经联通,这些边是无用的
res[x[i]]=res[y[i]]=1;
edgeid[x[i]]=i;
edgeid[y[i]]=i;
}
}
for(int v:all){//先找到度数为1的节点,这些点作为所在连通块的移动线段
if(ind[v]==1&&!vis[find(v)]){
Point.push_back(v);
vis[find(v)]=1;
}
}
for(int v:all){//再找那些无用的边,作为移动线段
if((res[v])&&!vis[find(v)]){
Point.push_back(v);
vis[find(v)]=1;
}
}
int siz=(int)Point.size();
printf("%d\n",siz-1);
for(int i=0;i<siz-1;i++){
printf("%d %d %d\n",edgeid[Point[i]],Point[i],Point[siz-1]);
}
}
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------