JZTXT

2019, XII Samara Regional Intercollegiate Programming Contest

发布时间 2023-09-20 23:51:27作者: EdGrass

\(Problem A. Rooms and Passages\)

倒着处理每个位置正数的最前部的位置。
如果是正数，显然答案为后一个位置的答案 \(+1\) 。
如果是负数且前面出现过相应的正数，答案要对这个区间长度 \(-1\) 的取 \(min\) 。

void solve(){
    int n=read();
    vector<int>a(n+2),cnt(n+2,-1),ans(n+2,0);
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=n;i>=1;i--){
        if(a[i]>0){
            cnt[a[i]]=i;
            ans[i]=ans[i+1]+1;
        }else if(cnt[-a[i]]==-1){
            ans[i]=ans[i+1]+1;
        }else{
            ans[i]=min(ans[i+1]+1,cnt[-a[i]]-i);
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(Problem B. Rearrange Columns\)

显然上下都为 \(\#\) 的时候，可以为桥。
如果上面一排和下面一排都有 \(\#\) ，必须要桥。

char a[3][N];
void solve(){
    string s,t;
    cin>>s>>t;
    int fl1=0,fl2=0,li=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='#'&&t[i]=='.')fl1++;
        if(s[i]=='.'&&t[i]=='#')fl2++;
        if(s[i]=='#'&&t[i]=='#')li++;
    }
    puts(fl1>0&&fl2>0&&li==0?"NO":"YES");
    if(fl1>0&&fl2>0&&li==0){}
    else {
        for(int i=1;i<=fl1;i++){
            a[1][i]='#';
            a[2][i]='.';
        }
        for(int i=fl1+1;i<=fl1+li;i++){
            a[1][i]='#';
            a[2][i]='#';
        }
        for(int i=fl1+li+1;i<=fl1+fl2+li;i++){
            a[1][i]='.';
            a[2][i]='#';
        }
        for(int i=fl1+li+fl2+1;i<=s.size();i++){
            a[1][i]='.';
            a[2][i]='.';
        }
        for(int i=1;i<=2;i++){
            for(int j=1;j<=s.size();j++){
                cout<<a[i][j];
            }
        cout<<'\n';
        }
    }
    //puts(ans>0?"Yes":"No");
}

\(Problem C. Jumps on a Circle\)

由于走的路径长度是等差数列的值，那么显然最多走 \(2*p\) 次必然会是取模后相同的。那么只要看 $ min(2*p,n)$ 次会有多少经历的点。

int vis[N];
void solve(){
    int p=read(),n=read(),now=0,ans=0;
    for(int i=0;i<=min(2*p,n);i++){
        now=(now+=i)%p;
        if(vis[now]==0)vis[now]=1,ans++;
    }
    cout<<ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(Problem D. Country Division\)

计算两类点分别的 \(lca\) ，如果 \(lca\) 的子树里出现过另一类点那么 \(yes\) 。
对子树的判断可以用 \(dfn\) 序判断。

struct tree{
    int t, nex;
}e[N << 1]; int head[N], tot;
void add(int x, int y) {
	e[++tot].t = y;
	e[tot].nex = head[x];
	head[x] = tot;
}
int depth[N], fa[N][22], lg[N],dfin[N],dfout[N],cnt=0;
void dfs(int now, int fath) {
	fa[now][0] = fath; depth[now] = depth[fath] + 1;
    dfin[now]=++cnt;
	for(int i = 1; i <= lg[depth[now]]; ++i)
		fa[now][i] = fa[fa[now][i-1]][i-1];
	for(int i = head[now]; i; i = e[i].nex)
		if(e[i].t != fath) dfs(e[i].t, now);
    dfout[now]=cnt;
}
int LCA(int x, int y) {
	if(depth[x] < depth[y]) swap(x, y);
	while(depth[x] > depth[y])
		x = fa[x][lg[depth[x]-depth[y]] - 1];
	if(x == y) return x;
	for(int k = lg[depth[x]] - 1; k >= 0; --k)
		if(fa[x][k] != fa[y][k])
			x = fa[x][k], y = fa[y][k];
	return fa[x][0];
}
bool check(int u, vector<int>tmp){
    for(auto x:tmp){
        if(dfin[x]>=dfin[u]&&dfout[x]<=dfout[u]) return false;
    }
    return true;
}
void solve(){
    int n=read();
	for(int i = 1; i <= n-1; ++i) {
		int x=read(), y=read(); 
		add(x, y); add(y, x);
	}
	for(int i = 1; i <= n; ++i)
		lg[i] = lg[i-1] + (1 << lg[i-1] == i);
	dfs(1, 0);
    int q=read();
	for(int i = 1; i <= q; ++i) {
		int x=read(),y=read();
        int lcar,lcab;
        vector<int>rr,bb;
        for(int i=1;i<=x;i++){
            int u=read();
            rr.push_back(u);
            if(i==1)lcar=u;
            else lcar=LCA(u,lcar);
        }
        for(int i=1;i<=y;i++){
            int u=read();
            bb.push_back(u);
            if(i==1)lcab=u;
            else lcab=LCA(u,lcab);
        }
        puts((check(lcar,bb)||check(lcab,rr))?"YES":"NO");
	}
    //puts(ans>0?"Yes":"No");
}

\(Problem E. Third-Party Software - 2\)

对于区间取最大右端点，然后从左端点在上个右端点到目前右端点的区间里选择右端点最大的，依次向后，如果不能达到 \(m\) 就是不能。

bool cmp(array<int,3>a,array<int,3>b){
    if(a[0]==b[0]) return a[1]>b[1];
    return a[0]<b[0];
}
void solve(){
    int n=read(),m=read();
    vector<array<int,3> >a(n);
    for(int i=0;i<n;i++){
        a[i]=(array<int,3>){read(),read(),i};
    }
    sort(a.begin(),a.end(),cmp);
    int l=0,ok=0;
    vector<int>ans;
    for(int i=0,j=1;i<n;i++){
        if(a[i][0]>j||i==n-1){
            if(i==n-1&&a[i][0]<=j)i++;
            int  maxr=-1,re=-1;
            for(int k=l;k<i;k++){
                maxr=max(maxr,a[k][1]);
                if(maxr==a[k][1])re=a[k][2];
            }
            l=i;
            j=maxr+1;
            if(re==-1){
                ok=0;
                break;
            }
            ans.push_back(re);
            if(maxr>=m){
                ok=1;
                break;
            }
            i--;
        }
    }
    cout<<'\n';
    if(ok){
        cout<<"YES\n";
        cout<<ans.size()<<"\n";
        for(auto x:ans){
            cout<<x+1<<" ";
        }
    }else{
        cout<<"NO\n";
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(Problem F. Friendly Fire\)

\(Problem G. Akinator\)

\(Problem H. Missing Number\)

每轮选择每个数的同一位，由最后位向前。由于奇偶性每次选择都可以知道 \(Missing Number\) 当前位是否缺少。每次选择的数字个数分别变成了 \(n\) ， \(\frac{1}{2} n\) ， $\frac{1}{4}n $， \(\ldots\) ，$\frac{1}{2^n}n $ 个

int ask(int x,int y){
    cout<<"? "<<x<<" "<<y<<endl;
    int res;
    cin>>res;
    return res;
}
void solve(){
    int n=read();
    set<int>st;
    for(int i=1;i<=n;i++){
        st.insert(i);
    }
    int res=0,ans=0,b=0;
    for(int i=0;st.size()>=1;i++){
        int m=st.size();
        b=0;
        set<int>tmp;
        for(auto x:st){
            int res=ask(x,i);
            if(res){
                tmp.insert(x);
                b++;
            }
        }
        if(b<(m+1)/2){
            ans+=(1<<i);
            st=tmp;
        }else{
            for(auto x:tmp){
                st.erase(x);
            }
        }
    }
    cout<<"! "<<ans<<endl;
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(Problem I. Painting a Square\)

最优解是螺旋拖动正方形。不过计算很麻烦，要研究一下。

void solve(){
    int n=read(),m=read(),ans=-m;
    while(n>0){
        if(n<=m){
            ans+=n;
            break;
        }else if(n<=m*2){
            ans+=(n-m)*3+m;
            break;
        }else {
            ans+=(n-m)*4;
            n-=m*2;
        }
    }
    cout<<ans;
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(Problem J. The Power of the Dark Side - 2\)

显然是一个人的最小的两个值小于自己的能力值和 \(-2\) ，就可以打败他。那只要记录每个人的最小的两个值，然后排序后二分查找几个数比自己的能力值和 \(-2\) ，注意清掉自己的影响。

void solve(){
    int n=read();
    vector<array<int,3> >a(n);
    vector<int>ruo(n),stg(n);
    for(int i=0;i<n;i++){
        a[i][0]=read(),a[i][1]=read(),a[i][2]=read();
        sort(a[i].begin(),a[i].end());
        ruo[i]=a[i][1]+a[i][0];
        stg[i]=ruo[i]+a[i][2];
    }
    sort(ruo.begin(),ruo.end());
    for(int i=0;i<n;i++){
        int p = upper_bound(ruo.begin(),ruo.end(),stg[i]-2)-ruo.begin();
        if(a[i][0]+a[i][1]<=stg[i]-2)p--;
        cout<<p<<' ';
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(Problem K. Deck Sorting\)

遍历所有的组合，然后对于要分成的两堆的那个牌，只要碰到这种牌，一定要满足一种牌一张没有活着一种牌放完了。

string s;
map<char,int>mp;
bool check(string tmp){
    tmp=' '+tmp;
    map<char,int>now;
    for(int i=0;i<s.size();i++){
        if(s[i]==tmp[2]){
            if(now[tmp[1]]==0||now[tmp[3]]==mp[tmp[3]]){}
            else return false;
        }
        now[s[i]]++;
    }
    return true;
}
void solve(){
    cin>>s;
    for(auto x:s){
        mp[x]++;
    }
    reverse(s.begin(),s.end());
    puts(check("RBG")||check("RGB")||check("GRB")||check("GBR")||check("BGR")||check("BRG")?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(Problem L. Inscribed Circle\)

这个圆很显然，半径很好算。然后对圆点用相似三角形的比例计算出来。

double dis(double a,double b,double c,double d){
    return sqrt((c-a)*(c-a)+(d-b)*(d-b));
}
void solve(){
    double x,y,z,a,b,c;
    cin>>x>>y>>z>>a>>b>>c;
    double dx=x-a,dy=b-y;
    double ddis=dis(x,y,a,b);
    double ansr=(c+z-ddis)/2;
    double ansx=a-(a-x)/ddis*(ddis-z+ansr);
    double ansy=b-(b-y)/ddis*(ddis-z+ansr);
    printf("%.15lf %.15lf %.15lf",ansx,ansy,ansr);
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(Problem M. Shlakoblock is live!\)

先把游戏按照 \(pi\) 从大到小排序，按需枚举选择的游戏个数，选择最大值。

bool cmp(array<int,3> a,array<int,3> b){
    if(a[0]==b[0])return a[1]>b[1];
    return a[0]>b[0];
}
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
void solve(){
    int n=read();
    vector<array<int,3> >a(n);
    for(int i=0;i<n;i++){
        a.push_back((array<int,3>){read(),read(),i});
    }
    sort(a.begin(),a.end(),cmp);
    int fenzi=0,fenmu=0;
    for(int i=0;i<n;i++){
        fenzi+=a[i][0]*a[i][1];
        fenmu+=a[i][1];
    }
    int ansx=fenzi,ansy=fenmu;
    vector<int>ans,record;
    for(int i=0;i<n;i++){
        fenzi+=a[i][0];
        fenmu++;
        record.push_back(a[i][2]);
        if(1.0*fenzi/fenmu>1.0*ansx/ansy){
            ansx=fenzi;
            ansy=fenmu;
            ans=record;
        }
        
    }
    int g=gcd(ansx,ansy);
    ansx/=g;
    ansy/=g;
    cout<<ansx<<"/"<<ansy<<'\n';
    cout<<ans.size()<<'\n';
    for(auto x:ans){
        cout<<x+1<<" ";
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}