2016 Multi University Training Contest 2

官方题解

题目链接

题目大意

给定向量(W=(w_1,w_2,…,w_n)),又有向量(B=(b_1,b_2,…,b_n)),其中:(b_i∈{-1,1} ),求( {||W-α*B||}^2 )的最小值?

思路 - 数学

将原式展开化简可得:( {||W-α*B||}^2 ) (=sum {i=1} ^n * {α}^2 -2* sum {i=1} ^n {w_i * bi})* α + sum {i=1} ^n * {w_i}^2)
由于(b_i∈{-1,1} ),(wi)已给定,所以上式是一个关于(α)的二次函数,则当:(α = frac { sum {i=1} ^n {w_i * bi} } {n} =frac { sum {i=1} ^n {|wi|} } {n} )时,取得最小值:(sum {i=1} ^n * {wi}^2 + frac { { sum {i=1} ^n {|w_i|} }^2 } {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

#include <cstring>
#include <algorithm>

using namespace std;

long long n,w,sigema,sum,ans,gd;

int () {
int T;
scanf("%d",&T);
while(T-->0) {
scanf("%I64d",&n);
sigema=sum=0;
for(int i=0;i<n;++i) {
scanf("%I64d",&w);
sum+=abs(w);
sigema+=w*w;
}
ans=n*sigema-sum*sum;
if(ans<=0) {
printf("0/1n");
}
else {
gd=__gcd(ans,n);
printf("%I64d/%I64dn",ans/gd,n/gd);
}
}
return 0;
}

1002. Chess

题目大意

给定一棵有(n)个结点的有根树,第(i)个结点(i)的权值为(w[i]),定义(f[i]),在满足(v_1=i)且(vi)是(v {i-1} )的结点序列(v_1,v_2,…,v_m)中,(f[i]=max{w[vi]+ sum {i=2} ^ {m} {ope(w_{vi},w{v{i-1} } ) } } )。

思路 - 树形DP&&Meet in the middle

很容易就能想到在树上进行(DP)处理求(f[i]),设(dp[i]=f[i]-w[i]),则有(dp[i]=max{dp[j]+ope(w[i],w[j])},j是i的祖先),但是直接枚举序列是(O(n^2)),会超时。
看了题解后明白权值最大只有(2^16),可以将(ope(w[i],w[j])拆成((ope(w[i]>>8,w[j]>>8)<<8)+ope(w[i]&255,w[j]&255)\),可以用\(meet in="" the="" middle\)的方法,将前八位和后八位分开处理。设辅助数组\(ds[a][b]表示祖先结点j的前八位为a,当前结点i的后八位为b时,\(max="" {dp[j]+ope(ds[w[j]="">>8][w[i]&255] } )。
更新当前结点(i)的(dp[i])时,枚举祖先结点(j)的权值的前八位(x),即(dp[j]=max{ds[x][w[i]&255]+(ope(w[i]>>8,x)<<8) } )
更新当前结点(i)的(ds[x][0~256])时,枚举其子结点(k)的权值的后八位(y),即(ds[x][y]=max(ds[x][y],dp[i]+ope(w[i]&255,y)))。

代码

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

#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN=(1<<16)+7;
const long long MOD=1e9+7;

int n,m,par;
int w[MAXN],vis[MAXN];
long long ds[257][257],backup[MAXN][256];
long long ans;
char cmd[5];
vector<int> g[MAXN];

inline long long ope(long long a,long long b) {
if(cmd[0]=='A') {
return a&b;
}
if(cmd[0]=='O') {
return a|b;
}
return a^b;
}

void dfs(int u) {
int a=w[u]>>8,b=w[u]&255;
long long dp=0;
for(int i=0;i<256;++i) {//枚举结点u的祖先权值的前八位
if(vis[i]!=0) {//如果祖先结点前八位为i的结点出现过
dp=max(dp,ds[i][b]+(ope(a,i)<<8));
}
}
ans=(ans+u*(dp+w[u]))%MOD;
++vis[a];//祖先结点前八位为a出现的次数+1
for(int i=0;i<256;++i) {//备份ds并将ds[a][0~256]更新为当前结点的ds值
backup[u][i]=ds[a][i];
ds[a][i]=max(ds[a][i],dp+ope(b,i));
}
for(int i=g[u].size()-1;i>=0;--i) {//递归处理子结点
dfs(g[u][i]);
}
--vis[a];//祖先结点前八位为a出现的次数-1
for(int i=0;i<256;++i) {//还原当前结点的ds[a][0~256]
ds[a][i]=backup[u][i];
}
}

int () {
int T;
scanf("%d",&T);
while(T-->0) {
scanf("%d%s",&n,cmd);
for(int i=1;i<=n;++i) {
scanf("%d",w+i);
g[i].clear();
}
for(int i=2;i<=n;++i) {
scanf("%d",&par);
g[par].push_back(i);
}
memset(vis,0,sizeof(vis));
ans=0;
dfs(1);
printf("%I64dn",ans);
}
return 0;
}

1004. Task

题目链接

题目大意

有(n)台机器,每台机器有最大能处理的任务时间(x[i]),机器的等级(y[i]);(m)个任务,每个任务有需要处理的时间(x[j]),任务的等级(y[j]),当且仅当机器(i)的(x[i])和(y[i])均大于任务的(x[j])和(y[j])时,机器(i)才能处理完任务(j),收益为(500*x[j]+2*y[j]),求最多能完成的任务,及此时的最大收益?

思路 - 贪心

由于(y)最大只有(100),所以可以对机器以(y)值为下标建立(vector),存储相应的(x)值,然后对其排序,从小到大枚举机器的(y)值,找到第一个符合的机器。

代码

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

#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN=101;
const long long MOD=1e9+7;

struct Node {
int x,y;

bool operator < (const Node& a) const {
if(x!=a.x) {
return x>a.x;
}
return y>a.y;
}
}cur,task[100005];

vector<int> q[105];
vector<int>::iterator it;

int n,m,cnt;
long long ans;

int () {
while(2==scanf("%d%d",&n,&m)) {
for(int i=0;i<=100;++i) {
q[i].clear();
}
for(int i=0;i<n;++i) {
scanf("%d%d",&cur.x,&cur.y);
q[cur.y].push_back(cur.x);
}
for(int i=0;i<m;++i) {
scanf("%d%d",&task[i].x,&task[i].y);
}
for(int i=0;i<=100;++i) {
sort(q[i].begin(),q[i].end());
}
sort(task,task+m);
ans=cnt=0;
for(int i=0;i<m;++i) {
for(int j=task[i].y;j<=100;++j) {
it=lower_bound(q[j].begin(),q[j].end(),task[i].x);
if(it!=q[j].end()) {
ans+=500*task[i].x+2*task[i].y;
++cnt;
q[j].erase(it);
break;
}
}
}
printf("%d %I64dn",cnt,ans);
}
return 0;
}

1005. Eureka

题目链接

题目大意

给定(n)个点(含有重点),求有多少种不同的子集,使得这个集合中元素个数不小于2,并且共线?

思路 - 枚举&&排列组合

刚开始枚举出所有非重点之间的直线,按照斜率排序找出平行的直线,然后就可以计算出这些点的个数,结果一直(WA),第二天才想到只是找出了平行的,然而不一定是共线的。。。

然后就换了一种枚举直线的方法(其实当时刚开始就这样写的,只不过那时还没有处理重点,所以就枚举了所有的直线,最后没改回去,认为是一样的):枚举每个点必在集合中,然后让其与之后的点形成直线,按照斜率排序找出平行的直线(此时平行一定共线),然后通过排列组合即可求出答案。

题解给的是先将所有点排序,然后枚举点,将该点“右侧”的点按照极角排序,再统计共线的点。感觉其实和枚举直线差不多,只不过我只是按照斜率排序,不懂极角排序为什么要用( frac {1} {gcd(dx, dy)} (dx, dy) )。

代码

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
112
113
114
115
116
117
118
119

#include <cstring>
#include <map>
#include <algorithm>

using namespace std;

const long long MOD=1e9+7;

struct Point {
long long x,y;

bool operator < (const Point& a) const {
return x<a.x||(x==a.x&&y<a.y);
}
}p[1005];

struct Node {
long long dx,dy;
Point e;

bool operator < (const Node& a) const {
if(dx==0)
return false;
if(a.dx==0)
return true;
return dy*a.dx<a.dy*dx;
}

bool operator == (const Node& a) const {
if(dx==0)
return a.dx==0;
if(a.dx==0)
return false;
return dy*a.dx==a.dy*dx;
}

void makeLine(const Point& ss,const Point& ee) {
e=ee;
dx=ss.x-ee.x;
dy=ss.y-ee.y;
if(dx<0) {
dx=-dx;
dy=-dy;
}
}
}line[1005];

int n,tot,num,t;
long long ans,cnt,sta;
map<Point,int> mp;
map<Point,bool> vis;

long long quickpow(long long m,long long n) {
long long b = 1;
while (n > 0) {
if (n & 1)
b = (b*m)%MOD;
n = n >> 1 ;
m = (m*m)%MOD;
}
return b;
}

void addAns(int j) {
t=cnt;
vis.clear();
while(t>0) {
if(!vis[line[j-t].e]) {
cnt+=mp[line[j-t].e]-1;
vis[line[j-t].e]=true;
}
--t;
}
//此时cnt表示与起点p[i]在同一条直线上的所有点(不包括起点)的个数
//x个点选择1~x共有C(x,1)+C(x,2)+...+C(x,x)=2^x-C(x,0)=2^x-1种选法
ans=(ans+(quickpow(2,sta)-1+MOD)*(quickpow(2,cnt)-1+MOD))%MOD;//起点可以选1~sta个,quick也可以选1~cnt个
}

int () {
int T;
scanf("%d",&T);
while(T-->0) {
mp.clear();
tot=0;
scanf("%d",&n);
for(int i=0;i<n;++i) {
scanf("%I64d%I64d",&p[tot].x,&p[tot].y);
++mp[p[tot]];
if(mp[p[tot]]==1) {
++tot;
}
}
ans=num=0;
for(int i=0;i<tot;++i) {
num=0;
for(int j=i+1;j<tot;++j) {
line[num++].makeLine(p[i],p[j]);
}
sort(line,line+num);
sta=mp[p[i]];//表示必在集合中的那个点p[i],共有多少个重点
cnt=1;
for(int j=1;j<num;++j) {
if(line[j]==line[j-1]) {
++cnt;//统计重合的平行线的个数
}
else {
addAns(j);
cnt=1;
}
}
if(num>0) {//最后一条(或几条平行)直线也需要处理
addAns(num);
}
ans=(ans+(quickpow(2,sta)-1-sta+MOD))%MOD;//只有起点p[i]在集合中
}
printf("%I64dn",ans);
}
}

1009. It’s All In The Mind

题目链接

题目大意

有一个长度为(n)的非递增序列(a_1,a_2,…,a_n),给定其中部分(a_i)的值,求( frac { a_1 + a2 } { sum {i=1} ^{n} a_i})的最大值?

思路 - 贪心

设(x=a_1+a_2,y=a_3+a_4+…+a_n),则( frac { a_1 + a2 } { sum {i=1} ^{n} a_i})(=frac {x} {x+y}=frac {1} {1+frac {y} {x} }),则(x)越大,(y)越小,原式的值越大。
所以(a_1,a_2)取能取到的最大值,(a_3,…,a_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

#include <cstring>
#include <algorithm>

using namespace std;

int n,m,a[105],x,y,gd,num,deno,last;

int () {
int T;
scanf("%d",&T);
while(T-->0) {
memset(a,-1,sizeof(a));
scanf("%d%d",&n,&m);
while(m-->0) {
scanf("%d%d",&x,&y);
a[x]=y;
}
if(a[1]==-1) {
a[1]=100;
}
if(a[2]==-1) {
a[2]=a[1];
}
num=deno=a[1]+a[2];
a[n+1]=0;
last=n+1;
for(int i=n;i>=3;--i) {
if(a[i]!=-1) {
last=i;
}
deno+=a[last];
}
gd=__gcd(num,deno);
printf("%d/%dn",num/gd,deno/gd);
}
return 0;
}

1011. Keep On Movin

题目链接

题目大意

有(n)种不同的字符,第(i)种字符有a_i)个,用这些字符拼成一些回文串,使得所有回文串中最短的长度最长,输出这个长度?

思路 - 贪心

统计奇数个字符的个数(cnt),并将这些字符的个数变为(1),其余的当作偶数个字符看待,统计所有偶数字符个数的总和(even),然后将(even)均分给(cnt)个回文串,每个串分得(ans=floor(even/cnt))个字符,如果(ans)为奇数,则不能这样分,每个串只能分得(ans-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
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n,a,even,cnt,ans;

int main() {
int T;
scanf("%d",&T);
while(T-->0) {
even=cnt=0;
scanf("%d",&n);
for(int i=0;i<n;++i) {
scanf("%d",&a);
if((a&1)==1) {
++cnt;
even+=a-1;
}
else {
even+=a;
}
}
if(cnt==0) {//没有个数为奇数的字符
printf("%dn",even);
}
else {
ans=even/cnt;//每个回文串均能分得ans个字符
if((ans&1)==1) {//如果每个回文串分得的字符不是偶数个
--ans;
}
printf("%dn",ans+1);
}
}
return 0;
}

1012. La Vie en rose

题目链接

题目大意

有一个串(s)和一个串(p),可以交换串(p)的两个相邻的字符,但每个字符只能交换一次,求这样产生的字串能在(s)串中

思路 - DP

设(dp[j])表示能匹配到串(p)的(j)位置,则枚举串(s)的起始位置,做(n)次(DP),复杂度为:(O(n*m))
(DP)时不需要考虑当前位置是如何匹配上的,因为如果不交换就能匹配上一定选择不交换的,此时交换能匹配上就说明串(p)的前两个字符是相同的。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n,m;
bool dp[5005];//dp[j]表示能匹配到串p的j位置
char s[100005],p[5005];
char ans[100005];

char solve(int i) {
int j=0;
memset(dp,false,sizeof(dp));
if(s[i]==p[j]) {//不用交换就能匹配上肯定选不用交换的
dp[j]=true;
++i;
++j;
}
else if(s[i]==p[1]&&s[i+1]==p[j]) {//交换后才能匹配上就选交换的
dp[j+1]=true;
i+=2;
j+=2;
}
else {//均不能匹配则无法匹配成功
return '0';
}
for(;i<n&&j<m;) {
if(dp[j-1]&&s[i]==p[j]) {//不用交换就能匹配上肯定选不用交换的
dp[j]=true;
++i;
++j;
}
else if(dp[j-1]&&s[i]==p[j+1]&&s[i+1]==p[j]) {//交换后才能匹配上就选交换的
dp[j+1]=true;
i+=2;
j+=2;
}
else {//均不能匹配则无法匹配成功
return '0';
}
}
return dp[m-1]?'1':'0';
}

int main() {
int T;
scanf("%d",&T);
while(T-->0) {
scanf("%d%d",&n,&m);
scanf("%s%s",s,p);
for(int i=0;i<n;++i) {
ans[i]=solve(i);
}
ans[n]='';
printf("%sn",ans);
}
}