2022.4.30 五一模拟赛 记
前言
说实话，这套题挺厉害的，厉害的超出了我的想象，可以说已经恶心到一个境界了
满分 400pts，我拿了 178 pts，九个参赛学校，两个参赛团体，我 Rk.1，一般吧只能说。。。
T1 小葱的期末考试
一道纯模拟题，官方给的难度是普及-，是挺水的，这个签到题大部分人都签到了。
#include
typedef long long ll;
using namespace std;
struct node{int s1,s2;string name;}arr[305];
bool cmp(node x,node y){
if(x.s1==y.s1){
return x.namey.s1;
}
}
bool com(node x,node y){
if(x.s2==y.s2){
return x.namey.s2;
}
}
int a,b,c,d,e,f;
string s;
int main(){
cin>>a>>b>>c>>d>>e>>f;
arr[0].s1=a+b+c;
arr[0].s2=arr[0].s1+d+e+f;
arr[0].name="cong";
int n;
cin>>n;
for(int i=1;i>s>>a>>b>>c>>d>>e>>f;
arr[i].s1=a+b+c;
arr[i].s2=arr[i].s1+d+e+f;
arr[i].name=s;
}
sort(arr,arr+n,cmp);
for(int i=0;i T2 并联电阻
官方难度普及+/提高
数论题，刚开始打了 8 分暴力，后来尝试优化，自己推了个式子：
for(int i=1;i<=n;i++){
if(tot[i])
cnt*=tot[i]*2+1;
}
式子是推出来，但是白写，，，但是非常脑*地用了一个sqrt(n)在for循环里作为指数分解，所以，，，，还是 8pts。
T3 答题
最大上升子序列，最优解是两端同时记录，但是当时由于T2废了太久时间，就直接写了一个\(O(5000*n)\)的 50 分代码，很幸运，这个题我是最高分，，也因为这个 Rk.1
#include
using namespace std;
namespace Main{
const int inf=0x3f3f3f3f;
const int maxn=100005;
int n;
int a[maxn];
int f[maxn];
int len[maxn],len2[maxn];
vector pro[5005];
vector pro2[5005];
int maxx[maxn];
void main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
len[i]=1;
for(int j=1;j=1;i--){
len2[i]=1;
for(int j=a[i]+1;j<=5000;j++){
for(int k:pro[j]){
len2[i]=max(len2[i],len2[k]+1);
}
}
pro2[a[i]].emplace_back(i);
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,f[i]+len2[i]-1);
}
printf("%d",ans);
}
}
int main(){
Main::main();
return 0;
}
T4 冰糖葫芦
压轴题，难度给到了提高+/省选-
正解其实很好想到，将字符串从新排序然后字典树即可，还是因为第二题的缘故，没时间了，，，就直接暴搜了
20pts：
#include
#define int long long
using namespace std;
void read(int &x){
x=0;
char c=getchar();
while(!('0'<=c && c<='9')){
c=getchar();
}
while('0'<=c && c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
}
char s[1010][50];
int len[1010],val[1010][1010]={0};
bool is[1010]={0};
int n,cur=0,mx=0;
void dfs(int k){
if(k==n+1){
mx=max(mx,cur);
}else{
if(!is[k]){
is[k]=true;
for(int i=k+1;i<=n;i++){
is[i]=true;
cur+=val[k][i];
dfs(k+1);
cur-=val[k][i];
is[i]=false;
}
}else{
dfs(k+1);
}
}
}
signed main(){
read(n);
for(int i=1;i<=n;i++){
scanf(" %s",s[i]+1);
len[i]=strlen(s[i]+1);
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
int cur=min(len[i],len[j]);
for(int k=0;cur;k++){
cur--;
if(k%2==0){
if(s[i][k/2+1]==s[j][k/2+1]){
val[i][j]++;
}else{
break;
}
}else{
if(s[i][len[i]-k/2]==s[j][len[j]-k/2]){
val[i][j]++;
}else{
break;
}
}
}
}
}
dfs(1);
printf("%lld",mx);
return 0;
}