JSZX Winter Camp Day 3 爆零记

2021-02-17 02:20

阅读：738

emmmm蒟蒻的我爆零啦！！T1码了个dijikstra然后T了，正解为Floyd。T2蒟蒻并不会，唯一会的只有暴力。。T3写了个Trie然后MLE了，然而正解是

哈希。T4是蒟蒻唯一一道会的，然而却忘了开long long。手动GG。。

题意：在一个有向图中，求从指定起点到指定终点的最小值，最小值定义为路径上的边权和减去路径上点权的最小值。

超时代码：

#include
#include
#define maxn 300
#define inf 2e9
using namespace std;
int vis[maxn],head[maxn],tot,n,m,w[maxn];
struct DIS{
    int juli,minn;
}dis[maxn];
int read(){
    int w=0,f=1;char c=getchar();
    while(c‘0‘||c>‘9‘) if(c==‘-‘) f=-1,c=getchar();
    while(c>=‘0‘&&c‘9‘) w=w*10+c-48,c=getchar();;
    return w*f;
}
struct Edge{
    int to,next,v;
}e[200050];
void add(int x,int y,int v){
    e[++tot]=(Edge){y,head[x],v};head[x]=tot;
}
void dijk(int s){
    int i,j;
    for(i=1;iif(w[i]==-1) vis[i]=true;
//    printf("w:%d vis:%d\n",w[2],vis[2]);
    for( i=head[s];i;i=e[i].next){
        if(!vis[e[i].to]) dis[e[i].to].juli=e[i].v-min(w[e[i].to],w[s]),dis[e[i].to].minn=min(w[e[i].to],w[s]);
    }
    for(i=1;i){
        int mi=inf,k;
        for(j=1;j){
            if(!vis[j]&&dis[j].julij;
        }
//        printf("k:%d   vis[2]:%d\n",k,vis[2]);
        vis[k]=true;
        for(j=head[k];j;j=e[j].next){
            if(!vis[e[j].to]&&(mi+e[j].v-min(w[e[j].to],dis[e[j].to].minn)+dis[e[j].to].minn)dis[e[j].to].juli)
            dis[e[j].to].juli=mi+e[j].v-min(w[e[j].to],dis[e[j].to].minn)+dis[e[j].to].minn,dis[e[j].to].minn=min(dis[e[j].to].minn,w[e[j].to]);
        }
        
    }
}
int main(){
    freopen("T1_.in","r",stdin);
    freopen("T1_.out","w",stdout);
int i,x,y,v,q,s,t;
    n=read();m=read();
    for(i=1;i){
        w[i]=read();
    }
    for(i=1;i){
        x=read();y=read();v=read();
        add(x,y,v);add(y,x,v);
    }
    q=read();
    while(q--){
        s=read();t=read();
        if(w[s]==-1||w[t]==-1){
            printf("mon panache!\n");continue;
        }
        for(i=1;iinf;
//        printf("1");
        for(i=1;ifalse;
        dijk(s);
        if(dis[t].juli==inf) printf("mon panache!\n");
        else printf("%d\n",dis[t]);
//        printf("1");
    }
    return 0;
}

正解（某大神）：

#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn=233+23;
struct zs{int v,id;}a[maxn];
ll dis[maxn][maxn],ans[maxn][maxn];
int id[maxn];
int i,j,k,n,m;


int ra,fh;char rx;
inline int read(){
    rx=getchar(),ra=0,fh=1;
    while(rx‘0‘)rx==‘-‘&&(fh=-1),rx=getchar();
    while(rx>=‘0‘)ra=ra*10+rx-48,rx=getchar();return ra*fh;
}

inline ll min(ll a,ll b){return aa:b;}
bool operator return a.vb.v;}
int main(){
    freopen("T1_.in","r",stdin);
    freopen("T1_.out","w",stdout);
    n=read(),m=read();
    for(i=1;ii;
    sort(a+1,a+1+n);
    for(i=1;ii;
    
    memset(dis,10,sizeof(dis)),memset(ans,10,sizeof(ans));;
    for(i=1;imin(dis[j][k],read());
    
    for(k=n;k;k--)if(a[k].v>-1)
        for(i=1;ifor(j=1;j)
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]),
            ans[i][j]=min(ans[i][j],dis[i][j]-a[k].v);
    int q=read();
    while(q--){
        i=id[read()],j=id[read()];
        if(ans[i][j]"%lld\n",ans[i][j]);else puts("mon panache!");
    }
}

题意：求I字形的最大面积，规定I字形，分为三个矩形，第二个矩形一定比另外两个窄。

#include
#include
#includeusing namespace std;
const int maxn=205;
const int inf=1002333;
int f[2][3][maxn][maxn];
int sm[maxn][maxn],mx1[maxn][maxn],mx2[maxn][maxn];
int n,m,pre,now,ans,tmpmx;
 
int ra;char rx;
inline int read(){
    rx=getchar(),ra=0;
    while(rx‘0‘||rx>‘9‘)rx=getchar();
    while(rx>=‘0‘&&rx‘9‘)ra*=10,ra+=rx-48,rx=getchar();return ra;
}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return aa:b;}
char rs[233];
int main(){
    freopen("T6_.in","r",stdin);
    freopen("T6_.out","w",stdout);
    register int i,j,k;
    n=read(),m=read();
    for(i=1;i){
        scanf("%s",rs+1);
        for(j=1;j1]+(rs[j]==‘1‘);
    }
    for(i=1;i0][i]=i;
     
    now=1,pre=0;
    for(i=1;i2;i++)memset(f[0][i],200,sizeof(f[0][i]));
    for(i=1;i,swap(now,pre)){
        for(j=1;jfor(k=j+1;k)
            if(sm[i][k]==sm[i][j-1])
                f[now][0][j][k]=(sm[i-1][k]==sm[i-1][j-1]?f[pre][0][j][k]:0)+k-j+1;
            else f[now][0][j][k]=-inf;
         
         
        for(j=1;jfor(k=m,tmpmx=-inf;k>j;k--)
            tmpmx=max(tmpmx,f[pre][0][j][k]),
            mx1[j][k]=max(mx1[j-1][k],tmpmx);
        for(j=2;jfor(k=j;k)
            if(sm[i][k]==sm[i][j-1]){
                f[now][1][j][k]=f[pre][1][j][k]+k-j+1;
                if(sm[i-1][k+1]==sm[i-1][j-2])
                    f[now][1][j][k]=max(f[now][1][j][k],mx1[j-1][k+1]+k-j+1);
            }
            else f[now][1][j][k]=-inf;
         
         
        for(j=2;j1][j][j];
        for(j=1;j)
            for(k=2;k)
            mx2[k][k+j]=max(mx2[k][k+j-1],max(mx2[k+1][k+j],f[pre][1][k][k+j]));
 
        for(j=1;jfor(k=j+2;k){
            if(sm[i][k]==sm[i][j-1])
                f[now][2][j][k]=max(f[pre][2][j][k],mx2[j+1][k-1])+k-j+1;
            else f[now][2][j][k]=-inf;
            if(f[now][2][j][k]>ans)ans=f[now][2][j][k];
        }
    }
    printf("%d\n",ans);
    return 0;
}

题意：求最多有几对字符串相匹配，A与T配，G与C配。

#include
#include
#include
#include
#define ll long long
#define ull unsigned long long
using namespace std;
const int maxn=1e5+233,modd=2333333;
struct zs{ull v;int pre,rest;}e[maxn];int tot,last[modd];
char s[maxn];
int i,j,k,n,m;


int ra,fh;char rx;
inline int read(){
    rx=getchar(),ra=0,fh=1;
    while(rx‘0‘)rx==‘-‘&&(fh=-1),rx=getchar();
    while(rx>=‘0‘)ra=ra*10+rx-48,rx=getchar();return ra*fh;
}

inline bool tryget(ull v){
    int x=v%modd,i;
    for(i=last[x];i&&e[i].v!=v;i=e[i].pre);
    return (i&&e[i].rest)?(e[i].rest--,1):0;
}
inline void ins(ull v){
    int x=v%modd,i;
    for(i=last[x];i&&e[i].v!=v;i=e[i].pre);
    if(i)e[i].rest++;else e[++tot].v=v,e[tot].rest=1,e[tot].pre=last[x],last[x]=tot;
}
int mp1[255];
int main(){
    freopen("T8_.in","r",stdin);
    freopen("T8_.out","w",stdout);
    n=read();
    mp1[‘A‘]=0,mp1[‘T‘]=1,mp1[‘C‘]=2,mp1[‘G‘]=3;
    int ans=0;
    for(i=1;i){
        scanf("%s",s+1);
        ull h1=0,h2=0;int len=strlen(s+1),ch;
        for(j=1;j)
            ch=mp1[(int)s[j]],
            h1=h1*2333+ch+1,h2=h2*2333+(ch^1)+1;
        if(tryget(h2))ans++;else ins(h1);
    }printf("%d\n",ans);
}

T 3

蒟蒻忘了开long long 啊!!

解法：从任意一点出发找到离他最远的点，那么找到的这个点必然为树的直径的某一端点，顺着这个端点我们就能找到直径的令一个端点，

那么树上所有点到其他点的距离必然是到直径的某个端点的距离，那么分别DFS直径的两个端点，每个点到直径两个端点的距离取个max值即可。

#include
#include
#include#define maxn 100050
using namespace std;
#define int long long
int tot,n,dp[maxn],head[maxn],maxlen,len,fan;
int read(){
    int w=0,f=1;char c=getchar();
    while(c‘0‘||c>‘9‘) if(c==‘-‘) f=-1,c=getchar();
    while(c>=‘0‘&&c‘9‘) w=w*10+c-48,c=getchar();;
    return w*f;
}
struct Edge{
    int to,next,v;
}e[200050];
void add(int x,int y,int v){
    e[++tot]=(Edge){y,head[x],v};head[x]=tot;
}
void dfs(int x,int fa,int len){
    if(len>maxlen) maxlen=len,fan=x;
    for(int i=head[x];i;i=e[i].next){
        if(e[i].to!=fa){
            dfs(e[i].to,x,len+e[i].v);
            dp[e[i].to]=max(dp[e[i].to],len+e[i].v);
        }
    }
}
#undef int
int main(){
    #define int long long
    freopen("T3_.in","r",stdin);
    freopen("T3_.out","w",stdout);
    int i,x,v;
    n=read();
    for(i=1;i){
        x=read();v=read();add(i,x,v);add(x,i,v);
    }
    memset(dp,0,sizeof(dp));
    dfs(1,-1,0);
    dfs(fan,-1,0);
    dfs(fan,-1,0);
//    dfs(fan,-1,0);
//    dfs(fan,-1,0);
//    dfs(fan,-1,0);
//    dfs(fan,-1,0);
//    dfs(fan,-1,0);
//    dfs(fan,-1,0);
    for(i=1;i)
    printf("%lld\n",dp[i]);
    fclose(stdin);fclose(stdout);
    return 0;
}

上一篇：DEV Winform分页用户组件

下一篇：四则运算表达式生成器（C语言）

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：JSZX Winter Camp Day 3 爆零记
文章链接：http://soscw.com/index.php/essay/56377.html

亲，登录后才可以留言！

JSZX Winter Camp Day 3 爆零记

评论

热门文章

推荐文章

最新文章

置顶文章