福建农林大学校赛（同步赛）题解
由于未知原因，B题派蒙派之门缺失，导致赛时题目只有七题。
A 派蒙之灵
进制转换，剩下的按题意模拟即可
B 派蒙派之门
DP+离散化+DFS+二叉搜索。从结点1开始，进行DFS，对每种边权和维护一个最大的点权和，再将所有维护信息按边权和排序，并从前往后取最大点权和。最后对于每次询问，在维护信息中进行二叉搜索。
代码如下：
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
using namespace std;
using LL = long long;
using PLL = pair<LL,LL>;
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n,q;
map<LL,LL> mp;
cin>>n>>q;
vector ve(n+1,vector<PLL>());
vector a(n+1,(LL)0);
for(int i=2;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
ve[u].pb({v,w});
ve[v].pb({u,w});
}
auto dfs = [&](auto dfs,int u,int fa,LL sx,LL sy)->void{
mp[sx]=max(mp[sx],sy);
for(auto &[x,y] : ve[u]){
if(x!=fa) dfs(dfs,x,u,sx+y,sy+a[x]);
}
};
dfs(dfs,1,0,0,0);
vector<PLL> dp;
for(auto &[x,y] : mp){
dp.pb({x,y});
}
for(int i=1;i<dp.size();i++){
dp[i].y=max(dp[i-1].y,dp[i].y);
}
dp.pb({1e18,1e18});
while(q--){
LL T;
cin>>T;
PLL t={T,(LL)1e18};
int k=lower_bound(dp.begin(),dp.end(),t)-dp.begin();
LL ans=dp[k-1].y;
cout<<ans<<endl;
}
return 0;
}
C 派蒙家的荧女仆
观察可得：对第i对袜子而言，第一只取出时，将放在桌子上，总袜子数加一；第二只袜子取出时，收入衣柜，总答案减一。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n;
cin>>n;
vector<int> a(n+1);
int ans=0,ma=0;
for(int i=1;i<=n*2;i++){
int u;
cin>>u;
if(a[u]) ans--;
else a[u]++,ans++;
ma = max(ma , ans);
}
cout<<ma<<endl;
return 0;
}
D 派蒙的奇妙冒险——石之海
把所有素数染成同一种颜色即可满足题目描述，注意特判1和2。
E 派蒙游戏世界对旅行荧妹很不友好
简单贪心。第一步，判断 是否有解，无解则输出NO，第二步，从n到1贪心，若i<=a，则取i，a=a-i，否则，不取i，那么，显然存在一个比i小的整数等于a未被取过。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
int a,b;
cin>>a>>b;
int c=a+b;
int ans=0;
for(n=1;ans<c;n++){
ans+=n;
}
n--;
if(ans!=c){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
cout<<n<<endl;
for(int i=n;i>0;i--){
if(a>=i){
a-=i;
cout<<i<<" ";
}
}
return 0;
}
F 派蒙的风花，从下面看？还是从侧面看？
离线：离散差分。在线：离散线段树、离散树状数组等。观察题目可知，需要一个可以区间修改，单点查询的数据结构，很容易就能想到 线段树 树状数组、差分，并且题目给定的区间过大，所以需要离散化，再由于询问是独立的，所以可以将其按顺序排列进行离线处理（好麻烦，还是直接暴力打线段树吧）。将所有花期开始开始、花期结束时间、赏花时间进行排序，然后进行差分处理（注意操作的先后顺序），再将询问按原顺序输出。
离线离散差分代码如下：
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
using PII = pair<int,int>;
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n,m;
cin>>n>>m;
vector<int> a(m+1);
map<int,int> mp;
vector<PII> ve;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
ve.pb({x,-1});
ve.pb({y,1});
}
for(int i=1;i<=m;i++){
cin>>a[i];
ve.pb({a[i],0});
}
sort(ve.begin(),ve.end());
int ans=0;
for(auto &[x,y] : ve){
if(y) ans-=y;
else mp[x]=ans;
}
for(int i=1;i<=m;i++) cout<<mp[a[i]]<<" ";
return 0;
}
G 派蒙大小姐想让你告白，天才们的恋爱头脑战！
男朋友算法（BF）、哈希、KMP、AC自动机等。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int ans=0,sum=0;
for(auto &i : s){
if(535048==(sum=(sum*100+i)%1000000)) ans++;
}
if(ans) cout<<ans<<endl;
else cout<<"O kawaii koto!"<<endl;
return 0;
}
H 绝不放过任何一个视线之内的宝箱！（清籁岛篇）
单调队列维护前缀和最小值。读题后可知，需要一个可以查询区间最小值的无需修改的数据结构，很容易想到线段树 ST表，但由于需要查询的区间是有规律的，所以我们可以继续线段树 用单调队列进行维护。（本题数据量会卡ST表和线段树，输入时尽量使用较快速的读入方式，否则可能会超时）
某直觉代码如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n;
cin>>n;
int ans=0;
vector<int> a(n+2,1e9),s=a,ls=a,rs=a;
s[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
ls[i] = min(ls[i-1] , s[i]);
}
for(int i=n;i>0;i--){
rs[i] = min(rs[i+1] , s[i]);
}
for(int i=1;i<=n;i++){
ans+=(rs[i]-s[i-1]>=0 && ls[i-1]+s[n]-s[i-1]>=0);
}
cout<<ans;
return 0;
}
同步赛H题一血代码（单调队列做法）：
#include <iostream>
using namespace std;
using int64 = long long;
const int N = 4000010;
int p[N << 1], d[N << 1];
int w[N << 1];
int64 s[N << 1];
int q[N];
int n;
bool suc[N];
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 <= n << 1; i++) s[i] += s[i - 1];
int tt, hh;
q[tt = hh = 0] = 0;
for (int i = 1; i <= n << 1; i++) {
if (i - q[hh] > n) hh++;
while (hh <= tt && s[q[tt]] >= s[i]) tt--;
q[++tt] = i;
if (i > n && s[i - n - 1] <= s[q[hh]]) suc[i - n] = true;
}
int res = 0;
for (int i = 1; i <= n; i++)
if (suc[i]) res++;
cout << res;
return 0;
}
std：
#include<bits/stdc++.h>
using namespace std;
const int N=2e7+10;
int n,head=1,tail,ans;
long long a[N],s[N],q[N];
int main(){
head = 1,tail = 0, ans = 0;
scanf("%d",&n);
for(int i=1;i<=n;i+=1)
scanf("%lld",&a[i]);
for(int i=1;i<=n-1;i+=1)
a[i+n]=a[i];
for(int i=1;i<=2*n-1;i+=1)
s[i]=s[i-1]+a[i];
for(int i=1;i<=2*n-1;i+=1)
{
while(head<=tail&&max(i-n+1,1)>q[head])head++;
while(head<=tail&&s[i]<=s[q[tail]])tail--;
q[++tail]=i;
if(i-n+1>0&&s[q[head]]-s[i-n]>=0)ans++;
}
printf("%d\n",ans);
return 0;
}
京公网安备 11010502036488号