忘关文件然后暴击60分被送回非洲

T1

找到 $x,y$

满足 $(x+y)\pmod p=b,(x*y)\pmod p=c$

很好,我特么看了一早上都没看出来这么像韦达定理

我们写成一元二次方程大概就是这个样子

$x^2-bx+c=0\pmod p$

为什么要看出韦达定理呢,小编也是很疑惑首先我们可以得到$\Delta=b^2-4*c$

但是我们要给 $\Delta$ 开个根号 ,这要用到什么芝士呢,原来是二次剩余

再乘以 $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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int modp=1e9+7;

inline int qpow(int x,int y)
{
int ans=1;
while(y)
{
if(y&1) ans=(ans*x)%modp;
x=x*x%modp;
y>>=1;
}
return ans;
}

signed main()
{
ios::sync_with_stdio(false);
register int i,j;
int t;
cin>>t;
while(t--)
{
int b,c;
cin>>b>>c;
int delta=b*b-c*4;
delta%=modp;
if(delta<0) delta+=modp;
if(delta!=0&&qpow(delta,(modp-1)/2)!=1)
{
cout<<"-1 -1\n";
continue;
}
delta=qpow(delta,(modp+1)/4);
int inv=qpow(2,modp-2);
int x,y;
x=((b+delta+2*modp)*inv)%modp;
y=((b-delta+2*modp)*inv)%modp;
cout<<min(x,y)<<" "<<max(x,y)<<endl;
}
return 0;
}

T2

字符串裸题,本质上是在求一个字符串最长的作为后缀的长度

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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=1e5+20;

char s1[maxn],s2[maxn],s3[maxn];
int pi[maxn][30],l[maxn];
int n,m;
int looker[maxn];
int r;

inline void kmp()
{
int i,j;
i=j=0;
for(i=2;i<=n;i++)
{
while(j&&s1[j+1]!=s1[i]) j=l[j];
if(s1[i]==s1[j+1]) j++;
l[i]=j;
}
for(i=1;i<=n;i++)
{
for(j=0;j<=25;j++)
pi[i][j]=pi[l[i]][j];
pi[i][s1[l[i]+1]-'a']=l[i];
}
}

int main()
{
ios::sync_with_stdio(false);
register int i,j;
scanf("%s %s",s1+1,s2+1);
n=strlen(s1+1); m=strlen(s2+1);
j=1;
int timeline;
kmp();
// for(i=2,j=0;i<=n;i++)
// {
// while(j&&s1[j+1]!=s1[i]) j=pi[i][s1[i]-'a'];
// for(int k=0;k<=25;k++) pi[i][k]=pi[j][k];
// if(s1[j+1]==s1[i]) j++; pi[i][s1[i]-'a']=j;
// }
j=0;
cout<<n<<endl;
for(timeline=1;timeline<=m;timeline++)
{
if(s2[timeline]=='-') r=max(0,--r);
else s3[++r]=s2[timeline];
j=looker[r-1];
while(j&&s1[j+1]!=s3[r]) j=pi[j][s3[r]-'a'];
if(s1[j+1]==s3[r]) j++;
cout<<n-j<<endl;
looker[r]=j;
}
return 0;
}

T3

这个很巧妙,首先这个区间覆盖先看做是差分,然后来我们的昏析:

区间长度是大于等于6的偶数,哥德巴赫猜想,小于6的偶数简单推一下,操作都是两次

区间长度是一个奇质数,花费显然是1

区间长度是一个奇合数(或者1),看做是一个偶数+质数,花费是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
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=20010;

int n,m,size=1;
int st=0,ed=300,a[maxn],b[maxn];
int N=maxn;
int p[maxn],tot;

struct edge{
int next,to,flow;
}e[maxn];

int lp[maxn],rp[maxn],head[maxn],looker[maxn];
int dep[maxn],vis[maxn];

inline void addedge(int next,int to,int flow)
{
e[++size].to=to;
e[size].flow=flow;
e[size].next=head[next];
head[next]=size;
}

int _isprime(int x)
{
int i;
if(x==1||x==2) return 0;
for(i=2;i*i<=x;i++) if(x%i==0) return 0;
return 1;
}

inline int bfs()
{
queue <int> q;
q.push(st);
memset(vis,0,sizeof(vis));
memset(dep,0,sizeof(dep));
vis[st]=1;
while(!q.empty())
{
int t=q.front();
q.pop();
int i,j,k;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
k=e[i].flow;
if(k<=0||vis[j]) continue;
vis[j]=1;
dep[j]=dep[t]+1;
q.push(j);
}
}
return vis[ed];
}

int dfs(int t,int nowt)
{
if(t==ed||!nowt) return nowt;
int tot=0,j,k,f;
for(int &i=looker[t];i;i=e[i].next)
{
j=e[i].to;
k=e[i].flow;
if(k>0&&dep[t]+1==dep[j])
{
f=dfs(j,min(nowt-tot,k));
e[i].flow-=f;
e[i^1].flow+=f;
tot+=f;
if(tot==nowt) return tot;
}
}
return tot;
}

inline int dinic()
{
int ans=0;
while(bfs())
{
ans+=dfs(st,0x3f3f3f3f);
memcpy(looker,head,sizeof(looker));
}
return ans;
}

int main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n;
for(i=1;i<=n;i++) cin>>a[i],b[a[i]]=1;
for(i=N;i;i--) b[i]^=b[i-1];
for(i=1;i<=N;i++)
{
if(!b[i]) continue;
if(!(i&1))
{
lp[++lp[0]]=i;
p[++tot]=i;
addedge(st,i,1);
addedge(i,st,0);
}
else
{
p[++tot]=i;
rp[++rp[0]]=i;
addedge(i,ed,1);
addedge(ed,i,0);
}
}
for(i=1;i<=lp[0];i++)
for(j=1;j<=rp[0];j++)
for(i=1;i<=tot;i++)
for(j=i+1;j<=tot;j++)
{
int delta=abs(p[i]-p[j]);
if(_isprime(delta))
{
int lok=0;
if(!(p[i]&1)) swap(p[i],p[j]),lok=1;
addedge(p[i],p[j],1);
addedge(p[j],p[i],0);
if(lok) swap(p[i],p[j]);
}
}
int t=dinic();
int t2=(lp[0]-t)/2+(rp[0]-t)/2; t2*=2;
int t3=((lp[0]-t)%2)*3;
cout<<t+t2+t3<<endl;
return 0;
}

// if(delta&1)
// {
// addedge(lp[i],rp[j],1);
// addedge(rp[j],lp[i],0);
// }
// else
// {
// if(_isprime(delta))
// {
// addedge(lp[i],rp[j],);
// addedge(lp[])
// }
// else
// {
//
// }