AIM Tech Round 4 (Div. 2)

A Diversity

题意:最少改多少个字母能使得这个字符串至少有$k$个不同字母

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;
string buf;
int kd;
set<char> dict;
int main()
{
cin>>buf;
cin>>kd;
int len=buf.length();
for(int i=0;i<len;i++){
dict.insert(buf[i]);
}
if((int)dict.size()>=kd) printf("0\n");
else{
if(kd>len) printf("impossible\n");
else printf("%d\n",kd-(int)dict.size());
}
return 0;
}

B Rectangles

题意:给你一个表格,每个格子有个颜色,可能是白的或者黑的,然后问你能选出多少个集合使得集合中所有格子相同并且都在同一行或者同一列

先记下每行每列0和1得个数,然后组合数计算集合个数,由于$ans=n\times 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
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=55;
int a[maxn][maxn];
int n,m;
int row[2][maxn],col[2][maxn];
ll quickpow(ll x,int k){
ll res=1;
while(k>0){
if(k&1)res=res*x;
x=x*x;
k>>=1;
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++){
int Sum=0,Sum1=0;
for(int j=1;j<=m;j++)
Sum+=a[i][j]==1,Sum1+=a[i][j]==0;
row[0][i]=Sum,row[1][i]=Sum1;
}
for(int i=1;i<=m;i++){
int Sum=0,Sum1=0;
for(int j=1;j<=n;j++)
Sum+=a[j][i]==1,Sum1+=a[j][i]==0;
col[0][i]=Sum,col[1][i]=Sum1;
}
ll Ans=n*m;
for(int i=1;i<=n;i++){
Ans+=quickpow(2ll,row[0][i])-row[0][i]-1;
Ans+=quickpow(2ll,row[1][i])-row[1][i]-1;
}
for(int i=1;i<=m;i++){
Ans+=quickpow(2ll,col[0][i])-col[0][i]-1;
Ans+=quickpow(2ll,col[1][i])-col[1][i]-1;
}
printf("%lld\n",Ans);
return 0;
}

C Sorting by Subsequences

题意:将整个序列分为最多的子序列,使得子序列分别排序后得到的序列是原序列排序以后的结果,输出划分方法。

其实把原数列和排好序的数列进行对比会发现换的其实是个循环…然后根据没排好的找它的循环就可以了,复杂度近似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
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+5;
int a[maxn];
int n;
int sorted[maxn];
map<int ,int > ind;
vector<vector<int > > Ans;
bool book[maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);sorted[i]=a[i];ind[a[i]]=i;}
sort(sorted+1,sorted+1+n);
vector<int > buf;
for(int i=1;i<=n;i++){
if(a[i]==sorted[i]) {
buf.clear();buf.push_back(i);
Ans.push_back(buf);
book[i]=true;
}
}
for(int i=1;i<=n;i++){
if(!book[i]){
buf.clear();
buf.push_back(i);book[i]=true;
int nxt=sorted[i],ni=ind[nxt];
buf.push_back(ni);book[ni]=true;
while(sorted[ni]!=a[i]){
ni=ind[sorted[ni]];
buf.push_back(ni);book[ni]=true;
}
Ans.push_back(buf);
}
}
printf("%d\n",Ans.size());
for(int i=0;i<(int)Ans.size();i++){
printf("%d ",Ans[i].size());
for(int j=0;j<(int)Ans[i].size();j++){
printf("%d ",Ans[i][j]);
}
puts("");
}
return 0;
}

D Interactive LowerBound

题意:询问和输出一共最多2000次,问一个乱序并有后继的数列中x的lower_bound值,若没有输出-1

先询问大概1000次(包括start本身),然后在已知的结果里找一个最接近结果的答案,如果已经大于了x就输出,否则在询问次数范围内继续询问…还问不出来比x大的数的话那就估计没了,输出-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
#include <bits/stdc++.h>
using namespace std;
const int maxn=50000+5;
int n,start,x;
pair<int ,int > d[maxn];
int idx[maxn];
#define MP make_pair
void proce(int val,int nxt,int lef){
if(val>=x) {printf("! %d\n",val);fflush(stdout);exit(0);}
else{
if(nxt==-1 || lef==0) {printf("! -1\n");fflush(stdout);exit(0);}
else{
printf("? %d\n",nxt);fflush(stdout);
scanf("%d%d",&val,&nxt);
proce(val,nxt,lef-1);
}
}
}
int main()
{
scanf("%d%d%d",&n,&start,&x);
for(int i=1;i<=n;i++) idx[i]=i;
srand((unsigned)time(NULL));
random_shuffle(idx+1,idx+1+n);
printf("? %d\n",start);
fflush(stdout);
int val,nxt;
scanf("%d%d",&val,&nxt);
if(val>=x) {printf("! %d\n",val);fflush(stdout);exit(0);}
int len=min(999,n);
for(int i=1;i<=len;i++){
printf("? %d\n",idx[i]);
fflush(stdout);
scanf("%d%d",&d[i].first,&d[i].second);
}
d[0].first=val,d[0].second=nxt;
sort(d,d+1+len);
pair<int ,int > now=*(upper_bound(d,d+len+1,MP(x,0))-1);
proce(now.first,now.second,995);
return 0;
}

E Upgrading Tree

题意:给你一棵树,你需要替换一些边,使得这棵树的所有点对之间距离的平方和最小,替换边形如$(x,y,y’)$,把$(x,y)$这条边拆掉并且替换为$(x,y’)$这条边,前提是:

  1. $(x,y)$要存在在树中
  2. 这次替换后必须保持是一棵树
  3. 断开后,$x$所在的连通分量要严格大于$y$的

输出替换边的方案

对于这棵树所有点对之间距离的平方和最小,在相同节点数中这样的形态应该是菊花树,简证:假定不是菊花树使得平方和最小,那么我们随便取一个不是根的点$x$拿到一个叶子$y$上接着(不可能接在根上不然还是菊花树),会发现除了$(x,y)$之间的距离减小了$1$,对于其他所有叶子结点和根,$x$到其的距离都会增加$1$,因而增加的距离就有$n-1$次,自然得不偿失。那么我们考虑将这个树转成菊花树一类的东西。

那么一棵树最多有2个重心,因为菊花树的重心就是根,那么我们就不改树的重心了(反正他只是要找到构造方法…不是要求操作最少)。

证明一下在修改过程中重心的度不会变。可以发现每次修改操作$(x,y,y’)$中$x$一定所属的重心方面的分量(因为重心的最大子树大小不超过整棵树的一半,所以自然以重心为根时,$x$接近重心(在后面的操作中发现他其实就是重心的儿子)),因而我们也可以发现无论如何修改,重心的度不变,因为不可能有点断开在重心子树中的连接而转到重心上(根据换边的前提3)。

考虑先找出树的重心,然后对这个重心的所有儿子建菊花树。为什么不直接以重心为根呢?根据上一段我们可以发现重心的度是不变的,因而在总有顶点连在重心的情况下不可能重心为根建菊花树。对所有儿子为根具体的建造方法是:设重心的一个儿子是$v$,对于与$v$不直接相连的点$u$,我们先断开根与$v$的关系连上$u$,再让$u$与它的父亲断开关系连上$v$,此时$u$成为了重心的儿子,再对其他点以此类推。最后把重心和最后一个点(此时仍然是重心的儿子)断开,连上原先的$v$即可。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=2*100000+5;
vector<int > g[maxn];
const int inf=0x3f3f3f3f;
#define MP make_pair
void addedge(int from,int to)
{
g[from].push_back(to);
g[to].push_back(from);
}
int n;
int siz[maxn];
void predfs(int v,int fa)
{
siz[v]=1;
for(int i=0;i<(int)g[v].size();i++){
int u=g[v][i];
if(u!=fa){
predfs(u,v);
siz[v]+=siz[u];
}
}
}
int Findcent(int v,int fa)
{
for(int i=0;i<(int)g[v].size();i++){
int u=g[v][i];
if(u!=fa && siz[u]>n/2) return Findcent(u,v);
}
return v;
}
vector<pair<int ,pair<int ,int > > > Ans;
vector<pair<int ,int > > topo;
void dfs(int v,int fa){
for(int i=0;i<(int)g[v].size();i++){
int u=g[v][i];
if(u!=fa){
dfs(u,v);
}
}
topo.push_back(MP(v,fa));
}
void getans(int v,int fa)
{
topo.clear();
dfs(v,fa);
topo.pop_back();
int iter=v;
for(int i=0;i<(int)topo.size();i++){
pair<int ,int > now=topo[i];
Ans.push_back(MP(fa,MP(iter,now.first)));
Ans.push_back(MP(now.first,MP(now.second,v)));
iter=now.first;
}
Ans.push_back(MP(fa,MP(iter,v)));
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n-1;i++){
int from,to;
scanf("%d%d",&from,&to);
addedge(from,to);
}
predfs(1,-1);
int Cent=Findcent(1,-1);
int Cent2=0;
for(int i=0;i<(int)g[Cent].size();i++){
int u=g[Cent][i];
if(siz[u]*2==n) Cent2=u;
}
for(int i=0;i<(int)g[Cent].size();i++){
int u=g[Cent][i];
if(u!=Cent2) getans(u,Cent);
}
if(Cent2!=0){
for(int i=0;i<(int)g[Cent2].size();i++){
int u=g[Cent2][i];
if(u!=Cent) getans(u,Cent2);
}
}
printf("%d\n",Ans.size());
for(int i=0;i<(int)Ans.size();i++){
printf("%d %d %d\n",Ans[i].first,Ans[i].second.first,Ans[i].second.second);
}
return 0;
}


comments powered by HyperComments