scoi2013

lavendir让我帮忙出数据→_→
谁来教我卡暴力和乱搞做法
题目怎么说……
应该还是比较简单的= =

感觉某题和今年noip d1 T3超级像2333

update:

……大好人zhonghaoxi上传了官方数据……我不用出数据了

说说题目吧:

摩托车交易

挺裸的
首先火车站是个废条件,有火车站的城市直接两两移动不受限制,所以我们把它们缩为一点
显然就是在图的最大生成树上走
倍增搞搞就可以了
→_→这不就是今年noip D1 T3么……不过鉴于这题比noip2013 D1 T3出得早……
所以应该说今年noip D1 T3 就是这题……233

[Scoi2013]多项式的运算

其实就是维护序列……
区间shift,然后加法乘法……
双标记+splay即可
询问的时候O(n)遍历出序列,用秦九韶算法搞一搞就可以了→_→

[Scoi2013]火柴棍数字

乱搞dp

[Scoi2013]密码

一种比较好理解的做法就是
显然第一个字符为'a'
我们从左往右扫……
维护一个右端点指针r
然后对于一个以i为回文半径x,我们把[i-x,i]翻折过去得到[i,i+x],更新已经完成的右端点,然后标记[i+x+1]!=[i-x-1]
这样就好了……
然后注意到翻折的时候不要做无意义翻折……就能做到O(n)了
其实就是manacher……
复杂度O(n)
代码很短

code_from_csy.cpp
#include <cstdio>
using namespace std;
int n,a[100004],c[100004];
bool b[100004][26];
char s[100004];
int main()
{
    int i,j;
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    for (i=1;i<n;i++) scanf("%d",&c[i]);
    for (i=1;i<=n;i++) for (j=0;j<26;j++) b[i][j]=true;
    int now=0;
    for (i=1;i<=n;i++)
    {
        if (now<i) for (j=0;j<26;j++) if (b[i][j]) {s[i]=j+'a'; break;}
        if (i+a[i]/2>now)
        {
            for (j=now+1;j<=i+a[i]/2;j++) s[j]=s[2*i-j];
            now=i+a[i]/2;
        }
        if (i-a[i]/2>1) b[i+a[i]/2+1][s[i-a[i]/2-1]-'a']=false;
        if (i+c[i]/2>now)
        {
            for (j=now+1;j<=i+c[i]/2;j++) s[j]=s[2*i-j+1];
            now=i+c[i]/2;
        }
        if (i-c[i]/2>0) b[i+c[i]/2+1][s[i-c[i]/2]-'a']=false;
    }
    s[n+1]='\0';
    puts(s+1);
    return 0;
}

数数

数位dp……显然的B(N+M)
然后注意用数学技巧来避免枚举位
就没了

泡泡鱼

计算几何……我没有写

这个O((n+q)q)应该可以过

我们对于一个发射操作,O(n)暴力扫描当前所有的圆……然后算出如果按角度发射,和第i个圆相切的时候能在极角alpha的方向前进多少,接下来对这些前进长度取min,就得到了这次发射到达的位置

注意到对于同半径的圆,最多有六个圆和它同时相切……(摆硬币就明白了)

所以暴力保存一个圆与多少个圆直接直接相切,一旦出现了可以消除的条件,就bfs或dfs来标记删除

应该就没有问题了……
毕竟这题没有写……有错的话请指出……

Comments

comments powered by Disqus