10.26 시험 폭발 기

21796 단어 OI자질구레한 문제 들 이 한데 모이다.동적 계획 강
emm... 절 지 반격 장 (1) copycat 는 두 문자열 에 소문 자의 유일한 대응 관계 가 있 는 지 판단 합 니 다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
inline int read(){
    int i=0,f=1;
    char ch;
    for(ch=getchar();!isdigit(ch);ch=getchar())
        if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar())
        i=(i<<3)+(i<<1)+(ch^48);
    return i*f;
}
int buf[1024];
inline void write(int x){
    if(!x){putchar('0');return ;}
    if(x<0){putchar('-');x=-x;}
    while(x){buf[++buf[0]]=x%10,x/=10;}
    while(buf[0]) putchar(buf[buf[0]--]+48);
    return ;
}
#define stan 1111
#define sten 33
char s1[stan],s2[stan];
int T,len1,len2,rev[sten],tag;
signed main(){
    T=read();
    for(register int i=1;i<=T;++i){
        gets(s1);
        gets(s2);
        memset(rev,-1,sizeof(rev));
        tag=true;
        len1=strlen(s1);
        len2=strlen(s2);
        if(len1!=len2){
            puts("0");
            continue;
        }
        for(int i=0;iif(s1[i]<='z'&&s1[i]>='a'){
                if(s2[i]>'z'||s2[i]<'a'){
                    puts("0");
                    tag=false;
                    break;
                }
                if(rev[s1[i]-'a']!=-1&&s2[i]-'a'!=rev[s1[i]-'a']){
                    puts("0");
                    tag=false;
                    break;
                }
                else rev[s1[i]-'a']=s2[i]-'a';
            }else
                if(s1[i]!=s2[i]){
                    puts("0");
                    tag=false;
                    break;
                }
        if(tag) puts("1");
    }
    return 0;
}

（2）running
이중 가중치 최 단 로 우선 kruskal 1 파
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
inline int read(){
    int i=0,f=1;
    char ch;
    for(ch=getchar();!isdigit(ch);ch=getchar())
        if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar())
        i=(i<<3)+(i<<1)+(ch^48);
    return i*f;
}
int buf[1024];
inline void write(long long x){
    if(!x){putchar('0');return ;}
    if(x<0){putchar('-');x=-x;}
    while(x){buf[++buf[0]]=x%10,x/=10;}
    while(buf[0]) putchar(buf[buf[0]--]+48);
    return ;
}
#define stan 555555
#define sten 2222222
int n,m,lim,x,y,S,T;
int tot,first[stan],nxt[sten],goal[sten],fa[stan];
long long to[stan],dis[sten];
bool exi[stan],tag;
struct edg{
    int a,b,c,t;
}edge[sten];
priority_queuelong long,int> >que;
void addedge(int a,int b,long long c){
    nxt[++tot]=first[a];first[a]=tot;goal[tot]=b;dis[tot]=c;
    nxt[++tot]=first[b];first[b]=tot;goal[tot]=a;dis[tot]=c;
    return; 
}
bool cmp(const edg &x,const edg &y){
    return x.tinline int getfa(int x){
    if(fa[x]!=x) return fa[x]=getfa(fa[x]);
    else return x;
}
void dij(){
    for(int i=1;i<=n;++i)
        to[i]=-1;
    to[S]=0;
    que.push(make_pair(-to[S],S));
    while(!que.empty()){
        int u=que.top().second;que.pop();
        if(exi[u]) continue;
        exi[u]=true;
        for(int p=first[u];p;p=nxt[p])
            if(to[goal[p]]>to[u]+dis[p]||to[goal[p]]==-1){
                to[goal[p]]=to[u]+dis[p];
                que.push(make_pair(-to[goal[p]],goal[p]));
            }
    }
    return ;
}
signed main(){
    n=read();m=read();
    for(register int i=1;i<=n;++i)
        fa[i]=i;
    for(register int i=1;i<=m;++i){
        edge[i].a=read();
        edge[i].b=read();
        edge[i].t=read();
        edge[i].c=read();
    }
    S=read();T=read();
    sort(edge+1,edge+m+1,cmp);
    for(register int i=1;i<=m;++i){
        if(tag&&edge[lim].tbreak;
        x=getfa(edge[i].a);
        y=getfa(edge[i].b);
        if(x!=y) fa[x]=y;
        lim=i;
        x=getfa(S);
        y=getfa(T);
        if(x==y) tag=true;
    }
    for(register int i=1;i<=lim;++i)
        addedge(edge[i].a,edge[i].b,(long long)edge[i].t*edge[i].c);
    dij();
    write(edge[lim].t);putchar(' ');write(to[T]);
    return 0;
}

（3）toyuq
트 리 DP, f [i] [j] [0] 은 i 에서 출발 하기 위해 i f [i] [j] [1] 는 i 에서 출발 하기 위해 f [i] [j] [2] 는 i 만 지나 간다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
inline int read(){
    int i=0,f=1;
    char ch;
    for(ch=getchar();!isdigit(ch);ch=getchar())
        if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar())
        i=(i<<3)+(i<<1)+(ch^48);
    return i*f;
}
int buf[1024];
inline void write(long long x){
    if(!x){putchar('0');return ;}
    if(x<0){putchar('-');x=-x;}
    while(x){buf[++buf[0]]=x%10,x/=10;}
    while(buf[0]) putchar(buf[buf[0]--]+48);
    return ;
}
#define stan 333
#define sten 666
int tot,first[stan],nxt[sten],goal[sten],dis[sten];
int f[stan][stan][3],rev[stan][stan],tmp[stan],ans,a,b,c,n,T,w[stan],t[stan];
void addedge(int a,int b,int c){
    nxt[++tot]=first[a];first[a]=tot;goal[tot]=b;dis[tot]=c;
    nxt[++tot]=first[b];first[b]=tot;goal[tot]=a;dis[tot]=c;
    return; 
}
void dfs(int u,int fa){
    for(int i=t[u];i<=T;++i)
        f[u][i][0]=f[u][i][1]=f[u][i][2]=w[u];
    for(int p=first[u];p;p=nxt[p])
        if(goal[p]!=fa){
            dfs(goal[p],u);
            for(int i=0;i<=T;++i)
                tmp[i]=f[u][i][2];
            for(int i=0;i<=T;++i){
                for(int j=0;j<=i-dis[p]-t[u];++j)
                    tmp[i]=max(tmp[i],f[u][i-dis[p]-j][1]+f[goal[p]][j][1]);
                for(int j=0;j<=i-2*dis[p]-t[u];++j)
                    tmp[i]=max(tmp[i],f[u][i-2*dis[p]-j][0]+f[goal[p]][j][2]);
                for(int j=0;j<=i-2*dis[p]-t[u];++j)
                    tmp[i]=max(tmp[i],f[u][i-2*dis[p]-j][2]+f[goal[p]][j][0]);
            }
            for(int i=0;i<=T;++i)
                f[u][i][2]=tmp[i];
            for(int i=0;i<=T;++i)
                tmp[i]=f[u][i][1];
            for(int i=0;i<=T;++i){
                for(int j=0;j<=i-dis[p]-t[u];++j)
                    tmp[i]=max(tmp[i],f[u][i-dis[p]-j][0]+f[goal[p]][j][1]);    
                for(int j=0;j<=i-2*dis[p]-t[u];++j)
                    tmp[i]=max(tmp[i],f[u][i-2*dis[p]-j][1]+f[goal[p]][j][0]);
            }
            for(int i=0;i<=T;++i)
                f[u][i][1]=tmp[i];
            for(int i=0;i<=T;++i)
                tmp[i]=f[u][i][0];
            for(int i=0;i<=T;++i)
                for(int j=0;j<=i-2*dis[p]-t[u];++j)
                    tmp[i]=max(tmp[i],f[u][i-2*dis[p]-j][0]+f[goal[p]][j][0]);
            for(int i=0;i<=T;++i)
                f[u][i][0]=tmp[i];
        }
}
signed main(){
    n=read();T=read();
    for(int i=1;i<=n;++i)
        w[i]=read();
    for(int i=1;i<=n;++i)
        t[i]=read();
    for(int i=1;i1,0);
    for(int i=1;i<=n;++i)
        for(int j=0;j<=T;++j)
            for(int k=0;k<=2;++k)
                ans=max(ans,f[i][j][k]);
    write(ans);
    return 0;
}
ViewPager 슬라이딩 속도 전환
커 널 명령 처리

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage