edward_mj

[SSLOJ2018 帮助]【状压dp】【贪心思想】

【题目】

【算法分析】

首先有一个显而易见的性质，我们如果拿起了一些书，那么对于同样高度的，就应该合在一起再放回去。如果分开放的话，不会使答案更优。

另外，如果我们拿起了一些高度为k的书，而书架上还有高度为k的书没被拿走。那么我们肯定会把这些书放到其中一个没被拿走的书的前面或者后面。显然，另外的方法不会比这更优。

于是，我们定义

F[i,j,k,l]表示决策完前i本书，已经被拿起的高度的书的集合为j(0<=j<2^8,二进制表示)，然后已经拿起了k本书，并且上一段的末尾为l的时候的最小混乱度。

转移有3种。

1、如果集合j里面包含有a[i+1]这样高度的书，那么把这些高度为a[i+1]的书全部放到a[i+1]前面。

2、我们把第i+1本书给拿起来，那么会出现两种情况。第一种：前面没有高度为a[i+1]且没有被拿起来的书。第二种：前面有高度为a[i+1]且没有被拿起来的书。

首先一个问题就是对“是否存在没动的高度为a[i+1]的书”的判定。我的判定方法是这样的：如果前面有高度为a[i+1]的书，而且j这个被拿起的书的集合里没有高度为a[i+1]的书，那么肯定前面有没被“拿起的书”。否则必然没有。

对于第一种情况，我们把被拿起的第i+1本书放进集合j里面。

对于第二种情况，我们把被拿起的第i+1本书放到前面没被动的，高度为a[i+1]的书的后面。

3、不拿书也不放书，就直接算~

最后由于空间巨大，要用一下滚动数组。。。

【时间复杂度】

O(n*2^8*m*8)

【空间复杂度】

O(2^8*m*8)

【其它】据说有O(n*2^8*m)的算法。。。求好心人发一下。

【CODE】

C++ CODE :SSL2018 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061 #include

[BZOJ2005 [Noi2010]能量采集]【容斥定理】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=2005

【题目大意】

给出m,n，求Sum{gcd(i,j) | 1<=i<=m && 1<=j<=n}*2-m*n。

【算法分析】

下面所有/都表示整除。

看了oimaster的题解，Orz容斥原理原来可以这么用= =。Orz比正解更快的解法。

我们先枚举g=gcd(i,j)。然后转化为求1<=i<=m/g && 1<=j<=n/g，并且gcd(i,j)=1的二元对(i,j)的个数。

然后我们考虑这个新的问题。

令x=m/g y=n/g

显然ans=x*y-所有gcd(i,j)>1的二元对个数。

后者res可以通过容斥原理求解。

先假设我们先把1~m的素数求了出来。存在p数组里面。

然后后者就等于f(p[1])∪f(p[2])∪f(p[3])….的个数。（其中f(t)表示t在gcd(i,j)>1里面所占的二元对。）

我们套用容斥原理的公式可以发现，1~x每个数字都最多只会被使用一次。

res=-f(1)+f(2)+f(3)+f(5)-f(6)….

若t分解质因数对于同一个素因子含有两个以上，那么不会被容斥原理所需要。

若t分解质因数有偶数个素因子，那么前面的系数为-1。

若t分解质因数有奇数个素因子，那么前面的系数为1。

、

回到原题。

因为a/b/c = a/(b*c)

所以我们可以直接按容斥求那个res。暴力得解。

【时间复杂度】

先预处理那个f()前面的系数n lg n即可。

后面的暴力的部分的复杂度相当于

1<=i<=n && 1<=j<=i

i%j==0的对数。

= =其实就是约数啦。。。

单个数的约数是可能到达该数的sqrt(n)级别的。

但是前n个约数的个数的和是n lg n级别的。。。

所以后面这部分的时间复杂度也是n lg n。

总的时间复杂度O(n lg n)

【CODE】

C++ CODE :Noi2010 energy 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061 #include

[SGU120 Archipelago]【平面几何】【向量旋转】

【题目链接】http://acm.sgu.ru/problem.php?contest=0&problem=120

【题目大意】

给定一个N边形，这个N边形上的点都被按顺时针顺序标号为1,2,3…。然后给出标号为m1和m2的点的坐标，最后按标号顺序输出这个多边形所有的点。

【算法分析】

大概思路是先算出中心，然后用向量一直转，就能得到所有的点。

我们先连接m1,m2两个点得到线段L，然后作这条线段的中垂线L’。然后可以很轻松算出图中的角α的值（就是pi/n*(abs(m1-m2))）。然后搞到0~pi之间就可以了。然后我们知道中心点Mid到L的距离d。

然后对向量m1->m2旋转个90°/270°，再把长度调成d。就可以得出中心点的位置了。

当然，如果abs(m1-m2)*2==n要特判一下。因为取不到tan。。。= =，应该有更好的方法。

然后可以得出中心Mid的坐标。然后构造Mid->a[m1]的向量，然后把这个向量每次旋转2*pi/n，就可以了得出所有坐标了噢。

^_^

【关于向量旋转】

学过极坐标的话。。。这个太简单了。

下面推导一下~~

对于向量(x,y)，如果要顺时针旋转的角度β的话，那么这样弄。

转化为极坐标:

x=L*cos(α)

y=L*sin(α)

然后旋转以后变成

x=L*cos(α-β)=L*cos(α)*cos(β)+L*sin(α)*sin(β)

y=L*sin(α-β)=L*sin(α)*cos(β)-L*cos(α)*sin(β)

然后变回直角坐标系

x=x*cos(β)+y*sin(β)

y=y*cos(β)-x*sin(β)

然后就完成了旋转

【CODE】

C++ CODE :SGU120 1 2 3 4 5 6 7 8 91011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586 #include

[Hust1017 Exact cover]【DLX】【精确覆盖例题】

【题目链接】http://acm.hust.edu.cn/thanks/problem.php?id=1017

【题目大意】

给定一个M*N的矩阵，上面只有1和0。其中M,N<=1000。

并且每一行的1的数量<=100。

让你取一些行，使得每一列恰好有一个1。

【算法分析】

这个吓人的规模。。。没错。。。就是搜索。

Dancing Link + Algorithm X

【其它】

很寂寞。时限15秒，我跑了4秒。第一名跑了120+MS。。。很好很沙茶。

【CODE】

C++ CODE :Hust1017 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 #include #include #include const int N=1005;
int m,n,dep,tot;
int Sum[N];
int L[N],R[N],U[N][N],D[N][N];
int a[N][105];
int ansL[N];
int Sx[N*N/10],Sy[N*N/10];

void init(){
int i,j,x;
for (j=0;j<=n;j++){
D[0][j]=0;
U[0][j]=0;
}
memset(Sum,0,sizeof(Sum));
for (i=1;i<=m;i++){
scanf("%d",&a[i][0]);
for (j=1;j<=a[i][0];j++){
scanf("%d",&x);
a[i][j]=x;
Sum[x]++;
D[i][x]=0;
U[i][x]=U[0][x];
U[D[i][x]][x]=i;
D[U[i][x]][x]=i;
}
}
for (i=0;i for (i=1;i<=n;i++) L[i]=i-1; L[0]=n;
}

void Delete(int Col){
int i,j,tmp=tot,next;
for (i=D[0][Col];i;i=next){
next=D[i][Col];
for (j=1;j<=a[i][0];j++){
int &x=a[i][j];
Sum[x]–;
U[D[i][x]][x]=U[i][x];
D[U[i][x]][x]=D[i][x];
tot++;
Sx[tot]=i;
Sy[tot]=x;
}
}
L[R[Col]]=L[Col];
R[L[Col]]=R[Col];
}

void Recover(int k){
while (tot!=k){
int &i=Sx[tot],&x=Sy[tot];
Sum[x]++;
U[D[i][x]][x]=i;
D[U[i][x]][x]=i;
tot–;
}
}

bool dfs(){
if (!R[0]) return true;
int i,j,Min=0x7FFFFFFF,Mini,tmp;
for (i=R[0];i;i=R[i])
if (Sum[i] Min=Sum[i];
Mini=i;
}
if (Min==0) return false;
for (i=D[0][Mini];i;i=D[i][Mini]){
ansL[dep++]=i;
tmp=tot;
for (j=1;j<=a[i][0];j++)
Delete (a[i][j]);
if (dfs()) return true;
dep–;
for (j=a[i][0];j>=1;j–){
int &Col=a[i][j];
L[R[Col]]=Col;
R[L[Col]]=Col;
}
Recover(tmp);
}
return false;
}

void output(){
printf("%d",dep-1);
for (int i=1;i puts("");
}

int main(){
while (1){
if (scanf("%d%d",&m,&n)==EOF) break;
init();
dep=1;
tot=0;
if (dfs()) output();
else puts("NO");
}
return 0;
}

Tyvj真是一个疼死人不偿命的题库

昨晚的模拟赛下面交400分的程序被测成0分。
貌似好多神牛都这么悲剧。。。。
真是疼。。。
我从昨晚深夜观察，发现几次rejudge我的评测结果有如下变化：
第一次：
第 1 题: NetworkError
第 2 题: InternalError
System.OutOfMemoryException: 引发类型为“System.OutOfMemoryException”的异常。
在 System.IO.MemoryStream.set_Capacity(Int32 value)
在 System.IO.MemoryStream.EnsureCapacity(Int32 value)
在 System.IO.MemoryStream.Write(Byte[] buffer, Int32 offset, Int32 count)
在 System.IO.BinaryWriter.Write(String value)
在 VijosNT_Server.TestCase.Serialize(BinaryWriter Writer)
在 VijosNT_Server.TestCaseLoader.Write(IList`1 TestCaseList, BinaryWriter Writer)
在 VijosNT_Server.Judger.JudgerSub()
第 3 题: NetworkError
第 4 题: NetworkError
、
、
、
、
、
、
第二次：
第 1 题: InternalError
System.OutOfMemoryException: 引发类型为“System.OutOfMemoryException”的异常。
在 System.String.GetStringForStringBuilder(String value, Int32 startIndex, Int32 length, Int32 capacity)
在 System.Text.StringBuilder.GetNewString(String currentString, Int32 requiredLength)
在 System.Text.StringBuilder.Append(Char[] value, Int32 startIndex, Int32 charCount)
在 System.IO.StreamReader.ReadToEnd()
在 System.IO.File.ReadAllText(String path, Encoding encoding)
在 VijosNT_Server.TestCase..ctor(Int32 TimeLimit, Int32 MemoryLimit, String& InputFileName, String& OutputFileName, Int32 Weight)
在 VijosNT_Server.TestCaseLoader.LoadFromLocal(String Abbreviation)
在 VijosNT_Server.Judger.JudgerSub()
第 2 题: InternalError
System.OutOfMemoryException: 引发类型为“System.OutOfMemoryException”的异常。
在 System.String.GetStringForStringBuilder(String value, Int32 startIndex, Int32 length, Int32 capacity)
在 System.Text.StringBuilder.GetNewString(String currentString, Int32 requiredLength)
在 System.Text.StringBuilder.Append(Char[] value, Int32 startIndex, Int32 charCount)
在 System.IO.StreamReader.ReadToEnd()
在 System.IO.File.ReadAllText(String path, Encoding encoding)
在 VijosNT_Server.TestCase..ctor(Int32 TimeLimit, Int32 MemoryLimit, String& InputFileName, String& OutputFileName, Int32 Weight)
在 VijosNT_Server.TestCaseLoader.LoadFromLocal(String Abbreviation)
在 VijosNT_Server.Judger.JudgerSub()
第 3 题: NetworkError
第 4 题: NetworkError
、
、
、
、
、
、
第三次：
第 1 题: InternalError
System.OutOfMemoryException: 引发类型为“System.OutOfMemoryException”的异常。
在 System.String.GetStringForStringBuilder(String value, Int32 startIndex, Int32 length, Int32 capacity)
在 System.Text.StringBuilder.GetNewString(String currentString, Int32 requiredLength)
在 System.Text.StringBuilder.Append(Char[] value, Int32 startIndex, Int32 charCount)
在 System.IO.StreamReader.ReadToEnd()
在 System.IO.File.ReadAllText(String path, Encoding encoding)
在 VijosNT_Server.TestCase..ctor(Int32 TimeLimit, Int32 MemoryLimit, String& InputFileName, String& OutputFileName, Int32 Weight)
在 VijosNT_Server.TestCaseLoader.LoadFromLocal(String Abbreviation)
在 VijosNT_Server.Judger.JudgerSub()
第 2 题: InternalError
System.OutOfMemoryException: 引发类型为“System.OutOfMemoryException”的异常。
在 System.String.GetStringForStringBuilder(String value, Int32 startIndex, Int32 length, Int32 capacity)
在 System.Text.StringBuilder.GetNewString(String currentString, Int32 requiredLength)
在 System.Text.StringBuilder.Append(Char[] value, Int32 startIndex, Int32 charCount)
在 System.IO.StreamReader.ReadToEnd()
在 System.IO.File.ReadAllText(String path, Encoding encoding)
在 VijosNT_Server.TestCase..ctor(Int32 TimeLimit, Int32 MemoryLimit, String& InputFileName, String& OutputFileName, Int32 Weight)
在 VijosNT_Server.TestCaseLoader.LoadFromLocal(String Abbreviation)
在 VijosNT_Server.Judger.JudgerSub()
第 3 题: Accepted
VijosNT Judger: 1.2 build 100318
Judger #2
Compiler: G++111
g++ -O2 -g -otest.exe test.cpp
Test #1: Accepted… 0ms
Test #2: Accepted… 0ms
Test #3: Accepted… 0ms
Test #4: Accepted… 0ms
Test #5: Accepted… 0ms
Test #6: Accepted… 0ms
Test #7: Accepted… 0ms
Test #8: Accepted… 0ms
Test #9: Accepted… 0ms
Test #10: Accepted… 0ms
Total score: 100, time usage: 0ms
第 4 题: Accepted
VijosNT Judger: 1.2 build 100318
Judger #2
Compiler: G++111
g++ -O2 -g -otest.exe test.cpp
Test #1: Accepted… 0ms
Test #2: Accepted… 0ms
Test #3: Accepted… 0ms
Test #4: Accepted… 46ms
Test #5: Accepted… 46ms
Test #6: Accepted… 140ms
Test #7: Accepted… 78ms
Test #8: Accepted… 62ms
Test #9: Accepted… 250ms
Test #10: Accepted… 265ms
Total score: 100, time usage: 887ms
、
、
、
、
、
、
第四次：
变回第二次一样。
、
、
、
、
、
、
第五次：
第 1 题: InternalError
未将对象引用设置到对象的实例。
第 2 题: InternalError
未将对象引用设置到对象的实例。
第 3 题: InternalError
未将对象引用设置到对象的实例。
第 4 题: InternalError
未将对象引用设置到对象的实例。
、
、
、
、
、
、
最后&&现在：
第 1 题: NetworkError
第 2 题: NetworkError
第 3 题: NetworkError
第 4 题: NetworkError
、
、
、
、
、
、
弱问400->0_RP能+多少？
更疼的是我的徒弟多次rejudge依然屹立290分。排行第3的淫霸地位= =。。。
真真无语也~