noip2017

noip

DAY1T1小凯的疑惑

**结论题**a*b-a-b;

DAY1T2时间复杂度

分的情况有点多的模拟。一定要在草稿纸上把情况分清！！

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int T,L,hd;
char s[100],op[100],a[100],b[100],c[100];
typedef pair<char,int> pci;
pci sta[1050];
void Solve(){
    int p=0,cnt=0,ans=0;hd=0;int flg=0;
    scanf("%d%s",&L,s);
//  cout<<L<<endl;
    if(s[2]=='n'){
        int pos=4,len=strlen(s);
        while(pos<=len&&s[pos]>='0'&&s[pos]<='9') p=p*10+s[pos++]-'0';
    }
    else p=0;
    while(L--){
        scanf("%s",op);
        if(op[0]=='F'){
            scanf("%s%s%s",a,b,c);
            for(int i=1;i<=hd;++i)
                if(sta[i].first==a[0])  
                    flg=1;
            if(b[0]!='n'&&c[0]=='n') {
                if(!hd||sta[hd].second) {
                    cnt++;
                    sta[++hd]=make_pair(a[0],2);
                }
                else{
                    sta[++hd]=make_pair(a[0],0);
                }
            }
            else if(b[0]=='n'&&c[0]!='n') {
                sta[++hd]=make_pair(a[0],0);
            }
            else if(b[0]=='n'&&c[0]=='n'){
                sta[++hd]=make_pair(a[0],1);
            }
            else{
                int x=0,y=0,pos=0,lb=strlen(b),lc=strlen(c);
                while(pos<=lb&&b[pos]>='0'&&b[pos]<='9') x=x*10+b[pos++]-'0';
                pos=0;
                while(pos<=lc&&c[pos]>='0'&&c[pos]<='9') y=y*10+c[pos++]-'0';
                if(x<=y){
                    if(!hd||sta[hd].second)     sta[++hd]=make_pair(a[0],1);
                    else    sta[++hd]=make_pair(a[0],0);
                }
                else{
                    sta[++hd]=make_pair(a[0],0);
                }
            }
        }
        else{
            ans=max(cnt,ans);
            if(hd&&sta[hd].second==2) cnt--;
            hd--;
        }
    }
    if(hd||flg) {
        puts("ERR");
        return;
    }
    if(p==ans) {
        puts("Yes");
        return;
    }
    puts("No");
}
int main(){
//  freopen("a.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        Solve();
    }
    return 0;
}

DAY1T3逛公园

先跑出最短路，然后在用dfs来DP。
$f[u][j]=∑f[v][dis[u]+j−dis[v]−w]$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long
using namespace std;
inline int read(){
    char ch;int op=1;
    while((ch=getchar())<'0'||ch>'9') if(ch=='-') op=-1;
    int ret=ch-'0';
    while((ch=getchar())>='0'&&ch<='9') ret=ret*10+ch-'0';
    return ret*op;
}
const int N=100000+10;
const int D=50+2;
const int INF=0x3f3f3f3f;
int T,n,m,k,kk,flg;
int head[N],vis[N],dis[N],g[N][D];
int ans,P,dp[N][D];
struct edge{
    int v,w,nxt;
}e[N<<2];
inline void adde(int u,int v,int w){
    e[kk].v=v;
    e[kk].w=w;
    e[kk].nxt=head[u];
    head[u]=kk++;
}
typedef pair<int,int> pii;
priority_queue <pii,vector<pii>,greater<pii> >q;
inline void dijkstra(){
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;q.push(make_pair(dis[1],1));
    while(!q.empty()){
        int u=q.top().second;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(register int i=head[u];i!=-1;i=e[i].nxt){
            if((i&1)) continue;
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
}
ll dfs(int u,int d){
    if(~dp[u][d]) return dp[u][d];
    g[u][d]=1;
    dp[u][d]=0;
    for(register int i=head[u];i!=-1;i=e[i].nxt){
        if(i&1){
            int v=e[i].v,t=dis[u]+d-e[i].w-dis[v];
            if(t<0) continue;
            if(g[v][t]) flg=1;
            dp[u][d]=(dp[u][d]+dfs(v,t))%P;
        }
    }
    g[u][d]=0;
    return dp[u][d];
}
int main(){
//  freopen("a.txt","r",stdin);
    T=read();
    while(T--){
        memset(head,-1,sizeof(head));
        memset(dp,-1,sizeof(dp));
        kk=0;flg=0;ans=0;
        n=read();m=read();k=read();P=read();
        for(register int i=1,a,b,c;i<=m;++i){
            a=read();b=read();c=read();
            adde(a,b,c);adde(b,a,c);
        }
        dijkstra();
        dp[1][0]=1;
        for(register int i=0;i<=k;++i)
            ans=(ans+dfs(n,i))%P;
        dfs(n,k+1);//-1
        if(flg) puts("-1");
        else printf("%d\n",ans);
    }
    return 0;
}

DAY2T1奶酪

模拟直接维护小鼠能到的空洞即可。

DAY2T2宝藏

树上的状压，好题强推。

DAY2T3列队

主席树的思想：动态开点线段树。不过确实不是特别好实现。

数学，结论题
模拟
最短路+dp
模拟
树上状压dp
主席树/动态开点线段树