作者存档：edward_mj

【题目】

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1010

【算法分析】

好不容易终于看懂了，我还是链接一下算了。。。

http://www.byvoid.com/blog/noi-2009-poet/

模仿他的解法三即可。。。

【CODE】

#include #include #include #include #define sqr(x) ((x)*(x))
using namespace std;
const int N=60000;
int n,L,head,tail,a[N],qp[N];
long long qf[N],f[N],sum[N];

void init(){
     scanf("%d%d",&n,&L);
     for (int i=1;i<=n;i++){
         scanf("%d",&a[i]);
         a[i]++;
     }
     sum[0]=0;
     for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
}

double xl(int i,int j){
       return (f[j]+sqr(sum[j])-f[i]-sqr(sum[i]))/(sum[j]-sum[i]);
}

void work(){
     f[0]=0;
     int head=1, tail=1;
     qf[1]=0; qp[1]=0;
     for (int i=1;i<=n;i++){
         while (head         int &j=qp[head];
         f[i]=f[j]+sqr(sum[i]-sum[j]-1-L);
         while (head         tail++;
         qp[tail]=i;
         qf[tail]=f[i];
     }
     cout << f[n] << endl;
}

int main(){
    init();
    work();
}

这次GDKOI总的来说比较遗憾，但是也不算太差。。。

给AekdyCoin师傅丢脸了。。。

首先说下题目类型（后面的是题目分值）：

Day1

1：Floyed——30分

2：基于连通性的状态压缩动态规划——40分

3：找循环节，然后比较繁琐的处理——40分

4：IMBA的压轴题，构造简单割处理，转化比较牛B，很可惜居然这题是上一年winter camp上的原题，而且当时的出题人也在参加比赛。。。无语——40分

Day2

1：直接积分 or 利用导数求出单调性，发现是单峰函数，可以二分 or 直接推导出答案O(1)，总的来说是数学题——30分

2：简单的DP——40分

3：双向BFS——40分

4：平衡树连边再处理。主要是这题我推不出那个边数必然为O（N）规模的这一结论。

我的情况：

Day1：

1：AC

2：暴力DFS拿了90%的分数。。。

3：悲剧，怎么拍都有BUG，于是只拿30%分数。

4：被秒杀。。。55555555，被虐了，用了个状态压缩DP，拿了30%分数。

Day2：

1：AC

2：居然10分钟敲的DP写错了。。。我无语，直接丢32分。。。。

3：双向BFS写出来了，不过操作步数为0的情况没有特判，WA1个点。拿到36分。

4：居然暴力都写错，12分就这样没了。

假设是当前水平下，最好状态：

Day1第3题过掉。+28分

Day2第2题DP写对。+32分

Day2第3题那个点拿掉。+4分

Day2第4题写对。+12分。

总共可以+76分，但是毕竟比赛不能说都能做出来，也算是这样了。。

最后并列第10，前面有两个是高三拿了NOI金牌回来FUN的。。。

总的来说比较遗憾，下次要减少这些SB失误唉。。。

【题目大意】

就是找一个最短连续子序列，使得对于每个i,min[i]<=sum(i)<=max[i]

【算法分析】

很简单的头尾指针维护。

不过要注意题目有负数等无关数字，无视即可（只增加长度）。

然后由于满足单调性我们维护一个最短的区间使得其满足所有的min

然后判断这时候符不符合max即可。

【其它】比赛时1A

【CODE】

#include #include int n,kind,ans;
int hash[3000],a[401111],min[3000],max[3000];

void work(){
    ans=0x7FFFFFFF;
    int i,j=0,que=0,more=0;
    for (i=1;i<=kind;i++){
      if (min[i]>0) que++;
      if (max[i]<0) more++;
    }   
    for (i=1;i<=n;i++){
        while (j            j++;
            if (a[j]>=1 && a[j]<=kind){
              hash[a[j]]++;
              if (hash[a[j]]==max[a[j]]+1) more++;
              if (hash[a[j]]==min[a[j]]) que–;
            }   
        }
        if (!que && !more && j-i+1        if (a[i]>=1 && a[i]<=kind){
            hash[a[i]]–;
            if (hash[a[i]]==min[a[i]]-1) que++;
            if (hash[a[i]]==max[a[i]]) more–;
        }   
    }   
}   

int main(){
    while (scanf("%d%d",&n,&kind)!=EOF){
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        for (int i=1;i<=kind;i++){
            scanf("%d%d",&min[i],&max[i]);
        }   
        memset(hash,0,sizeof(hash));
        work();
        if (ans==0x7FFFFFFF) printf("-1n");
        else printf("%dn",ans);
    }   
}