A - Showstopper
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n,a[110],b[110];
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
scanf("%d",&b[i]);
bool fl=0;
for (int i=1;i<n;i++)
{
if (a[i]>a[n] || b[i]>b[n]) swap(a[i],b[i]);
if (a[i]>a[n] || b[i]>b[n])
{
fl=1;
break;
}
}
if (fl==0) printf("Yes\n");
else printf("No\n");
}
return 0;
}
B - Three Sevens
#include <bits/stdc++.h>
#define M 50010
using namespace std;
int t,m,n[M];
bool f[M];
int ans[M];
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
int main()
{
int t;
t=read();
vector <int> q[M];
while (t--)
{
int m;
m=read();
vector <int> cl;
for (int i=1;i<=m;i++)
{
q[i].clear();
n[i]=read();
for (int j=1;j<=n[i];j++)
{
int s;
s=read();
q[i].emplace_back(s);
}
}
bool fl=1;
for (int i=m;i>0;i--)
{
fl=0;
for (auto v:q[i])
{
if (f[v]==0)
{
fl=1;
f[v]=1;
cl.emplace_back(v);
ans[i]=v;
}
}
if (fl==0) break;
}
for (auto v:cl)
f[v]=0;
if (fl==0) printf("-1\n");
else
{
for (int i=1;i<=m;i++)
printf("%d ",ans[i]);
printf("\n");
}
}
return 0;
}
值得注意的是最开始我将 \(vector <int> q[M]\) 放在了循环里面，导致 TLE 了三发
C - Candy Store
从上至下贪心地选取。
正确性：因为在同一个价签中多选择一种糖果只会将结果变“劣”，即这个价签只有可能无法接受这种糖果。并且既然第一种糖果就要使用价签，那就可以充分利用这个价签，让这个价签向下继续选取，使得之后的价签需要承载的糖果种类变少，这样结果必然更优。
考虑如何维护这个贪心。
#include <bits/stdc++.h>
#define LL long long
#define N 200010
#define int long long
using namespace std;
LL n,t,a[N],b[N],g,ans;
signed main()
{
scanf("%lld", &t);
while (t--)
{
scanf("%lld", &n);
for (int i = 0; i < n; i++)
scanf("%lld %lld", &a[i], &b[i]);
g = a[0];
ans = 1;
for (int i = 1; i < n; i++)
{
LL lcm = b[i] / __gcd(b[i], b[i - 1]) * b[i - 1];
LL a1 = lcm / b[i - 1];
LL a2 = lcm / b[i];
if (g % a1 || a[i] % a2)
{
ans += 1;
g = a[i];
continue;
}
g = __gcd(g / a1, a[i] / a2);
b[i] *= a2;
}
printf("%lld\n", ans);
}
return 0;
}
D - Shocking Arrangement
可以构造时始终让前缀和是最大的子串，这样贪心地放就可以了。
#include <bits/stdc++.h>
#define N 300010
#define ll long long
using namespace std;
int t,n,a[N];
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
int l=1,r=n,del=a[n]-a[1];
ll pre=0;
bool fl=1;
vector <int> ans;
while (l<=r)
{
fl=0;
while (l<=r && pre+a[r]<del)
{
pre+=a[r];
ans.emplace_back(a[r]);
fl=1;
r--;
}
if (l<=r)
{
pre+=a[l];
if (pre<del)
{
ans.emplace_back(a[l]);
fl=1;
l++;
}
}
if (fl==0) break;
}
if (fl==0) printf("No\n");
else
{
printf("Yes\n");
for (auto v:ans)
printf("%d ",v);
printf("\n");
}
}
return 0;
}