2019牛客暑期多校训练营（第十场） 补题
2019牛客暑期多校训练营（第十场） 补题
这场比赛是三个人一起写的，但都是单挑，比赛过程中第一水题以为是找规律，然后浪费了半个小时，其实暴力递归就能写。还有一道水题，对于两个图的判断情况没想清除，导致一直wa，最后总的来说自己着只A了三道吧。补了两道题
B:Coffee Chicken
以为是找规律，从而浪费了半个小时。其实就是个简单的暴力递归。
题意：有一个字符串序列 s[i]，满足 s[1]="COFFEE",s[2]="CHICKEN"，且 s[i]=s[i−2]+s[i−1]，给你一个n和k，让求 s[n]中第k个开始的10个字符是多少。如果不够则输出第k个到结尾即可。 n<=500,k<=1012
思路：该序列形似斐波那契，长度增长极快，当 i=60，字符串长度早已经大于k的最大值，对于n>60的字符串的长度为 1012+10，他们的前缀一定是 s[59]或 s[60], 这样我们就可以把范围归为 n<=60。
我们只要预处理出前60个字符的长度。那么求字符串 s[i]的第k往后的几个字符可以转化为求 s[i−2],s[i−1]的第k’往后的几个字符。当递归到 n<=10小范围时，直接输出答案即可。
代码：
#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long u64;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int N=1e4+10;
//string s[20];
ll f[100];//56就已经超过了
string s[100];
void back(ll n,ll k,ll cnt)
{
if(n<=10)
{
for(ll i=0;i<cnt;++i) cout<<s[n][k+i-1];
return ;
}
if(k+cnt-1<=f[n-2]){//在s[n-2]
back(n-2,k,cnt);
}
else if(k<=f[n-2]&&k+cnt-1>f[n-2]){//在s[n-2]和s[n-1]上
back(n-2,k,f[n-2]-k+1);
back(n-1,1,10-(f[n-2]-k+1));
}
else{
back(n-1,k-f[n-2],cnt);//在 s[n-1]上
}
}
void init()
{
f[1]=6ll,f[2]=7ll;
s[1]="COFFEE";
s[2]="CHICKEN";
for(ll i=3; i<=10; ++i) s[i]=s[i-2]+s[i-1];
for(ll i=3; i<=57; ++i) f[i]=f[i-1]+f[i-2];
}
int main()
{
init();
ll t;
cin>>t;
while(t--)
{
ll n,k;
cin>>n>>k;
if(n>56)//控制到60以内
{
ll k=n-56;
if(k&1) n=57;
else n=56;
}
if(f[n] <k+10-1 )
{
back(n,k,f[n]-k+1);
}
else
{
back(n,k,10);
}
cout<<endl;
}
}
D:Han Xin and His Troops
这道题补的也不太顺序，因为我的代码中用的是不互质的扩展CRT，但是自己对扩展CRT不理解。导致对于炸long long的地方不知道入手点。然而比赛过后因为马虎导致又 wa了三次
题意：
给出n个同余方程 ai,bi，代表 x=bi(mod ai)。解的可能最大值max，判定属于无解，解太大，正常解 的哪种情况，对于第三种情况输出其解。 0<=max<=1e18,ai<=1e5,bi<=1e5。
思路：
可以考虑将 ai分解为质数，再使用CRT。或者使用扩展CRT，不过要注意模数和解爆long long 的情况。可以使用 __int128。但这里使用 __int128只能过95%，这里猜测是模数炸 __int128 。因为使用可扩展CRT解一次方程过程中，解是不断增大的，所以我们可以提前判断解是否大于max。
代码：
#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long u64;
typedef pair<int,int> P;
//#define i128 __int128
typedef __int128 i128 ;
const int inf=0x3f3f3f3f;
const int N=1e4+10;
i128 extend_gcd(i128 a,i128 b,i128 &x,i128 &y)
{
if(a == 0 && b == 0)return -1;
if(b ==0 )
{
x = 1;
y = 0;
return a;
}
i128 d = extend_gcd(b,a%b,y,x);
y -= a/b*x;
return d;
}
long long m[110],a[110];//模数为m,余数为a, X % m = a
long long _n,_m;
bool is_big;
bool solve(i128 &m0,i128 &a0,i128 m,i128 a)
{
i128 y,x;
i128 g = extend_gcd(m0,m,x,y);
i128 d=a0-a;
if(d < 0) d = -d;
if(d % g) return false;
x *= (a - a0)/g;
x %= m/g;
a0 = (x*m0 + a0);
m0 *= m/g;
a0 %= m0;
if( a0 < 0 )a0 += m0;
if(a0>_m)
is_big=true;
return true;
}
/* * 无解返回false,有解返回true; * 解的形式最后为 a0 + m0 * t (0<=a0<m0) */
bool MLES(i128 &m0,i128 &a0,i128 n) //解为 X = a0 + m0 * k
{
bool flag = true;
m0 = 1;
a0 = 0;
for(i128 i = 0; i < n; i++)
if( !solve(m0,a0,m[i],a[i]) )
{
flag = false;
break;
}
return flag;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
cin>>_n>>_m;
for(i128 i=0;i<_n;++i){
cin>>m[i]>>a[i];
}
i128 m0,a0;
is_big=false;
bool ok=MLES(m0,a0,_n);
if(ok==false){
cout<<"he was definitely lying"<<endl;
}
else if(a0>_m||is_big){
cout<<"he was probably lying"<<endl;
}
else
cout<<(long long)(a0)<<endl;
return 0;
}
H：Hilbert Sort
简单的递归，但是因为打代码不细心，wa了两次。导致慢了20分钟
题意：给你一个递归图，图中每个坐标的二维大小为区间经过点的顺序，给出n个点，输出二维排序后的点。
思路：递归求出每个点是几个经过的即可
代码：
#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long u64;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
ll get(int k,int x,int y)
{
if(k==0) return 1;
ll cnt=(1ll<<(2*k-2));
int md=1<<(k-1);
if(x<=md&&y<=md){
return get(k-1,y,x);
}
if(x<=md&&y>md){
y-=md;
return 3ll*cnt+get(k-1,md-y+1,md-x+1);
}
if(x>md&&y<=md){
x-=md;
return cnt+get(k-1,x,y);
}
if(x>md&&y>md){
x-=md,y-=md;
return cnt*2ll+get(k-1,x,y);
}
return 0;
}
struct S
{
int x,y;
ll pos;
bool operator <(const S& other) const{
return pos<other.pos;
}
}sta[N];
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;++i)
{
cin>>sta[i].x>>sta[i].y;
sta[i].pos=get(k,sta[i].x,sta[i].y);
}
sort(sta+1,sta+n+1);
for(int i=1;i<=n;++i)
cout<<sta[i].x<<" "<<sta[i].y<<endl;
return 0;
}
F: Popping Balloons
思路+模拟，因为没考虑完全所有情况，导致代码有所不及。出过一次bug，因为注意点错导致找了1个小时bug
题意：给出n个气球的坐标，自己可以选择三行，和三列进行射击。射击该行或该列可以打爆这条直线上的所有气球。现要求选择的相邻行和列列的距离必须为d。求打爆气球的最大个数。
思路：
引用题解
用f(i)表示中间一枪打第i行，能够射中的气球个数；用g(i)表示中间一枪打第i列，能射中的气球个数。 用multiset存所有g(i)的值，枚举中间一枪打第x行，将对每一个位于第x-r,x,x+r行的气球，将它们影响到 的列（共三列）的g(j)的值更新，然后更新multiset内的元素。 中间一枪打第x行的最大收益即f(x)+(当前multiset内最大元素)。
代码：
#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long u64;
typedef pair<int,int> P;
//typedef __int128 i128 ;
const int inf=0x3f3f3f3f;
const int N=1e5+10;
vector<int> row[N];
multiset<int,greater<int>> mmp;
int r_sum[N],c_sum[N];
int f[N],g[N];
int n,k,maxr,maxc;
void del(int val)
{
mmp.erase(mmp.find(val));
}
void add(int val)
{
mmp.insert(val);
}
void work(int i,int val)//将第i列的和增加1
{
del(g[i]);
add(g[i]+val);
g[i]+=val;
if(i-k>=0)
{
del(g[i-k]);
add(g[i-k]+val);
g[i-k]+=val;
}
if(i+k<=maxc)//i+k>=k
{
del(g[i+k]);
add(g[i+k]+val);
g[i+k]+=val;
}
}
int main()
{
// freopen("C:\\Users\\12495\\Desktop\\data\\9.in","r",stdin);
scanf("%d%d",&n,&k);
maxr=-1,maxc=-1;
for(int i=0;i<n;++i){
int x,y;
scanf("%d%d",&x,&y);
maxr=max(maxr,x);
maxc=max(maxc,y);
++r_sum[x];
++c_sum[y];
row[x].push_back(y);
}
// cout<<"k:"<<k<< "maxc:"<<maxc<<endl;
int ans=-1;
for(int i=0;i<=maxr;++i){
int sum=r_sum[i];
if(i-k>=0)
sum+=r_sum[i-k];
if(i+k<=maxr)
sum+=r_sum[i+k];
f[i]=sum;
}
for(int i=0;i<=maxc;++i){
int sum=c_sum[i];
if(i-k>=0)
sum+=c_sum[i-k];
if(i+k<=maxr)
sum+=c_sum[i+k];
g[i]=sum;
}
for(int i=0;i<=maxc;++i) mmp.insert(g[i]);
for(int i=0;i<=maxr;++i){
for(int v:row[i]) work(v,-1);
if(i-k>=0)
for(int v:row[i-k]) work(v,-1);
if(i+k<=maxr)
for(int v:row[i+k]) work(v,-1);
int maxx=*(mmp.begin());
ans=max(ans,f[i]+maxx);
for(int v:row[i]) work(v,1);
if(i-k>=0)
for(int v:row[i-k]) work(v,1);
if(i+k<=maxr)
for(int v:row[i+k]) work(v,1);
}
printf("%d\n",ans);
}
H:Stammering Chemists
签到，这就是前面提到的签到题没考虑完所有状况导致卡了快两个小时的题
题意：水题
思路：可以根据度数的个数来判断出4个图，剩下的两个图可以根据最大度数的顶点到叶子的最大距离来区分
代码：
#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long u64;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int N=1e4+10;
int du[6],cnt[6];
vector<int> g[7];
int root,mx;
int dfs(int u,int fa)
{
int maxx=0;
for(int v:g[u]){
if(v==fa) continue;
maxx=max(maxx,dfs(v,u));
}
return maxx+1;
}
int mid;
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
int t;
cin>>t;
while(t--)
{
for(int i=1;i<=6;++i) g[i].clear();
for(int i=1;i<=6;++i) du[i]=cnt[i]=0;
int inx=0;
for(int i=0;i<5;++i){
int u,v;
cin>>u>>v;
du[u]++;
du[v]++;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=6;++i){
if(du[i]>du[inx]) inx=i;
}
for(int i=1;i<=6;++i) cnt[du[i]]++;
if(cnt[1]==2&&cnt[2]==4){
cout<<"n-hexane"<<endl;
}
else if(cnt[1]==3&&cnt[2]==2&&cnt[3]==1){
if(dfs(inx,inx)==3){
cout<<"3-methylpentane"<<endl;
}
else{
cout<<"2-methylpentane"<<endl;
}
}
else if(cnt[1]==4&&cnt[3]==2){
cout<<"2,3-dimethylbutane"<<endl;
}
else if(cnt[1]==4&&cnt[2]==1&&cnt[4]==1)
{
cout<<"2,2-dimethylbutane"<<endl;
}
}
return 0;
}
总结：
其实还有一些题目不难，比如 J 题的DP等等，这场比赛还有color coding近似算法可以说是非常精彩了。
不过在比赛中自己也犯了不少错误，导致浪费了很多时间。比如刚开局，花了20分钟去找规律，其实开始感觉这题可以分治，但是没往上面想，导致题目半小时的时候才开始写正解，但是期间因为马虎出bug了，调试了10分钟左右才给A了。接下来去做H题的签到题了，因为思路是错误的，就一直wa，wa了6发左右才清楚过来。D题是个暴力递归（分治）。思路是正确的，但是实现上有些问题导致wa了2发。
总的来说比赛过程中因为思路不全面，写代码不严谨导致wa了许多***费了很多时间，今后要注意。
补题过程中也不顺利，比如说气球那题，找一个简单的bug找了许久，感觉原因是因为自己注意力不够。（当然思路也有点不严谨）。至于D题扩展CRT，这也是我第一次用int128（发现code blocks 不支持 __int128) ，也学了一下扩展CRT，复习了CRT。
查看8道真题和解析
学而思公司福利 413人发布