lp5077 Tweetuzki 爱等差数列

令首项为\(x\),长度为\(l\)由等差数列求和式可得:
$$s=\frac{l(l-1)}{2}+l*x$$
故,题意等价于求:
使得式子:
$$2s=l(l-1+2x)$$
成立的最小\(x\)
即求使得式子成立的最大\(l\)
又,易知:
$$l<\sqrt{2s},s\le10^{12}$$
故,
$$l<10^{6}$$
显然这个复杂度是可以接受的。

#include<iostream>
#include<cstdio>
#include<cmath>
long long s;
inline void init(){
	scanf("%lld",&s);
	long long ans=0,len;
	for(long long i=1;i*i<=2*s;++i){
		if((2*s%i==0)&&(2*s/i-i+1>0)&&((s-(i*(i-1)/2))%i==0)){
			len=i;ans=((2*s)/i-i+1)>>1;
		}
	}
	printf("%lld %lld",ans,ans+len-1);
}

int main(){
	init();
	return 0;
} 

lp2540 NOIP2015 斗地主增强版

首先,我们注意到花色对于斗地主不会造成任何影响,所以我们可以忽视掉花色这个信息。
然后,我们将剩余的信息,依据数码的从小到大储存。
然后我们可以注意到,对于一种出牌方式,调整一些牌组的出牌顺序对答案并不会造成影响。
并且,散牌似乎具有贪心的性质。看起来如果能出三带二那么出三带一就不会更优,如果能出四带二那出三带二就不会更优。
对于顺子的情况是一个例外,因为如果能出顺子的话,可能存在一种情况,使得不出顺子比出顺子更优;亦有可能将一个顺子出一部分会更优。故而对于顺子应该爆搜判定。
总结起来就是:爆搜出顺子,贪心出散牌。
但是仔细考虑,我们可以发现,这种贪心是一种想当然的对正确答案的近似。这事实上仅因为四不可带一这一性质。
故而,对于4 4 1 2的情况,用上述的贪心得出的答案应当是3,然而事实上只需2即可。
但是,前面仍然有一个结论是正确的——也就是,出牌顺序不对答案造成影响。又考虑到,数码的顺序其实仅对顺子而言有意义。
所以我们可以仅储存,数量为k的数码有多少种,从而可以用5^13的空间复杂度预处理每一种散牌的状态。
但是如果这么做的话会发现连样例二都过不了。这事实上是因为,暴力搜索散牌的时间复杂度是完全不可接受的。
考虑到状态数极少,可以记忆化搜索来完成预处理。
用f[i][j][k][l]表示,有i个1,j个2,k个3,l个4时的最小解决花费即可。
几个坑点:
1.出顺子的时候应当是-=,+=而非直接赋值。
2.预先判双王以后应当计算花费。
3.出顺子的时候,在遍历到长度没达到要求的区间的时候也应当先将其清零然后在遍历之后加回去。
4.注意四带二的各种拆法:理论上应当有\(C_{4}^{2}+C_{3}^{2}\)种,少一种都不行,例如:两组三张和两组四张可以把两组三张拆开来打。
真可以说是丧心病狂的模拟题。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define dfs(X) X.srch()
//所有数+10之后mod13,13小王,14大王。 
inline int Max(int A,int B){
    return A>B?A:B;
}
inline int Min(int A,int B){
    return A<B?A:B;
}
struct statue;
int n,ans=0x3f3f3f3f,f[14][14][9][7];
int CNT[4]={0,0,0,0};
struct statue{
    int cst;
    int a[15];
    inline void init(){
        for(int i=0;i<15;++i){
            a[i]=0;
        }
    }
    inline statue(int cstin){
        cst=cstin;
    }
    inline void srch(){
        /*
        for(int i=0;i<15;++i){
            printf("%d ",a[i]);
        }
        printf("\n");
        */
        statue nw(cst+1);
        for(int i=0;i<15;++i){
            nw.a[i]=a[i];
        }
        for(int i=0;i<12;++i){
            if(a[i]>=3){
                nw.a[i]-=3;
                for(int j=i+1;j<12;++j){
                    if(a[j]<3){
                        break;
                    }
                    nw.a[j]-=3;
                    dfs(nw);
                }
                for(int j=i+1;j<12;++j){
                    if(a[j]<3){
                        break;
                    }
                    nw.a[j]+=3;
                }
                nw.a[i]+=3;
            }
            if(a[i]>=2){
                nw.a[i]-=2;
                for(int j=i+1;j<12;++j){
                    if(a[j]<2){
                        break;
                    }
                    nw.a[j]-=2;
                    if(j-i<2){
                        continue;
                    }
                    dfs(nw);
                }
                for(int j=i+1;j<12;++j){
                    if(a[j]<2){
                        break;
                    }
                    nw.a[j]+=2;
                }
                nw.a[i]+=2;
            }
            if(a[i]>=1){
                --nw.a[i];
                for(int j=i+1;j<12;++j){
                    if(a[j]<1){
                        break;
                    }
                    --nw.a[j];
                    if(j-i<4){
                        continue;
                    }
                    dfs(nw);
                }
                for(int j=i+1;j<12;++j){
                    if(a[j]<1){
                        break;
                    }
                    ++nw.a[j];
                }
                ++nw.a[i];
            }
        }
        CNT[0]=CNT[1]=CNT[2]=CNT[3]=0;
        for(int i=0;i<15;++i){
        	++CNT[a[i]-1];
		}
		ans=Min(ans,cst+f[CNT[0]][CNT[1]][CNT[2]][CNT[3]]);
//		printf("%d:%d %d %d %d\n",cst,CNT[0],CNT[1],CNT[2],CNT[3]);
    }
};
int II=0,JJ=0,KK=0,LL=0;
inline int rnw(int A,int B,int C,int D){
	if(A<0||B<0||C<0||D<0||A>13||B>13||C>8||D>6){
		return 0;
	}
    f[A][B][C][D]=Min(f[A][B][C][D],f[II][JJ][KK][LL]+1);
    return 0;
}
inline void prpr(){
    memset(f,0x3f,sizeof(f));
    f[0][0][0][0]=0;
    for(int i=0;i<=13;++i){
        for(int j=0;j<=13;++j){
            for(int k=0;k<=8;++k){
                for(int l=0;l<=6;++l){
//                	printf("%d %d %d %d\n",i,j,k,l);
                    II=i,JJ=j,KK=k,LL=l;
                    rnw(i,j,k,l+1);
                    rnw(i+2,j,k,l+1);
                    rnw(i,j+1,k,l+1);
                    rnw(i-1,j,k+1,l+1),rnw(i+1,j-1,k+1,l+1),rnw(i,j-1,k,l+2),rnw(i+1,j,k-1,l+2),rnw(i-1,j+1,k-1,l+2),rnw(i,j-2,k+2,k+1);
                    rnw(i,j+2,k,l+1);
                    rnw(i,j,k,l+2);
                    rnw(i-1,j+1,k+1,l+1),rnw(i-1,j-1,k+1,l+2),rnw(i-2,j,k+2,l+1);
                    
                    rnw(i,j,k+1,l);
                    rnw(i+1,j,k+1,l);
                    rnw(i,j+1,k+1,l);
                    
                    rnw(i,j+1,k,l);
                    
                    rnw(i+1,j,k,l);
                }
            }
        }
    }
}
void init(){
    ans=0x3f3f3f3f;
    int x,xx;
    statue s(0);
    s.init();
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x,&xx);
        ++s.a[(!x)?(12+xx):((x+10)%13)];
    }
    if(s.a[13]&&s.a[14]){
        s.a[13]=s.a[14]=0;
        ++s.cst;
        dfs(s);
        --s.cst;
        s.a[13]=s.a[14]=1;
    }
    dfs(s);
    printf("%d\n",ans);
}
int main(){
	prpr();
    int T;
    scanf("%d%d",&T,&n);
    while(T--){
        init();
    }
    return 0;
}

 

lp2324 SCOI2005 骑士精神

一道\(IDA*\)的入门题。
首先我们发现移动空格比移动马更容易。
然后考虑如何移动。爆搜马的位置是一种有效的做法。
但是直接爆搜很容易出现一个问题:搜索可能会在一些劣的情况下搜很久,或者搜进死胡同不出来。
这时候我们设计一个东西叫做估价函数\(g_S\),如果当前局面的花费\(h_S\)加上估价函数大于花费上界\(f_S\)的话,这条选择支就是不优的。
然后我们可以枚举上界进行搜索。
由于随着上界的增长,花费的增长速度极快——每一层的花费都远大于上一层的花费。故而尽管上界具有单调性,但二分上界并不会更优。
(其实\(IDA*\)本质上就是玄学剪枝吧。)

#include<iostream>
#include<cstdio>

int nw[6][6];
const int mp[6][6]={
    {0,0,0,0,0,0},
    {0,1,1,1,1,1},
    {0,0,1,1,1,1},
    {0,0,0,-1,1,1},
    {0,0,0,0,0,1},
    {0,0,0,0,0,0},
};
const int dx[8]={-2,-2,-1,-1,1,1,2,2};
const int dy[8]={1,-1,2,-2,2,-2,1,-1};
inline int val(){
    int rt=0;
    for(int i=1;i<=5;++i){
        for(int j=1;j<=5;++j){
            if(mp[i][j]!=nw[i][j]){
                ++rt;
            }
        } 
    }
    return rt;
}

inline int Min(int A,int B){
    return A>B?A:B;
}

inline void Swap(int &X,int &Y){
    X^=Y^=X^=Y;
}

inline bool srch(int dp,int X,int Y,int dm,int lst){
    int Nval=val();
    if(!Nval){
        return 1;
    }
    if(dp>dm){
        return 0;
    }
    for(int i=0;i<8;++i){
        if(i+lst==7){
            continue;
        }
        int NX=X+dx[i],NY=Y+dy[i];
        if(NX<1||NY<1||NX>5||NY>5){
            continue;
        } 
        Swap(nw[X][Y],nw[NX][NY]);
        Nval=val();
        if(Nval+dp<=dm+1){
            if(srch(dp+1,NX,NY,dm,i)){
                return 1;
            }
        }
        Swap(nw[X][Y],nw[NX][NY]);
    }
    return 0;
}

void init(){
    char ch[6];
    int SX,SY;
    for(int i=1;i<=5;++i){
        std::cin>>ch+1;
        for(int j=1;j<=5;++j){
            nw[i][j]=ch[j]-'0';
            if(!isdigit(ch[j])){
                nw[i][j]=-1;
                SX=i,SY=j;
            }
        }
    }
    if(!val()){
        puts("0");
        return;
    }
    for(int i=1;i<=15;++i){
        if(srch(1,SX,SY,i,-1)){
            printf("%d\n",i);
            return;
        }
    }
    puts("-1");
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

lp3605 USACO Promotion Counting晋升者计数

题意是求树上逆序对。
统计方式基本和序列逆序对相同。但是需要注意的是,由于树上逆序对需要求的是,一个节点的「子孙节点」中权值比它大的个数,故而可以求差:
具体地来说,在每一次搜索到一个节点之前,把已有的比它大的个数先记录下来,然后往下搜索。在搜索完毕之后将比它大的个数的结果减去原有的比它大的数量,这就是答案。
很容易可以知道这个增量一定是在搜索它的子孙节点的时候增加的。
记住填写的变量到底是\(X\)还是\(b_{X}\).

lp3959 NOIP2017 宝藏

我们首先,如果两个点之间有连多条边,肯定只有最短的那条最优。
那么我们进行状压,对于某一个状态\(S_{0}\),我们维护它的所有拓展的集合\(T_{S_{1}}\)
然后,记\(f_{i,k}\)表示,当前状态为\(i\),当前的深度为\(k\)时的最小花费。
这样拓展,每一次拓展都相当于把深度加深了一层,因此就可以不要花费太多的精力去考虑\(k\)对贡献的影响。
而,从某一个根开始拓展,即相当于\(f_{(1<<i),0}\)
于是我们便可以开始DP。每一次拓展都会将可行集合纳入范围。这样拓展的花费也是可以被轻松计算出来的。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int n,m,f[1<<12][12],usf[1<<12];
int mp[15][15];
void init(){
    scanf("%d%d",&n,&m);
    int u,v,w;
    memset(mp,0x3f,sizeof(mp));
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        --u,--v; 
        mp[u][v]=Min(mp[u][v],w);
        mp[v][u]=Min(mp[v][u],w);
    }
    const int MAX=1<<n;
    for(int i=1;i<MAX;++i){
        for(int j=0;j<n;++j){
            if((i|(1<<j))!=i){
                continue;
            }
            for(int k=0;k<n;++k){
                if(mp[j][k]!=0x3f3f3f3f){
                    usf[i]|=(1<<k);
                }
            }
        }
    }
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<n;++i){
        mp[i][i]=0;
        f[1<<i][0]=0;
    }
    long long sm,nw,x;
    for(int i=2;i<MAX;++i){
        for(int j=i-1;j;j=(j-1)&i){
            if(((usf[i]|j)!=usf[i])){
                continue;
            }
            sm=0,nw=i^j;
            for(int k=0;k<n;++k){
                if((nw>>k)&1){
                    x=0x3f3f3f3f;
                    for(int l=0;l<n;++l){
                        if((j>>l)&1){
                            x=Min(x,mp[l][k]);
                        }
                    }
                    sm+=x;
                }
            }
            for(int k=1;k<n;++k){
                f[i][k]=Min(f[i][k],f[j][k-1]+sm*k);
            }
        }
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<n;++i){
        ans=Min(ans,f[MAX-1][i]);
    }
    printf("%d\n",ans);
}
int main(){
    init();
    return 0;
}

 

lp4578 FJOI2018 所罗门王的宝藏

首先,我们可以知道,令每一行、列数字的变化为\(dx_{i},dy_{i}\),那么对于\(z_{i,j}\),一定有:
$$dx_{i}+dy_{j}=z_{i,j}$$
对这个线性方程组变形,我们可以发现,如果指定序列合法,那么:
$$ \forall x ,z_{x,j_{1}}-z_{x,j_{2}}=dy_{j_{1}}-dy_{j_{2}} $$
$$ \forall y ,z_{i_{1},y}-z_{i_{2},y}=dx_{i_{1}}-dx_{i_{2}} $$
而,当\(dx\)和\(dy\)的相对关系不矛盾时,一定可以导出一个符合题意的矩阵。
因此,我们对于每组\(x,y\),统计它们的相对关系即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k; 
int dx[1005][1005],dy[1005][1005];
bool visx[1005][1005],visy[1005][1005];
int x[1005],y[1005],z[1005];
void init(){
    memset(dx,0,sizeof(dx));
    memset(dy,0,sizeof(dy));
    memset(visx,0,sizeof(visx));
    memset(visy,0,sizeof(visy));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;++i){
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
    }
    int nw;
    for(int i=1;i<k;++i){
        for(int j=i+1;j<=k;++j){
            if(x[i]==x[j]&&y[i]==y[j]&&z[i]!=z[j]){
                puts("No");
                return; 
            }
            if(x[i]==x[j]){
                nw=y[i]>y[j]?z[j]-z[i]:z[i]-z[j];
                if(visx[y[i]][y[j]]&&dx[y[i]][y[j]]!=nw){
                    puts("No");
                    return;
                }
                dx[y[i]][y[j]]=dx[y[j]][y[i]]=nw;
                visx[y[i]][y[j]]=visx[y[j]][y[i]]=1; 
            }
            if(y[i]==y[j]){
                nw=x[i]>x[j]?z[j]-z[i]:z[i]-z[j];
                if(visy[x[i]][x[j]]&&dy[x[i]][x[j]]!=nw){
                    puts("No");
                    return;
                }
                dy[x[i]][x[j]]=dy[x[j]][x[i]]=nw;
                visy[x[i]][x[j]]=visy[x[j]][x[i]]=1; 
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(dx[i][i]||dy[i][i]){
            puts("No");
            return;
        }
    }
    puts("Yes");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
} 

 

lp3953 NOIP2017 逛公园

容易知道,对于每个点,最多只能偏移50。
由此可以跑记忆化搜索:\(f_{i,j}\)表示,在第i个点,比最短路长了j时的方案数。
那么,我们倒着搜即可。
具体来说,定义\(dn_{x}\)表示\(x->u\)的最短路。
那么我们可以得到状态转移方程:
$$f_{u,k}=\sum_{v,v\in S,st: \forall x \in S,x_{u}=u}f_{v,k-dn_{v}+dn_{u}-w}$$
答案为\(f_{1,K}\)
几个细节:
e[i].nxt不应写作e[i].v
不要使用长得差不多的变量。

#include<iostream>
#include<cstdio>
#include<queue> 
#include<cstring>
using namespace std;
struct ee{
    int v;
    int w;
    int nxt;
}e[400005];
int h[100005],h2[100005],et=0,n,m,K,p,dis[100005],dn[100005],f[100005][51];
bool usd[100005][51];
inline void add(int *_H,const int &u,const int &v,const int &w){
    e[++et]=(ee){v,w,_H[u]};
    _H[u]=et;
}
struct cmp2{
    inline bool operator ()(const int &X,const int &Y)const{
        return dn[X]>dn[Y];
    }
};
void dij2(){
    priority_queue< int,vector<int>,cmp2 > q;
    memset(dn,0x3f,sizeof(dn));
    dn[n]=0;
    q.push(n);
    int nw;
    while(!q.empty()){
        nw=q.top();
        q.pop();
        for(int i=h2[nw];i;i=e[i].nxt){
            if(dn[e[i].v]>dn[nw]+e[i].w){
                dn[e[i].v]=dn[nw]+e[i].w;
                q.push(e[i].v);
            }
        }
    }
}
int dfs(int u,int k){
    if(usd[u][k]){
        return -1;
    }
    if(f[u][k]){
        return f[u][k];
    }
    usd[u][k]=1;
    if(u==n){
        f[u][k]=1;
    }
    int X,sm;
    for(int i=h[u];i;i=e[i].nxt){
        //e[i].v不能写成e[i].nxt 
        sm=dn[e[i].v]-dn[u]+e[i].w;
        if(sm>k){
            continue;
        }
        X=dfs(e[i].v,k-sm);
        if(X==-1){
            return f[u][k]=-1;
        }
        f[u][k]+=X;
        f[u][k]%=p;
    }
    usd[u][k]=0;
    return f[u][k];
}
void init(){
    memset(h,0,sizeof(h));
    memset(h2,0,sizeof(h2));
    scanf("%d%d%d%d",&n,&m,&K,&p);
    et=0;
    int u,v,w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        add(h,u,v,w);
        add(h2,v,u,w);
    }
    dij2();
    memset(f,0,sizeof(f));
    memset(usd,0,sizeof(usd));
    printf("%d\n",dfs(1,K));
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}