普及T1 珠心算测验
没读懂题目就会被坑。
模拟即可，但是要注意先去重，不然会多次统计。另外还要注意整数对的无序性。也就是说，两个数$a+b=c$和$b+a=c$不能算$2$遍。在找到这个数$c$后，还要及时把他删除，以免多次统计。
所以，$O(n^2)$扫一遍即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace std;
int a[104],n,ans=0;
char vis[20004]={0};
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
sort(a,a+n);
n=unique(a,a+n)-a;
for(int i=0;i<n;i++)vis[a[i]]=1;
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(vis[a[i]+a[j]])ans++,vis[a[i]+a[j]]=0;
printf("%d\n",ans);
return 0;
}
普及T2 比例简化
方法一
模拟即可，注意简化后分数和原分数的比较，涉及浮点数的运算。
时间复杂度$O(L^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
using namespace std;
int a,b,lim,fz,fm;
double bi,mini=1e9,cur;
int gcd(int a,int b){
return (!b)?a:gcd(b,a%b);
}
int main(){
scanf("%d%d%d",&a,&b,&lim);
bi=(double)a/b,cur=1e9;
for(int i=1;i<=lim;i++)
for(int j=1;j<=lim;j++){
double t=(double)i/j;
if(t-bi>0&&t-bi<cur)
cur=t-bi,fz=i,fm=j;
else if(fabs(t-bi)<1e-8){
fz=i,fm=j;break;
}
}
int g=gcd(fz,fm);
fz/=g,fm/=g;
printf("%d %d\n",fz,fm);
return 0;
}
方法二
对每一个不大于$L$的数进行一次二分，找出以此数为分母时最接近$\frac {A}{B}$的分数的分子。
时间复杂度：$O(LlogL)$。
普及T3 螺旋矩阵
观察发现这个结构很有规律，因为螺旋矩阵是一层一层螺旋的，所以考虑一层一层递进求解。我们每一次去掉矩阵最外面的一层，如1
2
3
41 2 3 4
12 13 14 5 ---> 13 14
11 16 15 6 ---> 16 15
10 9 8 7
这样里面还是一个螺旋矩阵，但由$n\times n$变为了$(n-2)\times (n-2)$。最后到了要求的数的那一层的时候采用模拟算法，算出那个数即可。
时间复杂度：$O(n)$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
int n,x,y,tot=0;
int main(){
scanf("%d%d%d",&n,&x,&y);
for(;x!=1&&y!=1&&x!=n&&y!=n;)
tot+=4*n-4,n-=2,x--,y--;
if(x==1)tot+=y;
else{
tot+=n-1;
if(y==n)tot+=x;
else{
tot+=n-1;
if(x==n)tot+=(n-y+1);
else{
tot+=n-1;
if(y==1)tot+=(n-x+1);
}
}
}
printf("%d\n",tot);
return 0;
}
普及T4 子矩阵
这题一脸不可做。
是吗？
我们先尝试搜索，按照计算，我们最多搜索$(C_{16}^8)^2$次。这样会$TLE$。
别急，先搜出我们当前选取的行。然后问题就转化为了求这些行中某些列产生的最小的分数。这个问题我们就很熟悉了，这不是一个$O(m^2)$的$DP$么？设$f(i,j)$为选了$i$列，当前在第$j$列时最小的分数，则状态转移方程易导出。
综上，我们使用搜索和$DP$相结合的方法解决了本题。
实际上，这样的搜索和高效算法结合的思想早在许多年前就已经用到（即$NOI2003$智破连环阵），在这里出现着实很妙。而在$NOIP2015$中也有这样的思想。
时间复杂度：$O(C_n^mm^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
82
83
84
85
86
87
88
89
90
91
92
using namespace std;
typedef long long ll;
int n,m,r,c,mat[20][20],ans=1000000000;
int cur_r[20],cur_c[20],v_c[20]={0},w[20][20],dp[20][20]={0};
void dfs_c(int at,int cur){
int fm=cur_c[at-1],val,pos;
cur+=v_c[fm];
if(cur>=ans)return;
if(at==c){
ans=min(ans,cur);return ;
}
for(int i=fm+1;i<=m-c+at;i++){
cur_c[at]=i;
if(cur>=ans)return ;
else dfs_c(at+1,cur);
for(int j=0;j<r;j++){
pos=cur_r[j];
val=mat[pos][i]-mat[pos][fm];
if(val<0)val=-val;
cur-=val;
}
}
}
void solve_(){
int pos;
memset(v_c,0,sizeof(v_c));
memset(w,0,sizeof(w));
memset(dp,0,sizeof(dp));
for(int i=0;i<m;i++)
for(int j=1;j<r;j++)
v_c[i]+=abs(mat[cur_r[j]][i]-mat[cur_r[j-1]][i]);
for(int i=0;i<m;i++)
for(int j=i+1;j<m;j++)
for(int k=0;k<r;k++)
pos=cur_r[k],
w[i][j]+=abs(mat[pos][i]-mat[pos][j]);
for(int i=0;i<m;i++)
dp[1][i]=v_c[i];
for(int i=2;i<=c;i++){
for(int j=0;j<m;j++){
pos=1000000000;
for(int k=0;k<j;k++)
if(dp[i-1][k]+w[k][j]<pos)
pos=dp[i-1][k]+w[k][j];
dp[i][j]=pos+v_c[j];
}
}
for(int i=c-1;i<m;i++)
ans=min(ans,dp[c][i]);
}
void dfs_r(int at){
int fm=cur_r[at-1],val;
for(int i=fm+1;i<=n-r+at;i++){
cur_r[at]=i;
for(int j=0;j<m;j++){
val=mat[i][j]-mat[fm][j];
if(val<0)val=-val;
v_c[j]+=val;
}
if(at==r-1)solve_();
else dfs_r(at+1);
for(int j=0;j<m;j++){
val=mat[i][j]-mat[fm][j];
if(val<0)val=-val;
v_c[j]-=val;
}
}
}
void init(){
scanf("%d%d%d%d",&n,&m,&r,&c);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&mat[i][j]);
}
void solve(){
for(int i=0;i<=n-r;i++){
cur_r[0]=i;
dfs_r(1);
}
printf("%d\n",ans);
}
int main(){
init();
solve();
return 0;
}
提高D1T1 生活大爆炸版石头剪刀布
判断胜负你可以用一堆if else 或者 switch case，但最简便的还是打表计算。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
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int tab[5][5]={//A打B
{0,0,1,1,0},
{1,0,0,1,0},
{0,1,0,0,1},
{0,0,1,0,1},
{1,1,0,0,0}};
int n,na,nb,a[205],b[205],ans1=0,ans2=0;
void init(){
n=read(),na=read(),nb=read();
for(int i=0;i<na;i++)a[i]=read();
for(int i=0;i<nb;i++)b[i]=read();
}
void solve(){
int ra,rb;
for(int i=0;i<n;i++)
ra=i%na,rb=i%nb,
ans1+=tab[a[ra]][b[rb]],ans2+=tab[b[rb]][a[ra]];
printf("%d %d\n",ans1,ans2);
}
int main(){
init();
solve();
return 0;
}
提高D1T2 联合权值
这是一棵树，同时点对距离为$2$这个条件也很微妙，所以先把他转化为一棵有根树，再利用父子关系求解。
距离为$2$，我们可以枚举中心点。对于树上的一个点来说，这意味着以他为中心点的点对是由它的父亲与儿子，儿子与儿子构成的。
这样最大的权值好做了，记录儿子中的最大权值和次大权值，比较父亲的权值和儿子中最大权值的积以及儿子中最大、次大权值的积，以此更新答案即可。
但是权值的和就比较麻烦，儿子和父亲形成的点对的权值和好算，但儿子之间相互的乘积是相互乘的，一次要花费$O(儿子数^2)$的时间计算。最坏情况下是$O(n^2)$的。如何优化？
这需要一些数学知识。
设儿子的权值为,那么儿子们的联合权值之和就是。
这里不加证明的给出$2$种在$O(n)$时间计算该值的方法：
1.设，。
更新$g(i)$需要$f(i)$。步骤如下：初始$f(0)=g(0)=0$，$i=1$。
（1：
（2：
（3：$i=i+1$
2.展开可知维护儿子的权值和和权值平方和就可以算出联合权值之和。
代码用的是方法2.
综上所述，在使用$DFS/BFS$对树进行遍历的情况下，以上算法的时间复杂度是$O(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
using namespace std;
typedef struct{
int w,par,son,bro;
}Tree;
Tree tr[200005];
int n,q[200005],f=0,r=0,M=10007,ans=0,ans2=0;
void prepare(){
int i,h,sum,sum2,mx,mx2,e;
for(i=0;i<n;i++)
if(tr[i].par<0){q[r++]=i;break;}
while(r-f){
h=q[f++],sum=sum2=mx=mx2=0;
for(i=tr[h].son;i!=-1;i=tr[i].bro){
e=tr[i].w,
sum=(sum+e)%M,
sum2=(sum2+(e*e)%M)%M;
if(e>mx)mx2=mx,mx=e;
else if(e>mx2)mx2=e;
q[r++]=i;
}
ans2=max(ans2,max(mx*mx2,mx*tr[tr[h].par].w)),
ans=(ans+(tr[tr[h].par].w*sum*2)%M)%M,
ans=(ans+(sum*sum-sum2)%M+M)%M;
}
}
int main(){
scanf("%d",&n);
int i,u,v;
for(i=0;i<n;i++)
tr[i].par=tr[i].son=tr[i].bro=-1;
for(i=0;i<n-1;i++){
scanf("%d%d",&u,&v),
u--,v--;
if(tr[v].par>=0)swap(u,v);
tr[v].par=u,tr[v].bro=tr[u].son,tr[u].son=v;
}
for(i=0;i<n;i++)
scanf("%d",&tr[i].w);
prepare();
printf("%d %d\n",ans2,ans);
return 0;
}
提高D1T3 飞扬的小鸟
一个背包DP的模型。
按$x$坐标划分阶段，状态是坐标，决策有：1.点若干次屏幕；2.不点屏幕。
发现决策$1$对应无限背包，决策$2$对应$01$背包。所以做一次DP。
设$f(i,j,l)$表示到了点$(i,j)$最少需要点击屏幕的次数，其中$l=0$表示本次不点击屏幕，$l=1$表示本次点击。
则状态转移方程容易导出，在此就不列出了。
在转移的时候注意之前转移而来的状态和当前转移的合法性，以及一个细节：在最高处，小鸟可以平移飞行。
时间复杂度：$O(nm)$（近似，因为在最高点有一次枚举）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
using namespace std;
int dp[2][1005][2],n,m,k,up[10005],down[10005],rec[10005][2];
void input(){
scanf("%d%d%d",&n,&m,&k);
int i,j;
for(i=0;i<n;i++)
scanf("%d%d",&up[i],&down[i]),
rec[i][0]=-1,rec[i][1]=m+3;
rec[n][0]=-1,rec[n][1]=m+3;
for(i=0;i<k;i++)
scanf("%d",&j),
scanf("%d%d",&rec[j][0],&rec[j][1]);
}
void solve(){
int res,ans,i,j,t,u,v,o,l,p,q;
for(i=0;i<=m;i++)
dp[0][i][0]=dp[0][i][1]=0;
for(i=1;i<=n;i++){
for(o=0,j=1;j<=m;j++){
dp[i&1][j][0]=dp[i&1][j][1]=INF;
if(j+down[i-1]<=m)
p=(j+down[i-1]<rec[i-1][1])&&(j+down[i-1]>rec[i-1][0]),
q=(j<rec[i][1])&&(j>rec[i][0]),
u=(p)?dp[1^(i&1)][j+down[i-1]][0]:INF,
v=(p)?dp[1^(i&1)][j+down[i-1]][1]:INF,
dp[i&1][j][0]=(q)?min(u,v):INF;
if(j-up[i-1]>0)
for(l=(j==m)?0:up[i-1];l<=up[i-1];l++)
p=(j-l<rec[i-1][1])&&(j-l>rec[i-1][0]),
t=dp[i&1][j-l][1],
u=(p)?dp[1^(i&1)][j-l][0]:INF,
v=(p)?dp[1^(i&1)][j-l][1]:INF,
t=min(min(u,v),t),
dp[i&1][j][1]=min(dp[i&1][j][1],t+1);
if(j<rec[i][1]&&j>rec[i][0]&&(dp[i&1][j][0]<INF||
dp[i&1][j][1]<INF))o=1;
}
if(!o){res=0;break;}
}
if(i==n+1)res=1;
printf("%d\n",res);
if(res)
for(ans=INF,j=n,i=1;i<=m;i++)
ans=min(ans,min(dp[j&1][i][0],dp[j&1][i][1]));
else
for(ans=0,j=0;j<i;j++)
if(rec[j][0]!=-1)ans++;
printf("%d\n",ans);
}
int main(){
input();
solve();
return 0;
}
提高D2T1 无线网络发射器选址
枚举一下路口即可。
或者玩矩阵前缀和。
时间复杂度：$O(128^2 n)$或者$O(d^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
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int d,R,n,sum[1000][1000],cnt=0,ans=0;
void init(){
d=read(),n=read(),R=(d<<1|1);
for(int i=1;i<=n;i++)
sum[read()+R][read()+R]=read();
for(int i=R;i<=128+R+d;i++)
for(int j=R;j<=128+R+d;j++)
sum[i][j]+=sum[i][j-1];
for(int i=R;i<=128+R+d;i++)
for(int j=R;j<=128+R+d;j++)
sum[i][j]+=sum[i-1][j];
}
void solve(){
for(int i=R+d;i<=128+R+d;i++)
for(int j=R+d;j<=128+R+d;j++){
int val=sum[i][j]-sum[i-R][j]-sum[i][j-R]+sum[i-R][j-R];
if(val>ans)ans=val,cnt=1;
else if(val==ans)cnt++;
}
printf("%d %d\n",cnt,ans);
}
int main(){
init();
solve();
return 0;
}
提高D2T2 寻找道路
考虑先删不合法的点，再跑一遍BFS找到最短路。
首先把边反向，从终点跑一下，看看哪些点是合法的。
遍历到的点都是和终点直接或者间接连通着的。对于没有被遍历到的点，就要取消它和它连着的点的合法性。这一步可以直接在下一步跑最短路的时候做。
时间复杂度：$O(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
using namespace std;
typedef long long ll;
typedef struct{
int v,_nex;
}Edge;
Edge edge[400005];
char vis[10005]={0};
int n,m,que[20005],f,r,at[10005],cnt=0,S,T,d[10005];
int at_[10005];
void bfs1(){
f=r=0;
que[r++]=T,vis[T]=1;
int h,i,j,v;
while(r-f){
h=que[f++];
for(i=at[h];i;i=edge[i]._nex){
v=edge[i].v;
if(!vis[v])
vis[v]=1,que[r++]=v;
}
}
}
bool judge(int u){
for(int i=at_[u];i;i=edge[i]._nex)
if(!vis[edge[i].v])return 0;
return 1;
}
void bfs2(){
if(!judge(S))return ;
d[S]=0,f=r=0;
que[r++]=S;
int i,j,h,v,st;
while(r-f){
h=que[f++];
for(i=at_[h];i;i=edge[i]._nex){
v=edge[i].v;
if(!judge(v))continue;
if(d[v]>d[h]+1)
d[v]=d[h]+1,que[r++]=v;
}
}
}
int main(){
scanf("%d%d",&n,&m);
int i,j,u,v;
for(i=0;i<m;i++)
scanf("%d%d",&u,&v),
edge[++cnt].v=u,edge[cnt]._nex=at[v],at[v]=cnt;
scanf("%d%d",&S,&T);
fill(d+1,d+n+1,INF);
bfs1();
for(i=1;i<=n;i++)
for(j=at[i];j;j=edge[j]._nex)
edge[++cnt].v=i,edge[cnt]._nex=at_[edge[j].v],at_[edge[j].v]=cnt;
bfs2();
if(d[T]==INF)printf("-1\n");
else printf("%d\n",d[T]);
return 0;
}
提高D2T3 解方程
高精大概可以做到$50$分。
想一想，带进去一个$x$，怎么判断左边是否是$0$呢？可不可以避免计算这个准确值呢？
学过哈希，我们知道可以把字符串映射到一个值上，值相等那么认为两个字符串相等。但是这个数一般而言很大，所以要对素数取模，来缩小这个值。
（虽然哈希跟这题没什么关系）
我们也可以用这种类似的做法。对于一个$x$，只要把左边的值模一下一个质数$p$，如果答案是$0$，那么左边的值就很有可能是$0$。
为了提高准确程度，我们多模几个质数，如果得到的结果都是$0$，就认为$x$是一个根。
这么做可以拿$70$分，因为判断一个解的时间复杂度是$O(n\times $质数个数$)$的，总时间复杂度是$O(m\times n\times $质数个数$)$。
然后发现其实没必要全部枚举$m$，因为只要几个$x$模$p$的余数相同，左边的值都是相同的。所以只要保存$x=0,1,…p-1$的取模结果即可，时间复杂度是$O(n\times p_{max}\times $质数个数$+m)$。
质数选几个不大不小的即可，推荐选$5$~$6$个。当然如果你幸运EX的话模一两个也是能A掉的。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
using namespace std;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int p[]={9973,10723,10937,11161,13337};
int n,m,a[5][105]={0},fx[5][20000];
char s[100005];
bool ans[1000005];
int read_(int M){;
int f=1,x=0;
if(s[0]=='-')f=-f;
for(char *t=(s[0]=='-'?s+1:s);*t;t++)x=(x*10+*t-'0')%M;
return f*x;
}
void init(){
n=read(),m=read();
for(int i=0;i<=n;i++){
scanf("%s",s);
for(int j=0;j<5;j++)a[j][i]=read_(p[j]);
}
for(int i=0;i<5;i++)
for(int j=1;j<=p[i];j++){
int res=0;
for(int k=n;k>=0;k--)
res=(res*j+a[i][k])%p[i];
fx[i][j]=res;
}
}
void solve(){
int cnt=0,flag;
for(int i=1;i<=m;i++){
flag=0;
for(int j=0;j<5;j++)
if(fx[j][i%p[j]]){
flag=1;
break;
}
if(!flag)cnt++,ans[i]=1;
}
printf("%d\n",cnt);
for(int i=1;i<=m;i++)
if(ans[i])printf("%d\n",i);
}
int main(){
init();
solve();
return 0;
}