A：卡片
题目
答案
：3181
#include <iostream>
using namespace std;
const int N=100;
int n;
int st[N];
int split(int n)
{
while(n)
{
if(--st[n%10]<0) return false;
n/=10;
}
return true;
}
int main()
{
n=2021;
for(int i=0;i<10;i++) st[i]=n;
int i=1;
while(split(i)) i++;
cout<<i-1<<endl;
return 0;
}
B：直线
题目
题解
- 常规思路用斜率，但这里斜率相同的可能也是不同的直线，由此我们可以存一下该斜率在 y 轴上的截距，就能唯一判断了
-
特殊处理
x1
−
x
2
=
0
x1-x2=0
x
1
−
x
2
=
0
的点（斜率为无穷）：直接加上竖线条数即可 - 也可以先弄出所有直线，排个序方便去重一些，这里就不写了
答案
： 40257
#include <iostream>
#include <cmath>
using namespace std;
const int N=1000010;
const double eps=1e-6;
int n,m;
double st[N],d[N];
int cnt;
bool check(double k,double t)
{
for(int i=0;i<cnt;i++)
{
if(abs(st[i]-k)<eps&&abs(d[i]-t)<eps) return false;
}
d[cnt]=t;
st[cnt++]=k;
return true;
}
int main()
{
//n=20,m=21;
//n=3,m=4; //35
//n=2,m=3; //11
cin>>n;
m=n+1;
int res=0;
for(int x1=0;x1<n;x1++)
for(int y1=0;y1<m;y1++)
for(int x2=0;x2<n;x2++)
for(int y2=0;y2<m;y2++)
{
if(x1==x2) continue;
double dx=x1-x2,dy=y1-y2;
double k=dy/dx;
if(check(k,y1-k*x1)) res++;
}
cout<<res+n<<endl;
return 0;
}
C：货物摆放
答案
：2430
算法1：
枚举约数法，因为乘积等于 n 只可能是 n 的约数，因此我们可以先预处理出所有的约数，最后
n
3
n^3
n
3
枚举即可（只有128个约数）
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
LL n;
int main()
{
n=2021041820210418;
vector<LL> a;
for(LL i=1;i*i<=n;i++)
{
if(n%i==0)
{
a.push_back(i);
a.push_back(n/i);
}
}
int res=0;
for(auto i:a)
for(auto j:a)
for(auto k:a)
if(i*j*k==n) res++;
cout<<res<<endl;
return 0;
}
算法2：
直接暴力法（也就4s而已）
#include <iostream>
using namespace std;
typedef long long LL;
LL n;
int main()
{
n=2021041820210418;
int res=0;
for(LL i=1;i*i*i<=n;i++)
if(n%i==0)
for(LL j=i;i*j*j<=n;j++) //j=i开始，保持递增
if(n/i%j==0)
{
LL k=n/i/j;
if(i==j&&i==k) res++;
else if(i==j||i==k||j==k) res+=3;
else res+=6;
}
cout<<res<<endl;
return 0;
}
算法3：
筛质因子+手算排列组合比较快，也可以 dfs，但是要处理一下重复
筛质因子代码就不展示了
质因子及个数如下：
5882353 1
2857 1
131 1
2 1
17 1
3 3
D：路径
题解
知识点：最短路，dijkstra
-
最短路问题，涉及到求最小公倍数
lc
m
(
a
,
b
)
=
a
∗
b
/
g
c
d
(
a
,
b
)
lcm(a,b)=a*b/gcd(a,b)
l
c
m
(
a
,
b
)
=
a
∗
b
/
g
c
d
(
a
,
b
)
- 听一些大佬说dp也可以，但是不清楚正确性，即是否一定从前往后走。
-
由于本题数据范围很小加上是填空题，直接最暴力的
O(
n
2
)
O(n^2)
O
(
n
2
)
迪杰即可。如果边过多或者
n2
n^2
n
2
超时可以考虑堆优化迪杰
答案
：10266837
#include <iostream>
#include <cstring>
using namespace std;
const int N=2050;
int g[N][N],n;
bool st[N];
int dis[N];
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
void djs()
{
memset(dis,0x3f,sizeof dis);
dis[1]=0;
for(int k=0;k<n;k++)
{
int u=0;
for(int i=1;i<=n;i++)
{
if(!st[i]&&dis[i]<dis[u]) u=i;
}
st[u]=true;
if(u==2021) break;
for(int i=1;i<=n;i++) dis[i]=min(dis[i],dis[u]+g[u][i]);
}
}
int main()
{
n=2021;
for(int i=1;i<N;i++)
for(int j=i;j<N;j++)
{
if(j-i>21) g[i][j]=g[j][i]=0x3f3f3f3f;
else g[i][j]=g[j][i]=i*j/gcd(i,j);
}
djs();
cout<<dis[n]<<endl;
return 0;
}
E：回路计数
题解
-
直接爆搜时间复杂度是阶乘级别的，即
O(
n
!
)
O(n!)
O
(
n
!)
，大概只能搜到15就不行了，原因在于每个点搜索顺序可以不一样，近似看成 n 的全排列就是阶乘级别了。 -
仔细分析题目会发现每个点的状态我们都要处理到位，且要经过每个点，20是非常nice的一个数字，会想到什么：
状态压缩
，我们不妨用
(1
<
<
21
)
−
1
(1<<21)-1
(
1
<<
21
)
−
1
内的每个数字来表示所有状态，但是会发现如果只这样是不好处理的，因此再加入一维。 -
状态表示
：
dp
[
s
t
a
t
e
]
[
j
]
dp[state][j]
d
p
[
s
t
a
t
e
]
[
j
]
表示当前经过了的点状态为
st
a
t
e
state
s
t
a
t
e
且最后一次经过的点为
jj
j
的方案数。 -
状态转移
：
dp
[
s
t
a
t
e
]
[
j
]
=
∑
i
=
0
20
d
p
[
s
t
a
t
e
−
2
i
]
[
k
]
dp[state][j]= \sum_{i=0}^{20}dp[state-2^i][k]
d
p
[
s
t
a
t
e
]
[
j
]
=
∑
i
=
0
20
d
p
[
s
t
a
t
e
−
2
i
]
[
k
]
转移条件
：
st
a
t
e
state
s
t
a
t
e
的第
jj
j
位是 1 并且
st
a
t
e
state
s
t
a
t
e
的第
kk
k
位也是 1，
j!
=
k
j!=k
j
!
=
k
，
gc
d
(
i
+
1
,
k
+
1
)
=
=
1
gcd(i+1,k+1)==1
g
c
d
(
i
+
1
,
k
+
1
)
==
1
。 -
结果表示
：
re
s
=
∑
i
=
0
20
d
p
[
(
1
<
<
21
)
−
1
]
[
i
]
res=\sum_{i=0}^{20}dp[(1<<21)-1][i]
res
=
∑
i
=
0
20
d
p
[(
1
<<
21
)
−
1
]
[
i
]
。有的小伙伴可能会问原因：
dp
[
(
1
<
<
21
)
−
1
]
[
i
]
dp[(1<<21)-1][i]
d
p
[(
1
<<
21
)
−
1
]
[
i
]
表示的是经过了所有点且最后在第
ii
i
个位置上的方案数，现在并没有回到源点，也就是说最后的所有结尾点为
ii
i
的方案中就是最后倒数第2个点，再往前走一步就是终点（原点）了，而最后的状态是由所有倒数第2的状态转移过来，所以将所有
dp
[
(
1
<
<
21
)
−
1
]
[
i
]
dp[(1<<21)-1][i]
d
p
[(
1
<<
21
)
−
1
]
[
i
]
加起来就是最终回到原点的方案数，也就是哈密顿回路的方案数。
答案
：881012367360
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
const int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=22,M=400010;
int n=21;
long long dp[1<<21][21];
bool g[N][N];
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
rep(i,1,n)
rep(j,i+1,n)
if(gcd(i,j)==1) g[i][j]=g[j][i]=true;
dp[1][0]=1;
rep(i,2,1<<n)
rep(j,0,20)
if(i>>j&1)
rep(k,0,20)
if(j!=k&&g[j+1][k+1]&&(i>>k&1))
dp[i][j]+=dp[i-(1<<j)][k];
long long res=0;
rep(i,0,20) res+=dp[(1<<21)-1][i];
cout<<res<<endl;
return 0;
}
F：砝码称重
题解
dp 可以做，枚举每一个砝码，再枚举所有已经存在的重量，加减当前重量
a[i]
即可，复杂度
O
(
n
m
)
O(nm)
O
(
nm
)
状态方程：
t[j]=t[j-a[i]]=true,t[j+a[i]]=true
; 用前面轮的结果标记这一轮。
众所周知：一维肯定快点（滚动数组）
一维：
#include <iostream>
#include <cstring>
using namespace std;
const int N=110,M=200010,B=M/2;
int a[N],n;
bool f[M],t[M];
int main()
{
cin>>n;
int m=0;
for(int i=1;i<=n;i++) cin>>a[i],m+=a[i];
f[B]=1;
for(int i=1;i<=n;i++)
{
for(int j=-m;j<=m;j++)
if(f[j+B])
{
t[j+B]=true;
t[j+a[i]+B]=t[j-a[i]+B]=true;
}
memcpy(f,t,sizeof t);
}
int res=0;
for(int i=1;i<=m;i++) res+=f[i+B];
cout<<res<<endl;
return 0;
}
二维：
#include <iostream>
using namespace std;
const int N=110,M=200010,B=M/2;
bool f[N][M];
int a[N],n;
int main()
{
cin>>n;
int m=0;
for(int i=1;i<=n;i++) cin>>a[i],m+=a[i];
f[0][B]=1;
for(int i=1;i<=n;i++)
{
for(int j=-m;j<=m;j++)
{
if(f[i-1][j+B]) f[i][j+B]=true; //不选
if(f[i-1][j+B])
f[i][j+a[i]+B]=f[i][j-a[i]+B]=true;
}
}
int res=0;
for(int i=1;i<=m;i++) res+=f[n][i+B];
cout<<res<<endl;
return 0;
}
G：异或数列
题解
知识点：博弈论
首先这类题咱们自己可以比划比划，可以找到一些性质
- 如果所有数的异或和为 0，那么所有位的值都为偶数，每个数不管怎么选，双方的数最终都会相等，必然是平局
-
不是平局，必然异或和有一个1，我们找到最高位的1，统计数列中这位为1的数量
cn
t
1
cnt1
c
n
t
1
，它必定是奇数。如果如果Alice(先手)想赢，必然要使最高位掌握在自己手中，这里还有一个点就是这一位为0的元素数量
cn
t
0
cnt0
c
n
t
0
，如果打不赢的时候，使用这一位为0的数可以使得攻防反转，最终我们要统计的就是
cn
t
1
+
c
n
t
0
cnt1+cnt0
c
n
t
1
+
c
n
t
0
的数量，如果是奇数，则Alice必胜，反之Bob必胜 -
值得注意的最后一点就是如果该异或值的最高位只有一位1，那么选了这个1后无论后面怎么选都是选了这个1的最大，因此如果
cn
t
1
=
0
cnt1=0
c
n
t
1
=
0
，则 Alice 必胜，这个情况要先判。
#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
typedef pair<int,int> PII;
typedef pair<pair<int,int>,int> PIII;
typedef long long LL;
typedef unsigned long long ULL;
const int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=200010,M=200010;
int n;
int w[N];
int main()
{
int T; cin>>T;
while(T--)
{
scanf("%d",&n);
int res=0;
rep(i,1,n)
{
scanf("%d",&w[i]);
res^=w[i];
}
if(res==0) puts("0");
else
{
int k=30,cnt1=0,cnt0=0;
while(!(res>>k&1)) k--;
rep(i,1,n)
{
if(w[i]>>k&1) cnt1++;
else cnt0++;
}
if(cnt1==1) puts("1");
else if(n&1) puts("1");
else puts("-1");
}
}
return 0;
}
H：左孩子右兄弟
题解
知识点：树的遍历，树形DP
这题是给定一棵树，问怎么转可以使得树的深度最大
- 首先孩子可以任意选，那么对于任意一个树上的结点，我们找到它的所有的子树中最深的一个孩子，然后统计它的孩子数量，把最深的这个孩子结点依次接到它所有孩子后面就可以了。例如：有三个子树，深度分别是 2，3，4，那么我们答案就是 4+1(接在2孩子上)+1(再接在3孩子上) = 6
#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
typedef pair<int,int> PII;
typedef pair<pair<int,int>,int> PIII;
typedef long long LL;
typedef unsigned long long ULL;
const int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=100010,M=200010;
int n;
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{
int cnt=0,maxv=0;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
cnt++;
maxv=max(maxv,dfs(j));
}
return maxv+cnt;
}
int main()
{
memset(h,-1,sizeof h);
cin>>n;
rep(i,2,n)
{
int x; scanf("%d",&x);
add(x,i);
}
cout<<dfs(1)<<endl;
return 0;
}
I：括号序列
题解
这题才发现是个原题，可惜当时没写出来
- 分别计算插左右括号的方案数
- 计算另一种括号数的时候直接翻转再翻转符号就行了
- 最后计算总方案数，其实就是插空法，分别插左右括号，最后相乘即可
DP分析：
状态表示：
f
[
i
]
[
j
]
f[i][j]
f
[
i
]
[
j
]
：只考虑前i个括号并且左括号比右括号多
j
j
j
的方案数
状态转移：
当
s
[
i
]
=
s[i]=
s
[
i
]
=
‘(’ ，
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
−
1
]
f[i][j]=f[i-1][j-1]
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
−
1
]
;
反之
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
+
1
]
+
f
[
i
]
[
j
−
1
]
f[i][j]=f[i-1][j+1]+f[i][j-1]
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
+
1
]
+
f
[
i
]
[
j
−
1
]
;（推导过程与完全背包类似）
-
这里有个小问题就是有可能最终的答案刚好取模后 =0 造成返回值错误，但是这种情况十分罕见，可以忽略不计，也可以在官网通过，如果要避免这种情况可以参考
代码2
，通过计算最少需要添加的括号数
cn
t
cnt
c
n
t
，然后再计算出答案是需要返回几
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=5010,MOD=1e9+7;
LL f[N][N];
int n;
char s[N];
LL get()
{
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=1;i<=n;i++)
{
if(s[i]=='(')
{
for(int j=1;j<=n;j++)
f[i][j]=f[i-1][j-1];
}
else
{
f[i][0]=(f[i-1][1]+f[i-1][0])%MOD;
for(int j=1;j<=n;j++)
f[i][j]=(f[i-1][j+1]+f[i][j-1])%MOD;
}
}
for(int i=0;i<=n;i++)
if(f[n][i]) return f[n][i];
return -1;
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
LL a=get();
reverse(s+1,s+n+1);
for(int i=1;i<=n;i++)
if(s[i]=='(') s[i]=')';
else s[i]='(';
LL b=get();
cout<<a*b%MOD<<endl;
return 0;
}
代码2：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=5010,M=2*N;
char s[N];
int n;
LL f[N][N];
LL calc()
{
int cnt=0, k=0, l=0, r=0;
for(int i=1;i<=n;i++)
{
if(s[i]==')')
{
r++, k++;
if(k>0) k=0,cnt++;
}
else l++,k--;
}
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=1;i<=n;i++)
{
if(s[i]=='(')
{
for(int j=1;j<=n;j++)
f[i][j]=f[i-1][j-1];
}
else
{
f[i][0]=(f[i-1][1]+f[i-1][0])%MOD;
for(int j=1;j<=n;j++)
f[i][j]=(f[i-1][j+1]+f[i][j-1])%MOD;
}
}
return f[n][cnt+l-r]; //直接返回答案
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
LL l=calc();
reverse(s+1,s+n+1);
for(int i=1;i<=n;i++)
if(s[i]==')') s[i]='(';
else s[i]=')';
LL r=calc();
cout<<l*r%MOD<<endl;
return 0;
}
J：分果果（题目）
后续待官网题更新后再更新…心态爆炸