【AtCoder】 ARC 103
linkC-////直接算会出现奇偶两组选了同一个数,注意处理一下就行 #include<bits/stdc++.h> #define ll long long #define dbg1(x) cerr<<#x<<"="<<(x)<<" " #define dbg2(x) cerr<<#x<<"="<<(x)<<"n" #define dbg3(x) cerr<<#x<<"n" using namespace std; #define reg register inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } const int MN=1e5+5; int n,a[MN],pre[MN],suf[MN],num[MN],nmp[MN]; int main() { n=read(); reg int i,mx=0,mxp=0,ans=n;bool fl=1;a[1]=read(); for(i=2;i<=n;++i) a[i]=read(),fl&=(a[i]==a[i-1]); for(i=1;i<=n;i+=2) ++num[a[i]]; for(i=1;i<=100000;++i) pre[i]=max(pre[i-1],num[i]); for(i=100000;i;--i) suf[i]=max(suf[i+1],num[i]); for(i=2;i<=n;i+=2) ++nmp[a[i]]; for(i=1;i<=100000;++i) ans=min(ans,n-nmp[i]-max(pre[i-1],suf[i+1])); if(fl) printf("%dn",n/2); else printf("%dn",ans); return 0; } D-Robot Arms在原点构造一个机械手臂,关节数(<40),末端可以到达给出的(n,nleq10^5)个点 发现方案存在当且仅当(X[i]+Y[i])奇偶性相同 考虑一个点((x,y)),如果(|x|+|y|leq 2^{k+1}),在这个点向外连一个(2^k)长度的机械手臂 一定存在一个方向,使得手臂的另一个端点((x_1,y_1))满足(|x_1|+|y_1|leq2^{k}) 所以我们只要构造一个数列(2^0,2^1,...,2^m),就可以了,如果(X[i]+Y[i])是个偶数,考虑加一个(1),然后当作原点在((1,0))上做就行 #include<bits/stdc++.h> #define ll long long #define dbg1(x) cerr<<#x<<"="<<(x)<<" " #define dbg2(x) cerr<<#x<<"="<<(x)<<"n" #define dbg3(x) cerr<<#x<<"n" using namespace std; #define int ll #define reg register inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } const int MN=10005; int N,X[MN],Y[MN]; int d[45],n; const int dx[4]={0,1,-1},dy[4]={1,-1,0}; const char dc[4]={'D','L','U','R'}; void get(int x,int y) { reg int i,j; for(i=n;~i;--i)for(j=0;j<4;++j) { int xx=x+dx[j]*d[i],yy=y+dy[j]*d[i]; if(abs(xx)+abs(yy)<d[i]){x=xx,y=yy;printf("%c",dc[j]);j=5;} } } signed main() { N=read(); reg int i,mx=0;bool fl=1; for(i=1;i<=N;++i) X[i]=read(),Y[i]=read(),fl&=(~(X[i]+Y[i]-X[1]-Y[1])&1),mx=max(mx,abs(X[i])+abs(Y[i])+2); if(!fl) return 0*puts("-1"); fl=~(X[1]+Y[1])&1; for(d[1]=n=1;(d[n]<<1)<mx;++n,d[n]=d[n-1]<<1); printf("%dn",n+fl); if(fl) printf("1 "); for(i=1;i<=n;++i) printf("%d ",d[n-i+1]);puts(""); for(i=1;i<=N;++i) { if(fl) printf("R"); get(X[i]-fl,Y[i]); puts(""); } return 0; } E-Tr/ee构造一棵树,满足若(s_i=1),则删除一条边后,可以得到大小(i)的联通块,否则没有 答案存在当且仅当(s_1=1,s_n=0,s_i=s_{n-i}) 从(1)开始枚举每个值,如果(s_i=1),新建一个根连上当前的树,并不断加叶子直到大小为(i) 处理到((n+1)/2)后,新加一个点,然后继续补叶子直到大小为(n) #include<bits/stdc++.h> #define ll long long #define dbg1(x) cerr<<#x<<"="<<(x)<<" " #define dbg2(x) cerr<<#x<<"="<<(x)<<"n" #define dbg3(x) cerr<<#x<<"n" using namespace std; #define reg register const int MN=1e5+5; char s[MN]; int n,rt;bool a[MN]; int main() { scanf("%s",s+1);n=strlen(s+1); reg int i; for(i=1;i<=n;++i) a[i]=(s[i]=='1'); if(!a[1]||a[n]) return 0*puts("-1"); for(i=1;i<=n-1;++i) if(a[i]!=a[n-i]) return 0*puts("-1"); for(rt=1,i=2;i<=(n+1)/2;++i)if(a[i]) { printf("%d %dn",i,rt); for(int j=rt+1;j<i;++j) printf("%d %dn",j); rt=i; } printf("%d %dn",rt+1,rt);++rt; for(i=rt+1;i<=n;++i) printf("%d %dn",rt,i); return 0; } F-Distance Sums构造一棵树,满足(D_i)为其它点到(i)的距离的和 发现如果以(D_i)最小的做根,每个点的孩子的(D_i)必定比它大,(D_i)最大一定是叶子 (D_{fa}=D_x+2times siz_x-N) 可以把(D_i)从大到小排序,对每个点找个父亲(满足父亲的(D)值比它小)。 如果可以顺利完成这一步,并不一定是合法的方案,因为只满足了所有非根节点与父亲之间的(D)的关系 只要在(dfs)算一下根节点的(D_{root})是否满足就可以了 (D)数组要开long long #include<bits/stdc++.h> #define ll long long #define dbg1(x) cerr<<#x<<"="<<(x)<<" " #define dbg2(x) cerr<<#x<<"="<<(x)<<"n" #define dbg3(x) cerr<<#x<<"n" using namespace std; #define se second #define fi first #define reg register #define mp make_pair inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } const int MN=1e5+5; ll N,D[MN],siz[MN],fa[MN]; struct edge{int to,nex;}e[MN<<1];int hr[MN],en; void ins(int x,int y){e[++en]=(edge){y,hr[x]};hr[x]=en;} pair<ll,int> a[MN]; ll dfs(int x) { reg int i;ll r=0; for(i=hr[x];i;i=e[i].nex) r+=dfs(e[i].to)+siz[e[i].to]; return r; } int main() { N=read();reg int i,j; for(i=1;i<=N;++i) D[i]=read(),a[i]=mp(D[i],i); std::sort(a+1,a+N+1); for(i=N;i>1;--i) { int x=a[i].se; ++siz[x]; int pos=lower_bound(a+1,a+N+1,mp(D[x]+2*siz[x]-N,0))-a; if(pos>=i||D[x]+2*siz[x]-N!=a[pos].fi) return 0*puts("-1"); fa[x]=a[pos].se;siz[fa[x]]+=siz[x];ins(fa[x],x); } ++siz[a[1].se]; if(dfs(a[1].se)!=D[a[1].se]) return 0*puts("-1"); for(i=1;i<=N;++i)for(j=hr[i];j;j=e[j].nex)printf("%d %dn",e[j].to); return 0; } Blog来自PaperCloud,未经允许,请勿转载,TKS! (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- ruby-on-rails – Rails ActiveRecord:跳过关联的验证
- c#-3.0 – 将日期转换为“dd-MMM-yyyy”格式c#
- Flex学习笔记15——module 模块
- 在Swift中解析json,AnyObject类型
- 使用create-react-app+react-router-dom+axios+antd+react-
- c – 函数重载时的Typedef编译错误
- c#HTTP POST – 需要跟踪发布/上传进度
- 如何从Flash AS3中的URL获取/获取变量
- ruby-on-rails – Rails:获取特定数量的随机记录
- oracle:创建job时提示“ORA-01008 并非所有变量都已关联,”