【训练】算法竞赛进阶指南-3数学30题

本处难度分档以个人实力为参照系
难度1:半小时内想出,半小时内ac
难度2:半小时想不出,看题解,服气
难度3:半小时想不出,看题解,ac后依然觉得难度很大

0x30 数学

题目

1 poj2689 Prime Distance

7.19 难度2

请先思考后再展开

有一个很妙的做法:采用类似埃筛的方法筛素数
所以只要线性预处理出前面$\sqrt R$内的素数p,然后在后面搞一搞就好了

复杂度计算:
$$
O(
\sum_{质数p \leq \sqrt R} \frac{R-L}{p}
)
$$
然后根据什么调和级数之类的东西,$1+1/2+1/3+1/4….1/n ≈ log_2 n$
所以说复杂度就大概是$O((R-L) \times log_2 \sqrt R)$

最后提醒各位特判一下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
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=310;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
const int MAXNUM=100000;
int pr=0,prime[MAXNUM];
bool v[MAXNUM];
void pre()
{
for(int i=2;i<MAXNUM;i++)
{
if(!v[i]) prime[++pr]=i;
for(int j=1;j<=pr and i*prime[j]<MAXNUM;j++)
{
v[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
bool bk[1100000];
int main()
{
pre();
int l,r;
while(scanf("%d%d",&l,&r)!=EOF)
{
memset(bk,1,sizeof bk);
if(l==1) bk[0]=0;//debug
for(int i=1;i<=pr;i++)
for(int j=l/prime[i];j<=r/prime[i];j++)
if(l<=j*prime[i] and j>1)
bk[j*prime[i]-l]=0;//debug
bool two=0;
int mix=0,miy=INF,mxx=0,mxy=0,lst=0;
for(int i=0;i<=r-l;i++)
{
if(!bk[i]) continue;
int tmp=l+i;
if(lst>0 and tmp-lst<miy-mix) mix=lst,miy=tmp,two=1;
if(lst>0 and tmp-lst>mxy-mxx) mxx=lst,mxy=tmp,two=1;
lst=tmp;
}
if(two) printf("%d,%d are closest, %d,%d are most distant.\n",mix,miy,mxx,mxy);
else puts("There are no adjacent primes.");
}
}

2 3101 阶乘分解

7.19 难度1

请先思考后再展开

枚举素数p,考虑贡献,对于次幂为1,有$\frac{n}{p}$个
对于次幂为t,有$\frac{n}{p^t}$个,新贡献恰好为$\frac{n}{p^t}$
所以,枚举每个素数,然后以log的时间计算贡献即可

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=1100000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
const int MAXNUM=1000000;
int pr=0,prime[MAXNUM];
bool v[MAXNUM];
void pre()
{
for(int i=2;i<MAXNUM;i++)
{
if(!v[i]) prime[++pr]=i;
for(int j=1;j<=pr and i*prime[j]<MAXNUM;j++)
{
v[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
int main()
{
pre();
int n;scanf("%d",&n);
for(int k=1;k<=pr;k++)
{
int tot=0;
for(ll kn=prime[k];kn<=n;kn*=prime[k]) tot+=n/kn;
if(tot>0) printf("%d %d\n",prime[k],tot);
}
}

3 HAOI2007 反素数

8.6 难度2

请先思考后再展开

找找反素数共有的性质吧

性质1:如果约数个数相同,根据性质,应该取最小的

性质2:素因子只有2,3,5,7,11,13,17,19,23
证明:
回忆约数个数公式,只与每个素数的次幂有关。
如果使用更大的素因子,前面这9个中至少有一个空缺(否则超出题目范围)
如果用这个空缺替换,次幂不变,会得到更小的数字,违背性质1

性质3:若将反素数表示为
$
2^{k_2} \times
3^{k_3} \times
5^{k_5} \times
7^{k_7} \times
11^{k_{11}} \times
13^{k_{13}} \times
17^{k_{17}} \times
19^{k_{19}} \times
23^{k_{23}}
$

$
k_2 \geq
k_3 \geq
k_5 \geq
k_7 \geq
k_{11} \geq
k_{13} \geq
k_{17} \geq
k_{19} \geq
k_{23} \geq
0
$
证明:
如果不递减,把某个逆序对交换后,
可以得到相同约数下更小的数字,违背性质1

最后用dfs枚举一下就好了

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int mxn;
int mxg=1,ans=1;//最小
const int p[10]={0,2,3,5,7,11,13,17,19,23};
int k[10];
void dfs(int now,int nowg,int num)
{
if(num>mxn) return;
if(now==10)
{
if(nowg>mxg) mxg=nowg,ans=num;
else if(nowg==mxg and num<ans) ans=num;//debug,不能保证数字递增
return;
}
int tmp=1;
for(int i=0;i<=k[now-1] and tmp<=mxn and ll(num)*tmp<=mxn;i++)//debug num写成now
{
k[now]=i;
dfs(now+1,nowg*(i+1),num*tmp);
tmp*=p[now];
}
}
int main()
{
scanf("%d",&mxn);
k[0]=30;
dfs(1,1,1);
printf("%d",ans);
}

4 CQOI2007 余数求和

8.6 难度1

请先思考后再展开

先化简柿子
$
ans
=\sum_{i=1}^n k-\lfloor \frac{k}{i} \rfloor \times i
=nk - \sum_{i=1}^k \lfloor \frac{k}{i} \rfloor \times i
$
这是因为当i>k时,结果就是k

然后这东西初看时线性的,还是会超时
如果有经验的话,可以一眼看出用一个技巧解决
详见套路集锦中枚举方法3
本来不知道怎么算复杂度,反正比k小,曾经听说期望根号
现在已经把书上的证明补充上去了,其实也不复杂

总之就这样枚举过去,等差数列推推柿子就好了

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int main()
{
int n,k;scanf("%d%d",&n,&k);
ll ans=ll(n)*k;
for(int i=1;i<=k and i<=n;)//debug 也要判n
{
int lst=k/(k/i);
if(lst>n) lst=n;//debug
ans-=ll(k/i)*(i+lst)*(lst-i+1)/2;//debug long long
i=lst+1;
}
printf("%lld",ans);
}

5 poj3090 Visible Lattice Points

8.7 难度2

请先思考后再展开

先分析题目,不难发现要求的是gcd(1~n,1~n)=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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
const int MAXNUM=1001;
int prime[MAXNUM],pr=0;
bool v[MAXNUM];
int mu[MAXNUM];
void pre()
{
mu[1]=1;
for(int i=2;i<MAXNUM;i++)
{
if(!v[i]) prime[++pr]=i,mu[i]=-1;
for(int j=1;j<=pr and i*prime[j]<MAXNUM;j++)
{
v[i*prime[j]]=1;
if(i%prime[j]==0) break;//mu=0
else mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<MAXNUM;i++) mu[i]+=mu[i-1];
}
int main()
{
pre();
int T;scanf("%d",&T);int ct=0;
while(T--)
{
int n;scanf("%d",&n);
int f1=0;
for(int i=1;i<=n;)
{
int lst=n/(n/i);
int F=(n/i)*(n/i);
f1+=(mu[lst]-mu[i-1])*F;
i=lst+1;
}
printf("%d %d %d\n",++ct,n,2+f1);
}
}

那么我们尝试用欧拉搞一搞
其实就是因为长宽相同,那么对于每一列,累加一下欧拉就好了

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<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
const int MAXNUM=1001;
int prime[MAXNUM],pr=0;
bool v[MAXNUM];
int phi[MAXNUM];
void pre()
{
phi[1]=1;
for(int i=2;i<MAXNUM;i++)
{
if(!v[i]) prime[++pr]=i,phi[i]=i-1;
for(int j=1;j<=pr and i*prime[j]<MAXNUM;j++)
{
v[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
int main()
{
pre();
int T;scanf("%d",&T);int ct=0;
while(T--)
{
int n;scanf("%d",&n);
int ans=0;
for(int i=2;i<=n;i++) ans+=phi[i];
printf("%d %d %d\n",++ct,n,3+ans*2);
}
}

6 poj3696 The Luckiest number

8.7 难度3

请先思考后再展开

x个8连在一起的数字,可以用$\frac{8}{9} (10^x-1)$表示
那么题目要求$L | \frac{8}{9} (10^x-1)$
等效于$9L | 8(10^x-1)$
设$d=gcd(L,8)$假设条件满足,那么L中的偶因子是8的约数
两边同时除以d后,左边不再有偶因子,则右边剩下的偶因子没有意义
$\frac{9L}{d} | 10^x-1$
转化成$10^x=1 (\mod \frac{9L}{d})$

当$gcd(10,\frac{9L}{d})=1$时,
根据中欧拉函数与欧拉定理的定理8
可枚举其约数,快速幂判断即可

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
ll gcd(ll x,ll y) {return (y==0)?x:gcd(y,x%y);}
ll qmul(ll a,ll e,ll Mod)
{
ll ans=0;
while(e>0)
{
if(e&1) ans=(ans+a)%Mod;
e>>=1;a=(a+a)%Mod;
}
return ans;
}
ll qpower(ll a,ll e,ll Mod)
{
ll ans=1;
while(e>0)
{
if(e&1) ans=qmul(ans,a,Mod);
e>>=1;a=qmul(a,a,Mod);
}
return ans;
}
ll getphi(ll tmp)
{
ll phi=tmp;
for(ll i=2;i*i<=tmp;i++)
if(tmp%i==0)
{
while(tmp%i==0) tmp/=i;
phi=phi/i*(i-1);//debug phi*(i-1)/i 这里可能爆
}
if(tmp>1) phi=phi/tmp*(tmp-1);//debug
return phi;
}
int main()
{
int ct=0;
while(1)
{
int L;scanf("%d",&L);
if(L==0) break;
printf("Case %d: ",++ct);
ll tmp=(ll)L*9/gcd(L,8);
if(gcd(10,tmp)==1)
{
ll phi=getphi(tmp);
ll ans=phi;
for(ll i=1;i*i<=phi;i++)
if(phi%i==0)
{
if(i<ans and qpower(10,i,tmp)==1) ans=i;
if(i*i!=phi and phi/i<ans and qpower(10,phi/i,tmp)==1) ans=phi/i;
}
printf("%lld\n",ans);
}
else puts("0");
}
}

7 bzoj2973 1801 石头游戏

8.10 难度1

请先思考后再展开

脑残题
但是题目居然不说清楚:如果操作违法,要把它丢掉
还有就是一些sb错误,耽误了一个早上

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int n,m;
struct Matrix
{
ll a[100][100];
Matrix()
{
memset(a,0,sizeof a);
}
};
Matrix pre()
{
Matrix ans;
for(int i=1;i<=90;i++) ans.a[i][i]=1;
return ans;
}
Matrix cheng(Matrix a,Matrix b)
{
Matrix c;
for(int i=1;i<=90;i++)
for(int j=1;j<=90;j++)
for(int k=1;k<=90;k++)
c.a[i][j]+=a.a[i][k]*b.a[k][j];
return c;
}
Matrix qpower(Matrix a,int e)
{
Matrix ans=pre();
while(e>0)
{
if(e&1) ans=cheng(ans,a);
a=cheng(a,a);e>>=1;
}
return ans;
}
int gcd(int a,int b) {return (b==0)?a:gcd(b,a%b);}
int lcm(int a,int b) {return a/gcd(a,b)*b;}
Matrix op[100];
int calc(int x,int y) {return (x-1)*m+y;}
void main()
{
int ti,act;scanf("%d%d%d%d",&n,&m,&ti,&act);
char mp[10][10];
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
int tlen=1;
char oper[10][10];int oplen[10];
for(int i=0;i<=act-1;i++)
{
scanf("%s",oper[i]+1);
oplen[i]=strlen(oper[i]+1);
tlen=lcm(tlen,oplen[i]);
}
int now[10];for(int i=0;i<=act-1;i++) now[i]=1;//debug 忘记初始化
Matrix all=pre();
for(int s=1;s<=tlen;s++)
{
op[s]=pre();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int id=mp[i][j]-'0',t=now[id];
if(isdigit(oper[id][t])) op[s].a[calc(i,j)][n*m+1]=oper[id][t]-'0';
else if(oper[id][t]=='D') op[s].a[calc(i,j)][calc(i,j)]=0;
else//推
{
op[s].a[calc(i,j)][calc(i,j)]=0;
int nx=i,ny=j;
if(oper[id][t]=='N') nx--;if(oper[id][t]=='S') nx++;
if(oper[id][t]=='W') ny--;if(oper[id][t]=='E') ny++;
if(1<=nx and nx<=n and 1<=ny and ny<=m) op[s].a[calc(nx,ny)][calc(i,j)]=1;
}
}
all=cheng(op[s],all);
for(int i=0;i<=act-1;i++) if( (++now[i])==oplen[i]+1) now[i]=1;//debug 本来写(++now[i])==oplen[i]
}
Matrix st;st.a[n*m+1][1]=1;
Matrix tmp=pre();for(int s=ti%tlen;s>=1;s--) tmp=cheng(tmp,op[s]);
st=cheng( cheng(tmp,qpower(all,ti/tlen)) ,st);
ll ans=0;
for(int i=1;i<=n*m;i++) if(st.a[i][1]>ans) ans=st.a[i][1];
printf("%lld",ans);
}
};
int main()
{
mine::main();
}

8 JSOI2008 球形空间产生器

8.10 难度2

请先思考后再展开

先推推柿子
如果把n+1个点,与球心的距离表示出来,会得出一个多元二次方程组
为了变成一次,考虑把相邻的相减
$\sum (a_{i,j}-x_j)^2-(a_{i+1,j}-x_j)^2=0$
$\sum 2(a_{i+1,j}-a_{i,j})x_j=\sum a_{i+1,j}^2-a_{i,j}^2$
然后高斯消元就好了

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
double myabs(double x) {return x>0?x:-x;}
const double eps=1e-8;
const int MAXN=20;
double p[MAXN][MAXN];
double a[MAXN][MAXN],b[MAXN];//系数、常数
void gauss(int n)
{
for(int i=1;i<=n;i++)//目标为xi
{
int nx=-1;
for(int j=i;j<=n;j++) if(myabs(a[j][i])>eps) {nx=j;break;}
if(nx<0) continue;
swap(b[i],b[nx]);for(int k=1;k<=n;k++) swap(a[i][k],a[nx][k]);
for(int j=1;j<=n;j++)
{
if(i==j) continue;
double t=a[j][i]/a[i][i];//确保分母不为0
b[j]-=b[i]*t;for(int k=i;k<=n;k++) a[j][k]-=a[i][k]*t;
}
}
}
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n+1;i++)
for(int j=1;j<=n;j++)
scanf("%lf",&p[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
a[i][j]=2*(p[i+1][j]-p[i][j]);
b[i]+=p[i+1][j]*p[i+1][j]-p[i][j]*p[i][j];
}
gauss(n);
for(int i=1;i<=n;i++) printf("%.3lf ",b[i]/a[i][i]);
}
};
int main()
{
mine::main();
}

9 poj1830 开关问题

8.10 难度2

请先思考后再展开

如果把异或看做是不进位的加法,那么就很好理解了

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
const int MAXN=40;
int n;
int p[MAXN][MAXN];
int a[MAXN][MAXN],b[MAXN];//系数、常数
bool iszero(int i)
{
for(int j=1;j<=n;j++) if(a[i][j]>0) return 0;
return 1;
}
int gauss()
{
for(int i=1;i<=n;i++)
{
int nx=-1;
for(int j=i;j<=n;j++) if(a[j][i]>0) {nx=j;break;}
if(nx<0) continue;
swap(b[i],b[nx]);for(int k=1;k<=n;k++) swap(a[i][k],a[nx][k]);
for(int j=1;j<=n;j++)
{
if(i==j or !a[j][i]) continue;
b[j]^=b[i];for(int k=i;k<=n;k++) a[j][k]^=a[i][k];
}
}
int tot=0;//主元
for(int i=1;i<=n;i++)
if(!iszero(i)) tot++;
else if(b[i]!=0) return -1;
return 1<<(n-tot);
}
void main()
{
int T;scanf("%d",&T);
while(T--)
{
memset(a,0,sizeof a);
scanf("%d",&n);
for(int i=1;i<=n;i++) a[i][i]=1,scanf("%d",&b[i]);
for(int i=1;i<=n;i++) {int t;scanf("%d",&t);b[i]^=t;}
while(1)
{
int x,y;scanf("%d%d",&x,&y);
if(x==0 and y==0) break;
a[y][x]=1;//debug 要反过来
}
int ans=gauss();
if(ans>0) printf("%d\n",ans);
else puts("Oh,it's impossible~!!");
}
}
};
int main()
{
mine::main();
}

10 JLOI2015 装备购买

8.11 难度2

请先思考后再展开

卡精度,要开long double
所以决定以后无脑long double了hh

为了做第二问,贪心地每次找最小的作为主元
证明不会,但是我构造不出反例
本来以为找到一个:
3 2
3 0
4 4
5 0
2 1 3
但其实,经过消元,第一行不会是0
如果非要是0,那么第二行一定是第一行的倍数,则也能反过来……(感觉我表述得乱七八糟,意会一下吧)

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
#define double long double
double myabs(double x) {return x>0?x:-x;}
const double eps=1e-8;
int n,m;
double a[510][510],c[510];
int tot=0;double sum=0;
void gauss()
{
for(int i=1;i<=m;i++)
{
int nx=-1;
for(int j=tot+1;j<=n;j++)
if(myabs(a[j][i])>eps)
if(nx<0 or c[nx]>c[j]) nx=j;
if(nx<0) continue;
tot++;sum+=c[nx];
for(int k=1;k<=m;k++) swap(a[tot][k],a[nx][k]);
swap(c[tot],c[nx]);//debug 漏了
for(int j=1;j<=n;j++)
{
if(tot==j or myabs(a[j][i])<=eps) continue;
double t=a[j][i]/a[tot][i];
for(int k=i;k<=m;k++) a[j][k]-=a[tot][k]*t;
}
}
}
void main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%Lf",&a[i][j]);
for(int i=1;i<=n;i++) scanf("%Lf",&c[i]);
gauss();
printf("%d %.0Lf",tot,sum);
}
};
int main()
{
mine::main();
}

11 Hdu3949 XOR

8.11 难度2

请先思考后再展开

key:
高斯消元后,得到的简化阶梯形矩阵,具有一个重要的性质————对于主元i,该列上唯一的1在这上面
所以说,在其他相同的情况下,选i一定比不选要大
所以说,可以把k按二进制拆分,按位,对应于要不要选择第i行

细节:
注意0,线性基可以通过【自己异或自己】得出,但本题不行
所以说特判一下最后的矩阵,就好了,具体自己分析

最后补充一下【异或线性基组合出来的数(即span张成)互不相同】的证明:
假设有一个柿子,左右两边都是异或出来的数字,把左边留下某一个,
其他移项到右边,那么出现,那个数字能被其他数字表示出,则违反线性基定义

顺便说说异或能移项的证明:把两边同时异或那个数

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
ll bin[70];
int n;
bool zero;
ll a[11000];
int tot;//线性基长度
void gauss()
{
zero=0;tot=0;
for(int i=60;i>=0;i--)
{
int nx=tot+1;
while( !(a[nx]&bin[i]) and nx<=n ) nx++;
if(nx>n) continue;
tot++;swap(a[tot],a[nx]);
for(int k=1;k<=n;k++)
if(k!=tot and a[k]&bin[i])
a[k]^=a[tot];
}
if(tot<n) zero=1;
}
ll solve()
{
ll k;scanf("%lld",&k);
if(zero) k--;//能产生0时,k=1得0,k=2得最小
if(k>bin[tot]-1) return -1;//去除【什么都不选的情况】
ll ans=0;
for(int i=0;i<=tot-1;i++) if(k&bin[i]) ans^=a[tot-i];
return ans;
}
void main()
{
bin[0]=1;for(int i=1;i<=60;i++) bin[i]=bin[i-1]<<1;
int T;scanf("%d",&T);
for(int ct=1;ct<=T;ct++)
{
printf("Case #%d:\n",ct);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
gauss();
int q;scanf("%d",&q);
while(q--) printf("%lld\n",solve());
}
}
};
int main()
{
mine::main();
}

12 3602 Counting Swaps

8.13 难度3

请先思考后再展开

多重集组合数

假如写出前面的几个数(谁会这样啊……都退出柿子了,也好像化简不出什么):
1,1,3,16,125
会发现$s[n]=n^{n-2}$

对于k个长度分别为l1,l2,…,lk的环
$ans=\prod s[l_1]s[l_2]s[l_k]\frac{(n-k)!}{(l_1-1)!(l_2-1)!…(l_k-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
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAXN=110000;
const int MOD=1e9+9;
ll fac[MAXN];
ll qpower(ll a,int e)
{
ll ans=1;
while(e>0)
{
if(e&1) ans=ans*a%MOD;
a=a*a%MOD;e>>=1;
}
return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;y=0;
return a;
}
ll tx,ty;
ll d=exgcd(b,a%b,tx,ty);
x=ty;
y=tx-(a/b)*ty;
return d;
}
ll inv(ll a)
{
ll x,y;
exgcd(a,MOD,x,y);
return (x%MOD+MOD)%MOD;
}
int p[MAXN];
bool v[MAXN];
int getsiz(int x)
{
int now=p[x],tot=1;
v[x]=1;
while(now!=x)
{
v[now]=1;
tot++;
now=p[now];
}
return tot;
}
void main()
{
fac[0]=1;for(int i=1;i<MAXN;i++) fac[i]=fac[i-1]*i%MOD;
int T;scanf("%d",&T);
while(T--)
{
memset(v,0,sizeof v);
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
ll ans=1;int tot=0;
for(int i=1;i<=n;i++)
if(!v[i])
{
int l=getsiz(i);tot++;
ans=ans*qpower(l,l-2)%MOD;
ans=ans*inv(fac[l-1])%MOD;
}
printf("%lld\n",ans*fac[n-tot]%MOD);
}
}
};
int main()
{
mine::main();
}

13 CF451E Devu and Flowers

8.16 难度2

请先思考后再展开

多重集组合数裸题,讲解

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const ll MOD=1e9+7;
ll qpower(ll x,ll e)
{
ll ans=1;
while(e>0)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll inv(ll x) {return qpower(x,MOD-2);}
ll C(ll m,ll n)//O(m)
{
if(m<0 or n<0 or m>n) return 0;
ll ans=1;
for(ll t=n;t>=n-m+1;t--) ans=ans*(t%MOD)%MOD;
ll s=1;for(ll t=2;t<=m;t++) s=s*t%MOD;
return ans*inv(s)%MOD;
}
ll a[30];
int bin[30];
void main()
{
bin[0]=1;for(int i=1;i<30;i++) bin[i]=bin[i-1]<<1;
int n;ll m;scanf("%d%I64d",&n,&m);
for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);
ll ans=0;
for(int s=0;s<=bin[n]-1;s++)
{
int num=0;
ll M=n-1,N=(ll)n-1+m;//debug n转longlong
for(int i=0;i<=n-1;i++) if(s&bin[i]) N-=a[i+1]+1,num++;//debug a[i]
if(num&1) ans-=C(M,N);
else ans+=C(M,N);
ans%=MOD;
}
printf("%I64d",(ans+MOD)%MOD);
}
};
int main()
{
mine::main();
}

14 POI2007 ZAP-Queries

8.16 难度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
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAXNUM=51000;
bool v[MAXNUM];
int pr=0,prime[MAXNUM];
int mu[MAXNUM];
void pre()
{
mu[1]=1;
for(int i=2;i<MAXNUM;i++)
{
if(!v[i]) prime[++pr]=i,mu[i]=-1;
for(int j=1;j<=pr and (ll)i*prime[j]<MAXNUM;j++)
{
v[i*prime[j]]=1;
if(i%prime[j]==0) {mu[i*prime[j]]=0;break;}
mu[i*prime[j]]=-mu[i];
}
}
for(int i=2;i<MAXNUM;i++) mu[i]+=mu[i-1];
}
int mymin(int x,int y) {return x<y?x:y;}
void main()
{
pre();
int q;scanf("%d",&q);
while(q--)
{
int a,b,d;scanf("%d%d%d",&a,&b,&d);
int n=a/d,m=b/d;if(n>m) swap(n,m);
ll ans=0;
for(ll d=1;d<=n;)
{
int lst=mymin(n/(n/d),m/(m/d));
ans+=ll(mu[lst]-mu[d-1])*(n/d)*(m/d);
d=lst+1;
}
printf("%lld\n",ans);
}
}
};
int main()
{
mine::main();
}

15 3801 Rainbow的信号

8.16 难度2

请先思考后再展开

期望
位运算的特性在于,不同的二进制位之间没有影响
所以为了方便统计,先枚举每一个位,然后分类讨论

线性枚举r
①and
如果出现了0,就是0
那么最后一个0把前面l的取值范围分成两半,其中只有后面的部分有贡献
所以记录一下lst0
②or
如果出现1,就是1
和and同理,记录lst1
③xor
这个稍微麻烦一些,因为取值涉及到1出现个数的奇偶性
那么把按照1的出现次数,分奇偶,形成交替的区间
那么只有贡献为奇数的区间是有用的
用c0、c1分别记录偶数区间和奇数区间的总长度即可

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
#define double long double
int bin[40];
int a[110000];
void main()
{
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
double xor1=0,and1=0,or1=0;
for(int k=0;k<=29;k++)
{
int lst0=0,lst1=0;//上一个
int c1=0,c0=0;//奇偶区间
for(int r=1;r<=n;r++)
{
int now=a[r]&bin[k];
//l=r
if(now) xor1+=bin[k],and1+=bin[k],or1+=bin[k];
//l<r
if(now)
{
xor1+=2.0*c0*bin[k];
and1+=2.0*(r-lst0-1)*bin[k];//lst0+1~r
or1+=2.0*(r-1)*bin[k];//1~lst1
}
else
{
xor1+=2.0*c1*bin[k];
or1+=2.0*lst1*bin[k];//1~lst1
}
//update
if(now) lst1=r; else lst0=r;
if(now) swap(c1,c0),c1++; else c0++;
}
}
printf("%.3Lf %.3Lf %.3Lf",xor1/n/n,and1/n/n,or1/n/n);
}
};
int main()
{
mine::main();
}

16 3802 绿豆蛙的归宿

8.16 难度2

请先思考后再展开

期望的线性性

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
const int MAXN=110000,MAXM=210000;
struct Nod
{
int hou;
int ru;
int backup;
Nod()
{
hou=ru=0;
}
}p[MAXN];
struct Edge
{
int y,c,g;
}e[MAXM];
int ln=0;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=p[x].hou;p[x].hou=ln;
p[y].ru++;
}
double E[MAXM];
int sta[MAXN];
void topsort(int st)
{
int top=0;sta[++top]=st;
while(top>0)
{
int x=sta[top--];
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
p[y].ru--;
E[y]+=(E[x]+e[k].c)/p[y].backup;
if(!p[y].ru) sta[++top]=y;
}
}
}
void main()
{
int n,m;scanf("%d%d",&n,&m);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
ins(b,a,c);
}
for(int i=1;i<=n;i++) p[i].backup=p[i].ru;
topsort(n);
printf("%.2lf",E[1]);
}
};
int main()
{
mine::main();
}

17 3803 扑克牌

8.16 难度2

请先思考后再展开

本来写的是倒着dp,好像被卡边界了
结果tm改成记忆化搜索就过了??

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
double mymin(double x,double y) {return x<y?x:y;}
int A,B,C,D;
double f[20][20][20][20][5][5];
bool v[20][20][20][20][5][5];
double dp(int a,int b,int c,int d,int x,int y)
{
if(v[a][b][c][d][x][y]) return f[a][b][c][d][x][y];
v[a][b][c][d][x][y]=1;
double &ans=f[a][b][c][d][x][y];
int aa=a+(x==1)+(y==1),bb=b+(x==2)+(y==2),cc=c+(x==3)+(y==3),dd=d+(x==4)+(y==4);
if(aa>=A and bb>=B and cc>=C and dd>=D) return ans=0;
int left=54-aa-bb-cc-dd;
if(a<13) ans+=(dp(a+1,b,c,d,x,y)+1)*(13-a)/left;
if(b<13) ans+=(dp(a,b+1,c,d,x,y)+1)*(13-b)/left;
if(c<13) ans+=(dp(a,b,c+1,d,x,y)+1)*(13-c)/left;
if(d<13) ans+=(dp(a,b,c,d+1,x,y)+1)*(13-d)/left;
if(x==0) {double mi=1000;for(int i=1;i<=4;i++) {mi=mymin(mi,dp(a,b,c,d,i,y));}ans+=(mi+1)/left;}
if(y==0) {double mi=1000;for(int i=1;i<=4;i++) {mi=mymin(mi,dp(a,b,c,d,x,i));}ans+=(mi+1)/left;}
return ans;
}
void main()
{
scanf("%d%d%d%d",&A,&B,&C,&D);
int p1=(A>13)?A-13:0,p2=(B>13)?B-13:0,p3=(C>13)?C-13:0,p4=(D>13)?D-13:0;
if(p1+p2+p3+p4>2) puts("-1.000");
else printf("%.3lf",dp(0,0,0,0,0,0));
}
};
int main()
{
mine::main();
}

18 poj2311 Cutting Game

8.17 难度2

请先思考后再展开

博弈
不过,如果出现(1,1),并定义为必败态,本身没有问题
但考虑只有一行或一列的情况,会把两个有向图游戏异或起来,
然后对方就会“努力翻盘”,导致本来游戏早就结束,却被“莫名其妙翻盘了”
所以要跳过这些状态,并早点判断出必败态:(2,2)和(2,3)

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
int sg[210][210];
bool v[210][210];
bool b[410];//每次产生不同,最多只有400个
int SG(int n,int m)
{
if(n>m) swap(n,m);
if(v[n][m]) return sg[n][m];
v[n][m]=1;
if(n==1 and m==1) return sg[n][m]=0;
//if(n==2 and m==2) return sg[n][m]=0;
//if(n==2 and m==3) return sg[n][m]=0;
memset(b,0,sizeof b);
for(int k=2;k<=n-2;k++) b[ SG(k,m)^SG(n-k,m) ]=1;
for(int k=2;k<=m-2;k++) b[ SG(n,k)^SG(n,m-k) ]=1;
int now=0;while(b[now]) now++;
return sg[n][m]=now;
}
void main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(SG(n,m)>0) puts("WIN");
else puts("LOSE");
}
}
};
int main()
{
mine::main();
}

0x3B 数学练习

题目

19 SDOI2012 Longge的问题

8.17 难度2

请先思考后再展开

按照反素数的思路,只考虑前面几个素数,按照约数个数公式dfs
最终得出,在int范围内约数最多约1500个

那么,如果枚举约数s,把它作为gcd的结果
$\sum s \times 【gcd(1 \to n,n)=s的个数】$
$\sum s \times 【gcd(1 \to n/s)=1的个数】$
$\sum s \times \varphi (n/s)$

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
ll phi(ll x)
{
ll ans=x;
for(ll t=2;t*t<=x;t++)
{
if(x%t!=0) continue;
while(x%t==0) x/=t;
ans=ans/t*(t-1);
}
if(x>1) ans=ans/x*(x-1);
return ans;
}
void main()
{
ll n;scanf("%lld",&n);
ll ans=0;
for(ll k=1;k*k<=n;k++)
{
if(n%k!=0) continue;
ans+=k*phi(n/k);
if(k*k!=n) ans+=n/k*phi(k);
}
printf("%lld",ans);
}
};
int main()
{
mine::main();
}

20 bzoj1477 poj1061 青蛙的约会

8.17 难度1

请先思考后再展开

同余方程组裸题
t(n-m)+kL=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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0) {x=1,y=0;return a;}
ll tx,ty;ll d=exgcd(b,a%b,tx,ty);
x=ty;y=tx-(a/b)*ty;
return d;
}
void main()
{
ll x,y,m,n,L;scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L);
ll A=n-m,B=L,K=x-y;
ll tx,ty;
ll d=exgcd(A,B,tx,ty);//t(n-m)+kL=x-y
if(K%d!=0) puts("Impossible");
else
{
tx=tx*(K/d);
ll t=B/d;
printf("%lld",(tx%t+t)%t);
}
}
};
int main()
{
mine::main();
}

21 3B04 Xiao 9*大战朱最学

8.17 难度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
38
39
40
41
42
43
44
45
46
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0) {x=1,y=0;return a;}
ll tx,ty;ll d=exgcd(b,a%b,tx,ty);
x=ty;y=tx-(a/b)*ty;
return d;
}
void main()
{
int n;scanf("%d",&n);
ll a1,b1;scanf("%lld%lld",&a1,&b1);
for(int i=2;i<=n;i++)
{
ll a2,b2;scanf("%lld%lld",&a2,&b2);
ll A=a1,B=a2,K=b2-b1;
ll k1,k2;ll d=exgcd(A,B,k1,k2);
k1=k1*(K/d);
ll t=B/d;k1=(k1%t+t)%t;
b1=k1*a1+b1;
a1=a1*a2;
}
printf("%lld",b1);
}
};
int main()
{
mine::main();
}

22 SDOI2011 计算器

8.17 难度2

请先思考后再展开

裸题

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
ll qpower(ll x,ll e,ll MOD)
{
ll ans=1;x%=MOD;
while(e>0)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0) {x=1,y=0;return a;}
ll tx,ty;ll d=exgcd(b,a%b,tx,ty);
x=ty;y=tx-(a/b)*ty;
return d;
}
void solve2(ll A,ll B,ll K)
{
ll x,y;ll d=exgcd(A,B,x,y);
if(K%d!=0) puts("Orz, I cannot find x!");
else
{
x*=(K/d);
ll t=B/d;
printf("%lld\n",(x%t+t)%t);
}
}
map<ll,ll> hash;
void solve3(ll A,ll z,ll MOD)
{
if(A%MOD==0) {puts("Orz, I cannot find x!");return;}//debug
A%=MOD;z%=MOD;
hash.clear();
ll t=ceil(sqrt( (double)MOD ));
ll now=z;for(ll b=0;b<=t;b++) hash[now]=b,now=now*A%MOD;
ll tmp=qpower(A,t,MOD);
now=tmp;
for(ll a=1;a<=t;a++)
{
if(hash.count(now)) {printf("%lld\n",a*t-hash[now]);return;}
now=now*tmp%MOD;
}
puts("Orz, I cannot find x!");
}
void main()
{
int T,k;scanf("%d%d",&T,&k);
while(T--)
{
ll y,z,p;scanf("%lld%lld%lld",&y,&z,&p);
if(k==1) printf("%lld\n",qpower(y,z,p));
else if(k==2) solve2(y,p,z);
else solve3(y,z,p);
}
}
};
int main()
{
mine::main();
}

23 hdu5015 233 Matrix

8.17 难度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
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const ll MOD=10000007;
struct Matrix
{
ll a[30][30];
Matrix() {memset(a,0,sizeof a);}
};
const int N=20;
Matrix pre()
{
Matrix ans;
for(int i=0;i<=N;i++) ans.a[i][i]=1;
return ans;
}
Matrix cheng(Matrix a,Matrix b)
{
Matrix ans;
for(int i=0;i<=N;i++)
for(int j=0;j<=N;j++)
for(int k=0;k<=N;k++)
ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j]%MOD)%MOD;
return ans;
}
Matrix qpower(Matrix x,int e)
{
Matrix ans=pre();
while(e>0)
{
if(e&1) ans=cheng(ans,x);
x=cheng(x,x);e>>=1;
}
return ans;
}
void main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
Matrix st;st.a[0][0]=0;
for(int i=1;i<=n;i++) scanf("%lld",&st.a[i][0]);
st.a[++n][0]=233;st.a[++n][0]=1;
Matrix op;
for(int i=0;i<=n-2;i++)
{
for(int j=1;j<=i;j++) op.a[i][j]=1;
op.a[i][n-1]=1;
}
op.a[n-1][n-1]=10;op.a[n-1][n]=3;//233=>2333
op.a[n][n]=1;//1=>1
st=cheng(qpower(op,m),st);
printf("%lld\n",st.a[n-2][0]);
}
}
};
int main()
{
mine::main();
}

24 poj2947 Widget Factory

8.18 难度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
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
int qpower(int x,int e,int MOD)
{
int ans=1;
while(e>0)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
int inv(int x,int MOD) {return qpower(x,MOD-2,MOD);}
int a[310][310],b[310],MOD=7;
bool iszero(int x,int m)
{
for(int i=1;i<=m;i++) if(a[x][i]) return 0;
return 1;
}
void gauss(int n,int m)
{
int tot=0;
for(int i=1;i<=m;i++)//目标
{
int nx=-1;
for(int j=tot+1;j<=n;j++) if(a[j][i]) {nx=j;break;}
if(nx<0) continue;
tot++;swap(b[tot],b[nx]);for(int k=1;k<=m;k++) swap(a[tot][k],a[nx][k]);
for(int j=1;j<=n;j++)
{
if(tot==j or !a[j][i]) continue;
int x=a[j][i],y=a[tot][i];
for(int k=1;k<=m;k++)
{
a[tot][k]=a[tot][k]*x%MOD;
a[j][k]=a[j][k]*y-a[tot][k];
a[j][k]=(a[j][k]%MOD+MOD)%MOD;
}
b[tot]=b[tot]*x%MOD;
b[j]=b[j]*y%MOD-b[tot];
b[j]=(b[j]%MOD+MOD)%MOD;
}
}
for(int i=1;i<=n;i++) if(iszero(i,m) and b[i]!=0) {puts("Inconsistent data.");return;}
if(tot!=m) {puts("Multiple solutions.");return;}
for(int i=1;i<=m-1;i++) {int t=b[i]*inv(a[i][i],MOD)%MOD;printf("%d ",t>=3?t:t+7);}
int t=b[m]*inv(a[m][m],MOD)%MOD;printf("%d\n",t>=3?t:t+7);//debug 题目条件,3~9
}
char s[20];
int getday()
{
scanf("%s",s+1);
if(s[1]=='M') return 1;//MON
if(s[3]=='E') return 2;//TUE
if(s[1]=='W') return 3;//WED
if(s[2]=='H') return 4;//THU
if(s[1]=='F') return 5;//FRI
if(s[2]=='A') return 6;//SAT
return 7;
}
void main()
{
while(1)
{
int n,m;scanf("%d%d",&n,&m);
if(n==0 and m==0) break;
memset(a,0,sizeof a);//debug
for(int i=1;i<=m;i++)
{
int k;scanf("%d",&k);
int t1=getday(),t2=getday();
b[i]=((t2-t1+1)%MOD+MOD)%MOD;
while(k--)
{
int t;scanf("%d",&t);
a[i][t]=(a[i][t]+1)%MOD;
}
}
gauss(m,n);
}
}
};
int main()
{
mine::main();
}

25 WC2011 最大XOR和路径

8.18 难度2

请先思考后再展开

这道神题的关键在于 利用异或的抵消性质
当然交换、结合律也稍微要用到

对于一个路径,其实就是由链和在上面重叠的环组成
这样以后,你会发现,能对最终答案产生影响的就是一条链和几个环
因为对于重叠的部分或者为了到达环而经过的边(如果原路返回)被自己抵消了
因为这是一个无向图,如果有多条可选的链,而最优的不是这一条,
那当前这一条和它组成了一个环,所以说枚举环的时候异或一下,
自己就又被抵消了,变成了那条链

所以说,随便找一个链,找一些环放上去,让异或和最大
想到异或和会想到线性基
那怎么找环呢?dfs去找不难想到,但枚举起点复杂度过高
其实直接从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
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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAXN=51000;
ll bin[61];
ll bs[61];
void insert(ll now)
{
for(int i=60;i>=0;i--)
if(now&bin[i])
{
if(bs[i]<0)
{
bs[i]=now;
for(int j=60;j>i;j--) if(bs[j]&bin[i]) bs[j]^=now;//回代
break;
}
else now^=bs[i];
}
}
struct Nod
{
int hou;
bool v;
ll sum;
Nod()
{
hou=0;
sum=0;
v=0;
}
}p[MAXN];
struct Edge
{
int y,g;
ll c;
}e[MAXN*4];
int ln=0;
void ins(int x,int y,ll c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=p[x].hou;p[x].hou=ln;
}
void dfs(int x,ll now)
{
p[x].v=1;p[x].sum=now;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].v) insert(now^e[k].c^p[y].sum);
else dfs(y,now^e[k].c);
}
}
ll solve(ll now)
{
for(int i=60;i>=0;i--) if(bs[i]>=0 and (now^bs[i])>now) now=now^bs[i];
return now;
}
void main()
{
bin[0]=1;for(int i=1;i<=60;i++) bin[i]=bin[i-1]<<1;
int n,m;scanf("%d%d",&n,&m);
while(m--)
{
int x,y;ll c;scanf("%d%d%lld",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
memset(bs,-1,sizeof bs);
dfs(1,0);
printf("%lld",solve(p[n].sum));
}
};
int main()
{
mine::main();
}

26 CQOI2013 新Nim游戏

8.19 难度2

请先思考后再展开

根据博弈的基本知识,普通nim游戏在异或和=0的时候必败,否则必胜
那么只要能确保后手无法在第二回合把异或和变成0,那么就胜利

异或和基本上就和线性基有关了,主要是因为,对于异或线性基,
其异或空间除了0,其他的表示方法中每个元素最多用一次

什么情况下,能够把异或和变成0?
就是在某一次插入x中,发现无法插入
因为这意味着,里面的东西能够表示出x
这个时候,当前线性基 xor x=0,后手只要把后面取走就好了
我们的应对策略是把x取走(因为线性基内部,无法表示出0,否则违背定义)

那怎么求第一问,让取走的东西总数最小呢?
有一个精妙的贪心:按照从大到小考虑
这个可以用微扰证明,如果某个位置能用小也能用大,
我们用了大,不会让答案更差,因为线性基能否插入和其他位置无关

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
int bin[40];
int bs[40];
bool insert(int now)
{
for(int i=40;i>=0;i--)
if(now&bin[i])
{
if(bs[i]<0) {bs[i]=now;return 1;}
now^=bs[i];
}
return 0;
}
int a[110];
void main()
{
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
memset(bs,-1,sizeof bs);
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
ll ans=0,sum=0;
for(int i=n;i>=1;i--)
{
sum+=a[i];
if(!insert(a[i])) ans+=a[i];
}
if(ans==sum) puts("-1");
else printf("%lld",ans);
}
};
int main()
{
mine::main();
}

Sdoi2016 排列计数

8.29 难度2

请先思考后再展开

同学提醒这道题漏掉了……所以就没有编号了

把其中m个固定后,剩下的就是错排
发现题目要求的是$C_n^m \times D_{n-m}$

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=1100000;
const ll INF=0x3f3f3f3f;
const ll MOD=1e9+7;
ll fac[MAX_N];
ll D[MAX_N];
ll qpower(ll x,ll e)
{
ll ans=1;
while(e>0)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll inv(ll x) {return qpower(x,MOD-2);}
ll C(int n,int m) {return fac[n]*inv(fac[m])%MOD*inv(fac[n-m])%MOD;}
void main()
{
fac[0]=1;for(int i=1;i<MAX_N;i++) fac[i]=fac[i-1]*i%MOD;
D[0]=1;D[1]=0;D[2]=1;for(int i=3;i<MAX_N;i++) D[i]=(D[i-1]+D[i-2])%MOD*(i-1)%MOD;
int T;scanf("%d",&T);
while(T--)
{
int n,m;scanf("%d%d",&n,&m);
printf("%lld\n",C(n,m)*D[n-m]%MOD);
}
}
};
int main()
{
mine::main();
}

27 poj3904 Sky Code

8.20 难度1

请先思考后再展开

莫反裸题
一开始没想到F(d)那么好求……
复杂度$O(n \sqrt 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
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<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
ll C(ll n)//C(4,n)
{
return n*(n-1)*(n-2)*(n-3)/24;
}
const int MAXNUM=11000;
bool v[MAXNUM];
int pr=0,prime[MAXNUM];
int mu[MAXNUM];
void pre()
{
mu[1]=1;
for(int i=2;i<MAXNUM;i++)
{
if(!v[i]) prime[++pr]=i,mu[i]=-1;
for(int j=1;j<=pr and (ll)i*prime[j]<MAXNUM;j++)
{
v[i*prime[j]]=1;
if(i%prime[j]==0) {mu[i*prime[j]]=0;break;}
mu[i*prime[j]]=-mu[i];
}
}
}
int fd[MAXNUM];
void main()
{
pre();
int n;
while(scanf("%d",&n)!=EOF)
{
memset(fd,0,sizeof fd);
for(int i=1;i<=n;i++)
{
int t;scanf("%d",&t);
for(int j=1;j*j<=t;j++)
{
if(t%j!=0) continue;
fd[j]++;
if(j*j!=t) fd[t/j]++;
}
}
ll ans=0;
for(int i=1;i<=10000;i++) ans+=mu[i]*C(fd[i]);
printf("%lld\n",ans);
}
}
};
int main()
{
mine::main();
}

28 3B13/CF167B/bzoj4636 守卫者的挑战

8.20 难度1

请先思考后再展开

概率dp裸题
但是有很多细节,中文题目不是很清楚

  1. 必须n个都尝试过,最后再离开
  2. 某一时刻可以装不下
    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
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<map>
    #include<set>
    #include<queue>
    #include<deque>
    #include<bitset>
    #include<vector>
    #include<algorithm>
    using namespace std;
    namespace mine
    {
    int mymin(int x,int y) {return x<y?x:y;}
    double f[210][210][410];
    //f(i,vec,k)=【i次开始之前,赢了vec次,当前背包剩余空间为k-200】的概率
    int p[210],a[210];
    void main()
    {
    int n,L,K;scanf("%d%d%d",&n,&L,&K);
    for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    if(K>200) K=200;//debug
    f[1][0][200+K]=1;
    for(int i=1;i<=n;i++)
    for(int vec=0;vec<=i-1;vec++)
    for(int bg=-200;bg<=200;bg++)
    {
    f[i+1][vec+1][200+mymin(bg+a[i],200)]+=f[i][vec][200+bg]*p[i]/100;
    f[i+1][vec][200+bg]+=f[i][vec][200+bg]*(100-p[i])/100;//fail
    }
    double ans=0;
    for(int i=L;i<=n;i++)
    for(int j=0;j<=200;j++)
    ans+=f[n+1][i][200+j];
    printf("%.6lf",ans);
    }
    };
    int main()
    {
    mine::main();
    }

29 poj2976 Dropping tests

8.20 难度2

请先思考后再展开

01分数规划裸题
浮点二分果然练得还是太少了

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAXN=1100;
const double eps=1e-4;
int n,k;
ll a[MAXN],b[MAXN];
double tmp[MAXN];
bool check(double L)
{
for(int i=1;i<=n;i++) tmp[i]=(double)a[i]-L*b[i];
sort(tmp+1,tmp+n+1);
double sum=0;
for(int i=k+1;i<=n;i++) sum+=tmp[i];
return sum>=0;
}
void main()
{
while(1)
{
scanf("%d%d",&n,&k);if(n==0 and k==0) break;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]*=100;
for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
double l=0,r=100,ans=-1;
while(l<=r+eps)//l<r
{
double mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid+eps;
else r=mid-eps;
}
printf("%d\n",int(round(ans)));
}
}
};
int main()
{
mine::main();
}

30 poj1704 Georgia and Bob

8.20 难度2

请先思考后再展开

这是一道传说中的阶梯博弈
其实就是转化为nim游戏

首先,把两堆石子两两捆绑(奇数堆的时候,把第1堆和边界0捆绑)
然后如果每组石子内部,后面的向前移,最多移动就是空格数量
所以如果不考虑前面那个的移动情况,就是一个nim游戏

所以对于先手,如果他是赢家,一定按照nim来
这个时候如果后手突然移动前面,那么先手把后面那个等距离向前移动,
就能还原出相同局面,而且一定能实现
而如果先手是输家,那么和上面同理无法改变结局

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
int sg[11000];
bool v[11000];
bool b[11000];
int SG(int x)
{
if(v[x]) return sg[x];
v[x]=1;
memset(b,0,sizeof b);
for(int y=0;y<=x-1;y++) b[SG(y)]=1;
int now=0;while(b[now]) now++;
return sg[x]=now;
}
int a[1100];
void main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
int now=0;
if(n%2==1) { for(int i=1;i<=n;i+=2) now^=SG(a[i]-a[i-1]-1); }
else { for(int i=2;i<=n;i+=2) now^=SG(a[i]-a[i-1]-1); }
if(now>0) puts("Georgia will win");
else puts("Bob will win");
}
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/82f7.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%