CSP-S模擬41
T1：數(shù)軸取物(axis)
思路：
其實 \(O(n^3)\) 預(yù)處理出容量為 \(k\) 的背包在區(qū)間 \([i,j]\) 里最大能獲得多少價值不難想到。
但是如何使用這個處理好的數(shù)據(jù)呢？（賽時兩眼一黑就是暴搜）
我們再來考慮區(qū)間 \(dp\) （好像是我見過的第一道用兩個 \(dp\) 的題）。
設(shè) \(f_{i,j}\) 表示前 \(i\) 個背包處理到第 \(j\) 個物品的最大價值。不難得出轉(zhuǎn)移方程
那么現(xiàn)在我們來燒烤一下我們的時間復(fù)雜度。
\(emmm... ~ O(n^2m)\) 的。顯然會爆。
不過我們可以發(fā)現(xiàn)一個小性質(zhì)：由于題目保證背包的容量單調(diào)不減，而且可以肯定的是，由于只有 \(n\) 件物品，所以最多只有 \(n\) 個背包有用，且背包容量增大答案一定不劣。所以 當(dāng) \(m>n\) 是時我們只需要后 \(n\) 個背包即可 。
這樣我們的復(fù)雜度就將為 \(O(n^3)\) 了。
代碼：
$code$
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=205,M=1e5+5;
int m,n,r[M],dp[N][N][N],s[N],sum,f[N];
struct flower{
int val,cost;
}a[N],b[N];
signed main(){
// freopen("axis.in","r",stdin);
// freopen("axis.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i].cost>>a[i].val;
for(int i=1;i<=m;i++) cin>>r[i];
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
for(int k=1;k<=200;k++){
dp[i][j][k]=max(dp[i][j-1][k],dp[i][j][k]);
if(k>=a[j].cost) dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-a[j].cost]+a[j].val);
}
}
}
for(int i=m-200;i<=m;i++){
for(int j=n;j>=1;j--){
for(int k=0;k<j;k++){
f[j]=max(f[j],f[k]+dp[k+1][j][r[i]]);
}
}
for(int j=1;j<=n;j++) f[j]=max(f[j],f[j-1]);
}
cout<<f[n];
return 0;
}
T2：排列變環(huán)(circle)
思路：
通過手模可得結(jié)論： 逆序?qū)€數(shù)\(=2*(r-l+1)-num-1\)
因此我們發(fā)現(xiàn)，在一段區(qū)間內(nèi)，我們?nèi)〉臄?shù)越多，逆序?qū)驮缴佟?/p>
所以我們考慮如何來維護這一過程。
首先我們要執(zhí)行的操作是選出一段合法的區(qū)間。
那什么樣的區(qū)間是合法的呢？
如果一段區(qū)間內(nèi)有整數(shù)和大于等于 \(k\) ，那么這個區(qū)間顯然是合法的。
如果確定了這個區(qū)間合法，那么我們保證 \(sum>=k\) 的情況下盡可能的往里加盡可能多的數(shù)就好了。
最后用兩個優(yōu)先隊列維護就好了。
對了，記得特判 \(0\) 和 \(1\) 的情況哦
代碼：
$code$
#include<iostream>
#include<queue>
using namespace std;
const int N=1024;
int n,k,maxn=-1e9,sum,num,ans=1e9,w[N];
priority_queue<int,vector<int>,greater<int>> in;
priority_queue<int,vector<int>,less<int>> out;
int main(){
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>w[i];
maxn=max(maxn,w[i]);
if(w[i]>0) sum+=w[i];
}
if(maxn>=k){
cout<<0<<'\n';
return 0;
}
if(sum<k||k<=0){
cout<<-1<<'\n';
return 0;
}
for(int l=1;l<=n;l++){
sum=0;num=0;
while(!in.empty()) in.pop();
while(!out.empty()) out.pop();
for(int r=l;r<=n;r++){
sum+=w[r];
num++;
if(w[r]<0) in.push(w[r]);
while(!in.empty()&&sum<k){
sum-=in.top();//減絕對值大的數(shù)，減的數(shù)少，sum增加的多
out.push(in.top());
in.pop();
num--;
}//判合法性
if(sum<k) continue;
while(!out.empty()&&sum+out.top()>=k){
sum+=out.top();//加絕對值小的數(shù)，加的數(shù)多，sum減小的少
in.push(out.top());
out.pop();
num++;
}//求最大值
ans=min(ans,2*(r-l+1)-num-1);
}
}
cout<<ans<<'\n';
return 0;
}
T3：理想路徑(path)
思路：
神秘 \(bitset\) 優(yōu)化 \(floyed\).
首先我們用 \(bitset\) 優(yōu)化 \(floyed\) 來判可達性。
因為題目要求的字典序最小，所以我們對每個點連的邊進行一下排序。每次跑的時候就從前向后遍歷邊，能跑就跑。
最后用 \(vis\) 數(shù)組判一下是否有環(huán)就行了。
代碼：
$code$
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;
const int N=2500;
int n,m,q,op,x,y,s,t,k,step,last=1;
bool vis[N];
vector<int> v[N];
bitset<N> a[N];
int main(){
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m>>q>>op;
for(int i=1;i<=m;i++){
cin>>x>>y;
a[x][y]=1;
v[x].push_back(y);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[j][i]){
a[j]=a[j]|a[i];
}
}
}//可達性
for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());//字典序最小
while(q--){
if(last==-1) last=1;
cin>>s>>t>>k;
if(op){
s=((s^last)%n)+1;
t=((t^last)%n)+1;
k=((k^last)%n)+1;
}
if(!a[s][t]){
last=-1;
cout<<-1<<'\n';
continue;
}//到不了
last=-1;
step=0;
memset(vis,0,sizeof(vis));
while(1){
if(++step==k) last=s;//記錄一下
if(s==t) break;//到了
if(vis[s]){//有環(huán)
last=-1;
break;
}
vis[s]=1;
bool flag=0;
for(int x:v[s]){//從小到大能跑就跑
if(a[x][t]==1||x==t){
flag=1;
s=x;
break;
}
}
if(!flag){
last=-1;
break;
}//沒有能跑的了
}
cout<<last<<'\n';
}
return 0;
}
T4：最終禮物(gift)
??咕咕咕，放只鴿子
后言：
song1
憶當(dāng)年春華與秋月
我撫琴你皎潔
閣樓邊婆娑的淚眼
你轉(zhuǎn)身多決絕
聽暮雨瀟瀟眼前
你抽離了指尖
城樓下你飛鴻踏雪
背影凄切
訣別風(fēng)月千萬里
繞過姑蘇汴京
幾度紅塵故里
唇邊婉轉(zhuǎn)的鄉(xiāng)音
筆下離愁的詩句
祈求你入夢來相期
長風(fēng)起 醉復(fù)醒 你偏不來夢里
（念白：蒼天薄情）
當(dāng)年跪神佛 誓言不分離
（念白：難解相思意）
長風(fēng)去 相思寄 追尋你千萬里
（念白：偏要教我忍痛斷舍離）
神明坐高臺 不見君蹤影
拜天地 敬神明 難抵我 意難平
恨別離 你我卻生別離
春又來 秋又去 此情成追憶
盼歸期 不是你 空歡喜
訣別風(fēng)月千萬里
繞過姑蘇汴京
幾度紅塵故里
唇邊婉轉(zhuǎn)的鄉(xiāng)音
筆下離愁的詩句
祈求你入夢來相期
長風(fēng)起 醉復(fù)醒 你偏不來夢里
（念白：蒼天薄情）
當(dāng)年跪神佛 誓言不分離
（念白：難解相思意）
長風(fēng)去 相思寄 追尋你千萬里
（念白：偏要教我忍痛斷舍離）
神明坐高臺 不見君蹤影
拜天地 敬神明 難抵我意難平
恨別離 你我卻生別離
春又來 秋又去 此情成追憶
盼歸期 不是你 空歡喜
拜天地 敬神明 難抵我意難平
恨別離 你我卻生別離
春又來 秋又去 此情成追憶
盼歸期 不是你 空歡喜
song2
那一年你和我一樣年紀(jì)
年輕得像首青澀的歌曲
但為了創(chuàng)造夢中那個新天地
你轉(zhuǎn)身 匆匆走進風(fēng)雨
我看見千萬個可愛的你
不回頭向硝煙深處奔去
多少個青春背影消失在夜里
換來晨曦
我仰望你看過的星空
穿過百年時空再相逢
你轉(zhuǎn)過身之前的那個笑容
我都懂
我仰望你看過的星空
腳下大地已換了時空
你留在風(fēng)中搖曳的那抹紅
在心中 心中
舉起手我說出同樣誓言
黑白間你的笑容多清晰
你說你從來也不后悔把一生
奉獻給 這片遼闊大地
我多想伸手緊緊擁抱你
告訴你一切都塵埃落定
百年前你夢想的那個新中國
有多美麗
我仰望你看過的星空
穿過百年時空再相逢
在此刻我們總會心靈相通
我都懂
我仰望你看過的星空
腳下大地已換了時空
你留在風(fēng)中搖曳的那抹紅
在心中 心中
我仰望你看過的星空
穿過百年時空再相逢
在此刻我們總會心靈相通
我都懂
我仰望你看過的星空
腳下大地已換了時空
你留在風(fēng)中搖曳的那抹紅
在心中 心中
