AtCoder Beginner Contest 296
D
题意
给出n和m,问\(1\leq i,j\leq n\),使得\(ij\geq m\),求出这个乘积的最小值
思路
这两个乘数至少有一个在\([1,\sqrt{m}]\),枚举
代码
void solve()
{
cin>>n>>m;
int x=sqrt(m);
if(n>=m) {cout<<m<<endl;return;}
if(x*x==m)
{
if(n<x) cout<<-1<<endl;
else cout<<m<<endl;
return;
}
else if(n<=x) {cout<<-1<<endl;return;}
int mn=1e18;
for(int i=1;i<=(x+1);i++)
{
int k = (m+i-1)/i;
if(k<=n&&k*i>=m) mn=min(mn,k*i);
}
cout<<mn<<endl;
}
E
题意
这题抽象出来就是给出一个图,第i轮在对方可能让你走任意步数K时,你是否能选择一个能走到终点i且距离终点i为K的点。
思路
很显然,假设当前为第i轮,若在图中i不是环内点,那对方可能来个很大的步数让你无法获胜。若是环内点,则对方选任意步数你都能通过选择另一个环内点调整距离。
代码
void solve()
{
cin>>n;
vector<vector<int>> g(n+1);
for(int i=1;i<=n;i++)
{
cin>>a[i];
g[i].push_back(a[i]);
in[a[i]]++;
}
queue<int> q;
for(int i=1;i<=n;i++) if(!in[i]) q.push(i);
while(q.size())
{
int x=q.front();
q.pop();
vis[x]=1;//区分环内外的点
for(auto to : g[x])
{
if((--in[to])==0)
{
q.push(to);
}
}
}
int ans=0;
for(int i=1;i<=n;i++) if(!vis[i]) ans++;
cout<<ans<<endl;
}
F
题意
选择三个数\(i,j,k\),然后交换\(a[i],a[j]\),交换\(b[i],b[k]\),问能否通过这样的操作让数组a和数组b完全相同。
思路
首先如果两个数组包含的元素不同就失败。
包含元素相同,则可通过两次操作,在不改变a的情况下,改变b数组中任意三个数的位置,让他们循环左移一次。
交换后b数组的逆序对奇偶性不变,这样判断a数组的奇偶性和b数组的奇偶性是否相同即可。
还有一种特殊情况,如果有元素相同,则可通过只用两个相同元素来调整其他元素的位置,一定成功。
代码
int tr[N*2];
int a[N],b[N],cnt1[N],cnt2[N];
void add(int x,int k)
{
while(x<=n)
{
tr[x]+=k;
x+=(x&-x);
}
}
int sum(int x)
{
int res=0;
while(x) res+=tr[x],x-=x&-x;
return res;
}
void solve()
{
cin>>n;
int flag=0;
for(int i=1;i<=n;i++) cin>>a[i],cnt1[a[i]]++;
for(int i=1;i<=n;i++) cin>>b[i],cnt2[b[i]]++;
for(int i=1;i<=n;i++)
{
if(cnt1[i]!=cnt2[i]) {cout<<"No\n";return;}
if(cnt1[i]>1||cnt2[i]>1) flag=1;
}
if(flag==1) {cout<<"Yes\n";return;}
int ans1=0,ans2=0;
for(int i=n;i>=1;i--)
{
ans1+=sum(a[i]-1);
add(a[i],1);
}
memset(tr,0,sizeof(tr));
for(int i=n;i>=1;i--)
{
ans1+=sum(b[i]-1);
add(b[i],1);
}
if((ans1+ans2)%2==0) {cout<<"Yes\n";}
else cout<<"No\n";
}
- Beginner AtCoder Contest 296beginner atcoder contest 296 contest programming beginner atcoder beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310 beginner atcoder contest 315