11.4 模拟赛

终于AK了，虽然第三题主要是搞月想出来的

T1：

n个1*1的小方块，把这些小方块拼成一个图形，使这个图形周长最小

思路：

枚举拼成长方形的长为i，宽为n/i

可得面积 (i+n/i+(bool)(n%i))*2

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<cstring>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #define ll long long
11 #define inf 200000000000000LL
12 #define MAXN 100100
13 using namespace std;
14 inline ll read()
15 {
16     ll x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1,ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 ll T,n,ans,x;
22 int main()
23 {
24     freopen("block.in","r",stdin);
25     freopen("block.out","w",stdout);
26     T=read();
27     while(T--)
28     {
29         n=read(),ans=inf,x=sqrt(n);
30         for(ll i=1;i<=x;i++)
31         {
32             ans=min(ans,(i+n/i+(bool)(n%i))*2);
33         }
34         printf("%lld
",ans);
35     }
36 }

View Code

T2：

一个n个点的满图已知这个图只有一个最小生成树已知这个最小生成树

求这个图的边权和最小值

思路：

模拟kruskal 每加入一条边就把之前的两个联通块内所有的点没被连起来的边都连起来，权值为这条边的权值+1

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<cstring>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #define ll long long
11 #define inf 2147483611
12 #define MAXN 20101
13 using namespace std;
14 inline ll read()
15 {
16     ll x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1,ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 struct edge
22 {
23     int from,to,val;
24     bool operator < (const edge &a) const
25     {
26         return val<a.val;
27     }
28 }e[MAXN];
29 ll ans,fa,fb,n,T,f[MAXN],num[MAXN];
30 int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
31 int main()
32 {
33     freopen("tree.in","r",stdin);
34     freopen("tree.out","w",stdout);
35     T=read();
36     while(T--)
37     {
38         n=read();ans=0;
39         for(int i=1;i<n;i++) e[i].from=read(),e[i].to=read(),e[i].val=read(),f[i]=i,num[i]=1,ans+=e[i].val;
40         f[n]=n,num[n]=1;
41         sort(e+1,e+n);
42         for(int i=1;i<n;i++)
43         {
44             fa=find(e[i].from),fb=find(e[i].to);
45             f[fa]=fb;
46             ans+=(num[fa]*num[fb]-1)*(e[i].val+1);
47             num[fb]+=num[fa];
48         }
49         printf("%lld
",ans);
50     }
51 }

View Code

T3：

有 n 个不同颜色的球排成一排，其中 n 为偶数打算把这些球按照某种玄妙的顺序放入一个球筒中

每次他会选择一个未被放入球筒且不是当前排在第一个的球先把这个球放入球筒再把这个球的前一个球也放入球筒

重复 n/2 次这个操作后恰好所有球都被放入球筒希望最后球筒中从顶到底的颜色序列字典序最小

思路：

首先分析一下题目，我们需要不断的贪心找出字典序最小的串

可以想到每次找到两个最小的数对

但是这两个数对是有要求的，中间不能有奇数个数，两边也不能有奇数个数

所以我们可以想到分治+贪心

对于一段l-r的区间我们找到一个数使它的位数的奇偶性和l一样且这个数很小

然后再找到的数后面再找一个数使它尽量小且这个数的位数与前面找到的数奇偶性相反

这样整个区间就被分成了3段：两个点左边、中间、右边

然后分别分治

但是我们需要排序

这几部分处理出来之后顺序是可以打乱的，只要满足里面的比外面的先进筒即可

这样我们就需要一个归并排序

在这三部分都有序的前提下归并排序

然后可以得到答案

但是区间最值需要利用ST表或线段树来维护奇数位和偶数位的最小值

所以打了一个线段树打了一年

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<cstring>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #define ll long long
11 #define inf 2147483611
12 #define MAXN 200100
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1,ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 struct data { int a,b;}ans[MAXN];
22 int n,g[MAXN],cnt,hsh[MAXN];
23 struct tree {int l,r,minn;}tre[3*MAXN],tro[3*MAXN];
24 void builde(int k,int l,int r)
25 {
26     tre[k].l=l,tre[k].r=r;
27     if(l==r) {if(l&1) tre[k].minn=g[l];else tre[k].minn=inf;return ;}
28     int m=(l+r)>>1;
29     builde(k<<1,l,m);builde(k<<1|1,m+1,r);
30     tre[k].minn=min(tre[k<<1].minn,tre[k<<1|1].minn);
31 }
32 void buildo(int k,int l,int r)
33 {
34     tro[k].l=l,tro[k].r=r;
35     if(l==r) {if(l&1) tro[k].minn=inf;else tro[k].minn=g[l];return ;}
36     int m=(l+r)>>1;
37     buildo(k<<1,l,m);buildo(k<<1|1,m+1,r);
38     tro[k].minn=min(tro[k<<1].minn,tro[k<<1|1].minn);
39 }
40 int querye(int k,int a,int b)
41 {
42     if(a>b) return inf;
43     int l=tre[k].l,r=tre[k].r,m;
44     if(l==r) return tre[k].minn;
45     m=(l+r)>>1;
46     if(m<a) return querye(k<<1|1,a,b);
47     if(m>=b) return querye(k<<1,a,b);
48     return min(querye(k<<1,a,m),querye(k<<1|1,m+1,b));
49 }
50 int queryo(int k,int a,int b)
51 {
52     if(a>b) return inf;
53     int l=tro[k].l,r=tro[k].r,m;
54     if(l==r) return tro[k].minn;
55     m=(l+r)>>1;
56     if(m<a) return queryo(k<<1|1,a,b);
57     if(m>=b) return queryo(k<<1,a,b);
58     return min(queryo(k<<1,a,m),queryo(k<<1|1,m+1,b));
59 }
60 void work(int a,int b)
61 {
62     if(a>=b) return;
63     if(a==b-1) {ans[a].a=ans[b].a=g[a],ans[a].b=ans[b].b=g[b];return ;}
64     int k1,k2;
65     if(a&1) k1=hsh[querye(1,a,b)],k2=hsh[queryo(1,k1+1,b)];
66     else k1=hsh[queryo(1,a,b)],k2=hsh[querye(1,k1+1,b)];
67     work(k1+1,k2-1),work(a,k1-1),work(k2+1,b);
68     int t1=a,t2=k1+1,t3=k2+1;
69     data tm[MAXN];tm[a].a=tm[a+1].a=g[k1],tm[a].b=tm[a+1].b=g[k2],cnt=a+1;
70     while(t1<k1||t2<k2||t3<=b)
71     {
72         if(t1==k1) ans[t1].a=inf;
73         if(t2==k2) ans[t2].a=inf;
74         if(t3==b+1) ans[t3].a=inf;
75         if(ans[t1].a<ans[t2].a&&ans[t1].a<ans[t3].a) tm[++cnt]=ans[t1++];
76         if(ans[t2].a<ans[t3].a&&ans[t2].a<ans[t1].a) tm[++cnt]=ans[t2++];
77         if(ans[t3].a<ans[t1].a&&ans[t3].a<ans[t2].a) tm[++cnt]=ans[t3++];
78     }
79     for(int i=a;i<=b;i++) ans[i]=tm[i];
80 }
81 int main()
82 {
83     freopen("ball.in","r",stdin);
84     freopen("ball.out","w",stdout);
85     n=read();
86     for(int i=1;i<=n;i++) g[i]=read(),hsh[g[i]]=i;
87     builde(1,1,n);buildo(1,1,n);
88     work(1,n);
89     for(int i=1;i<=n;i+=2) printf("%d %d ",ans[i].a,ans[i].b);
90 }

View Code

调试的时候因为把部分变量定为了全局导致递归分治之后变量值改变了