发表于 
1
2
3
4
5
6
7
8
9
10
消成对角线的方法就不行了
不是方阵
消成行阶梯形
从now开始以后有系数全为0,但右边不为0的就无解
否则
now<n多解
这题数据挺大的（一般题都是0ms）
高斯约旦法在速度上的差异体现出来了
会慢100ms左右
阅读全文 »

发表于 
1
2
3
高斯消元解决模线性方程组
模数为质数且均相同
不同的不会，不是质数的更不会
阅读全文 »

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
高斯消元
然后搜索
枚举每个自由变量的值
为了方便确定自由变量的位置
a[i][i]=0表示i是自由变量
也就是将系数矩阵消成对角线
若对角线上为1，则1上面为0
若对角线上为0，则0上面可能有1
也就是是说
高斯消元不必消成行阶梯形
（a[i][j]==0写成a[i][j]，小错误要避免）
meet in the middle也能做
比高斯消元慢一点（不过感觉搜索的复杂度更没有保证啊。。）
代码抄hzwer
阅读全文 »

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
a*1+b*0=a
a*0+b*1=b
等式右边作辗转相除
设
ax''+by''=t1
ax' +by' =t2
ax  +by  =t1-t1/t2*t2
令q=t1/t2,r=t1%t2
则
x=x''-qx'
y=y''-qy'
当r=0时结束
阅读全文 »

发表于 
1
2
3
4
5
裸的异或方程组
注意记录最多用到哪个方程
不用bitset不开O2会t3个点
当然要用bitset啦（操作复杂度为bitset除以字长，大概就是cpu一次能处理字长长度的bit位吧——bx2k）
最快的同学是一边读一边高斯消元的，高级
阅读全文 »

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
高斯消元解决异或方程组
异或方程组为
a11·x1^a12·x2^...^a1n·xn=y1
a21·x1^a22·x2^...^a2n·xn=y2
...
an1·x1^an2·x2^...^ann·xn=yn
增广矩阵为
a11 a12 ... a1n y1
a21 a22 ... a2n y2
...
an1 an2 ... ann yn
所有a,x,y均是0/1
消元的时候将某一行加到另一行
相当于某一行异或到另一行（因为是模2的！！）
bitset空间消耗更小
但是bitset的每一位是1bit，不是c++基本类型，不能^=(a[i]^=j不行，a^=j可以)
阅读全文 »

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
套路的贪心
假如只有一个窗口，可以证明按吃饭时间降序排是最优的
先排序
然后将人按顺序分到两个窗口
这样就可以dp了
f[i][j]表示安排完第i个人，第一队的排队时间为j，的最小吃饭时间
sum[i]表示前i人的排队时间和
f[i][j]=min(f[i][j],max(f[i-1][j],sum[i]-j+a[i].y)) (j=0 to sum[i-1])
f[i][j]=min(f[i][j],max(f[i-1][j-a[i].x],j+a[i].x+a[i].y)) (j=a[i].x to sum[i])
观察到上下两个方程的范围正好差一个a[i].x
可以像01背包一样减一维
将j降序遍历
还有一个更厉害的做法
随机化。。
既然是随机化就有风险
随机化数组用到n+1就能a了（不管用不用srand(time(0)))
开到n+10就会出现wa了（用了70，不用80）
随机有风险，考试需谨慎
阅读全文 »