牛客周赛 Round 57题解
小红喜欢1
https://ac.nowcoder.com/acm/contest/88888/A
哦吼吼，我是菜狗，如果有错欢迎大家指出。
写在前面：
（玩原神的有福了，最后有惊喜哦）
前言：这次周赛有幸被抽中参加内测，且是本蒟蒻第一次参加内测所以本蒟蒻呢想写次题解来记录一下，也记录下大一最“厚”一篇题解，虽然在内测赛中还逆天般地拿下了首个“AK”但菜狗本狗还是有自知之明的，正式赛的话应该只能敲出前四个出来，然后后面三题再暴力骗点样例分的样子，不过说实话后面三题还是比较好骗样例分，把几种特殊情况列出来，骗的分说不定比自己前几道ac的题得分还药多hh(说的当然是我这种只会骗分的彩笔拉)。所以本彩笔就只在这写前四题题解辣。
最后再感谢一下内测赛中 佬 Pan_ma_ru 和佬 菲得 的解疑和帮助Orz Orz。当然后三题或者前四题本菜狗没讲清楚的可以去这看看佬菲得也是讲的灰常好的，不过他肯定会发在我下面的。xx
传送门1（菲得blog）
传送门2 （菜
佬的话还请略过本题解。orz 话不多说直接上代码：
题解：因为数组只有五个元素，且一定是4个0和1个1所以直接找就行了。
A.小红喜欢1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
using i64=int64_t;
const ll N =2e6+10;
inline ll read()
{
ll s=0,f=1;
char c=getchar();
while(c>'9'||c<'0') // 快读会和 ios 发生 矛盾。
{
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
s=s*10+c-'0';
c=getchar();
}
return s*f;
}
ll a[N],b[N];
void solve()
{
for(int i=0;i<5;i++)
a[i]=read();
int idx=find(a,a+5,1)-a;
cout<<idx+1<<"\n";
}
int main()
{
int _=1;
// cin>>_;
while(_--)
{
solve();
}
return 0;
}
B.小红的树切割
其实刚开始做到B我就蒙了，怎么第二题就能遇到树，那我不是寄了，因为本彩笔树都还没看。但是想着这才第二题啊能有多难，就深深的看了下发现用pair+map还是能ac的。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
using i64=int64_t;
const ll N =2e6+10;
map<pair<ll,ll>,ll>m;
void solve()
{
ll n,k,q,ans=0;
cin>>n;
string s;
cin>>s;
for(int i=0;i<n-1;i++)
{
int x,y;
cin>>x>>y;
m[{x,y}]=1; // x结点和y结点之间有边 标记下
}
for(auto &p:m)
{ // 因为是字符串所以记得减一，刚开始没减1，wa了一发，以为是方法不对
if(s[p.first.first-1]==s[p.first.second-1])
ans++; // 判断相邻结点颜色是否一样 一样就需要减掉
}
cout<<ans<<"\n"; // 输出需要减掉的边数
}
int main()
{
int _=1;
// cin>>_;
while(_--)
{
solve();
}
return 0;
}
C题感觉没啥好讲的，主要是找规律+特判 看完题找出规律后你会发现只有2不可以 输出NO，其他的都是可以的，尤其是需要注意1和3。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
using i64=int64_t;
const ll N =2e6+10;
ll a[N],b[N];
map<pair<ll,ll>,ll>m;
void solve()
{
ll n;
cin>>n;
if(n==1||n==3)
{
cout<<"YES"<<endl; // 1和3比较特殊 特判
cout<<"2 3"<<endl;
}
else if(n==2) // 2不行因为只有它本身
cout<<"NO"<<endl;
else
{
cout<<"YES"<<endl; //其他的就好说了 有多种答案比如：
cout<<2<<" "<<n-1<<"\n"; // 2 n-1 和 n n-1 和 2 n等等都可以
}
}
int main()
{
int _=1;
// cin>>_;
while(_--)
{
solve();
}
return 0;
}
这个题意是讲：给出2n个点，小红她希望两点连成的线段 和直线有交点 的数量尽可能多。我们可以想到之前学过叉积，不懂的宝可以点这看看回忆下 叉积 就是判断两点间的连线会不会和另一条直线相交，简单来说就是一个在直线“上”面的点和一个在直线下面的点连线一定会和这条直线相交，然后我们先找直线上和直线下的，再找直线“上”的，最后找直线上|下 和直线“上”的。直接看代码吧：
D.小红的线段
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using i64=int64_t;
const ll N =2e5+10;
inline ll read()
{
ll s=0,f=1;
char c=getchar();
while(c>'9'||c<'0') // 快读会和 ios 发生 矛盾。
{
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
s=s*10+c-'0';
c=getchar();
}
return s*f;
}
inline void write(int x)
{
if(x<0){
putchar('-');x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
return ;
}
void solve()
{
vector<ll>v1,v2,v3;
ll n,k,b,res=0;
std::cin>>n>>k>>b;
for(int i=1;i<=2*n;i++)
{
int x,y;
std::cin>>x>>y;
if(k*x+b<y)
v1.push_back(i); // 点在直线 “上”面
else if(k*x+b==y)
v2.push_back(i); // 点在直线上
else
v3.push_back(i); // 点在直线下
}
if(v1.size()>v3.size()) // 确保v3是存储的是点最多，方便后续的操作
std::swap(v1,v3);
int temp=0;
std::queue<std::pair<ll,ll> >q;
for(int i=0;i<(int)v1.size();i++)
{ // v1和v3分别是直线上和下的点，他们的连线肯定会和直线有交点。
q.push({v1[i],v3[i]}); //入队列 方便输出
res++;
}
int i=0; //这里 佬菲得温馨提示 要用（int）转换 因为v.size()默认是无符号整形
for(i=(int)v1.size(),temp=0;i<(int)v3.size()&&temp<(int)v2.size();i++,temp++) //再找max(上,下)-min(上,下)的点（即多出来）和直线“上”的点他们之间的连线也必有交点
{
q.push({v3[i],v2[temp]});
res++; //交点数++
}
std::vector<ll>v; // 最后这里判断哪儿的点有剩余 如果是直线上的那他们的连线必与直线有交点 反之没有
if(temp!=(int)v2.size())
{
res+=((int)v2.size()-temp)/2; //记录交点数
for(;temp!=(int)v2.size();temp+=2)
q.push({v2[temp],v2[temp+1]});
}
else
{
for(;i<(int)v3.size();i+=2) // 与直线无点
q.push({v3[i],v3[i+1]});
}
std::cout<<res<<"\n"; // 输出交点数
while(!q.empty())
{
if(res) // 输出交点
{
std::cout<<q.front().first<<" "<<q.front().second<<" "<<"Y"<<"\n";
res--; // 交点数--
}
else
std::cout<<q.front().first<<" "<<q.front().second<<" "<<"N"<<"\n";
q.pop(); // 记得出队 否则 额。。（可以自己试试）
}
}
int main()
{
int _=1;
//cin>>_;
while(_--)
{
solve();
}
return 0;
}
E题和G题虽说自己暴力加特判过了大半样例，但是也仅此而已，还是得学新的算法来ac。F题听佬们说是线段树板子题，但本蒟蒻又又又没有学，暴力也只拿了几十分。看来菜还是得多练。 然后呢在这里分享下佬 Pan_ma_ru 的E题做法： k<7的时候可以直接暴力打表，发现都是可以找到的输出YES，之后再爆搜，超出范围了就输出NO。 代码呈上：
#include<bits/stdc++.h>
#include<unordered_map>;
using namespace std;
using ll=long long;
#define mod 1000000007
using i64=int64_t;
const ll N =7;
inline ll read()
{
ll s=0,f=1;
char c=getchar();
while(c>'9'||c<'0') // 快读会和 ios 发生 矛盾。
{
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
s=s*10+c-'0';
c=getchar();
}
return s*f;
}
inline void write(int x)
{
if(x<0){
putchar('-');x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
return ;
}
ll a[N][N];
void solve()
{
ios::sync_with_stdio(false);
cin.tie(0);
auto check=[&](ll base, ll num)
{
if(base<2)return false;
while(num)
{
if(num%base>1)return false;
num/=base;
}
return true;
};
auto isvalid=[&](ll b1,ll b2,ll num)
{
return check(b1,num)&&check(b2,num);
};
int cnt=0;
for(int i=2;i<N;i++)
{
for(int j=i+1;j<N;j++)
{
a[i][j]=2;
while(!isvalid(i,j,a[i][j]))a[i][j]++;
}
}
ll b1,b2;
b1=read(),b2=read();
if(b2<N){
cout<<"YES"<<endl;
cout<<a[b1][b2]<<"\n";
return;
}
auto get=[&](ll digit,ll num)->__int128_t{
__int128_t res=0,power=1;
while(digit)
{
if(digit&1)res+=power;
digit>>=1;
power=power*num;
}
return res;
};
ll digit=2;
while(true)
{
auto num=get(digit,b2);
if(num>ll(1e18)){
cout<<"NO"<<"\n";
return;
}
if(isvalid(b1,b2,num))
{
cout<<"YES"<<"\n";
cout<<ll(num)<<"\n";
return;
}
++digit;
}
}
int main()
{
int _=1;
// cin>>_;
while(_--)
{
solve();
}
return 0;
}
//
// ██████╗ ██╗ ██╗ ██████╗
// ██╔══██╗██║ ██║██╔════╝
// ██████╔╝██║ ██║██║ ███╗
// ██╔══██╗██║ ██║██║ ██║
// ██████╔╝╚██████╔╝╚██████╔╝
// ╚═════╝ ╚═════╝ ╚═════╝
写在最后：
跪求一赞 orz xx 不xx
查看2道真题和解析