NOIP2017(문제풀이 아님)

노년 퇴역 선수가 왔을 때 입버릇이 나빠졌다

샤오카이의 의혹

시험장 에서 보편적 인 방법 은 바로 시계 를 치는 것 인데, 규칙 은 여전히 찾기 쉬워서, 답안 이 a*b-a-b 라는 것 을 쉽게 알 수 있다

시간 복잡도

16년 D1T2보다 양심이 얼마나 많은지...시뮬레이션을 하면 되지만 그래도 일정한 경기 경험이 필요하다. 다 쓴 후에 직접 만든 데이터를 많이 가지고 시험해 보면 높은 점수는 쉽게 얻을 수 있다

공원을 거닐다

처음에 저는 DAG의 DP만 할 줄 알고 고리의 문제를 어떻게 처리해야 할지 몰랐어요. 타잔으로 축소하고 싶었지만 소용이 없었어요. 나중에 직접 기억화하여 검색하면 돼요. f[i][j]는 DP가 i점까지 왔다고 했어요. 이때 가장 적게 걷는 추가 경로는 j예요. 상태가 다시 회복되지 않기 때문에 -1의 경우 0고리의 점이 가장 짧은 거리에 있는지 판단하면 돼요. dfs가 0고리를 한 번 판단하면 돼요.최단로에서 SPFA 시간 복잡도 O(T(최단로+km) O(T(최단로+km) 코드를 두 번 정반할 수 있는지 판단:

#include
#include
#include
#include
using namespace std;
int T,n,m,k,p,tot,goal;
int first[2][100005],dis[2][100005],f[100005][52],sta[100005];
char tim[100005][52],ok[100005];
bool vis[100005],flag;
struct edge{
    int v,w,next;
}e[2][200005];
int in()
{
    int t=0;char ch=getchar();
    while (ch>'9'||ch<'0') ch=getchar();
    while (ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
    return t;
}
void add(int x,int y,int z)
{
    e[0][++tot].v=y;e[0][tot].w=z;e[0][tot].next=first[0][x];first[0][x]=tot;
    e[1][tot].v=x;e[1][tot].w=z;e[1][tot].next=first[1][y];first[1][y]=tot;
}
int up(int x,int y){return ((x+y)%p+p)%p;}
queue<int>q;
void SPFA(int r)
{
    int now=(r?n:1);
    memset(dis[r],63,sizeof(dis[r]));
    dis[r][now]=0;
    for (q.push(now);!q.empty();q.pop())
    {
        now=q.front();
        for (int i=first[r][now];i;i=e[r][i].next)
            if (dis[r][e[r][i].v]>dis[r][now]+e[r][i].w)
            {
                dis[r][e[r][i].v]=dis[r][now]+e[r][i].w;
                if (!vis[e[r][i].v]) vis[e[r][i].v]=1,q.push(e[r][i].v);
            }
        vis[now]=0;
    }
}
int dp(int x,int D)
{
    if (dis[1][x]+D-goal>k) return 0;
    if (tim[x][dis[1][x]+D-goal]==T) return f[x][dis[1][x]+D-goal];
    tim[x][dis[1][x]+D-goal]=T;
    f[x][dis[1][x]+D-goal]=(x==n);
    for (int v,i=first[0][x];i;i=e[0][i].next)
    {
        v=e[0][i].v;
        f[x][dis[1][x]+D-goal]=up(f[x][dis[1][x]+D-goal],dp(v,D+e[0][i].w));
    }
    return f[x][dis[1][x]+D-goal];
}
void dfs(int x)
{
    ok[x]=T;
    sta[++sta[0]]=x;
    vis[x]=1;
    for (int v,i=first[0][x];i;i=e[0][i].next)
    if (e[0][i].w==0)
    {
        v=e[0][i].v;
        if (ok[v]!=T) dfs(v);
        else if (vis[v]&&dis[0][v]+dis[1][v]<=k+goal)
            flag=1;
    }
    --sta[0];
    vis[x]=0;
}
void work()
{
    n=in();m=in();k=in();p=in();
    tot=0;flag=0;
    for (int i=1;i<=n;++i) first[0][i]=first[1][i]=0;
    for (int u,v,w,i=1;i<=m;++i)
        u=in(),v=in(),w=in(),
        add(u,v,w);
    SPFA(0);
    SPFA(1);
    goal=dis[0][n];
    for (int i=1;i<=n;++i)
        if (ok[i]!=T) dfs(i);
    if (flag) puts("-1");
    else printf("%d
",dp(1,0));
}
main(){for (T=in();T;--T) work();}

치즈 치즈

시뮬레이션 + 및 검색 분명히 주의 거리의 제곱은 롱롱롱을 폭발시켜 스스로 처리할 수 있다

보물

재밌는 상압 DP, 16년간 이어온 콘셉트인데 16년 D2T3보다 조금 어려운 느낌?처음에 나는 1차원 상태를 추가했는데 답이 틀렸다는 것을 발견했다. f[D][S]로 최대 깊이를 D로 표시하고 n개의 점의 상태는 S로 한다. 이동할 때 미이동점의 집합 S를 일일이 열거하면 된다. 실제 프로그램에서(시작점을 일일이 열거한 후) 먼저 S를 일일이 열거한 다음에 S'가 S에 연결된 대가를 미리 처리하고 D의 시간 복잡도 O(n23n) O(n23n)를 일일이 열거한다.

#include
#include
#include
#include
using namespace std;
int n,m;
int dis[13][13],f[13][1<<12],w[1<<12],bit[1<<12],p[13];
stack<int>S;
int cal(int id)
{
    int t=1e9;
    for (int i=1;i<=p[0];++i) t=min(t,dis[p[i]][id]);
    return t;
}
main()
{
    scanf("%d%d",&n,&m);
    memset(dis,63,sizeof(dis));
    for (int x,y,z,i=1;i<=m;++i)
        scanf("%d%d%d",&x,&y,&z),
        dis[x][y]=dis[y][x]=min(dis[x][y],z);
    for (int i=1;i<=n;++i) dis[i][i]=0;
    for (int j=1,i=1;i<=n;++i,j<<=1) bit[j]=i;
    int ans=1e9,cop;
    for (int s=1;s<=n;++s)
    {
        memset(f,63,sizeof(f));
        f[0][1<<s-1]=0;
        for (int k,state=(1<<s-1);state1<state)
        if (state&(1<<s-1))
        {
            p[0]=0;
            cop=((1<1)^state;
            for (int i=cop;i;i=(cop&i-1)) S.push(i);
            k=state;
            for (;k;k^=(k&-k)) p[++p[0]]=bit[k&-k];
            for (;!S.empty();S.pop())
                k=S.top(),
                w[k]=(w[k^(k&-k)]<1e9?w[k^(k&-k)]+cal(bit[k&-k]):1e9);
            for (int D=0;Dfor (int sub=cop;sub;sub=(cop&sub-1))
                if (w[sub]<1e9)
                    f[D+1][state|sub]=min(f[D+1][state|sub],f[D][state]+w[sub]*(D+1));
        }
        for (int D=0;D1<1]);
    }
    printf("%d
",ans);
}

대열을 짓다

16년 된 D1T2보다 어려운 것 같은데?n, m이 어렸을 때 시뮬레이션을 했는데 q가 어렸을 때 전에 물어본 영향을 일일이 열거했다. x=1일 때 첫 줄과 m열로 구성된 거꾸로'L'형만 영향을 주었다. 실제로는 서열 문제가 되었다. 라인 트리나 균형 트리를 마음대로 하면 50~70이 된다. 16년 D1T2의 나무 사슬을 분석한 후에 나는 n+1개의 라인 트리를 만들어서 각 줄과 마지막 열을 유지하는 것을 고려하지 않았다.동적 개점의 권한 값 라인 트리를 활용하면 시작 상태 1~m-1(n)+q에 모두 1개가 있고 매번 수정할 때마다 대응하는 줄(열)의 라인 트리에 있는 수를 삭제하고 m-1(n)보다 큰 수를 vector로 저장하면 대응하는 번호 시간의 복잡도 O(qlog(max(n, m)+q)) O(q log⁡(max(n, m) + q)) O(q log⁡(max(n, m) + q))

#include
#include
#define LL long long
#define M 300005
using namespace std;
int in()
{
    int t=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') t=t*10+ch-48,ch=getchar();
    return t;
}
int n,m,q,cnt;
int root[M],ls[M*19],rs[M*19],del_num[M*19];
vector val[M];
int get(int &rt,int l,int r,int k)
{
    if (!rt) rt=++cnt;
    ++del_num[rt];
    if (l==r) return r;
    int mid=l+r>>1,sz=mid-l+1-del_num[ls[rt]];
    if (sz>=k) return get(ls[rt],l,mid,k);
    else return get(rs[rt],mid+1,r,k-sz);
}
main()
{
    n=in();m=in();q=in();
    LL ans;
    for (int x,y,t,i=1;i<=q;++i)
    {
        x=in();y=in();
        if (y==m)
        {
            t=get(root[n+1],1,q+n,x);
            if (t<=n) ans=1LL*t*m;
            else ans=val[n+1][t-n-1];
            printf("%lld
",ans);
            val[n+1].push_back(ans);
        }
        else
        {
            t=get(root[x],1,q+m,y);
            if (t1LL*x*m+t-m;
            else ans=val[x][t-m];
            printf("%lld
",ans);
            val[n+1].push_back(ans);

            t=get(root[n+1],1,q+n,x);
            if (t<=n) ans=1LL*t*m;
            else ans=val[n+1][t-n-1];
            val[x].push_back(ans);
        }
    }
}