Contest3137 - 2022-2023-2 ACM集训队每月程序设计竞赛（1）五月月赛

A 1! 5! 46 169

有一种数字，我们称它为 纯真数。 它等于自身每一个数位的阶乘之和。请你求出不超过n的所有 纯真数。(注：纯真数不含有前导0）数据范围1e18

纯真数只有四个，注意0!=1
1,2,145,40585

int n;cin>>n;int res[]={1,2,145,40585};if(n>=1)cout<<res[0]<<endl;if(n>=2)cout<<res[1]<<endl;if(n>=145)cout<<res[2]<<endl;if(n>=40585)cout<<res[3]<<endl;

B 翻转板游戏 4 26

幼儿园引进了一款新玩具，是包含若干块翻转板的一条长链。初始时翻转板上每块板子正面或反面朝上，游戏的目的为将所有翻转板最终翻转为均正面朝上。
老师认为翻转板游戏的原设置太过于简单，不能满足幼儿园里天才儿童们的游玩需求（要被小孩子嫌弃啦！），于是想要基于原游戏设备对于游戏进行升级。
为增加游戏难度， 老师规定：对于翻转板长链进行的每次操作，必须选择连续的至少 k块板子进行翻转。
现给定翻转板长链每块板子的初始状态，请你帮老师找到最大的限制条件 k，使得游戏难度最大但最终游戏有解（即一定存在至少一种方式可通过若干次操作使得所有翻转板最终翻转为正面朝上），并输出最大的 k
输入共一行，包含一个 01字符串 1~1e5
0表示第i块板子初始时正面朝上；1表示第i块板子初始时反面朝上

从左向右遍历，遇到不相等的两块板子，要么把前半边全部翻转（i+1个)，要么把后半边全部翻转(len-i+1个)，选择较大的那种翻转方式，遍历一遍，找出可以这样做的最小的k

signed main(){IOS;string s;cin>>s;int len=s.size(),ans=len;fer(i,0,len-1){if(s[i]!=s[i+1]){ans=min(ans,max(i+1,len-i-1));}}cout<<ans;return 0;
}

C 地毯规划 7 23

输出
4
暴力

const int N=101,mod=1e9+7;
int a[N][N],b[N][N];
signed main(){IOS;int n,m;cin>>n>>m;fer(i,0,n){fer(j,0,m)cin>>a[i][j];//要求 }int cnt,mn=1e18;fer(x,1,n+1){//遍历毯子大小xfer(y,1,n+1){//遍历毯子大小yfer(i,0,n){fer(j,0,m)b[i][j]=a[i][j];}//重置要求 cnt=0;bool f=1;fer(i,0,n){//遍历要求 fer(j,0,m){//遍历要求 int t=b[i][j];if(t==0)continue;else if(t<0){f=0;break;}else{cnt+=t;if(t>0&&i+x<=n&&j+y<=m){//可以铺毯子 fer(s,i,i+x){//把铺上毯子的地方减去 fer(k,j,j+y){b[s][k]-=t;}}}else {f=0;break;}}}if(!f)break;}if(f){mn=min(mn,cnt);//cout<<"x="<<x<<" y="<<y<<" "<<mn<<endl;}}}cout<<mn<<endl;return 0;}

D 国王移动 48 104

	int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;int horizon=abs(x1-x2);int vertical=abs(y1-y2);if(horizon>vertical)swap(horizon,vertical);//horizon<=vertical int res=vertical;cout<<res<<endl;

E 面包店 1 12

输出
2
由大到小排袋子，由美味值大到小排面包，双指针遍历，可以不选面包

int pack[N];
struct node{int size,taste;
};
bool cmp(node &a,node &b){if(a.taste==b.taste)return a.size>b.size;return a.taste>b.taste;
}
signed main(){IOS;int n,m;cin>>n>>m;vector<node> bread;fer(i,0,n){int a,b;cin>>a>>b;bread.pb({a,b});}fer(i,0,m)cin>>pack[i];sort(pack,pack+m,greater<int>());sort(bread.begin(),bread.end(),cmp);int cnt=0,j=0;fer(i,0,m){if(j>=n)break;if(bread[j].size<=pack[i]){j++;cnt++; }else{j++;i--;}}cout<<cnt;return 0;
}

F 拥挤的珠峰 0 11

G 最终会相等的 1 11

//暴力解法，54% TLE
const int N=2e5+1,mod=1e9+7;
int a[N],b[N];
int mn=1e18,n;
int dfs(int t){if(t==n-1){if(a[t]==b[t])return 0;else return -1;}if(a[t]==b[t])return dfs(t+1);int minn=1e18;if(a[t]!=b[t]){fer(i,t+1,n){if(a[i]+i-t==b[t]){//可以左加 int x=a[i];for(int j=i;j>t;j--){//所有数右移 a[j]=a[j-1]-1;} a[t]=x;int dg=dfs(t+1);if(dg==-1)continue;else minn=min(minn,dg+i-t);for(int j=t;j<i;j++){//所有数左移 a[j]=a[j+1]+1;}a[i]=x;}}if(minn!=1e18)return minn;else return -1;}
}
signed main(){IOS;cin>>n;int suma=0,sumb=0;fer(i,0,n){cin>>a[i];suma+=a[i];}fer(i,0,n){cin>>b[i];sumb+=b[i];}if(suma!=sumb)cout<<-1<<endl;else{int res=dfs(0); if(res!=-1)cout<<dfs(0)<<endl;else cout<<-1<<endl;}return 0;}

H 新版奔跑在北化 27 122

int a[N];
signed main(){IOS;int n,k;cin>>n>>k;int neg=-1,zero=0;fer(i,0,n){cin>>a[i];if(a[i]<0)neg=i;//最后一个负数的位置 else if(a[i]==0)zero++;}int cnt=0;if(zero==1)cnt++;int mn=1e18;int tmp;fer(i,0,n){//i是到达的该半轴的终点 tmp=cnt;//已打卡点数int cost=0; if(a[i]<0){tmp+=neg-i+1;//打卡了这么多点 cost+=abs(a[i]);if(tmp<k){if(neg+k-tmp<n){cost+=abs(a[i]);//折返 cost+=a[neg+k-tmp];}else continue;}}else if(a[i]>0){tmp+=i-neg;cost+=a[i];if(tmp<k){if(neg-k+tmp+1>=0){cost+=a[i];cost+=abs(a[neg-k+tmp+1]);}else continue;}}mn=min(mn,cost);}cout<<mn<<endl;return 0;}

I 花束紧凑 0 1

J 除杂草 37 246

	int n;cin>>n;fer(i,0,n)cin>>a[i];int kill=-1; bool f=1;fer(i,0,n-1){if(a[i]>a[i+1]){kill=i;break;//拔掉高的}}fer(i,0,n-1){if(i+1==kill){if(a[i]>a[i+2]){f=0;break;}}else if(i==kill){continue;}else{if(a[i]>a[i+1]){f=0;break;}}}if(f)cout<<"Yes"<<endl;else {f=1;fer(i,0,n-1){if(a[i]>a[i+1]){kill=i+1;break;//拔掉矮的 }//kill范围是1~n-1 }fer(i,0,n-1){if(i+1==kill&&i+2<n){if(a[i]>a[i+2]){f=0;break;}}else if(i==kill){continue;}else{if(a[i]>a[i+1]){f=0;break;}}}if(f)cout<<"Yes"<<endl;else cout<<"No"<<endl;}