| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 8/10 | O | O | Ø | . | Ø | O | O | O | Ø | . |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
给一个不超过$100$的正数$n$，求一个不超过$10^4$位的数$x$满足：$num(x)%n=0,x%n=0$ ，$num(x)$表示$x$的数位和。
解题思路
输出$n$个$n$即可。
AC代码
2
3
4
5
6
7
8
9
10
11
using namespace std;
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=0;i<n;i++)printf("%d",&n);
puts("");
}
}
B
题目描述
给$x_0,x_1,a,b$，求出满足$x_i=ax_{i-1}+bx_{i-2}$的$x_n$，$1\leq n\leq 10^{10^6}$。
解题思路
用十进制进行快速幂，复杂度$O(10\log n)$。
AC代码
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
using namespace std;
int mod = 1e9+7;
typedef long long ll;
const int maxn = 1e6+23;
char s[maxn];
ll x0,x1;int a,b,n;
struct matrix{
ll a,b,c,d;
void init(){
a=1,b=0,c=0,d=1;
}
};
matrix pow(matrix A,matrix B){
matrix C;
C.a=(A.a*B.a)+(A.b*B.c);C.a%=mod;
C.b=(A.a*B.b)+(A.b*B.d);C.b%=mod;
C.c=(A.c*B.a)+(A.d*B.c);C.c%=mod;
C.d=(A.c*B.b)+(A.d*B.d);C.d%=mod;
return C;
}
int main(){
cin >> x0 >> x1 >> a >> b ;
scanf("%s",s);cin >> mod ;
n=strlen(s);
matrix A;A.a=a,A.b=b,A.c=1,A.d=0;
matrix ans;ans.init();
for(int i=n-1;i>=0;i--){
int t=s[i]-'0';matrix B=A;
if(t==0) B.init();
for(int j=1;j<t;j++) B=pow(B,A);
ans=pow(ans,B);
for(int j=t;j<10;j++) B=pow(B,A);
A=B;
}
ll t=0;
t=ans.c*x1+ans.d*x0;t%=mod;
cout << t;
}
C
题目描述
给一个数列：$x_i=(ax_{i-1}+b)mod\space p$，$0\leq i<n$。给定$n,a,b,p$，有$q$次询问，每次询问$v$是否在数列中，如果是，输出下标，否则输出$-1$。
$1\leq n\leq 10^{18},0\leq x_p,a,b<p\leq 10^9+9,q\leq 1000,0\leq v<p$。
解题思路
一眼没看出来有式子可推，高中数学白学了
推式子：待定系数法化为等比数列，$x_i+\frac b{a-1}=a(x_{i-1}+\frac b{a-1})$，就可以$BSGS$了
高代学疯了看着是个矩阵，$\left(\begin{aligned}a\space {0}\\b\space{1}\end{aligned}\right)^p \left(\begin{aligned}x_0\\1\end{aligned}\right)=\left(\begin{aligned}v\\1\end{aligned}\right)$
于是设$p=i\times m-j$，式子转化为$\left(\begin{aligned}a\space {0}\\b\space{1}\end{aligned}\right)^{i\times m} \left(\begin{aligned}x_0\\1\end{aligned}\right)=\left(\begin{aligned}v\\1\end{aligned}\right)\left(\begin{aligned}a\space {0}\\b\space{1}\end{aligned}\right)^j $，这里特判一下不能转化为这个式子的情况（矩阵没有逆）。
正常套路$BSGS$，先预处理出矩阵的$i\times m$次幂$i\in [1,\lceil \frac pm\rceil]$，每次枚举$j\in [0,m]$即可。由于不是预处理$j$然后$i$从小枚举即可保证是最佳答案，所以不能找到解$im+j$就退出，找到$j$后需要与以前找过的答案做大小比较，复杂度可能会高一些。
由于有$q$次询问，平均复杂度为$O(T(\lceil \frac pm \rceil+qm))$，故取$m=\lceil \frac pq \rceil$来降低询问时的复杂度。
设矩阵为$A$，我们发现$A$的$k$次幂的形式都为$\left(\begin{aligned}k_1\space {0}\\k_2\space{1}\end{aligned}\right)$，故只保存两个数值即可减少一些常数。
时限剧毒，放一下卡常记录（$WA$那次是因为特判的时候$0$和$1$先后顺序反了）
AC代码
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
typedef long long ll;
using namespace std;
unordered_map<ll,int>mp;
int mod;
struct Matrix{
ll a,b;
Matrix operator*(Matrix t){return (Matrix){a*t.a%mod,(t.a*b+t.b)%mod};}
}E;
int main(){
int i,T;
E.a=1;E.b=0;
scanf("%d",&T);
while(T--){
ll n,x0,a,b,p,q,v;
scanf("%lld%lld%lld%lld%lld%lld",&n,&x0,&a,&b,&p,&q);
if(!a){//不存在逆矩阵
while(q--){
scanf("%lld",&v);
if(v==x0)printf("0\n");
else if(v==b)printf("1\n");
else printf("-1\n");
}
continue;
}
mp.clear();
mod=p;
Matrix A=(Matrix){a,b};
ll m=ceil(sqrt(1.0*p/q)),M=ceil(1.0*p/m);
Matrix now=A;
for(i=1;i<m;i++)now=now*A;//A^m
Matrix __im=E;
ll ans=1;
for(i=1;i<=M&&i*m-m<n;i++){//A^{im}
__im=__im*now,ans=(__im.a*x0+__im.b)%mod;
if(!mp.count(ans))mp[ans]=i;
else break;//循环
}
while(q--){
int v;
scanf("%d",&v);
ll res=2e18,ans=1;
Matrix now=E;
for(i=0;i<=m;i++){
if(i)now=now*A;
ans=(now.a*v+now.b)%mod;
if(mp.count(ans))res=min(res,mp[ans]*m-i);
}
if(res>=n)res=-1;
printf("%lld\n",res);
}
}
return 0;
}
D
题目描述
解题思路
AC代码
2
E
题目描述
给一张点最多有$26$个的图，求所有子图的独立集大小之和。
解题思路
设某个子图为$s$状态，$f[s]$表示该状态独立集的大小。假设$x$为$s$的最低为$1$的位，有$f[s]$为去掉$x$的大小和去掉$x$连边大小$+1$的最大值，即$f[s]=max(f[s-(1<<x)],1+f[s&(\text ~state[x])])$，其中$state[i]$表示和$i$连边或$i$本身的状态。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef long long ll;
using namespace std;
int state[30];int ans;
char dp[(1<<26)+10];
int main(){
int i,n,m,u,v,mb=-1;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)state[i]|=1<<i;
for(i=0;i<m;i++){
scanf("%d%d",&u,&v);
state[u]|=1<<v;
state[v]|=1<<u;
}
for(i=1;i<(1<<n);i++){
mb+=(i&(-i))==i;
dp[i]=max(dp[i-(1<<mb)],(char)(dp[i&(~state[mb])]+1));
ans+=dp[i];
}
printf("%d",ans);
return 0;
}
F
题目描述
有$n$个不同的数，求最大的子集，保证子集中任意两个数的二进制表示都至少有两个不同的位。
解题思路
两个恰有一位不同的数不在同一集合，也就是如果满足这个条件就连一条边，问题转化为二分图的最大独立集。先染色，再求一个最大匹配，再对所有左图没有对应右图中的点的点进行增广，在这些次增广没有被访问到的左图中的点和访问到的右图中的点为一个最小点覆盖，剩下的点就是最大独立集。
AC代码
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
typedef long long ll;
using namespace std;
int n,a[N];
struct Edge{
int e,n,l;
}e[N*N/2];
int vis[N],hd[N],ct=1,mt[N];
void add(int a,int b,int l){
e[++ct].e=b;e[ct].n=hd[a];hd[a]=ct;e[ct].l=l;
assert(ct<N*N/2);
}
int col[N];
vector<int>G[5];
void dfs(int x,int c){
col[x]=c;
G[c].push_back(x);
int i;
for(i=hd[x];i;i=e[i].n){
int q=e[i].e;
if(!col[q])dfs(q,c^1);
}
}
int L[N],R[N],S[N],T[N];
int dfs2(int p){//p:左半边编号
int i;
S[p]=1;
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(!T[q]){
T[q]=1;
if(L[q]==-1||dfs2(L[q])){
L[q]=p;
R[p]=q;
return 1;
}
}
}
return 0;
}
int outs[N];
void solve(){
int i,ans=0;
memset(L,-1,sizeof(L));
memset(R,-1,sizeof(R));
for(auto i:G[2]){
memset(S,0,sizeof(S));
memset(T,0,sizeof(T));
if(dfs2(i))ans++;
}
printf("%d\n",n-ans);
memset(S,0,sizeof(S));
memset(T,0,sizeof(T));
for(auto i:G[2])if(R[i]==-1)dfs2(i);
for(auto i:G[2])if(!S[i])outs[i]=1;
for(auto i:G[3])if(T[i])outs[i]=1;
for(i=1;i<=n;i++)if(!outs[i])printf("%d ",a[i]);
}
int main(){
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(__builtin_popcount(a[i]^a[j])<2)
add(i,j,1),add(j,i,1);
for(i=1;i<=n;i++){
if(!col[i])dfs(i,2);
}
solve();
return 0;
}
G
题目描述
求$s$有多少个合法子串$x$满足十进制下$x>t$。
解题思路
长度大于$m$的可以排列组合算出，求出有多少个长度为$m$的大于$t$的$s$的子串即可。
$f[i][j][0]$表示到$s$的第$i$个数字，与$t$前$j$位相等的种数；$f[i][j][1]$表示到$s$的第$i$个数字，比$t$前$j$位大的种数。转移非常显然。特判一下前导$0$即可。
AC代码
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
typedef long long ll;
using namespace std;
int f[N][N][2],m,n;
char a[N],b[N];
int fac[N]={1},inv[N],mod=998244353;
int qp(int x,int p){
int ans=1;
for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;
return ans;
}
int c(int n,int m){
if(n<m)return 0;
return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
int i,j,t;
scanf("%d",&t);
for(i=1;i<N;i++)fac[i]=fac[i-1]*1LL*i%mod;
for(i=0;i<N;i++)inv[i]=qp(fac[i],mod-2);
while(t--){
scanf("%d%d%s%s",&n,&m,a+1,b+1);
ll ans=0;
f[0][0][0]=1;
for(i=1;i<=n;i++){
f[i][0][0]=1;
if(a[i]!='0')for(j=m;j<=n-i;j++)(ans+=c(n-i,j))%=mod;
for(j=1;j<=m&&j<=i;j++){
(f[i][j][0]=f[i-1][j][0]+(a[i]==b[j]?f[i-1][j-1][0]:0))%=mod;
(f[i][j][1]=(f[i-1][j][1]+f[i-1][j-1][1])%mod+(a[i]>b[j]?f[i-1][j-1][0]:0))%=mod;
}
}
printf("%lld\n",(ans+f[n][m][1])%mod);
}
return 0;
}
H
题目描述
求构造一个串满足给定$hidden$字母的顺序。
解题思路
特判空串、各个字符个数，编完号建图拓扑序跑一遍即可。
AC代码
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
typedef long long ll;
using namespace std;
char a[N],s[10];
char ch[N];
struct Edge{
int e,n;
}e[1000000];
int hd[N],ind[N],cnt;
void add(int a,int b){
e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;
ind[b]++;
}
vector<int>id[30];
int tot,vis[30];
queue<int>Q;
vector<char>ans;
int main(){
int i,j,n,m;
scanf("%d%d",&n,&m);
for(i=0;i<m*(m-1)/2;i++){
int l;
scanf("%s%d",s,&l);
if(l)scanf("%s",a);
else a[0]='\0';
int t0=id[s[0]-'a'].size(),t1=id[s[1]-'a'].size();
if(vis[s[0]-'a']){
for(j=0;j<l;j++)if(a[j]==s[0])t0--;
if(t0)return printf("-1"),0;
}
if(vis[s[1]-'a']){
for(j=0;j<l;j++)if(a[j]==s[1])t1--;
if(t1)return printf("-1"),0;
}
for(j=0;j<l;j++){
if(!vis[a[j]-'a']){
id[a[j]-'a'].push_back(++tot);
ch[tot]=a[j];
}
}
vis[s[0]-'a']=vis[s[1]-'a']=1;
if(!l)continue;
int L=0,R=0,last=id[a[0]-'a'][0];
if(s[0]==a[0])L++;else R++;
for(j=1;j<l;j++){
int now;
if(a[j]==s[0])now=id[a[j]-'a'][L],L++;
else now=id[a[j]-'a'][R],R++;
add(last,now);
last=now;
}
}
for(i=1;i<=tot;i++)if(!ind[i])Q.push(i);
while(!Q.empty()){
int idt=Q.front();Q.pop();
ans.push_back(ch[idt]);
for(i=hd[idt];i;i=e[i].n){
int x=e[i].e;
if(!--ind[x])Q.push(x);
}
}
if(ans.size()!=n||tot!=n)printf("-1");
else for(auto it:ans)printf("%c",it);
return 0;
}
I
题目描述
求一个$x\in [0,w],y\in [0,h]$的三个点，满足距离分别为$a,b,c$。
解题思路
暴力枚举连在原点上的两条边，检查即可。有精度问题。
AC代码
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
using namespace std;
int T;
double w,h,a,b,c;
double dis[3];
int a1,a2,a3,a4,a5;
double x[3],y[3];
double getdis(int i,int j)
{
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main()
{
cin >> T;
while(T--){
scanf("%d%d%d%d%d",&a1,&a2,&a3,&a4,&a5);
int W=a1,H=a2,flag=0;
w=a1,h=a2,a=a3,b=a4,c=a5;
dis[0]=a,dis[1]=b,dis[2]=c;
bool change=false;
if(w<h) {swap(w,h);change=true;}
x[0]=y[0]=0;
double the;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(i==j)continue;
if(dis[i]<=w) x[2]=dis[i],y[2]=0,the=1;
else{
x[2]=w,y[2]=sqrt(dis[i]*dis[i]-w*w);
the=w/dis[i];
}
int k=3-i-j;
double cosi=(dis[i]*dis[i]+dis[j]*dis[j]-dis[k]*dis[k])/(2*dis[i]*dis[j]);
double phi=acos(cosi);the=acos(the);
x[1]=dis[j]*cos(phi+the);y[1]=dis[j]*sin(phi+the);
if(change)for(int l=0;l<3;l++)swap(x[l],y[l]);
for(int l=0;l<3;l++){
if(x[l]<1e-7)x[l]+=1e-7;
if(y[l]<1e-7)y[l]+=1e-7;
if(x[l]>W-1e-7)x[l]-=1e-7;
if(y[l]>H-1e-7)y[l]-=1e-7;
}
if(x[0]>=0&&x[0]<=W);else continue;
if(x[1]>=0&&x[1]<=W);else continue;
if(x[2]>=0&&x[2]<=W);else continue;
if(y[0]>=0&&y[0]<=H);else continue;
if(y[1]>=0&&y[1]<=H);else continue;
if(y[2]>=0&&y[2]<=H);else continue;
for(int p=0;p<3;p++){
for(int q=0;q<3;q++){
if(q==p)continue;
int r=3-p-q;
if(!(abs(getdis(p,q)-a)<1e-6))continue;
if(abs(getdis(p,r)-b)<1e-6&&abs(getdis(q,r)-c)<1e-6){
printf("%.10f %.10f %.10f %.10f %.10f %.10f\n",x[p],y[p],x[q],y[q],x[r],y[r]);
flag=1;
goto A;
}
}
}
}
}
A:;
assert(flag);
}
}
J
题目描述
解题思路
AC代码
2