Codeforces Round #563 Div. 2
2024-08-26 13:19:32
A：显然排序即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 1010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,a[N<<1];
signed main()
{
n=read();
for (int i=1;i<=2*n;i++ )a[i]=read();
sort(a+1,a+2*n+1);int s=0;
for (int i=1;i<=n;i++) s+=a[i];
int s2=0;for (int i=n+1;i<=2*n;i++) s2+=a[i];
if (s!=s2) {for (int i=1;i<=2*n;i++) cout<<a[i]<<' ';}
else cout<<-1;
return 0;
//NOTICE LONG LONG!!!!!
}
B：若奇偶数均存在就可以任意交换，sort即可。否则无法改变。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,a[N];
signed main()
{
n=read();
for (int i=1;i<=n;i++) a[i]=read();
int s=0,s2=0;
for (int i=1;i<=n;i++) if (a[i]&1) s++;else s2++;
if (s&&s2) sort(a+1,a+n+1);
for (int i=1;i<=n;i++) printf("%d ",a[i]);
return 0;
//NOTICE LONG LONG!!!!!
}
C：质数下标之间需要两两不同，于是最大值就是<=n的质数个数。对于合数，将其设为其最小质因子对应的数即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,a[N];
bool isprime(int x)
{
for (int i=2;i*i<=x;i++) if (x%i==0) return 0;
return 1;
}
signed main()
{
n=read();
int mx=0;
for (int i=2;i<=n;i++)
if (isprime(i)) a[i]=++mx;
else
{
for (int j=2;j*j<=i;j++) if (i%j==0) {a[i]=a[j];break;}
}
for (int i=2;i<=n;i++) printf("%d ",a[i]);
return 0;
//NOTICE LONG LONG!!!!!
}
D：如果m>=2n即没有限制，使序列前缀和依次为0,1,2……即可。否则这些数中有一半不能选择，做法类似。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 18
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,m,a[1<<N],cnt;
signed main()
{
n=read(),m=read();
if (m>=(1<<n))
{
cout<<(1<<n)-1<<endl;
for (int i=1;i<(1<<n);i++) printf("%d ",i^(i-1));
}
else
{
for (int i=1;i<(1<<n);i++) if (i<(i^m)) a[++cnt]=i;
cout<<(1<<n-1)-1<<endl;
for (int i=1;i<=(1<<n-1)-1;i++) printf("%d ",a[i]^a[i-1]);
}
return 0;
//NOTICE LONG LONG!!!!!
}
E：容易发现前缀gcd最大变化次数就是<=n的数所拥有的最大质因子个数。显然形如2k的数满足条件。同时3*2k-1也可能满足条件。对于前者， 设c[i]=[n/2i]-[n/2i+1]，也即恰有i个2的数的个数，那么合法排列方案数的计算类似于CTS2019随机立方体https://www.cnblogs.com/Gloid/p/10936699.html中的一个子问题，不再赘述。后者的话考虑一下3这个因子在还剩多少个2时被删去，类似地计算。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 1000010
#define P 1000000007
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,ans,a[30],fac[N],inv[N],b[2][30];
int C(int n,int m){if (m>n) return 0;return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;}
void inc(int &x,int y){x+=y;if (x>=P) x-=P;}
signed main()
{
n=read();
fac[0]=1;for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%P;
inv[0]=inv[1]=1;for (int i=2;i<=n;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;
for (int i=2;i<=n;i++) inv[i]=1ll*inv[i]*inv[i-1]%P;
int m=0,tmp=n;while (tmp) m++,tmp>>=1;
m--;
if ((3<<m-1)<=n)
{
for (int i=1;i<=n;i++)
{
int x=0,y=i;
while (y%2==0) y>>=1,x++;
if (i%3==0) b[1][min(x,m-1)]++;
else b[0][min(x,m-1)]++;
}
for (int i=m-1;i>=0;i--)
{
int s=1,u=n;
for (int j=m-1;j>=i;j--)
{
s=1ll*s*C(u-1,b[1][j]-1)%P*fac[b[1][j]]%P;
u-=b[1][j];
}
int tot=0;for (int j=m-1;j>=i;j--) tot+=b[0][j];
s=1ll*s*C(u-1,tot-1)%P*fac[tot]%P;
u-=tot;
for (int j=i-1;j>=0;j--)
{
s=1ll*s*C(u-1,b[0][j]+b[1][j]-1)%P*fac[b[0][j]+b[1][j]]%P;
u-=b[0][j]+b[1][j];
}
inc(ans,s);
}
}
memset(a,0,sizeof(a));
for (int i=1;i<=n;i++)
{
int x=0,y=i;
while (y%2==0) y>>=1,x++;
a[x]++;
}
int s=1,u=n;
for (int i=m;i>=0;i--)
{
s=1ll*s*C(u-1,a[i]-1)%P*fac[a[i]]%P;
u-=a[i];
}
inc(ans,s);
cout<<ans;
return 0;
//NOTICE LONG LONG!!!!!
}
F：点分治，问出当前点深度就可以知道其是不是隐藏点的祖先。如果不是就在该点父亲所在子树中继续寻找，否则问出到隐藏点路径上的第二个点到对应子树中寻找。发现离隐藏点距离为0时就找到了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,p[N],t,d,fa[N],deep[N],size[N];
bool flag[N];
struct data{int to,nxt;
}edge[N<<1];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
void dfs(int k)
{
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=fa[k])
{
deep[edge[i].to]=deep[k]+1;
fa[edge[i].to]=k;
dfs(edge[i].to);
}
}
void make(int k,int from)
{
size[k]=1;
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=from&&!flag[edge[i].to])
{
make(edge[i].to,k);
size[k]+=size[edge[i].to];
}
}
int findroot(int k,int from,int s)
{
int mx=0;
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=from&&!flag[edge[i].to]&&size[edge[i].to]>size[mx]) mx=edge[i].to;
if ((size[mx]<<1)>s) return findroot(mx,k,s);
else return k;
}
int getd(int x){cout<<"d "<<x<<endl;return read();}
int gets(int x){cout<<"s "<<x<<endl;return read();}
int solve(int k)
{
make(k,k);flag[k=findroot(k,k,size[k])]=1;
int u=getd(k);if (u==0) return k;
if (deep[k]+u==d) return solve(gets(k));
else return solve(fa[k]);
}
int main()
{
n=read();
for (int i=1;i<n;i++)
{
int x=read(),y=read();
addedge(x,y),addedge(y,x);
}
dfs(1);
d=getd(1);
cout<<"! "<<solve(1);
return 0;
}
小小小号。result：rank 18 rating +163
最新文章
- 数据结构：单链表结构字符串（python版）改进
- winform 可拖动的自定义Label控件
- cocos2d之json使用实例
- 检测端口状态的python脚本
- AFNetworking框架使用
- MySQL－ InnoDB锁机制
- Werkzeug源码阅读笔记(三)
- 关闭Outlook的时候使之最小化
- [SQL基础教程] 1-5 表的删除和更新
- 《JavaScript高级程序设计》读书笔记 ---基本类型和引用类型的值
- dip2px
- 如何在Eclipse中配置python开发环境
- python爬虫第一天
- C#解析HTML利器-Html Agility Pack
- libraries\include\boost-1_61\boost/regex/v4/perl_matcher.hpp(362): error C2292: 'boost::re_detail_106100::perl_matcher<const char *,std::allocator<boost::sub_match<const char *>>,boost::regex_traits<c
- 18-11-05ie 热键的使用
- uvaLive7303 Aquarium （kruskal）
- 100-days: eighteen
- 002-打开文件管理规范-20190406.bat
- django时间的时区问题（转）