本次Rating降至空心黄
500搞了半天j打成i看不出来。。。交的时候都只剩200+分了。
最后500还是挂掉了，后来发现if里有个东西又打错了。。。一改Y了。
5555555555555555，现在神马都不行了。
在TC里那个字体太疼了= =。下次在外面打算了。
250
题目给定一个矩阵，每一笔你可以横向涂一笔连续的红的，或者竖向涂一笔连续的蓝的。如果一个格子被涂了红和蓝的，那么会变绿的。最后给出矩阵每个格子的颜色，问最少涂多少笔涂成这个样。
矩阵最大是50*50的。
……就是枚举。
class ColoredStrokes {
vector
int v[55][55];
public:
void solvex(){
memset(v,0,sizeof(v));
for (int i=0;i
for (int k=j;k
ans++;
}
}
}
void solvey(){
memset(v,0,sizeof(v));
for (int i=0;i
for (int k=i;k
ans++;
}
}
}
int getLeast(vector
m=picture.size();
n=picture[0].size();
ans=0;
solvex();
solvey();
return ans;
}
};
500
有一些球在数轴上跑，然后他们都有一个相同的正的速度。(并且球不会发生碰撞)
然后他给出的第一个数组给定了一开始每个球的位置。
他又给了第二个数组，表示的是之后某个时刻每个球的位置。（但是有一些无关的球会被加进去）
假设way[i]表示第一个数组中第i个球是第二个数组中第way[i]个球，那么问way这个数组有多少种可能的不同的取值。
两个数组中的元素个数都<=50，题目保证了两个数组中，都不会有重复的数值。
样例：
具体做法就是先枚举他们的速度，设为dis。(显然速度只能是 abs(a[i]-b[j]) )
接下来我们来建边：
a[i] -> (a[i]-dis) in b[j]
a[i] -> (a[i]+dis) in b[j]
对于a[i]，如果不存在其它的a[j]和它争b数组中的结点，那么显然他连出去多少条边，就有多少种方案，然后利用乘法原理乘起来就行。
然后我们关注发生冲突的。因为a,b数组中都不包含重复元素，那么发生冲突只能是这样情况：
a[i]+dis=a[j]-dis
然后继续发生冲突：a[j]+dis=a[k]-dis…
如此下去就会变成一条链。
然后……就判一个每个结点-dis和+dis的是否在b数组中存在。然后匹配时对于这条链，要么全-dis，要么全+dis，要么从中间部分开始，前一半-dis,后一半+dis……于是就这样每条链分开讨论，乘法原理将方案数乘起来。
然后再根据加法原理把不同速度的方案加起来。得到解。
class OneDimensionalBalls {
public:
int up[55];
int down[55];
int m,n;
int a[55];
int b[55];
int v[55];
int tail;
int dis;
int List[55*55];
void make_up_down(){
int i,j;
memset(up,0,sizeof(up));
memset(down,0,sizeof(down));
for (i=0;i
if (a[i]+dis==b[j]) down[i]=1;
}
}
int Q[55];
int Qt;
int Link(int st){
int i;
Qt=1; Q[1]=st;
v[st]=1;
for (i=st+1;i
v[i]=1;
Q[++Qt]=i;
}
int ed=Q[Qt];
if (!up[st] && !down[ed]) return 0;
if (!up[st]) return 1;
if (!down[ed]) return 1;
return Qt+1;
}
long long countValidGuesses(vector
n=secondPicture.size();
for (int i=0;i
sort(b,b+n);
tail=0;
for (int i=0;i
List[++tail]=abs(a[i]-b[j]);
long long ans=0;
long long now;
sort(List+1,List+tail+1);
for (int i=1;i<=tail;i++)
if (i==1 || List[i]!=List[i-1]){
dis=List[i];
make_up_down();
memset(v,0,sizeof(v));
now=1;
for (int j=0;j
now*=Link(j);
ans+=now;
}
return ans;
}
};
950
推荐hhanger大神的解题报告
