517秋季好题集锦

以后模拟赛里的好题就放这里了,有有意义知识点会专门一篇

%你赛1

T3

一道DP,dp[i][0] dp[i][1] dp[i][2]分别表示从1到i的最优解,区别是
0 最后一个不选
1 最后一个正在乘
2 乘完了,最后一个无法乘
注意每次更新都要和0比较,因为可以到目前为止一个都不选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,x,b,ans=-100000;
ll a[300005],dp[300005][3];
int main()
{
scanf("%lld%lld",&n,&x);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
dp[1][2]=-1000000;
for(int i=1;i<=n;i++)
{
dp[i][0]=max(b,max(dp[i-1][0]+a[i],a[i]));
dp[i][1]=max(b,max(max(dp[i-1][1],dp[i-1][0])+a[i]*x,a[i]*x));
dp[i][2]=max(b,max(dp[i-1][1],dp[i-1][2])+a[i]);
ans=max(b,max(ans,max(dp[i][0],max(dp[i][1],dp[i][2]))));
}
printf("%lld\n",ans);
}

T4

alsoDP,dp[i][j]表示从i到j的最优解,答案自然就是dp[1][n],注意区间是从前往后,所以遍历是i在j外边
转移方程:dp[i][j]=max(dp[i][k]+dp[k][j]+w[i]*w[j])其中k是i~j中的一个合法的点,先吃别的,最后吃掉它之后就会只剩i和j

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int n;
int a[55];
int dp[60][60];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=1;i+j-1<=n;j++)
for(int k=j+1;k<=i+j-2;k++)
dp[j][i+j-1]=max(dp[j][i+j-1],dp[k][i+j-1]+dp[j][k]+a[j]*a[i+j-1]);
cout<<dp[1][n]<<endl;
}

%你赛2

T3

构造题,规则如下(括号中为个数):

1
2
3
4
5
6
7
8
9
10
11
12
ab最小
a:0000(ac)
b:1111(bc)0000(ab)
c:0000(ac)1111(bc)
ac最小
a:0000(ab)
b:0000(ab)1111(bc)
c:1111(bc)0000(ac)
bc最小
a:0000(ac)1111(ab)
b:1111(ab)0000(bc)
c:0000(ac)
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
#include<bits/stdc++.h>
using namespace std;
int ab,bc,ac;
string a,b,c;
int main()
{
cin>>ab>>bc>>ac;
if(ab<=min(bc,ac))
{
for(int i=1;i<=ac;i++)a=a+'0';
cout<<a<<endl;
for(int i=1;i<=bc;i++)b=b+'1';for(int i=1;i<=ab;i++)b=b+'0';
cout<<b<<endl;
for(int i=1;i<=ac;i++)c=c+'0';for(int i=1;i<=bc;i++)c=c+'1';
cout<<c<<endl;
}
else
{
if(bc<=min(ac,ab))
{
for(int i=1;i<=ac;i++)a=a+'0';for(int i=1;i<=ab;i++)a=a+'1';
cout<<a<<endl;
for(int i=1;i<=ab;i++)b=b+'1';for(int i=1;i<=bc;i++)b=b+'0';
cout<<b<<endl;
for(int i=1;i<=ac;i++)c=c+'0';
cout<<c<<endl;
}
else
{
for(int i=1;i<=ab;i++)a=a+'0';
cout<<a<<endl;
for(int i=1;i<=ab;i++)b=b+'0';for(int i=1;i<=bc;i++)b=b+'1';
cout<<b<<endl;
for(int i=1;i<=bc;i++)c=c+'1';for(int i=1;i<=ac;i++)c=c+'0';
cout<<c<<endl;
}
}
}

%你赛3

T3

多源bfs

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
#include<bits/stdc++.h>
using namespace std;
int n,m,p,over;
int s[10];
int ans[10];
int qx[5]={0,0,-1,1};
int qy[5]={1,-1,0,0};
int belong[1005][1005];
char mapp[1005][1005];
struct node
{
int x,y,step;
node(){}
node(int xx,int yy,int stepstep)
{
x=xx,y=yy,step=stepstep;
}
};
node chan[1000005];
queue<node>q[10];
void bfs()
{
over=1;
while(over)
{
over=0;
for(int i=1;i<=p;i++)
{
int cnt=0;
while(q[i].size())
{
node a=q[i].front();
q[i].pop();
if(a.step==0)
{
a.step=s[i];
chan[++cnt]=a;
continue;
}
for(int j=0;j<4;j++)
{
int xx=a.x+qx[j];
int yy=a.y+qy[j];
if(mapp[xx][yy]!='#'&&xx>=1&&xx<=n&&yy>=1&&yy<=m&&!belong[xx][yy])
{
q[i].push(node(xx,yy,a.step-1));
belong[xx][yy]=i;
over=1;
}
}
}
for(int j=1;j<=cnt;j++)
q[i].push(chan[j]);
}
}
}
int main()
{
cin>>n>>m>>p;
for(int i=1;i<=p;i++)
cin>>s[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>mapp[i][j];
if(mapp[i][j]>='1'&&mapp[i][j]<='9')
{
q[(int)mapp[i][j]-'0'].push(node(i,j,s[(int)mapp[i][j]-'0']));
belong[i][j]=(int)mapp[i][j]-'0';
}
}
}
bfs();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans[belong[i][j]]++;
for(int i=1;i<=p;i++)
cout<<ans[i]<<" ";
}

%你赛4

T4

若两个数GCD大于1,即这两个数有至少一个大于1的公因子。因此我们先筛选出所有2~1e5的数的因子。每个因子i初值为dp[i]=0; 一旦这个数的某个因子i 的dp[i]+1后成为这个数的所有因子中dp值最大的,那也就意味着挑选这个数可以使满足条件的序列长度最多为dp[i];
因此我们把它的所有因子的dp值都更新成dpi,这样下一个数只要和这一个数有任意一个>1的公因子,便可将下一个数加入合法的序列中使合法序列长度增加。于是就完成了状态转移。 最后遍历一遍dp取最大值即可。

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
#include<bits/stdc++.h>
using namespace std;
int a[1000000],f[1000000],n;
vector <int> y[1000000];
void maky(int x)
{
int p=a[x];
y[x].push_back(p);
for(int i=2;i<=floor(sqrt(p));i++)
{
if(p%i==0)
{
y[x].push_back(i);
if(i!=p/i)y[x].push_back(p/i);
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
maky(i);
}
for(int i=1;i<=n;i++)
{
int maxx=-0;
for(int j=0;j<y[i].size();j++)
f[y[i][j]]++,maxx=max(maxx,f[y[i][j]]);
for(int j=0;j<y[i].size();j++)
f[y[i][j]]=maxx;
}
for(int i=1;i<=a[n];i++)
f[0]=max(f[0],f[i]);
cout<<f[0]<<endl;
}

%你赛5

T2

两(行/列)确定,全盘确定

dp算出所有可能情况,枚举相乘,保证面积小于k,求和相加即可得到答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
#define ll long long
#define M 998244353
using namespace std;
int n,k;
ll dp[3000][3000],sum[3000][3000],ans;
int main()
{
cin>>n>>k;
dp[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
for(int p=1;p<=j;p++)
dp[i][j]=(dp[i][j]+dp[i-p][min(j,i-p)]+M)%M;
for(int i=n;i>=1;i--)dp[n][i]=(dp[n][i]-dp[n][i-1]+M)%M;
for(int i=1;i<=n;i++)
for(int j=1;j*i<k;j++)
ans+=dp[n][i]*dp[n][j]%M;
cout<<ans*2%M<<endl;
}

T4

一个点如果不合法,把他的父节点连到根比把他自己连到根要合适一些。直接dfs遍历整棵树,遇到一个点的子节点不合法就把这个点连到根,它的子节点不会被二次搜到,dis值可以不更新,但是它的父节点一定要更新成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
#include<bits/stdc++.h>
using namespace std;
int n,x,y,sum;
int de[200005],f[200005];
vector<int> tree[200005];
set<pair<int,int> >check;
void dfs(int pos,int depth,int father)
{
de[pos]=depth;
f[pos]=father;
for(int i=0;i<tree[pos].size();i++)
{
if(tree[pos][i]!=father)
{
dfs(tree[pos][i],depth+1,pos);
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
tree[x].push_back(y);
tree[y].push_back(x);
}
dfs(1,0,-1);
for(int i=1;i<=n;i++)
if(de[i]>2)
check.insert(make_pair(-de[i],i));
while(check.size())
{
int p=check.begin()->second;
p=f[p];
sum++;
auto it=check.find(make_pair(-de[p],p));
if(it!=check.end())
check.erase(it);
for(auto x : tree[p])
{
auto it=check.find(make_pair(-de[x],x));
if(it!=check.end())
check.erase(it);
}
}
cout<<sum<<endl;
}

%你赛6

T3

让大矩形的宽和长尽量靠近。把能被aa或bb整除的边长都存上(if(a%len==0)s.insert(a/len)),然后遍历sqrt(a+b)sqrt(a+b)到1,碰到能被a+ba+b整除的边长就查找是否包含最小的能被aa或bb整除的边长((a+b)%len==0&&*s.begin()<=(a+b)/len)。

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<bits/stdc++.h>
using namespace std;
#define ll long long
ll a,b,ans,x,y,z;
ll yina[70000],yinb[70000];
int main()
{
cin>>x>>y;
for(ll i=(ll)sqrt(x);i>=1;i--)
{
if(x%i==0)
{
yina[++a]=i;
}
}
for(ll i=(ll)sqrt(y);i>=1;i--)
{
if(y%i==0)
{
yinb[++b]=i;
}
}
z=x+y;
for(ll i=(ll)sqrt(z);i>=1;i--)
{
if(z%i!=0)continue;
int flag=0;
for(ll j=a;j>=1;j--)
{
if(yina[j]<=i&&x/yina[j]<=z/i||x/yina[j]<=i&&yina[j]<=z/i)
{
flag=1;
}
if(flag==1)
{
break;
}
}
for(ll j=b;j>=1;j--)
{
if(yinb[j]<=i&&y/yinb[j]<=z/i||y/yinb[j]<=i&&yinb[j]<=z/i)
{
flag=1;
}
if(flag==1)
{
break;
}
}
if(flag==1)
{
cout<<2*(i+z/i)<<endl;
return 0;
}
}
}

%你赛7

T4

要求字典序最小,所以我们改变这个矩阵中的字符,一定是把不是 a 的字符改成 a ,而且我们走一条路径的时候,一定是把所有机会全用到(如果 k 过大就可以全是 a ),并且尽可能地要让前面变成 aa 。所以我们设f[i][j]f[i][j]表示从(1,1)(1,1) 走到(i,j)(i,j)全走a至少要改变多少次,由于只能向下和向右走,所以f[i][j]f[i][j]只可能从f[i−1][j],f[i][j−1]f[i−1][j],f[i][j−1]转移过来。DP复杂度O(n^2)。之后,我们把f[i][j]≤k的点找出来,找出所有走得最远的点,作为接下来BFS的起点。

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
#include<bits/stdc++.h>
using namespace std;
int n,k,maxx;
int qx[]={0,1};
int qy[]={1,0};
int dp[2005][2005],ans[5005];
int vis[2005][2005];
char mapp[2005][2005];
struct node
{
int x,y,step;
};
queue<node>q;
void bfs()
{
if(!q.size())
{
q.push((node){1,1,1});
ans[1]=mapp[1][1]-'a';
}
while(q.size())
{
node a=q.front();
q.pop();
if(mapp[a.x][a.y]-'a'>ans[a.step]||a.step<maxx)continue;
for(int i=0;i<2;i++)
{
int xx=a.x+qx[i];
int yy=a.y+qy[i];
if(xx<=n&&yy<=n&&xx>=1&&yy>=1&&ans[a.step+1]>=mapp[xx][yy]-'a'&&!vis[xx][yy])
{
vis[xx][yy]=1;
ans[a.step+1]=mapp[xx][yy]-'a';
q.push((node){xx,yy,a.step+1});
}
}
}
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>mapp[i][j];
}
}
memset(ans,0x3f,sizeof(ans));
memset(dp,0x3f,sizeof(dp));
dp[1][0]=dp[0][1]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(mapp[i][j]=='a')
{
dp[i][j]=min(dp[i-1][j],dp[i][j-1]);
}
else
{
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
}
if(dp[i][j]==k&&maxx<=i+j-1)
{
maxx=i+j-1;
vis[i][j]=1;
q.push((node){i,j,i+j-1});
}
}
bfs();
if(dp[n][n]<k)
{
for(int i=1;i<=2*n-1;i++)
{
cout<<'a';
}
}
else
{
for(int i=1;i<=maxx;i++)
{
cout<<'a';
}
for(int i=maxx+1;i<=2*n-1;i++)
{
printf("%c",ans[i]+'a');
}
}
}

%你赛8

%你赛9

巧妙建图

利用floyd求出每个城市之间的最短距离。
如果城市间最短距离小于等于L,则记路径权重为1,表示只需要加一次油就可以到达。
如果最短距离大于L,则标记为无穷,记为无穷大,表示不能够直接到达。
再利用上述方法产生新的路径及权值,跑一遍floyd。即可获得任意两城市之间最少需要加多少次油。
注:无穷大,则视为不可达输出-1,输出最终答案时要减一,因为初始油箱是满的。

T5

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
#include<bits/stdc++.h>
#define int long long
#define inf 100000000000
using namespace std;
int n,m,l,a,b,c,q,s,t;
int mapp[305][305];
int mappp[305][305];
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
signed main()
{
n=read(),m=read(),l=read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j)
mapp[i][j]=inf;
}
}
for(int i=1;i<=m;i++)
{
a=read(),b=read(),c=read();
mapp[a][b]=mapp[b][a]=c;
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
mapp[i][j]=min(mapp[i][j],mapp[i][k]+mapp[k][j]);
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mapp[i][j]<=l)
{
mappp[i][j]=1;
}
else
{
mappp[i][j]=inf;
}
}
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
mappp[i][j]=min(mappp[i][j],mappp[i][k]+mappp[k][j]);
}
}
}
q=read();
while(q--)
{
s=read(),t=read();
if(mappp[s][t]==inf)cout<<-1<<endl;
else cout<<mappp[s][t]-1<<endl;
}
}

T6

二分答案

可以的情形是这样的

可以通过前缀和优化

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x;
int b[300005],sum[300005];
bool judge(int k,int x)
{
int l=1,r=n,p;
while(l<=r)
{
int mid=(l+r)/2;
if(b[mid]<x&&(mid==n||b[mid+1]>=x))
{
p=mid;
break;
}
if(b[mid]<x)l=mid+1;
else r=mid-1;
}
if((n-p)*x+sum[p]>=k*x)return 1;
return 0;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
b[x]++;
}
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+b[i];
x=n;
for(int k=1;k<=n;k++)
{
while(x&&!judge(k,x))x--;
cout<<x<<endl;
}
}

%你赛10

T5

很容易想到写n方代码,但显然会T飞

mapp[x][i]储存第i个x+’a’对应的字符在s中出现的位置

k代表t中我们要进行搜索的字符的位置

然后模拟

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s,t;
int sum,j,x,k,n,m;
vector<int>mapp[30] ;
signed main ()
{
cin>>s>>t;
n=s.length(),m=t.length();
for(int i=0;i<s.size();i++)
mapp[s[i]-'a'].push_back(i+1);
if(mapp[t[0]-'a'].size()==0)
{
puts("-1") ;
return 0 ;
}
k=mapp[t[0]-'a'][0];
sum+=k;
for(int i=1;i<m;i++)
{
x=t[i]-'a' ;
if(!mapp[x].size())
{
puts("-1") ;
return 0 ;
}
j=upper_bound(mapp[x].begin(),mapp[x].end(),k)-mapp[x].begin() ;
if(j==mapp[x].end()-mapp[x].begin())//没找到,再来一个
sum+=mapp[x][0]+n-k,k=mapp[x][0];
else //找到了
sum+=mapp[x][j]-k,k=mapp[x][j];
}
cout<<sum<<endl;
}