福建农林大学校赛（同步赛）
目录
A 派蒙之灵
题目思路
进制转换，剩下的按题意模拟即可
题目代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
ll n;
ll a[17];
int main(){
for(int i=0;i<=16;i++){
a[i]=0;
}
a[8]=a[11]=2;
a[0]=a[6]=a[9]=a[13]=1;
scanf("%lld",&n);
ll s=n;
ll sum=0;
while(s){
ll t=s%16;
sum+=a[t];
s/=16;
}
printf("%lld",sum);
return 0;
}
B 派蒙家的荧女仆
题目思路
? 观察可得：对第i对袜子而言，第一只取出时，将放在桌子上，总袜子数加一；第二只袜子取出时，收入衣柜，总答案减一。
题目代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=3e5+10;
ll n;
ll a[maxn];
ll mp[maxn];
ll ma=0;
int main(){
scanf("%lld",&n);
for(int i=1;i<=2*n;i++){
scanf("%lld",&a[i]);
}
ll sum=0;
for(int i=1;i<=2*n;i++){
mp[a[i]]++;
//sum++;
if(mp[a[i]]==2){
mp[a[i]]=0;
sum--;
}else{
sum++;
}
ma=max(ma,sum);
//cout<<sum<<endl;
}
printf("%lld",ma);
return 0;
}
C 派蒙的奇妙冒险------石之海
题目思路
? 把所有素数染成同一种颜色即可满足题目描述，注意特判1和2。
题目代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
ll pri[maxn];
ll m;
ll v[maxn];
ll n;
ll dp[maxn];
void init(){
v[1]=1;
for(int i=2;i<=maxn;i++){
if(!v[i]){
pri[++m]=i;
v[i]=i;
}
for(int j=1;j<=m&&i*pri[j]<=maxn;j++){
//if(i*pri[j]>maxn)break;
v[i*pri[j]]=pri[j];
//cout<<i*pri[j]<<endl;
if(i%pri[j]==0)break;
}
}
}
int main(){
//init();
scanf("%lld",&n);
if(n>=3){
printf("2\n");
}else{
printf("1\n");
}
return 0;
}
D 派蒙游戏世界对旅行荧妹很不友好
题目思路
- 简单贪心。第一步，判断 a+b=n?(n+1)/2a+b=n*(n+1)/2a+b=n?(n+1)/2 是否有解，无解则输出NO，第二步，从n到1贪心，若i<=a，则取i，a=a-i，否则，不取i，那么，显然存在一个比i小的整数等于a未被取过。
- 或者通过判断是否是前缀和，之后在进行构造答案，利用前缀和+二分
题目代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e7+10;
ll n,m;
ll a,b;
ll sum[maxn];
map<ll,ll> mp;
int main(){
for(int i=1;i<=maxn;i++){
sum[i]=sum[i-1]+i;
if(sum[i]>1e9){
n=i;
break;
}
mp[sum[i]]=i;
}
//cout<<n<<endl;
scanf("%lld%lld",&a,&b);
ll ans=a+b;
if(mp[ans]){
n=mp[ans];
printf("YES\n");
printf("%lld\n",n);
if(mp[a]){
ll m=mp[a];
for(ll i=1;i<=m;i++){
printf("%lld ",i);
}
}else{
ll id=upper_bound(sum+1,sum+1+n,a)-sum;
id--;
//cout<<id<<endl;
n=id+1;
ll an=a-sum[id];
an=n-an;
//cout<<an<<endl;
for(ll i=1;i<=id;i++){
if(an==i)continue;
printf("%lld ",i);
}
printf("%lld",n);
}
}else{
printf("NO");
}
/* 1 2 3 4 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 */
return 0;
}
E 派蒙的风花，从下面看？还是从侧面看？
题目思路
贪心+二分。
题目代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e6+10;
ll n,m;
ll a[maxn],b[maxn];
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
ll st,en;
scanf("%lld%lld",&st,&en);
a[i]=st;
b[i]=en;
}
sort(b+1,b+1+n);
sort(a+1,a+1+n);
while(m--){
ll x;
scanf("%lld",&x);
ll id=lower_bound(b+1,b+1+n,x)-b-1;
ll id1=upper_bound(a+1,a+1+n,x)-a-1;
// cout<<id<<" "<<id1<<endl;
id1-=id;
printf("%lld ",id1);
}
return 0;
}
F 派蒙大小姐想让你告白，天才们的恋爱头脑战！
题目思路
暴力模拟
题目代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e6;
char s[maxn];
ll n;
ll sum=0;
ll pan(ll id){
if(s[id+1]=='2'&&s[id+2]=='0')return 1;
return 0;
}
int main(){
cin.getline(s,100100,'\n');
n=strlen(s);
for(int i=0;i<=n-3;i++){
if(s[i]=='5'&&pan(i)){
sum++;
i=i+2;
}
}
if(sum){
cout<<sum;
}else{
cout<<"O kawaii koto!";
}
return 0;
}
G 绝不放过任何一个视线之内的宝箱！（清籁岛篇）
题目思路
通过单调队列维护区间最小值
题目代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=4e6+10;
bool suc[maxn];
ll n;
ll q[maxn*2];
ll p[maxn*2];
ll s[maxn*2];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i];
s[i]=s[i+n]=p[i];
}
for(int i=1;i<=2*n;i++){
s[i]+=s[i-1];
//cout<<s[i]<<' ';
}
// cout<<endl;
ll l,r;
l=0,r=0;
q[l]=0;
for(int i=1;i<=2*n;i++){
while(l<=r&&i-q[l]>n)l++;
if(i>n&&s[i-n-1]<=s[q[l]]){
suc[i-n]=true;
}
while(l<=r&&s[q[r]]>=s[i])r--;
q[++r]=i;
/*for(int j=l;j<=r;j++){
cout<<q[j]<<" ";
}
cout<<endl;*/
}
ll ans=0;
for(int i=1;i<=n;i++){
if(suc[i]){
ans++;
}
}
cout<<ans<<endl;
return 0;
}
结语
“遇事不决，可问春风。春风不语，即随本心。”的意思是：对一件事犹豫不决，就问春风该如何做，春风给不出答案，就凭自己本心做出决断。“遇事不决可问春风，春风不语即随本心”一句出自网络作家“烽火戏诸侯”的《剑来》，其原文是：“遇事不决，可问春风。春风不语，遵循己心”。
