6道DP题只拿了220分，NOIp我不滚粗谁滚粗？
考试历程貌似并没有什么可说的QAQ，就是不停的来回推方程和写崩的状态中。
正经题解
六道题其实除了第六道比较恶心..其他的都还算可以。
truck
水题，不多说.
//DP truck
//by Cydiater
//2016.10.3
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "truck"
const int MAXN=1e3+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,K;
db R[MAXN],U[MAXN],C[MAXN],f[MAXN][MAXN],ans=0;
namespace solution{
void init(){
N=read();K=read();
up(i,0,K)scanf("%lf",&R[i]);
up(i,0,K)scanf("%lf",&U[i]);
up(i,0,K)scanf("%lf",&C[i]);
}
void DP(){
memset(f,0,sizeof(f));
up(i,1,N){
up(j,1,K)f[i][j]=max(f[i][j],f[i-1][j-1]+R[j-1]-U[j-1]);
up(j,0,K)f[i][1]=max(f[i][1],f[i-1][j]+R[0]-U[0]-C[j]);
}
}
void output(){
up(i,0,K)ans=max(ans,f[N][i]);
cout<<ans<<endl;
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
DP();
output();
return 0;
}
带输出方案的版本..这个其实很好搞..比赛的时候好像把老师坑了
//DP truck
//by Cydiater
//2016.10.3
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "truck"
const int MAXN=1e3+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,K,id;
db R[MAXN],U[MAXN],C[MAXN],f[MAXN][MAXN],ans=0,sum=0;
bool choice[MAXN];
namespace solution{
void init(){
N=read();K=read();
up(i,0,K)scanf("%lf",&R[i]);
up(i,0,K)scanf("%lf",&U[i]);
up(i,0,K)scanf("%lf",&C[i]);
}
void DP(){
memset(f,0,sizeof(f));
up(i,1,N){
up(j,1,K)f[i][j]=max(f[i][j],f[i-1][j-1]+R[j-1]-U[j-1]);
up(j,0,K)f[i][1]=max(f[i][1],f[i-1][j]+R[0]-U[0]-C[j]);
}
}
void output(){
up(i,0,K){
if(f[N][i]>ans){
ans=f[N][i];
id=i;
}
ans=max(ans,f[N][i]);
}
printf("%.1lf\n",ans);
memset(choice,0,sizeof(choice));
down(i,N,1){
if(id==1){
choice[i]=1;
up(j,1,K)if(abs(f[i][1]-(f[i-1][j]+R[0]-U[0]-C[j]))<0.1){
id=j;
break;
}
}else id--;
}
choice[1]=0;
id=0;
up(k,1,N){
if(choice[k]!=1) id++;
else id=1;
printf("%d %d %.1lf\n",k,choice[k],f[k][id]-sum);
sum=f[k][id];
}
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
DP();
output();
return 0;
}
cleanup
很好的思路题。
当时写的时候还是太拿衣服了..，一眼DP方程$f[i]=min \{ f[j-1]+sum[i][j]^2 \}$。
这个平方呀，excited，再一眼数据范围，绝对是斜率优化（或者单调性优化），然后开始来回推方程。推到最后的时候悲惨的发现不满足斜率优化的条件，不甘心只拿暴力分（然而最后暴力分也没拿稳），又开始来回变形，无果。开始考虑单调性优化..两个小时过去了，无果。算了，随手码了个暴力，本来那个暴力是没问题的，后来写到第三题的时候加了个小优化QAQ，然后就炸了。
正解：
这个数据不管怎么给，答案不可能超过$N$（分$N$组即可）。所以最优解的每块对答案的贡献不可能超过$\sqrt{N}$，根据这个原理就可以对DP进行优化。
首先变形方程，$f[i]=min \{ f[b[j]-1]+j^2 \} j \in [1,\sqrt{N}]$，其中$b[j]$表示离$i$最近的（左），且满足$[b[j],i]$中不同的数字的个数不超过$j$个。
这时候我们如果能在$O(1)$的时间内求出$b[]$，就能在$O(N\sqrt{N})$的时间复杂度内求出本题答案。
如何在$O(1)$的时间内求出$b[]$?懒得说了，你搞个$pre[]$和$next[]$xjb搞搞就行了。
//NOIp DP cleanup
//by Cydiater
//2016.10.4
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "cleanup"
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M,a[MAXN],next[MAXN],tmp[MAXN],f[MAXN],lim,b[MAXN],pre[MAXN];
namespace solution{
void init(){
N=read();M=read();
memset(tmp,0,sizeof(tmp));
up(i,1,N){
a[i]=read();
next[i]=tmp[a[i]];
tmp[a[i]]=i;
}
memset(tmp,10,sizeof(tmp));
memset(pre,10,sizeof(pre));
down(i,N,1){
pre[i]=tmp[a[i]];
tmp[a[i]]=i;
}
lim=sqrt(1.0*N);
}
void DP(){
memset(f,10,sizeof(f));
memset(b,0,sizeof(b));
f[0]=0;f[1]=1;b[1]=1;
bool flag;
up(i,2,N){
flag=0;
up(j,1,min(lim,i)){
if(flag)break;
if(b[j]!=0&&b[j+1]==0){
if(next[i]<b[j])
b[j+1]=b[j];
flag=1;
}
if(next[i]>=b[j])continue;
else{
up(k,max(b[j],1),i-1)if(pre[k]>=i){
b[j]=k+1;
break;
}
}
}
up(j,1,min(lim,i))if(b[j]>0)f[i]=min(f[i],f[b[j]-1]+j*j);
}
}
void output(){
cout<<f[N]<<endl;
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
DP();
output();
return 0;
}
wrk
水题，但是考场上写挂了，不说。
//DP wrk
//by Cydiater
//2016.10.3
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <cstdlib>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "wrk"
const int MAXN=1e5+4;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int T,S,N,f[10005][105],Time[MAXN],ans=0;
struct Study{
int m,l,a;
}s[MAXN];
namespace solution{
void init(){
T=read();S=read();N=read();
up(i,1,S){
s[i].m=read()+1;
s[i].l=read();
s[i].a=read();
}
memset(Time,10,sizeof(Time));
up(i,1,N){
int c=read();
Time[c]=min(Time[c],read());
}
up(i,1,100)Time[i]=min(Time[i-1],Time[i]);
}
void slove(){
memset(f,-1,sizeof(f));
f[0][1]=0;
up(i,0,T){
up(j,1,100)if(f[i][j]>=0){
if(i+Time[j]<=T)f[i+Time[j]][j]=max(f[i+Time[j]][j],f[i][j]+1);
ans=max(ans,f[i][j]);
}
up(j,1,S)if(s[j].m==i+1&&i+s[j].l<=T&&f[i][j]>=0)f[i+s[j].l][s[j].a]=max(f[i+s[j].l][s[j].a],f[i][j]);
}
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
slove();
cout<<ans<<endl;
return 0;
}
exp
蛤省在11年省选的第一题，据说这一题稳妥A掉就进队了，弱省果然福利好....
其实这道题的关键不在于维护大小的关系，而在于维护相等的冲突。
首先，排除$x_i+y_i>N+1$这种显然不合法的情况，对于假设他们的值是从大到小排好序的，那么第$i$个人所属的区间显然就是$[x_i+1,N-y_i]$，也就是这个区间都是和这个人相等的人。
然后如果这个区间的人数大于这个区间的长度的话，那些超过的显然也是不合法的。
这时候问题就转化成了给你若干个区间，每个区间有一定的权值，要求用这些区间不重叠的覆盖线段且总权值和最大。到这里传统的DP就很容易解决了。
//NOIp DP exp
//by Cydiater
//2016.10.4
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "exp"
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,LINK[MAXN],len=0,f[MAXN];
struct edge{
int y,next,v;
}e[MAXN];
namespace solution{
inline void insert(int x,int y){
for(int i=LINK[x];i;i=e[i].next)if(e[i].y==y){
if(e[i].v<x-y+1)e[i].v++;
return;
}
e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=1;
}
void init(){
N=read();
up(i,1,N){
int x=read(),y=read();
int leftt=x+1,rightt=N-y;
if(x+y>=N)continue;
insert(rightt,leftt);
}
}
void DP(){
memset(f,0,sizeof(f));
up(i,1,N){
f[i]=f[i-1];
for(int j=LINK[i];j;j=e[j].next)f[i]=max(f[i],f[e[j].y-1]+e[j].v);
}
}
void output(){
cout<<N-f[N]<<endl;
}
}
int main(){
//freopen(FILE".in","r",stdin);
//freopen(FILE".out","w",stdout);
using namespace solution;
init();
DP();
output();
return 0;
}
pyr
区间DP/分治 +乘法原理,很经典的一道题。
//NOIp pyr
//by Cydiater
//2016.10.3
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
const ll MAXN=1e3+5;
const ll oo=0x3f3f3f3f;
const ll mod=1000000000;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
char s[MAXN];
ll N,f[MAXN][MAXN];
namespace solution{
void init(){
scanf("%s",s+1);
N=strlen(s+1);
memset(f,-1,sizeof(f));
}
ll col(ll leftt,ll rightt){
if(f[leftt][rightt]!=-1) return f[leftt][rightt];
ll sum=0;
if((rightt-leftt+1)%2==0) return 0;
if(leftt==rightt) return 1;
int mid=(leftt+rightt)>>1;
bool flag=1;
if(s[leftt]==s[rightt]){
sum+=col(leftt+1,rightt-1);
up(i,leftt+1,rightt-1)
if(s[leftt]==s[i])
(sum+=col(leftt+1,i-1)*col(i,rightt)%mod)%=mod;
}
f[leftt][rightt]=sum;
return sum;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
cout<<col(1,N)<<endl;
return 0;
}
apo
考场上不会写的我只能现在写个题解了
//NOIp DP apo
//by Cydiater
//2016.10.4
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <iomanip>
#include <cmath>
using namespace std;
#define ll long long
#define up(i,j,n) for(ll i=j;i<=n;i++)
#define down(i,j,n) for(ll i=j;i>=n;i--)
#define FILE "apo"
const ll MAXN=1e6+5;
const ll oo=0x3f3f3f3f;
const ll mod=(1<<31)-1;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll f[25][10],leftt,rightt,mid,T;
namespace solution{
void pret(){
memset(f,0,sizeof(f));
f[0][0]=1;
up(i,1,21){
f[i][3]=f[i-1][3]*10+f[i-1][2];
f[i][2]=f[i-1][1];
f[i][1]=f[i-1][0];
f[i][0]=(f[i-1][0]+f[i-1][1]+f[i-1][2])*9;
}
}
ll check(ll num){
ll di=0,far=1,tmp=0,cnt=0,ans=0;
for(;far<num;far*=10,di++);
while(tmp<num){
ll re_cnt;
while(tmp+far<=num){
tmp+=far;
if(cnt==3) re_cnt=3;
else if((tmp/far)%10==7) re_cnt=cnt+1;
else re_cnt=0;
down(i,3,3-re_cnt)ans+=f[di][i];
}
if(cnt!=3)cnt=((tmp/far)%10==6?cnt+1:0);
di--;far/=10;
}
return ans;
}
ll slove(ll N){
leftt=1;rightt=100000000000000000LL;
N--;
while(leftt+1<rightt){
mid=(leftt+rightt)>>1;
ll tmp=check(mid);
if(tmp>N) rightt=mid;
else leftt=mid;
}
if(check(leftt)==N) return leftt;
return rightt;
}
}
int main(){
freopen(FILE".in","r",stdin);
//freopen(FILE".out","w",stdout);
using namespace solution;
pret();
T=read();
while(T--)cout<<slove(read())<<endl;
return 0;
}
NOIp DP 1003 爆零记的更多相关文章
-
PKUWC 2019&;WC 2019爆零记
PKUWC 2019&WC 2019爆零记 毕竟过了很久了,杂七杂八的东西就不写了,并且除成绩之外的内容不保证其正确性. Day1 T1:看到这道题很舒服啊,枚举top序算合法图的数量,状压D ...
-
雅礼集训1-9day爆零记
雅礼集训1-9day爆零记 先膜一下虐爆我的JEFF巨佬 Day0 我也不知道我要去干嘛,就不想搞文化科 (文化太辣鸡了.jpg) 听李总说可以去看(羡慕)各路大佬谈笑风声,我就报一个名吧,没想到还真 ...
-
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals)爆零记
昨晚一个瓜皮说今晚有cf,听说是晚间场,我瞅了一眼,娃,VK Cup,上分的好机会,看着比赛时间就有点心酸了,0:35,当时一直在纠结要不要打的问题,当时想着应该不难吧,要不打一下吧,要不还是看看题先 ...
-
HNOI2019 爆零记
HNOI2019爆零记 day \(-inf\) ~ day \(0\) 开学一周之后才停的课,停课之后就开始每天被包菜.我三月份几乎没有更博,就是因为每天都被虐的自闭了. day \(0\) 本来是 ...
-
NOIp 0916 爆零记
题目来自神犇chad 上次爆零是说着玩,这次真的爆零了QAQ 好吧貌似是TYVJ的模拟赛打多了..一直按照TYVJ的格式提交的压缩包.. 然后莫名其妙就AK了hhh 来的时候迟到了半小时,昨晚痛苦的补 ...
-
CTS&;&;APIO2019爆零记
如果你只好奇测试相关请跳至day 2 day 3 day 6 scoi 2019 之后 由于实力问题,省选的时候排名在三十多,显然是没有进队.不过可能是受过的打击比较多,所以还没有特别颓废,甚至连 ...
-
[日常] NOIWC 2018爆零记
开个坑慢慢更(逃 (然而没准会坑掉?) day 0 大概 $8:30$ 就滚去雅礼了qwq 过去的时候发现并没有人...进报到处楼门的时候还被强行拍照围观了一波OwO 然后就领了HZ所有人的提包和狗牌 ...
-
HNOI2019爆零记
HNOI2019真-爆零祭 我怎么这么菜QAQ day-37 从学科溜过来搞OI. 班主任一直在谈论我退役的事情,这就是NOIP挂分的后果...说我没考好就找理由,人家xxxxxxx可不是xxxxxx ...
-
gdoi2017爆零记
前言 这次gdoi,用三个词来形容我:爆零+爆零+爆零.本来还希望能在gdoi搞个小新闻(拿个一等什么的). Day0 这次gdoi是在东莞东华中学,坐个动车下午3点多就到了,然后打个滴滴去酒店(本来 ...
随机推荐
-
Windows编程基础
主要内容:介绍Windows编程的一些基础概念 1.窗口的概念 <1>一个应用程序的窗口通常包括控制菜单框.下拉菜单. 工作区以及最大化按钮.最小化按钮, 还有垂直滚动条.水平滚动条 &l ...
-
Qt之QLCDNumber
简述 QLCDNumber控件用于显示一个LCD数字. 它可以显示几乎任意大小的数字.可以显示十进制.十六进制.八进制或二进制数.很容易使用display()槽连接到数据源,这个槽可以被任何五个参数类 ...
-
Qt之高级网络操作（HTTP/FTP快速上手）Qt之QHttpPart和QHttpMultiPart
http://blog.csdn.net/u011012932/article/details/52535755 http://blog.csdn.net/u011012932/article/det ...
-
linux dump 命令详解
功能说明:备份文件系统. 语 法:dump [-cnu][-0123456789][-b <区块大小>][-B <区块数目>][-d <密度>][-f <设备 ...
-
Nginx对于图片,js等静态文件的缓存设置
以下是自学it网--中级班上课笔记 网址:www.zixue.it Nginx对于图片,js等静态文件的缓存设置 注:这个缓存是指针对浏览器所做的缓存,不是指服务器端的数据缓存. 主要知识点: loc ...
-
Centos学习
Centos学习 ---恢复内容开始--- Centos学习手册by RuffianFish; 痞子鱼 近日闲的无聊,而最近又在搞Centos决定写个Centos详细的学习手册,以便自己在长时间没摸C ...
-
kill -3 导出 thread dump
详见:http://blog.yemou.net/article/query/info/tytfjhfascvhzxcyt361 有些Java应用服务器是在控制台上运行,如Weblogic,为了方便获 ...
-
智能指针之 shared_ptr
std::shared_ptr 是通过指针保持对象共享所有权的智能指针.多个 shared_ptr 对象可占有同一对象大概实现了一下,主要实现原理为,共享指针内部持有堆资源 的指针以及引用计数的指针 ...
-
易忽视的Python知识点
1.sort和sorted (1)sort:会直接修改原始列表的序列,只是排序,不去重. >>> a=[2,5,7,8,3,5,1,3,9,6,2] >>> a.s ...
-
阻止默认事件preventDefault与returnValue
通过阻止默认事件,禁止鼠标右键的使用 document.getElementById('dd').oncontextmenu = function(ev){ event = ev || window. ...