CSP-S模擬41
CSP-S模擬41
A. 數(shù)軸取物(axis)
顯然可以有一個 \(O(n^3)\) 的背包 dp，設 \(dp[i][j][k]\) 表示選區(qū)間 \([i,j]\)，背包容量為 \(k\) 時可獲得的最大價值。每次枚舉固定左端點從小到大枚舉右端點，發(fā)現(xiàn) \(dp[i][j]\) 可以由 \(dp[i][j-1]\) 轉(zhuǎn)移而來，那么直接背包做就完了。
然后你再設一個 \(f[i][j]\) 表示用前 \(i\) 個包走到位置 \(j\) 時可獲得的最大價值。然后有一個 \(O(n^2 m)\) 的 dp 轉(zhuǎn)移：枚舉右端點，再枚舉這個包所選物品區(qū)間左端點，直接可以轉(zhuǎn)移。
然后 TLE 了。
然后你直接根據(jù)復雜度欽定固定右端點時指針從右往左動的最大次數(shù)，即可通過本題。
其實發(fā)現(xiàn)只有后 \(n\) 個包有用，前面的包可以直接跳過。那么 \(O(n^3)\) 即可通過。
Code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar() \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt) \
? EOF \
: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{
int x=0,c=getchar(),f=0;
for(;c>'9'||c<'0';f=c=='-',c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
inline void write(int x)
{
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
// #ifndef ONLINE_JUDGE
// #define ONLINE_JUDGE
// #endif
int n,m;
int a[205],b[205];
int dp2[205][205][205];
int dp[205][205];
int r[205];
int maxn[205];
// #define max(x,y) ((x)>(y)?(x):y)
inline int max(int x,int y) { return x>y?x:y; }
signed main()
{
// axis
// #ifndef ONLINE_JUDGE
freopen("axis.in","r",stdin);
freopen("axis.out","w",stdout);
n=read();
m=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
b[i]=read();
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
for(int totval=0;totval<=200;totval++)
{
dp2[totval][j][i]=dp2[totval][j-1][i];
if(totval>=a[j])
dp2[totval][j][i]=max(dp2[totval][j][i],dp2[totval-a[j]][j-1][i]+b[j]);
}
// const int MAXN=min(200ll,max(10ll,(int)(3e8/(m*n))));
// cout<<MAXN<<endl;
for(int i=1;i<=m-n;i++) int x=read();
m=min(n,m);
for(int i=1;i<=m;i++)
{
int x=read();
for(int j=1;j<=n;j++)
for(int k=j+1;k>0;k--)
dp[i][j]=max(dp[i][j],dp[i-1][k-1]+dp2[x][j][k]);
// for(int j=1;j<=n;j++)
// maxn[j]=max(maxn[j-1],dp[i][j]),dp[i][j]=maxn[j];
}
int ans=0;R
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
ans=max(ans,dp[i][j]);
cout<<ans<<"\n";
// #endif
//mt19937_64 myrand(time(0));
return 0;
}Z
B. 排列變環(huán)(circle)
打表發(fā)現(xiàn)規(guī)律直接做。
Checker：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar() \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt) \
? EOF \
: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{
int x=0,c=getchar(),f=0;
for(;c>'9'||c<'0';f=c=='-',c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
inline void write(int x)
{
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
// #ifndef ONLINE_JUDGE
// #define ONLINE_JUDGE
// #endif
const int n=20;
int a[n+1];
int p[n+1],top;
int find(int *a)
{
int cnt=0;
for(int i=2;i<=n;i++)
for(int j=1;j<i;j++)
cnt+=(*(a+j))>(*(a+i));
return cnt;
}
int do1()
{
for(int i=top;i>1;i--)
{
int nw=p[i],pre=p[i-1];
swap(a[nw],a[pre]);
}
// cout<<"Final for 1: ";
// for(int i=1;i<=n;i++) cout<<a[i]<<" ";
// cout<<"\n";
int cnt=find(a);
for(int i=2;i<=top;i++)
{
int nw=p[i],pre=p[i-1];
swap(a[nw],a[pre]);
}
// cout<<"del for 1: ";
// for(int i=1;i<=n;i++) cout<<a[i]<<" ";
// cout<<"\n";
return cnt;
}
int do2()
{
for(int i=2;i<=top;i++)
{
int nw=p[i],pre=p[i-1];
swap(a[nw],a[pre]);
}
// cout<<"Final for 2: ";
// for(int i=1;i<=n;i++) cout<<a[i]<<" ";
// cout<<"\n";
int cnt=find(a);
for(int i=top;i>1;i--)
{
int nw=p[i],pre=p[i-1];
swap(a[nw],a[pre]);
}
// cout<<"del for 2: ";
// for(int i=1;i<=n;i++) cout<<a[i]<<" ";
// cout<<"\n";
return cnt;
}
void dfs(int pos)
{
if(pos>n)
{
if(top<2) return;
// cout<<"\nChange position: ";
// for(int i=1;i<=top;i++) cout<<p[i]<<" ";
// cout<<"\n";
int c1=do1();
int c2=do2();
// cout<<"cnt="<<c1<<"\n";
if(c1!=(p[top]-p[1])*2-(top-1))
{ cout<<"Egg!\n";
// cout<<"Change position: ";
// for(int i=1;i<=top;i++) cout<<p[i]<<" ";
// cout<<"\n";
// cout<<"c1="<<c1<<" c2="<<c2<<"\n";
exit(0);
}
// cout<<pos<<" "<<top<<" "<<c1<<" "<<c2<<"\n";
// if(c1==c2) { cout<<"It is the same!"<<endl; return; }
// else if(c1<c2) { cout<<"Plan 1 is the winner"<<endl; return; }
// else { cout<<"Plan 1 is the winner"<<endl; return; }
return;
}
dfs(pos+1);
p[++top]=pos;
dfs(pos+1);
p[top]=0;
top--;
}
signed main()
{
// #ifndef ONLINE_JUDGE
// freopen(".in","r",stdin);
freopen("Checking.out","w",stdout);
cout<<"Checking Perm "<<n<<":"<<endl;
for(int i=1;i<=n;i++) a[i]=i;
dfs(1);
// #endif
//mt19937_64 myrand(time(0));
return 0;
}
Code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar() \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt) \
? EOF \
: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{
int x=0,c=getchar(),f=0;
for(;c>'9'||c<'0';f=c=='-',c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
inline void write(int x)
{
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
// #ifndef ONLINE_JUDGE
// #define ONLINE_JUDGE
// #endif
int n,k;
int a[1<<20];
int ans=0x3f3f3f3f;
// priority_queue<int> p1,p2;
int b[1<<20];
int val[1<<20];
unordered_map<int,int> mp;
const int N=1e4+5;
struct Tree{
int sum,cnt;
}t[N<<2];
#define lp (p<<1)
#define rp ((p<<1)|1)
const int MINN=0,MAXN=1e3+1;
void build(int l,int r,int p)
{
t[p]={0,0};
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,lp);
build(mid+1,r,rp);
}
void pushup(int p)
{
t[p].cnt=t[lp].cnt+t[rp].cnt;
t[p].sum=t[lp].sum+t[rp].sum;
}
void add(int l,int r,int x,int p)
{
if(l==r)
{
t[p].sum=val[x];
t[p].cnt=1;
return;
}
int mid=(l+r)>>1;
if(x<=mid) add(l,mid,x,lp);
else add(mid+1,r,x,rp);
pushup(p);
}
int query(int l,int r,int sum,int p)
{
if(l==r) return t[p].cnt&&((t[p].sum+sum)>=0);
int mid=(l+r)>>1,ans=0;
if(t[rp].sum+sum>=0)
{
sum+=t[rp].sum;
ans+=t[rp].cnt;
ans+=query(l,mid,sum,lp);
}
else ans+=query(mid+1,r,sum,rp);
return ans;
}
signed main()
{
// #ifndef ONLINE_JUDGE
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
n=read();
k=read();
for(int i=1;i<=n;i++) b[i]=a[i]=read();
sort(b+1,b+1+n);
b[0]=1e9+1;
for(int i=1;i<=n;i++)
{
if(b[i]!=b[i-1]) mp[b[i]]=i;
val[i]=b[i];
}
int sum=0;
for(int i=1;i<=n;i++)
{
sum+=a[i];
int nw=a[i];
a[i]=mp[nw];
mp[nw]++;
}
// cout<<sum<<"\n";
sum=0;
// for(int i=1;i<=n;i++) cout<<a[i]<<" ";
// cout<<"\n";
// for(int i=1;i<=n;i++) sum+=val[i];
// // cout<<sum<<"\n";
// for(int i=1;i<=n;i++)
// {
// int sum=0;
// for(int j=i;j<=n;j++)
// {
// sum+=val[a[j]];
// if(sum>=k)
// {
// int len=j-i;
// if(len==76)
// {
// cout<<i<<" "<<j<<"\n";
// }
// }
// }
// }
/*
6 86
7 87
472 552
473 553
81
*/
for(int i=1;i<=n;i++)
{
if(val[a[i]]>=k) ans=0;
build(MINN,MAXN,1);
int sum=val[a[i]];
int cnt=1;
for(int j=i+1;j<=n;j++)
{
int nw=sum+val[a[j]];
// cout<<nw<<"\n";
if(nw>=k)
{
int nwcnt=cnt+1+query(MINN,MAXN,nw-k,1);
int nwans=(j-i)*2-nwcnt+1;
ans=min(ans,nwans);
// cout<<"\n["<<i<<","<<j<<"] sum="<<nw<<" query="<<query(MINN,MAXN,nw-k,1)<<" cnt="<<nwcnt<<" nwans="<<nwans<<"\n";
// break;
}
if(val[a[j]]>=0)
{
sum+=val[a[j]];
cnt++;
}
else add(MINN,MAXN,a[j],1);//,cout<<"val="<<val[a[j]]<<" p="<<a[j]<<"\n";
}
// cout<<"\n\n\n";
}
if(ans>=0x3f3f3f3f) ans=-1;
cout<<ans<<"\n";
// #endif
//mt19937_64 myrand(time(0));
return 0;
}
以下是博客簽名，正文無關
本文來自博客園，作者：Wy_x，轉(zhuǎn)載請在文首注明原文鏈接：http://www.rzrgm.cn/Wy-x/p/19172653
版權聲明：本作品采用「署名-非商業(yè)性使用-相同方式共享 4.0 國際」許可協(xié)議（CC-BY-NC-SA 4.0 協(xié)議）進行許可。
浙公網(wǎng)安備 33010602011771號