10.21-10.22模拟考试解题报告

Day1

1.刷题计划

这道题还是很简单的

每提交一道题 把它的序号放进vector中

如果AC了用数组标记一下

输出时 从后往前读vector

如果遇到的题目没有标记AC则输出并标记输出

输出到20个或者读完vector停止

那么问题是 n最大有10的9次方 数组开不了那么大

这时考虑到m最大只有100 hash即可 碰撞概率几乎没有

代码:

// <problem.cpp> – 10/21/15 08:15:02
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <ctime>
using namespace std;
typedef long long lol;
const int X=1928929;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
bool ac[X+1],sc[X+1];
vector <int> c;
int main(){
freopen(“problem.in”,”r”,stdin);
freopen(“problem.out”,”w”,stdout);
int n=getint(),m=getint();
while(m–){
int con=getint();
if(con==1){
int x=getint();
ac[x%X]=1;
c.push_back(x);
}else if(con==2){
int x=getint();
c.push_back(x);
}else{
for(int i=0;i<X;i++)sc[i]=0;
int l=c.size();int bili=0;
for(int i=l-1;i>=0&&bili<20;i–){
if(!ac[c[i]%X]&&!sc[c[i]%X]){
cout<<c[i]<<” “;
sc[c[i]%X]=1;
bili++;
}
}
cout<<endl;
}
}
return 0;
}

2.最优交换

这道题考虑贪心

从第一位到倒数第二位 每一位寻找之后的最大的和本位距离不超过k的数

然后把它交换到前面来

k再减去交换次数即可

代码:

// <swap.cpp> – 10/21/15 08:15:02
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}

int main(){
freopen(“swap.in”,”r”,stdin);
freopen(“swap.out”,”w”,stdout);
int T=getint();
char n[52];
while(T–){
scanf(“%s”,n);
int k=getint(),m=0;
int l=strlen(n);
for(int i=0;i<l;i++){
char ma=n[i];
int h=i;
for(int o=i+1;o<l&&o-i<=k;o++)
if(n[o]>ma){ma=n[o];h=o;}
for(int a=h;a>i;a–)swap(n[a],n[a-1]);
k-=h-i;
}
printf(“%s\n”,n);
}
return 0;
}

3.统一天下

这道题

 

 

不会做

不过思路还是知道的

就是求两棵树的重心 连起来 然后求总距离和就行了

好了赶快day2

 

Day2

1. 格点统计

QQ截图20151022202222

大概就是这样个图

先O(√n)算出y=x上面部分格点数

乘2再加上对角线上的格点数 为√n

代码:

// <count.cpp> – 10/22/15 08:11:37
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
long long ans;
int main(){
freopen(“count.in”,”r”,stdin);
freopen(“count.out”,”w”,stdout);
long long k;
cin>>k;
long long q=sqrt(k);
for(int i=1;i<=q;i++)ans=(ans+k/i-i)%998244353;
ans=ans*2%998244353;
ans=(ans+q)%998244353;
cout<<ans<<endl;
return 0;
}

2. 电话线铺设

先讲一下正解

其实我考试的时候想到了(就是不会写

先全部用王牌构建一棵最小生成树(有一个不能的要特判)

然后枚举李牌 算出换上李牌的最大收益

即在最小生成树中两房之间路径的最大值-李牌价值

取最大即可

然而不会倍增LCA

所以写个暴力+卡时80分的 枚举李牌求最小生成树

代码:

// <driver.cpp> – 10/22/15 08:11:37
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int cost[22],kk=7,c[6],ec[6],n;
void src(int x,bool m[],int k)
{
if(k>=kk||x==n)return;
if(m[cost[x]])src(x+1,m,k);
for(int i=k?c[k-1]:1;i<=cost[x];i++){
c[k]=i;
bool mm[51];
for(int o=0;o<51;o++)mm[o]=m[o];
for(int o=50-c[k];o>=0;o–)if(mm[o])mm[o+c[k]]=1;
for(int o=0;o<n;o++)if(!mm[cost[o]])goto next;
if(k+1<kk){
kk=k+1;
for(int o=0;o<k+1;o++)ec[o]=c[o];
}
return;
next:;
src(x+1,mm,k+1);
}
}
bool m[51]={1};
int main(){
freopen(“driver.in”,”r”,stdin);
freopen(“driver.out”,”w”,stdout);
cin>>n;
for(int i=0;i<n;i++)scanf(“%d”,&cost[i]);
sort(cost,cost+n);
src(0,m,0);
cout<<kk<<endl;
for(int i=0;i<kk;i++)cout<<ec[i]<<” “;
return 0;
}

3. 老司机

有一组始终合法解1 2 4 8 16 32

所以最多6个数

所以暴力

代码:

// <driver.cpp> – 10/22/15 08:11:37
// This file is created by XuYike’s black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don’t know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
int res=0;
char ch=getchar();
while(ch<‘0’||ch>’9′)ch = getchar();
while(ch>=’0’&&ch<=’9’)res=res*10+ch-‘0’,ch=getchar();
return res;
}
int cost[22],kk=7,c[6],ec[6],n;
void src(int x,bool m[],int k)
{
if(k>=kk||x==n)return;
if(m[cost[x]])src(x+1,m,k);
for(int i=k?c[k-1]:1;i<=cost[x];i++){
c[k]=i;
bool mm[51];
for(int o=0;o<51;o++)mm[o]=m[o];
for(int o=50-c[k];o>=0;o–)if(mm[o])mm[o+c[k]]=1;
for(int o=0;o<n;o++)if(!mm[cost[o]])goto next;
if(k+1<kk){
kk=k+1;
for(int o=0;o<k+1;o++)ec[o]=c[o];
}
return;
next:;
src(x+1,mm,k+1);
}
}
bool m[51]={1};
int main(){
freopen(“driver.in”,”r”,stdin);
freopen(“driver.out”,”w”,stdout);
cin>>n;
for(int i=0;i<n;i++)scanf(“%d”,&cost[i]);
sort(cost,cost+n);
src(0,m,0);
cout<<kk<<endl;
for(int i=0;i<kk;i++)cout<<ec[i]<<” “;
return 0;
}

说点什么

您将是第一位评论人!

提醒
wpDiscuz