首页 > 其他分享 >2019, XII Samara Regional Intercollegiate Programming Contest

2019, XII Samara Regional Intercollegiate Programming Contest

时间:2023-09-20 23:56:08浏览次数:40  
标签:Contest int XII Regional No read ans Problem Yes

\(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");
}

标签:Contest,int,XII,Regional,No,read,ans,Problem,Yes
From: https://www.cnblogs.com/edgrass/p/17718867.html

相关文章

  • AtCoder Grand Contest 017
    链接C.SnukeandSpells容易发现合法序列排序后一定是若干段值域连续的部分组成:可以发现最小次数就是重叠/空出的部分大小。每次修改只会对\(O(1)\)个点\(±1\),直接维护即可。#include<iostream>#include<cstdio>#include<cstring>#include<vector>#defineN200010......
  • The 2023 ICPC Asia Regionals Online Contest (1)
    Preface这场打的还行,因为学长们都没发挥好被我们队偷了,但感觉发挥的也一般前期开题顺序有点问题导致罚时很高,不过中期写题还是很顺的基本都是一遍过只不过在3h的时候过完F到达8题后就开始坐牢了,虽然这场有两个字符串但徐神把H想复杂了,B可以说前面的建SAM和反串的AC自动机都想到......
  • AtCoder Grand Contest 023 E Inversions
    洛谷传送门AtCoder传送门首先将\(a\)从小到大排序,设\(p_i\)为排序后的\(a_i\)位于原序列第\(p_i\)个位置,\(x_i\)为要填的排列的第\(i\)个数。设\(A=\prod\limits_{i=1}^n(a_i-i+1)\),则\(A\)为排列的总方案数(考虑按\(a_i\)从小到大填即得)。套路地,统......
  • 2018-2019 ACM-ICPC Brazil Subregional Programming Contest
    \(B.Marbles\)如果是\(Nim\)博弈,题目应该改成到转移所有石子。显然要转化到将所有石子转移到\((1,2)\)或者\((2,1)\),特判无需到达这两个点的必败态,对其他点使用\(Nim\)博弈判断胜负态。intsg[N][N],vis[N];voidinit(){for(inti=1;i<=100;i++){for(in......
  • Atcoder Regular Contest 165(A~E)
    赛时45min切A~C,降智不会D,罚坐1h,喜提rk70+->rk170+。A-SumequalsLCM可证明结论:若\(N\)只含有一种质因子则无解,否则有解。B-SlidingWindowSort2这么多cornercase的题竟然10min一发入魂,类目了。由于操作是升序排序,且要求最终字典序最大,所以如果存在一个......
  • AtCoder Beginner Contest 320
    A-LeylandNumbera,b=map(int,input().split(''))print(a**b+b**a)B-LongestPalindromes=input()n=len(s)res=0forlinrange(1,n+1):foriinrange(0,n-l):t=q=s[i:i+l]t=t+t[::-1]......
  • The 2023 ICPC Asia Regionals Online Contest (1) ADI
    The2023ICPCAsiaRegionalsOnlineContest(1)AQualifiersRankingRules思路:按位次为第一关键字,场次为第二关键字排序即可。//AConemoretimes//nndbk#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmod=1e9+7;constintN......
  • 2018-2019 ACM-ICPC Brazil Subregional Programming Contest
    B.Marbles题解显然如果存在棋子位于\((x,x)\),那么一定先手必胜容易发现必败态位于\((1,2)\)和\((2,1)\),那么我们可以通过\(sg\)函数暴力打表得到并且玩家一定不会将棋子移动至\((0,i),(i,0),(i,i)\)这三种情况上,因为谁移动到这些位置,对手一定处于必胜态intn,f[N][......
  • 2020-2021 ACM-ICPC Brazil Subregional Programming Contest
    A.StickerAlbum你想要得到\(n\)张贴纸,每包礼物中等概率出现\([A,B]\)范围内数量的贴纸,求需要买多少包礼物才能至少获得\(n\)张贴纸的期望次数\(1\leqn\leq10^6,0\leqA,B\leq10^6\)题解:期望DP我们考虑从后往前进行\(dp\)设计状态为\(dp[i]\)代表手上有\(i\)张......
  • 2022 International Collegiate Programming Contest, Jinan Site MKAEDGC
    2022InternationalCollegiateProgrammingContest,JinanSite目录2022InternationalCollegiateProgrammingContest,JinanSiteVP概况M-BestCarryPlayerK-StackSortA-TowerE-IdenticalParityD-FrozenScoreboardG-QuickSortC-DFSOrder2VP概况没......