12.24
DP
1.洛谷P1880：环形石子合并
思路：对于直线形，就是枚举所有区间，dp[i][j]表示i-j石子合并后的最小或最大代价，之后枚举分点来转移，因此时间复杂度(O(n^3))。遍历时按照长度来从小到大求解。
环形的话，延长两倍，但枚举len时上限仍然为n-1。最后遍历所有长度为n-1的区间，取最大或最小即可。
题解：
#include<bits/stdc++.h>
using namespace std;
const int M=4e2+20;
struct Stone{
int n,a[M],dp[M][M],sum[M],dp2[M][M];
void init(){
scanf("%d",&n);
for(int i=1;i<=2*n;++i)
for(int j=i;j<=2*n;++j)
dp2[i][j]=1e9+7;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),a[i+n]=a[i];
for(int i=1;i<=2*n;++i)
dp[i][i]=dp2[i][i]=0,sum[i]=sum[i-1]+a[i];
}
inline int query(int l,int r){
return sum[r]-sum[l-1];
}
void run(){
for(int len=2;len<=n;++len)
for(int i=1,j=len;j<=2*n;++i,++j)
for(int k=i;k<=j-1;++k)
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+query(i,j)),
dp2[i][j]=min(dp2[i][j],dp2[i][k]+dp2[k+1][j]+query(i,j));
int mn=1e9+7,mx=0;
for(int i=1;i<=n;++i)
mn=min(mn,dp2[i][i+n-1]),mx=max(mx,dp[i][i+n-1]);
printf("%d
%d
",mn,mx);
}
}s;
int main(){
s.init(),s.run();
return 0;
}
CF #610(div. 2)
A.Temporarily unavailable
题意：一维数轴，一个人要从a走到b，速度1/s，有一个基站在c，信号范围为r，问路程中有多少时间是没有信号的。
思路：实际上就是求线段[a,b]和[c-r,c+r]的交集。除了完全不相交的情况需要特判为0之外，其余情况可以
lf=max(lf,a),rt=min(rt,b),
printf("%d
",b-a-(rt-lf));
来实现。
#include<bits/stdc++.h>
using namespace std;
struct Task{
int a,b,c,r;
int lf,rt;
void init(){
scanf("%d%d%d%d",&a,&b,&c,&r);
if (a>b)
swap(a,b);
lf=c-r,rt=c+r;
}
void run(){
init();
if (rt<a||lf>b)
printf("%d
",b-a);
else
lf=max(lf,a),rt=min(rt,b),
printf("%d
",b-a-(rt-lf));
}
}t;
int main(){
int T;
scanf("%d",&T);
for(int i=1;i<=T;++i)
t.run();
return 0;
}
B.K for the Price of One (Hard Version)
题意：有n个物品，给定k。要么只买一个，花a[i]元，要么买恰好k个，只付最大的钱，一共有p块钱，问最多能买多少个物品。（简单版本为k=2）
思路：首先按价格从小到大排序，确定恰好买k个的情况，总共有k种，即购买1-k,k+1-2k,2k+1-3k……；2-k+1,k+2-2k+1,2k+2-3k+1……；每种情况都从小到大遍历，直到买不了为止。之后，每种情况如果还有剩余，还可以单独购买前面没买的剩下的东西，记录前缀和，每次二分找<=剩余钱的最大数的位置，相加即可。
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r+1)>>1)
#define db(x) cout<<#x<<":"<<x<<endl;
const int M=4e5+20;
struct Task{
int n,p,k,a[M];
void init(){
scanf("%d%d%d",&n,&p,&k);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
}
bool check(int x){
int ans=0;
while(x-k>=0)
ans+=a[x],x-=k;
for(int i=x;i>=1;--i)
ans+=a[i];
if (ans<=p)
return true;
return false;
}
void run(){
init();
sort(a+1,a+n+1);
int l=k,r=n;
while(l!=r){
if (check(mid))
l=mid;
else
r=mid-1;
db(l);
db(r);
}
if (l==k&&!check(l)){
int ans=0,pt=0;
while(ans+a[pt+1]<=p)
++pt,ans+=a[pt];
printf("%d
",pt);
}
else
printf("%d
",l);
}
}t;
int main(){
int T;
scanf("%d",&T);
for(int i=1;i<=T;++i)
t.run();
return 0;
}
C.Petya and Exam
题意：考试有T分钟，n道题目，简单题目amin切，困难题目bmin切，可以随时离场。每道题目还有一个截止时间(t_i)，若在s分钟离场，但存在题目(t_i<=s)，那么就0分，否则就是做出来题目的个数为得分。问最大得分是多少。
思路：一开始思考，最优策略肯定是按照截止时间从小到大开始做（不论难易），所以先排序，从小到大开始做，如果做完一道题之后发现可以离场，那就记录一下题目个数，否则就必须继续做（这个可以用v[p+1].mant和t的比较来判断）。但这样过不了样例。问题在于，如果b>>a，那么做完一道难题之后，最优策略有可能是在下一个b的mant到来之前，先疯狂切简单题，这样反而答案更优，那就每次做完题之后再看看全切水题能多少分即可，更新最大值。
#include<bits/stdc++.h>
using namespace std;
const int M=4e5+20;
struct Prob{
int diff,mant;
bool operator<(const Prob &x)const{
return mant<x.mant||(mant==x.mant&&diff<x.diff);
}
};
struct Task{
int n,T,a,b,numa;
Prob v[M];
void init(){
numa=0;
scanf("%d%d%d%d",&n,&T,&a,&b);
for(int i=1;i<=n;++i)
scanf("%d",&v[i].diff),numa+=(v[i].diff?0:1);
for(int i=1;i<=n;++i)
scanf("%d",&v[i].mant);
sort(v+1,v+n+1);
v[n+1].mant=T+1;
}
void run(){
init();
int mx=max(0,min(numa,(v[1].mant-1)/a)),now=0,t=0;
for(int i=1;i<=n;++i){
++now;
if (v[i].diff)
t+=b;
else
t+=a,--numa;
if (t>T)
break;
if (t<v[i+1].mant)
mx=max(mx,now+min(numa,(v[i+1].mant-t-1)/a));
}
printf("%d
",mx);
}
}t;
int main(){
int T;
scanf("%d",&T);
for(int i=1;i<=T;++i)
t.run();
return 0;
}
D.Enchanted Artifact
题意：一个密码锁，密码为长度<=300的，由a和b组成的字符串。每次你输入密码会返回一个耐久，耐久为最小删除/插入/修改的次数使得你输入的密码和答案相同的次数。给你n+2次机会尝试。n不知道。
题意：首先求出a和b的个数，方法是用300的a和300的b去试，那么a的个数就是300-c1，b的个数就是300-c2。那么len=c1+c2。之后c2表示还缺的b的个数。以len个a的字符串为基准开始试，每次修改一位为b。如果答案比c2小，说明改对了，这位就是b，--c2。如果答案比c2大，说明改错了，这位是a，就改回去，c2不变。最后一共用了n+2次。
#include<bits/stdc++.h>
using namespace std;
const int M=300;
int main(){
string s=string(M,'a');
int c1,c2;
cout<<s<<endl;cout.flush();
scanf("%d",&c1);
c1=300-c1;
s=string(M,'b');
cout<<s<<endl;cout.flush();
scanf("%d",&c2);
c2=300-c2;
if (c1==0){
s=string(c2,'b');
cout<<s<<endl;cout.flush();
scanf("%d",&c2);
return 0;
}
else if (c2==0){
s=string(c1,'a');
cout<<s<<endl;cout.flush();
scanf("%d",&c1);
return 0;
}
int len=c1+c2;
s=string(len,'a');
int c=0;
for(int i=0;i<len-1;++i){
s[i]='b';
cout<<s<<endl;cout.flush();
scanf("%d",&c);
if (c==0)
return 0;
if (c>c2)
s[i]='a';
else
--c2;
}
if(c2)
s[len-1]='b';
cout<<s<<endl;cout.flush();
scanf("%d",&c);
return 0;
}