A

Showstopper

题意：给你两个长度为n的数组a和b，每次操作你可以互换a[i]与b[i]，问最终能否满足

思路：若a[i]>b[i]，我们就进行操作。这样数组b元素都是较大的，一定比不操作更优。最后判断是否满足条件即可。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
int a[N],b[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];if(a[n]>b[n]) swap(a[n],b[n]);for(int i=1;i<=n;i++)if(a[i]>b[i])swap(a[i],b[i]);bool f=1;for(int i=1;i<=n;i++){if(a[i]>a[n]||b[i]>b[n]) {f=0;break;}} if(f) cout<<"Yes\n";else cout<<"No\n";
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

B

Three Sevens

题意：有m轮抽奖活动，中奖者无法参与后续抽奖。告诉你每轮来抽奖的人，问能否找到合法的每轮的获奖者。

思路：若某人在后续不再出现，那么他就可以是获奖者。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int m;
int ans[N];
void solve()
{cin>>m;vector<int>a[m];map<int,int>cnt;for(int i=0;i<m;i++){int n;cin>>n;for(int j=1;j<=n;j++){int x;cin>>x;a[i].push_back(x);cnt[x]++;}}for(int i=0;i<m;i++) ans[i]=-1;for(int i=0;i<m;i++){for(auto j:a[i]){cnt[j]--;if(cnt[j]==0) ans[i]=j;}}for(int i=0;i<m;i++)if(ans[i]==-1){cout<<-1<<'\n';return ;}for(int i=0;i<m;i++)cout<<ans[i]<<" \n"[i==m-1];
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

C

Candy Store

题意：有n种糖果，每种糖果的数量和单价分别是a[i]和b[i]。现在将他们打包，每包只能是同一种类的糖果，且每种糖果不能有剩余。现在给每种包标价，连续相同价格的包裹可以使用同一个标签，问最少需要多少个标签。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
ll n;
ll a[N],b[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i]>>b[i];ll g=a[1]*b[1];ll l=b[1];ll ans=1;for(int i=2;i<=n;i++){g=gcd(g,a[i]*b[i]);l=lcm(l,b[i]);if(g%l!=0) {ans++;g=a[i]*b[i];l=b[i];}}cout<<ans<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

D

Shocking Arrangement

题意：给定序列a，满足序列a的和为0.重排序a，满足

思路：全0是无解的。我们可以把正负数分到两个集合中，如果当前和为正那么就填负数，和为负就填正数。每次都填绝对值最大的数。

这样做所有的前缀和无论正负都不会超过正数和负数的最大值，而所有的子段和都是两个前缀和的差。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
#define int long long
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
void solve()
{vector<int>v[2];cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;if(x>=0) v[0].push_back(x);else v[1].push_back(x);}if(v[1].size()==0){cout<<"No\n";return ;}sort(v[0].begin(),v[0].end());sort(v[1].begin(),v[1].end(),greater<int>());vector<int>ans;int sum=0;for(int i=0;i<n;i++){if(sum>=0&&v[1].size()){ans.push_back(v[1].back());v[1].pop_back();}else{ans.push_back(v[0].back());v[0].pop_back();}sum+=ans.back();}cout<<"Yes\n";for(int i=0;i<n;i++)cout<<ans[i]<<" \n"[i==n-1];
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}