The Preliminary Contest for ICPC Asia Xuzhou 2019

B.so easy
그리고 집합 을 찾 으 면 맵 이 끊 길 수 있 습 니 다.unordered 를 사용 하 는 것 을 권장 합 니 다.map。

#include
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
inline bool read(ll &num) {
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
            num*=10,num+=in-'0';
    } 
    if(IsN) num=-num;
    return true;
}
unordered_map<int,int> par;
int find(int x){
    if(par[x]==0){
        par[x]=x;
        return x;
    }
    return x==par[x]?x:par[x]=find(par[x]);
}
int main(){
    int n,q;
    scanf("%d %d",&n,&q);
    int op,x;
    while(q--){
        scanf("%d %d",&op,&x);
        if(op==1){
            par[find(x)]=x+1;
        }else{
            if(find(x)>n) puts("-1");
            else printf("%d
",find(x));
        }
    }
    return 0;
}

C.Buy Watermelon
출석 은 2 이상 의 짝수 로 나 눌 수 있 습 니 다.

#include
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
inline bool read(ll &num) {
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
            num*=10,num+=in-'0';
    } 
    if(IsN) num=-num;
    return true;
}
int main(){
  //  freopen("1.in", "r", stdin);
    ll t,n;
    read(n);
    if(n>2&&(n%2==0)){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
    return 0;
}

D. Carneginon
KMP,쓰기 귀찮다.
E. XKC’s basketball team
모든 i i 에서 가장 오른쪽 을 찾 는 것 은 a i+m a 와 같 습 니 다.i+m ai+m 의 위치.선분 수 유지 구간 의 최대 치 는 오른쪽 트 리 를 우선 찾 으 면 됩 니 다.

#include
using namespace std;
const int N = 2e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
inline bool read(ll &num) {
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
            num*=10,num+=in-'0';
    } 
    if(IsN) num=-num;
    return true;
}
int mxx[N],a[N];
int n,m;
void pushup(int rt){
    mxx[rt]=max(mxx[rt<<1],mxx[rt<<1|1]);
}
void buildtree(int rt,int l,int r){
    mxx[rt]=0;
    if(l==r){
        mxx[rt]=a[l];return ;
    }
    int mid=(l+r)>>1;
    buildtree(rt<<1,l,mid);
    buildtree(rt<<1|1,mid+1,r);
    pushup(rt);
}
int query(int rt,int l,int r,int x){
   // cout<
    if(l==r){
        if(mxx[rt]>=x){
             return l;
        }
        else return -1;
    }
    int mid=(l+r)>>1;
    if(mxx[rt<<1|1]>=x){
        return query(rt<<1|1,mid+1,r,x);//    
    }else{
        return query(rt<<1,l,mid,x);
    }
}
int main(){
    //freopen("1.in", "r", stdin);
    scanf("%d %d",&n,&m);
    rep(i,1,n) scanf("%d",&a[i]);
    buildtree(1,1,n);
    vector<int> ans;
    rep(i,1,n){
        int id=query(1,1,n,a[i]+m);
        if(id<=i) ans.push_back(-1);
        else{
            ans.push_back(id-i-1);
        }
    }
    printf("%d",ans[0]);
    rep(i,1,(int)ans.size()-1) printf(" %d",ans[i]);
    puts("");
    return 0;
}

I. query
[1,n][1,n][1,n]에 대해 그들의 모든 배 수 를 매 거 하면 대략 O(n,8901,l o g(n)O(n\cdot log(n)O(n,8901,log(n)만 있 기 때문에 정사각형 으로 전환 하여 매번[l,l][l,l]에서[r,r][r,r][r,r,r]사이 의 점 수 를 조회 하면 된다.다음은 바로 오프라인 상태 에서 트 리 배열 로 접두사 와 유지 하면 됩 니 다.

#include
using namespace std;
const int N = 2e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
inline bool read(ll &num) {
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
            num*=10,num+=in-'0';
    } 
    if(IsN) num=-num;
    return true;
}

int n,m;
int c[N];
int lowbit(ll x){
    return (x&(-x));
}
void add(ll x,ll v){
    for(;x<N;x+=lowbit(x)){
         c[x]+=v;
         //cout<
    }
}
ll query(ll x){
    ll ans=0;
    for(;x;x-=lowbit(x)){
        ans+=c[x];
    }
    return ans;
}

int pos[N],a[N];
int l[N],r[N];
struct point{
    int x,y,flag;
}s[N];
bool cmp(point a,point b){
    if(a.x==b.x){
        if(a.y==b.y){
           return a.flag<b.flag;
        }
        return a.y<b.y;
    }
    return a.x<b.x;
}
int yy[N],id[N];
map<pair<int,int>,int> mmp;

int main(){
    scanf("%d %d",&n,&m);
    rep(i,1,n){
         scanf("%d",&a[i]);
         pos[a[i]]=i;
    }
    int cnt=0;
    rep(i,1,n){
        for(int j=2*i;j<=n;j+=i){
            s[++cnt]={pos[i],pos[j],0};
        }
    }
    rep(i,1,m){
        scanf("%d %d",&l[i],&r[i]);
        s[++cnt]={r[i],r[i],1};
        s[++cnt]={l[i]-1,r[i],1};
        s[++cnt]={r[i],l[i]-1,1};
        s[++cnt]={l[i]-1,l[i]-1,1};
    }

    rep(i,1,cnt) yy[i]=s[i].y;

    sort(yy+1,yy+cnt+1);
    int siz=unique(yy+1,yy+cnt+1)-yy-1;

    sort(s+1,s+cnt+1,cmp);
    rep(i,1,cnt){
        id[i]=lower_bound(yy+1,yy+siz+1,s[i].y)-yy;
    }
    rep(i,1,cnt){
        if(s[i].flag==0){
            add(id[i],1);
        }else{
            mmp[{s[i].x,s[i].y}]=query(id[i]);
        }
    }
    rep(i,1,m){
        printf("%d
",mmp[{r[i],r[i]}]-mmp[{l[i]-1,r[i]}]-mmp[{r[i],l[i]-1}]+mmp[{l[i]-1,l[i]-1}]);
    }
    return 0;
}

J. Random Access Iterator
먼저 각 점 에서 도달 할 수 있 는 최대 깊이 와 하위 노드 의 수량 을 미리 처리 하여 d p[x]dp[x]dp[x]는 잎 노드 에 도달 할 확률 을 나타 내 고 u u 에서 v v v v 로 이동 할 때 v v v v 가 도달 할 수 있 는 최대 깊이 가 나무의 깊이 와 같 을 때 만 이동 할 수 있다.잎 노드:d p[x]=1dp[x]=1 dp[x]=1,위로 이동 하면 됩 니 다.d p [ u ] = 1 − ( 1 − ∑ d p [ v ] ∣ s i z [ u ] ∣ ) ∣ s i z [ u ] ∣ dp[u]=1-(1- \frac{\sum{dp[v]}}{|siz[u]|})^{|siz[u]|} dp[u]=1−(1−∣siz[u]∣∑dp[v]​)∣siz[u]∣

#include
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;d
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
inline bool read(ll &num) {
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
            num*=10,num+=in-'0';
    } 
    if(IsN) num=-num;
    return true;
}
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=(ans%mod*a%mod)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans%mod;
}
ll inv(ll a){
    return qpow(a,mod-2);
}
vector<int> G[N];
int depth[N],maxxh[N],siz[N];
void dfs(int u,int par){
    depth[u]=depth[par]+1;
    maxxh[u]=depth[u];
    for(int v:G[u]){
        if(v==par) continue;
        siz[u]++;
        dfs(v,u);
        maxxh[u]=max(maxxh[u],maxxh[v]);
    }
}
ll dp[N];
ll solve(ll u,ll fa){
    if(siz[u]==0) return dp[u]=1;
    ll ans=0;
    for(int v:G[u]){
        if(v==fa) continue;
        if(maxxh[v]==maxxh[1]){
            ans+=solve(v,u);
        }
    }
    ans=ans*inv(siz[u])%mod;
    return dp[u]=(1-qpow(1-ans+mod,siz[u])+mod)%mod;
}
int main(){
    int n,u,v;
    cin>>n;
    rep(i,1,n-1){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,1);
    cout<<solve(1,1)<<endl;
    return 0;
}

K. Center
중심 점 을 매 거 하면 됩 니 다.매 거 진 이 점 이 점 집 내부 에 있다 고 가정 하면 다시 가 야 합 니 다.

#include
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
inline bool read(ll &num) {
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
            num*=10,num+=in-'0';
    } 
    if(IsN) num=-num;
    return true;
}
pair<int,int> a[N];
map<pair<int,int>,int> mp1,mp2;
int main(){
    int n;cin>>n;
    if(n==1){
        puts("0");return 0;
    }
    rep(i,1,n){
        cin>>a[i].first>>a[i].second;
        mp1[{2*a[i].first,2*a[i].second}]++;
    }
    rep(i,1,n){
        rep(j,i+1,n){
            mp2[{a[i].first+a[j].first,a[i].second+a[j].second}]++;
        }
    }
    int ans=INF;
    for(auto v:mp2){
        ans=min(ans,n-2*mp2[v.first]-mp1[v.first]);
    }
    cout<<ans<<endl;
    return 0;
}

M. Longest subsequence
S S S 에서 가장 긴 하위 시퀀스 를 찾 아 사전 순 서 를 T T 보다 크 게 하고 출력 길 이 를 찾 으 면 됩 니 다.
만약 에 T′T'T′,만약 에 T′>T T'>T′>T′>T′>T 가 T′T'T′가 어느 위치 에 있 는 p p p 가 T′[1..p-1]=T[1...p]T'[1...p-1]=T[1...p]T′[1...p-1]]]T′[1..p-1]=T[1...........p]=T′[p]][p]T'[p]T'[p]]T[p]]]T′[p]]]]]]]T[p]]][p]]]]]]]]]]]T[p]]]]p]T'[p]T′[p]와 빠 른 위치,답 을 계산 하면 된다.

#include
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
inline bool read(ll &num) {
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
            num*=10,num+=in-'0';
    } 
    if(IsN) num=-num;
    return true;
}
int nxt[N][27];
void init(char *s){
    int l=strlen(s);
    for(int i=0;i<26;i++) nxt[l][i]=INF;
    for(int i=l-1;i>=0;i--){
        for(int j=0;j<26;j++){
            nxt[i][j]=nxt[i+1][j];
        }
        nxt[i][s[i]-'a']=i;
    }
}
char s[N],t[N];
int main(){
    //freopen("1.in", "r", stdin);
    int n,m;
    cin>>n>>m;
    scanf("%s %s",s,t);
    init(s);
    int pos=-1;
    int ans=0;
    int cnt=0;
    bool flag=0;
    vector<int> id;
    for(int i=0;i<n;i++){
        for(int j=t[cnt]-'a'+1;j<26;j++){
            if(nxt[i][j]!=INF){
                flag=1;
                ans=max(ans,cnt+n-nxt[i][j]);
            }
        }
        if(s[i]==t[cnt]){
            cnt++;
            id.push_back(i);
        }
        if(cnt==m) break;
    }
    if(!flag){
        if(id.size()==m){
            if(id[m-1]==n-1)cout<<-1<<endl;
            else cout<<m+(n-id[m-1]-1)<<endl;
        }
        else cout<<-1<<endl;
    }
    else{
        if(id.size()==m&&id[m-1]!=-1){
            ans=max(ans,m+(n-id[m-1]-1));
        }
        cout<<ans<<endl;
    }
    return 0;
}