2017Summmer_上海金马五校 F题,G题,I题,K题,J题

时间:2023-03-08 16:24:26

以下题目均自己搜

F题  A序列

一开始真的没懂题目什么意思,还以为是要连续的子串,结果发现时序列,简直智障,知道题意之后,好久没搞LIS,有点忘了,复习一波以后,直接双向LIS,处理处两个数组L和R,然后对整个数组扫一遍对于每一个下标取m=min(L[i],R[i]);用ans取2*m-1中的最大值。LIS用nlogn的算法实现,二分用的是lower_bound(),直接看代码。

//Author: xiaowuga
#include <bits/stdc++.h>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
const long long N=;
using namespace std;
typedef long long LL;
int dp[N];
int L[N],R[N];
int main() {
ios::sync_with_stdio(false);cin.tie();
int n;
int a[N];
while(cin>>n){
for(int i=;i<n;i++){
cin>>a[i];
}
memset(dp,inf,sizeof(dp));
for(int i=;i<n;i++){
int pos=lower_bound(dp,dp+n,a[i])-dp;
dp[pos]=a[i];
L[i]=pos+;
} memset(dp,inf,sizeof(dp));
for(int i=n-;i>=;i--){
int pos=lower_bound(dp,dp+n,a[i])-dp;
dp[pos]=a[i];
R[i]=pos+;
}
for(int i=;i<n;i++) cout<<L[i]<<" "; cout<<endl;
for(int i=;i<n;i++) cout<<R[i]<<" "; cout<<endl;
int ans=minn;
int tmp;
for(int i=;i<n;i++){
int tmp=min(L[i],R[i]);
ans=max(tmp*-,ans);
}
cout<<ans<<endl;
}
return ;
}

G题 战斗

暴力阶乘题,因为n<10,所以暴力枚举全排列所有的出战顺序,然后模拟和电脑去打就好了,复杂度n*n!。不要真的老实的的每一次攻击的去模拟,万一两个两个怪兽都是1000的血1的攻击力,一次枚举,十个怪兽就是10000的计算计算量,而你的枚举量可能高达10!三百多万啊,绝逼超时GG,所以直接除找到每组对战的怪兽需要各自攻击对方几次才会死,然后取最小值,将hp减去攻击次数*攻击力,得到怪兽战后的状态,对于hp<=0的我们就换人。还有不要确切的计算具体要攻击多少次,因为有的时候比如你是9的hp,5的五的攻击力,9/5=1,实际上要攻击两次才会死攻击次数是hp/at+1。然后如果双方的hp变成10,10/5=2,刚好死亡攻击次数恰好是hp/at,这个时候如果用%取判断了话,是会超时的,因为%与运算是比较慢的。所以我们用一个while循环,模拟最后一次攻击,将会比算出这个具体的攻击次数速度要快。这就是我为什么一开始超时的原因,还有一个优化就是要枚举的时候都要复制一遍双方的怪兽信息,因为只有当前的怪兽有用,所以我们用一个值来存就好了,如果你用结构体,每次就有一个攻击实际上不用复制但是复制了,实际上浪费了时间,面对10!的枚举量,也会慢很多,然后就是边打边复制,这样有的时候电脑其实一只怪兽就团灭你了,但是你却多复制了其他怪兽同样浪费时间。

最后还有一个逆天优化:就是我们每次记住上一次枚举出场的顺序,如果电脑两只怪兽就把你团灭了,那么如果你下一次枚举前两只怪兽出场顺序没有发生改变,那么电脑还是可以用两只怪兽把你团灭,无论你后面的怪兽如何出出站,压倒性的实力。这样的枚举是无用的,如果对他的战斗进行模拟,又会有大量的复制会是无用功,而且对于字典序全排列,大多数的枚举的前几位都和上一次枚举基本是一样的。这就给我们启发,使我们可以快速的跳过一下无用的枚举,将n*n!的复杂度,优化成n!,加快了近十倍的速度。大概只需要100ms就可以ac,当然后还有2^n复杂度的做法,那个就更快了,需要用到状态压缩dp,本人目前不会。

//Author: xiaowuga
#include <bits/stdc++.h>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
const long long N=;
using namespace std;
typedef long long L;
struct M{
int at,hp,pos;
bool operator <(const M &m) const{
return at<m.at;
}
}me[N],co[N];
M cm[N],mm[N];
int main() {
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=;i<n;i++) scanf("%d%d",&co[i].hp,&co[i].at);
for(int i=;i<n;i++) {scanf("%d%d",&me[i].hp,&me[i].at);}
int flag=,flag2=;
int c1=,c2=,m;
sort(me,me+n);
do{
if(flag2){
if(c1==) break;
else{
int ifsame=;
for(int i=;i<=c1;i++){
if(me[i].at!=mm[i].at) {ifsame=;break;}
}
if(ifsame) continue;
}
}
flag2=;
c1=;c2=;
cm[]=co[]; mm[]=me[];
while(c1<n&&c2<n){
m=min(cm[c1].hp/mm[c2].at,mm[c2].hp/cm[c1].at);
cm[c1].hp-=m*mm[c2].at;
mm[c2].hp-=m*cm[c1].at;
while(cm[c1].hp>&&mm[c2].hp>){
cm[c1].hp-=mm[c2].at;
mm[c2].hp-=cm[c1].at;
}
if(cm[c1].hp<=) {c1++;cm[c1]=co[c1];}
if(mm[c2].hp<=) {c2++;mm[c2]=me[c2];}
}
if(c1==n&&c2<n) {flag=;break;}
}while(next_permutation(me,me+n));
if(flag) printf("YES\n");
else printf("NO\n");
}
return ;
}

I题   丢史蒂芬妮

博弈xjb搜题,博弈论知识不好,别人告诉我怎么搜的。xjb搜了一波,就过了,不是特别理解。直接代码吧!

//Author: xiaowuga
#include<cstdio>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
const long long N=;
using namespace std;
typedef long long L;
int vis1[N]={};
int num=;
int primnum_list[N];
void make_primnum(){
for(int i=;i<N/;i++)
for(int j=*i;j<N;j+=i){
vis1[j]=;
}
for(int i=;i<N;i++){
if(vis1[i]==) primnum_list[num++]=i;
}
}
int mat[N][N]={},vis[N][N]={};
int dfs(int x,int y){
if(vis[x][y]) return mat[x][y];
vis[x][y]=;
for(int i=;i<num;i++){
int t=primnum_list[i];
if(x-t>) mat[x][y] |=!(dfs(x-t,y));
if(y>t>) mat[x][y] |=!(dfs(x,y-t));
if(x-t>&&y-t>) mat[x][y] |=!(dfs(x-t,y-t));
}
return mat[x][y];
}
int main() {
make_primnum();
for(int i=;i<=;i++)
for(int j=;j<=;j++){
mat[i][j]=dfs(i,j);
}
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
if(mat[n][m]) printf("Sora\n");
else printf("Shiro\n");
}
return ;
}

K题   购买装备

第一眼尼玛不是一个背包dp吗?还是0-1背包,结果native了,10000的物品,一亿的预算,背包的复杂度更本跑不出来,所以我们采用贪心的思路。

我们首先要把问题分开去思考,这样有助于我们思考,而不会因为问题整体比较比较复杂,从而在思考上停滞不前,应该要把什么是主要问题什么是次要问题搞懂,题目中次要问题,是在主要问题的限制之下,也就是在购买尽量多的物品的情况下,物品中属性最小的值尽量大。首先是购买尽量多的物品,由于每个物品只能买一次,所以买便宜的物品,剩下的钱更多,也就可以买更多的物品,所以贪心对价格排序得到最大可以购买的数量m,但是这不一定是最小属性最大的。所以我们接着看后半部分的问题,问题就变成了在n个物品里面选m个其中属性最小的的物品的值要尽量大,标准的最小值最大化的套路。对属性排序,二分枚举属性,在大于等于当前枚举的最小属性中,对价格排序取 前m个,判断是否小于等于预算,这个是学长的做法,我也想过。但是每次复制一遍再排序,所以觉得没可行,所以没敢试。谁知学长用了特殊姿势。用了nth_element()这个库函数,使用m次,直接排序复杂度nlogn,减去复制的过程防止复杂度上升到n^2logn,从而使复杂度变为nlognlogn,这个复杂度可以满足题目的数据量。但是我想到是另一个种方法,前面和学长一样得到m的最大购买数量,然后对属性排序(从大到小),取前m个元素判断是否满足预算(枚举下标为m-1的元素为最小属性),不满足则枚举下标为m的元素为最小属性,从前m+1个元素里取m个最便宜的看一下,是否满足预算,不满足再次往后枚举,直到满足要求,我也需要复制一遍再排序,然而我想到用优先队列优化,建立一个大小为m的优先队列,计算一个堆的价格总和,然后每次枚举我们把堆顶元素pop,将枚举的元素插入,计算总价格的改变值,判断是否满足要求,直到满足要求位置。由于删除和插入的操作复杂度都是logn,所以总体的复杂度是nlogn,以下是我的代码

//Author: xiaowuga
#include <bits/stdc++.h>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
const long long N= 1e5+;
using namespace std;
typedef long long L;
priority_queue<long long, vector<long long>,less<long long> >q;
struct equip{
long long a,b;
}oj[N];
bool cmp1(equip x,equip y){
return x.b<y.b;
}
bool cmp2(equip x,equip y){
return x.a>y.a;
}
int main() {
long long T,n,m;
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&m);
for(int i=;i<n;i++) scanf("%lld%lld",&oj[i].a,&oj[i].b);
sort(oj,oj+n,cmp1);
long long sum=,k=;
for(int i=;i<n;i++){
if(sum+oj[i].b<=m){sum+=oj[i].b;k++;}
else break;
}
sort(oj,oj+n,cmp2);
sum=;
while(!q.empty()) q.pop();
for(int i=;i<k;i++){
q.push(oj[i].b);
sum+=oj[i].b;
}
if(sum<=m) {printf("%lld %lld\n",k,oj[k-].a);continue;}
for(int i=k;i<n;i++){
sum=sum-q.top()+oj[i].b;
if(sum<=m){ printf("%lld %lld\n",k,oj[i].a); break; }
q.pop();q.push(oj[i].b);
}
}
return ;
}

J题   膜一下将带给你好运

我一开始还以为这个题很难,没想到一个暴力题。抱歉本人太菜了。暴力打表找规律发现规律,正经的做法估计估计得是数论高玩才整的出来。找出规律∑phi(i)*(n/i)(1<=i<=n)的答案是n*(n+1)/2,然后欧拉1到232和n-232到n的phi(i)*(n/i),用欧拉函数的定力暴力算。也就是464个,算每个欧拉函数的复杂度是logn。在除2的地方需要使用乘法逆元,利用费马小定理求出逆元,有的人没用乘法逆元就A了,只能说可能数据比较水吧。这里多说一句,使用乘法逆元的时候先先求出n*(n+1)%mod的的答案。然后用这个答案利用乘法逆元算出除2取膜以后的答案。直接在一个算数表达式里面直接都算出来就会出错。原因不知道,反正因此wa了几次,怀疑是这个原因,改了一下就过了。直接看代码吧!

//Author: xiaowuga
#include <bits/stdc++.h>
#define maxx INT_MAX
#define minn INT_MIN
#define inf 0x3f3f3f3f
const long long N=;
using namespace std;
typedef long long LL;
const long long mod=1e9+;
LL q_power(LL a,LL k){
LL ans=;
while(k){
if(k%){ ans=ans*a%mod;}
k/=;
a=a*a%mod;
}
return ans;
}
LL euler(LL n){
LL res=n;
for(LL i=;i*i<=n;i++){
if(n%i==){
res=res/i*(i-);
while(n%i==) n/=i;
}
}
if(n>) res=res/n*(n-);
return res;
}
int main() {
ios::sync_with_stdio(false);cin.tie();
LL nCase;
cin>>nCase;
LL n,ans;
while(nCase--){
cin>>n;
ans=n*(n+)%mod;
ans=ans*q_power(,mod-)%mod;
for(LL i=;i<=;i++){
ans=(ans-euler(i)*(n/i)+mod)%mod;
}
for(LL i=n;i>=n-;i--){
ans=(ans-euler(i)*(n/i)+mod)%mod;
}
cout<<ans<<endl;
}
return ;
}

继续补题,这个随笔将会在最近持续更新,尽量把金马五校的题补完吧!!!