2021-02-22-2月22日题解
A题¶
题解¶
构造由n-1个2和一个3或者n-2个2和两个3的数，使其无法被2和3整除。
代码¶
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
if(n==1)
printf("-1\n");
else{
int sum=0;
for(int i=1;i<=n-1;i++)
{
if(i!=n-1)
{
sum+=2;
sum%=3;
printf("2");
}
else
{
if(sum==0)
printf("23\n");
else if(sum==1)
printf("33\n");
else if(sum==2)
printf("23\n");
}
}
}
}
return 0;
}
B题¶
题解¶
模拟，a[1]一定和b[1]相同，x[1]一定为0，然后模拟求2~n个数即可。
代码¶
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int b[200500]={0};
int a[200500]={0};
int main()
{
ll sum=0;
int n,m;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
}
int max1=0;
for(int i=1;i<=n;i++)
{
a[i]=b[i]+max1;
max1=max(max1,a[i]);
}
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
C题¶
题解¶
容易发现如果使求和最大，则每一块应该包含一个最大值，找出前k个最大值求和即为答案，然后对每个最大值的下标进行做差求积即为第二个答案。
代码¶
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long mod=998244353;
struct node
{
int x,p;
};
node a[200500]={0};
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i].x),a[i].p=i;
sort(a+1,a+n+1,[](node a,node b){
if(a.x!=b.x)
return a.x>b.x;
else
return a.p<b.p;});
long long ans1=0,ans2=1;
vector<int>v;
for(int i=1;i<=k;i++)
{
ans1+=a[i].x;
v.push_back(a[i].p);
}
sort(v.begin(),v.end(),[](int a,int b){return a<b;});
for(int i=1;i<v.size();i++)
{
ans2=ans2*(v[i]-v[i-1]);
ans2%=mod;
}
printf("%lld %lld\n",ans1,ans2);
return 0;
}
D题/E题¶
题解¶
可以预处理前缀和后缀相同的部分，然后对剩余部分进行manacher算法，求最长的回文串，注：该回文串必须位于开头或结尾。
参照链接：
https://www.luogu.com.cn/blog/xht37/solution-cf1326d2
https://zhuanlan.zhihu.com/p/137172524
代码¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char a[1005000]={0};
char t[1005000]={0};
int manacher(char *c)
{
int max_id=0,ans=1,id=0;
string str="$#";
for(int i=1;c[i];i++)
str+=c[i],str+="#";
vector<int>p;
p.push_back(1);
for(int i=1;i<(int)str.size();i++)
{
if(max_id>i)
p.push_back(min(max_id-i,p[2*id-i]));
else
p.push_back(1);
while(i+p[i]<(int)str.size()&&str[i+p[i]]==str[i-p[i]])
p[i]++;
if(i==p[i]) ///i==p[i]，代表该回文串位于开头
ans=max(ans,p[i]);
if(i+p[i]>max_id){
max_id=i+p[i],id=i;
}
}
return ans-1;
}
int main()
{
int time;
scanf("%d",&time);
while(time--)
{
scanf("%s",a+1);
int n=strlen(a+1),sum=1;
while(sum<=n&&a[sum]==a[n-sum+1])sum++;
if(sum==n+1)
{
printf("%s\n",a+1);
continue;
}
int m=0;
for(int i=sum;i<=n-sum+1;i++)
t[++m]=a[i];
t[m+1]='\0';
int l_ans=manacher(t);
reverse(t+1,t+m+1);
int r_ans=manacher(t);
reverse(t+1,t+m+1);
if(l_ans<r_ans)
reverse(t+1,t+m+1),swap(l_ans,r_ans);
for(int i=1;i<sum;i++)
printf("%c",a[i]);
for(int i=1;i<=l_ans;i++)
printf("%c",t[i]);
for(int i=sum-1;i>=1;i--)
printf("%c",a[i]);
printf("\n");
}
return 0;
}
组队训练赛A题 Comic Binge¶
题解¶
由于A必须等B读完后才读，那么一种可行的条件便是B把所有的书读完后A再去读所有的书，这样总时长是最大的，且A和B的重合读书时间为0。如果要使总时间最短，那么应当尽可能增大二者的重合读书时间，动态规划即可。
代码¶
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long mod=998244353;
int dp[1050][10050]={0}; ///dp[i][j]代表B在时间j读完前i-1本书二者最大重合读书时间
int sum_a[1050]={0};
int a[1050]={0},b[1050]={0};
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),sum_a[i]=sum_a[i-1]+a[i];
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
int max_b=n*10; ///B最大的时间
for(int i=1;i<=n+1;i++)
for(int j=0;j<=max_b;j++)
dp[i][j]=-1;
dp[1][0]=0;
for(int i=1;i<=n+1;i++)
{
for(int j=0;j<=max_b;j++)
{
if(dp[i][j]==-1)
continue;
if(i<=n&&j+b[i]<=max_b)
{
dp[i+1][j+b[i]]=max(dp[i+1][j+b[i]],min(dp[i][j]+b[i],sum_a[i-1]));
///B读i书，B读完前i本书重合时间最大值
//注意应当和sum_a[i-1]取最小值，由于A落后于B一本书
}
if(i>1&&i+1<=n&&j+b[i+1]<=max_b) ///B读i+1书，不要忘记i>1的条件，B必须读第一本书
dp[i+2][j+b[i+1]]=max(dp[i+2][j+b[i+1]],min(dp[i][j]+b[i+1],sum_a[i]));
}
}
int min1=999999999;
for(int j=0;j<=max_b;j++)
{
if(dp[n+1][j]!=-1)
min1=min(min1,j-dp[n+1][j]+sum_a[n]);
}
printf("%d\n",min1);
return 0;
}
组队训练赛C题 Cul-De-Sac Parades¶
题解¶
树上DP，对每个父节点的的边进行枚举选择，是否使用这个边（假设为边A），如果使用这条边A，则继续搜索子节点，找出连接子节点所有边中权值最大的边，将其与边A进行连接，组成一条通路，其余子节点上的边进行两两匹配组成通路；反之如果不使用这条边A，则继续搜索子节点，让子节点的边进行两两匹配，组成通路。
代码¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
ll to,val;
};
struct node1
{
ll yes,no;
};
vector<node>v[100500];
vector<node>chr[100500];
ll dp[100500][2]={0};
void dfs(ll now,ll fa) ///用于找这个点的子节点
{
for(node i:v[now])
{
if(i.to==fa)
continue;
chr[now].push_back(i);
dfs(i.to,now);
}
}
ll work(ll now,ll has_path) ///has_path代表是否使用这条边
{
if(chr[now].empty())
return 0;
if(dp[now][has_path]!=-1)
return dp[now][has_path];
vector<node1>data;
ll &ans=dp[now][has_path]=0;
for(node i:chr[now])
{
node1 data1;
data1.yes=work(i.to,true)+i.val; //使用这条边，继续搜索子节点
data1.no=work(i.to,false); ///不使用这条边，继续搜索子节点
data.push_back(data1);
}
sort(data.begin(),data.end(),[](node1 a,node1 b){return a.yes-a.no>b.yes-b.no;});
for(node1 i:data)
ans+=i.no; ///先对不使用这些边的权值求和
if(has_path)
ans+=data[0].yes-data[0].no; ///如果父节点使用这条边，则应当找一条权值最大的边与之连接
for(ll i=has_path;i+1<(ll)data.size();i+=2)
{
ll yes=data[i].yes+data[i+1].yes;
ll no=data[i].no+data[i+1].no;
if(yes<no)
break;
else{
ans+=yes-no; ///代表使用这两条边并组成一个通路
}
}
return ans;
}
int main()
{
ll n,s,e,val;
scanf("%lld",&n);
for(ll i=1;i<=n-1;i++)
{
scanf("%lld%lld%lld",&s,&e,&val);
v[s].push_back({e,val});
v[e].push_back({s,val});
}
memset(dp,-1,sizeof(dp));
dfs(1,-1);
ll ans=work(1,false);
if (chr[1].size() == 1) ///1为根节点，这条边必须使用
ans=max(ans,work(1,true));
cout<<ans<<endl;
}