noip2014

noip

DAY1T1生活大爆炸版剪刀石头布

算个周期，模拟即可。

DAY1T2联合权值

算是模拟/树形dp吧。反向考虑每个（中心）点的贡献。

DAY1T3飞扬的小鸟

第三题里面比较简单的。只要想到dp上就好了。棋盘型dp。
dp[i][j]表示到达（i，j）处所需的最小点击数。
注意初值，转移的顺序，终值。

DAY2T1无线网络发射器选址

二维前缀和 n=128的数据范围真的是极水。

DAY2T2寻找道路

从终点到起点跑一次最短路，记录可行的点。再从起点跑最短路到终点即可。

DAY2T3解方程

罕见的把数学放在第三题。不要怀疑，它的正解就是你想的模样。用秦久韶公式（其实就是读优那种边读边更新的方法），数据范围超大，多用几个大质数取模就可以愉快的暴力枚举了。
双HASH防冲突。

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int N=100+10;
const int M=1000000+10;
const int M1=1e9+7;
const int M2=1e9+9;
ll n,m,cnt;
ll a[M],b[M],ans[M];
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10) write(x/10);
    putchar('0'+x%10);
}
int main(){
//  freopen("a.in","r",stdin);
    scanf("%lld%lld",&n,&m);
    for(register int i=0;i<=n;++i){
        char ch;int op=1;
        while((ch=getchar())<'0'||ch>'9') if(ch=='-') op=-1;
        a[i]=b[i]=ch-'0';
        while((ch=getchar())>='0'&&ch<='9') {
            a[i]=(a[i]*10+ch-'0')%M1;
            b[i]=(b[i]*10+ch-'0')%M2;
        }
        if(op==-1) {
            a[i]=-a[i]+M1;
            b[i]=-b[i]+M2;
        }
    }
    for(register int i=1;i<=m;++i){
        ll A=0,B=0;
        for(register int j=n;j>=0;--j){
            A=(A*i+a[j])%M1;
            B=(B*i+b[j])%M2;
        }
        if(A==0&&B==0) {
            ans[++cnt]=i;
        }
    }
    write(cnt);putchar('\n');
    for(register int i=1;i<=cnt;++i){
        write(ans[i]);putchar('\n');
    }
    return 0;
}

模拟
模拟/树形dp
棋盘型dp
二维前缀和
最短路
数学