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";
}
标签:AtCoder,cout,Beginner,int,奇偶性,数组,296,题意
From: https://www.cnblogs.com/LIang2003/p/17425400.html