Codeforces Round 860 (Div. 2) A-D
本期封面原图 画师HMaX
C题这个数论确实没想出来，想到gcd但是没有往下推那么多，有点神奇的
A. Showstopper
思路
大的进b，小的放a，然后看最大的是不是在最后面就行
代码
#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
#define minOf(a) *min_element(a.begin(),a.end())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void solve()
{
int n;
scanf("%d",&n);
vector<int> a(n);
vector<int> b(n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<n;i++)
{
scanf("%d",&b[i]);
if(b[i]<a[i]) swap(a[i],b[i]);
}
int lsta=a[n-1],lstb=b[n-1];
sort(all(a));
sort(all(b));
if(a[n-1]!=lsta || b[n-1]!=lstb)
{
printf("No\n");
return;
}
printf("Yes\n");
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
B. Three Sevens
思路
从后往前扫，因为一般加肯定比删简单，然后谁没出现过就改答案就行
代码
#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
#define minOf(a) *min_element(a.begin(),a.end())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void solve()
{
int m;
scanf("%d",&m);
map<int,vector<int>> mv;
for(int i=1;i<=m;i++)
{
int n;
scanf("%d",&n);
for(int j=0;j<n;j++)
{
int x;
scanf("%d",&x);
mv[i].push_back(x);
}
}
map<int,int> cnt;
vector<int> ans(m+1,-1);
for(int i=m;i>=1;i--)
{
bool changed=false;
for(auto x:mv[i])
{
if(cnt[x]==0 and !changed)
{
ans[i]=x;
changed=true;
}
cnt[x]++;
}
}
for(int i=1;i<=m;i++)
{
if(ans[i]==-1)
{
printf("-1\n");
return;
}
}
for(int i=1;i<=m;i++)
{
printf("%d ",ans[i]);
}
printf("\n");
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
D. Shocking Arrangement
思路
首先小于的这个值是确定的，然后贪心摆就行，正数从大到小摆，如果摆了前面的子串和会超标的话就把负数从最小往最大插进去一下
代码
#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
#define minOf(a) *min_element(a.begin(),a.end())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void solve()
{
int n;
scanf("%d",&n);
vector<int> positive,negative;
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
if(x>=0) positive.push_back(x);
else negative.push_back(x);
}
if(negative.size()==0)
{
printf("No\n");
return ;
}
if(positive.size()==0)
{
for(int i=0;i<n;i++)
{
printf("%d ",negative[i]);
}
printf("\n");
return ;
}
sort(all(positive),greater<int>());
sort(all(negative));
ll goal=positive[0]-negative[0];
ll now=0;
vector<int> ans;
int p_idx=0,n_idx=0;
while(p_idx<positive.size() && n_idx<negative.size())
{
if(now+positive[p_idx]>=goal)
{
ans.push_back(negative[n_idx]);
now+=negative[n_idx];
now=max(now,0ll);
n_idx++;
}
else
{
ans.push_back(positive[p_idx]);
now+=positive[p_idx];
p_idx++;
}
}
if(p_idx<positive.size())
{
printf("No\n");
return;
}
printf("Yes\n");
while(n_idx<negative.size())
{
ans.push_back(negative[n_idx]);
n_idx++;
}
for(int i=0;i<n;i++)
{
printf("%d ",ans[i]);
}
printf("\n");
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
C. Candy Store
代码
参考这篇题解
#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
#define minOf(a) *min_element(a.begin(),a.end())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll lcm(ll a,ll b)
{
return a/__gcd(a,b)*b;
}
void solve()
{
int n;
scanf("%d",&n);
vector<ll> a(n),b(n);
for(int i=0;i<n;++i)
scanf("%lld%lld",&a[i],&b[i]);
int cnt=0;
for(int i=0;i<n;)
{
ll fx=b[i];
ll fy=a[i]*b[i];
int j;
for(j=i+1;j<n;++j)
{
fx=lcm(fx,b[j]);
fy=__gcd(fy,a[j]*b[j]);
if(fy%fx!=0)
{
i=j;
break;
}
}
cnt++;
if(j==n)
break;
}
printf("%d\n",cnt);
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
原文地址：https://blog.csdn.net/swan416/article/details/143952205
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！