7.12

bokaro_kyoku_mania · 2025-07-12 19:45:27 · 个人记录

P1276:

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
    x=0;
    char c;
    int sign=1;
    do{
        c=getchar();
        if(c=='-'){
            sign=-1;
        }
    }while(!isdigit(c));
    do{
        x=x*10+c-'0';
        c=getchar();
    }while(isdigit(c));
    x*=sign;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline string readstr(){
    string str="";
    char ch=getchar();
    while(ch==' '||ch=='\n'||ch=='\r'){
        ch=getchar();
    }
    while(ch!='\n'&&ch!='\r'){
        str+=ch;
        ch=getchar();
    }
    return str;
}
inline void printstr(string s){
    for(int i=0;s[i]!='\0';i++){
        putchar(s[i]);
    }
}
int n,l,ju,ans1,x,y,ans2;
int p[101010],c[101010],m[101010];
signed main(){
    memset(p,1,sizeof(p)); 
    memset(c,0,sizeof(c)); 
    read(l);
    read(n); 
    for(int i=1;i<=n;i++){
        read(ju);
        read(x);
        read(y);
        if(ju==0){
            for(int j=x;j<=y;j++){
                p[j]=0;
                m[j]=0;
                if(c[j]==1){
                    ans2++;
                    c[j]=0;
                }
            }
        }
        else{
            for(int j=x;j<=y;j++){
                if(p[j]==0){
                    c[j]=1;
                    m[j]=1;
                }
                p[j]=1;
            }
        }
    }
    for(int i=0;i<=l;i++){
        if(m[i]==1){
            ans1++; 
        }
    }
    write(ans1);
    putchar('\n');
    write(ans2);

    return 0; 
}

P1347:

#include<bits/stdc++.h>
//#define int long long
using namespace std;
template<typename T>inline void read(T&x){
    x=0;
    char c;
    int sign=1;
    do{
        c=getchar();
        if(c=='-'){
            sign=-1;
        }
    }while(!isdigit(c));
    do{
        x=x*10+c-'0';
        c=getchar();
    }while(isdigit(c));
    x*=sign;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline string readstr(){
    string str="";
    char ch=getchar();
    while(ch==' '||ch=='\n'||ch=='\r'){
        ch=getchar();
    }
    while(ch!='\n'&&ch!='\r'){
        str+=ch;
        ch=getchar();
    }
    return str;
}
inline void printstr(string s){
    for(int i=0;s[i]!='\0';i++){
        putchar(s[i]);
    }
}
vector<int>e[30];
int n,m;
queue<int>q;
string s,ans;
int in[30];
int topusort(){
    ans="";
    while(!q.empty()){
        q.pop();
    }
    for(int i=1;i<=n;i++){
        in[i]=0;
    }
    for(int i=1;i<=n;i++){
        for(auto to:e[i]){
            in[to]++;
        }
    }
    for(int i=1;i<=n;i++){
        if(!in[i]){
            q.push(i);
        }
    }
    int k=0;
    while(!q.empty()){
        if(q.size()!=1)k=2;
        int x=q.front();
        q.pop();
        ans+=char(x+'A'-1);
        for(auto to:e[x]){
            --in[to];
            if(!in[to]){
                q.push(to);
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(in[i])k=1;
    }
    return k;
}
signed main(){
    read(n);
    read(m);
    for(int i=1;i<=m;i++){
        s=readstr();
        e[s[0]-'A'+1].push_back(s[2]-'A'+1);
        int op=topusort();
        if(op==0){
            printf("Sorted sequence determined after %d relations: ",i);
            printstr(ans);
            putchar('.');
            putchar('\n');
            return 0;
        }
        if(op==1){
            printf("Inconsistency found after %d relations.\n",i);
            return 0;
        }
    }
    string ansss="Sorted sequence cannot be determined.";
    printstr(ansss);

    return 0;
}

P1807:

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
    x=0;
    char c;
    int sign=1;
    do{
        c=getchar();
        if(c=='-'){
            sign=-1;
        }
    }while(!isdigit(c));
    do{
        x=x*10+c-'0';
        c=getchar();
    }while(isdigit(c));
    x*=sign;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline string readstr(){
    string str="";
    char ch=getchar();
    while(ch==' '||ch=='\n'||ch=='\r'){
        ch=getchar();
    }
    while(ch!='\n'&&ch!='\r'){
        str+=ch;
        ch=getchar();
    }
    return str;
}
inline void printstr(string s){
    for(int i=0;s[i]!='\0';i++){
        putchar(s[i]);
    }
}
const int N=1e5+50;
queue<int>q;
vector<pair<int,int> >e[N];
int n,m,f[N];
int in[N];
void topu(){
    memset(f,-0x3f,sizeof(f));
    f[1]=0;
    for(int i=1;i<=n;i++){
        for(auto to:e[i]){
            in[to.first]++;
        }
    }
    for(int i=1;i<=n;i++){
        if(!in[i]){
            q.push(i);
        }
    }
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(auto to:e[x]){
            f[to.first]=max(f[to.first],f[x]+to.second);
            in[to.first]--;
            if(!in[to.first])q.push(to.first);
        }
    }
}
signed main(){
    read(n);
    read(m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        read(u);
        read(v);
        read(w);
        e[u].push_back(make_pair(v,w));
    }
    topu();
    if(f[n]<-1e8)write(-1);
    else write(f[n]);

    return 0;
}

P3379:

(lca模板)

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
    x=0;
    char c;
    int sign=1;
    do{
        c=getchar();
        if(c=='-'){
            sign=-1;
        }
    }while(!isdigit(c));
    do{
        x=x*10+c-'0';
        c=getchar();
    }while(isdigit(c));
    x*=sign;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline string readstr(){
    string str="";
    char ch=getchar();
    while(ch==' '||ch=='\n'||ch=='\r'){
        ch=getchar();
    }
    while(ch!='\n'&&ch!='\r'){
        str+=ch;
        ch=getchar();
    }
    return str;
}
inline void printstr(string s){
    for(int i=0;s[i]!='\0';i++){
        putchar(s[i]);
    }
}
const int N=1e6+50;
int n,m,s;
int head[N],nxt[N<<1],to[N<<1],tot;
int deep[N];
int p[N][21];
void add(int x,int y){
    nxt[tot]=head[x];
    to[tot]=y;
    head[x]=tot++;
}
void dfs(int x){
    for(int i=head[x];~i;i=nxt[i]){
        if(to[i]!=p[x][0]){
            deep[to[i]]=deep[x]+1;
            p[to[i]][0]=x;
            dfs(to[i]);
        }
    }
}
int lca(int x,int y){
    if(deep[x]<deep[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(deep[x]-deep[y]>=(1<<i)){
            x=p[x][i];
        }
    }
    if(x==y)return x;
    for(int i=20;i>=0;i--){
        if(p[x][i]!=p[y][i]){
            x=p[x][i];
            y=p[y][i];
        }
    }
    return p[x][0];
}
signed main(){
    memset(head,-1,sizeof(head));
    read(n);
    read(m);
    read(s);
    for(int i=1;i<=n-1;i++){
        int u,v;
        read(u);
        read(v);
        add(u,v);
        add(v,u); 
    }
    dfs(s);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            p[i][j]=p[p[i][j-1]][j-1];
        }
    }
    while(m--){
        int u,v;
        read(u);
        read(v);
        write(lca(u,v));
        putchar('\n');
    }

    return 0;
}

(离线做法)

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
    x=0;
    char c;
    int sign=1;
    do{
        c=getchar();
        if(c=='-'){
            sign=-1;
        }
    }while(!isdigit(c));
    do{
        x=x*10+c-'0';
        c=getchar();
    }while(isdigit(c));
    x*=sign;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline string readstr(){
    string str="";
    char ch=getchar();
    while(ch==' '||ch=='\n'||ch=='\r'){
        ch=getchar();
    }
    while(ch!='\n'&&ch!='\r'){
        str+=ch;
        ch=getchar();
    }
    return str;
}
inline void printstr(string s){
    for(int i=0;s[i]!='\0';i++){
        putchar(s[i]);
    }
}
const int N =5e5+50;
int n,m,s,p[N],fa[N],ans[N];
vector<pair<int,int> >q[N];
int head[N],nxt[N<<1],to[N<<1],tot;
void add(int x,int y){
    nxt[tot]=head[x];
    to[tot]=y;
    head[x]=tot++;
}
int get_p(int x){
    return p[x]==x?x:p[x]=get_p(p[x]);
}
bool vis[N];
void dfs(int x){
    vis[x]=1;
    for(auto t:q[x]){
        if(vis[t.first]){
        ans[t.second]=get_p(t.first);
        }
    }
    for(int i=head[x];~i;i=nxt[i]){
        if(to[i]!=fa[x]){
            fa[to[i]]=x;
            dfs(to[i]);
        }
    }
    p[x]=fa[x]; 
}
signed main(){
    memset(head,-1,sizeof(head));
    read(n);
    read(m);
    read(s);
    for(int i=1;i<=n-1;i++){
        int u,v;
        read(u);
        read(v);
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=m;i++){
        int u,v;
        read(u);
        read(v);
        q[u].push_back(make_pair(v,i));
        q[v].push_back(make_pair(u,i)); 
    }
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    dfs(s);
    for(int i=1;i<=m;i++){
        write(ans[i]);
        putchar('\n');
    }

    return 0;
}

(链剖做法)

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
    x=0;
    char c;
    int sign=1;
    do{
        c=getchar();
        if(c=='-'){
            sign=-1;
        }
    }while(!isdigit(c));
    do{
        x=x*10+c-'0';
        c=getchar();
    }while(isdigit(c));
    x*=sign;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline string readstr(){
    string str="";
    char ch=getchar();
    while(ch==' '||ch=='\n'||ch=='\r'){
        ch=getchar();
    }
    while(ch!='\n'&&ch!='\r'){
        str+=ch;
        ch=getchar();
    }
    return str;
}
inline void printstr(string s){
    for(int i=0;s[i]!='\0';i++){
        putchar(s[i]);
    }
}
const int N=1e6+50;
int n,m,s;
int head[N],nxt[N<<1],to[N<<1],tot;
int deep[N];
int fa[N],hson[N],sz[N],top[N];
void add(int x,int y){
    nxt[tot]=head[x];
    to[tot]=y;
    head[x]=tot++;
}
void dfs(int x){
    sz[x]=1;
    for(int i=head[x];~i;i=nxt[i]){
        if(to[i]!=fa[x]){
            deep[to[i]]=deep[x]+1;
            fa[to[i]]=x;
            dfs(to[i]);
            sz[x]+=sz[to[i]];
            if(sz[hson[x]]<sz[to[i]]){
                hson[x]=to[i];
            }
        }
    }
}
void dfs2(int x,int t){
    top[x]=t;
    if(hson[x])dfs2(hson[x],t);
    for(int i=head[x];~i;i=nxt[i]){
        if(to[i]!=fa[x]&&to[i]!=hson[x]){
            dfs2(to[i],to[i]);
        }
    }
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]){
            swap(x,y);
        }
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]){
        swap(x,y);
    }
    return x;
}
signed main(){
    memset(head,-1,sizeof(head));
    read(n);
    read(m);
    read(s);
    for(int i=1;i<=n-1;i++){
        int u,v;
        read(u);
        read(v);
        add(u,v);
        add(v,u); 
    }
    dfs(s);
    dfs2(s,s);
    while(m--){
        int u,v;
        read(u);
        read(v);
        write(lca(u,v));
        putchar('\n');
    }

    return 0;
}