Preface
两三天没写题了小小的补一下题
结果这场意外地很合胃口，1h不到就把A-E做完了，而且除了忘记初始化这种一眼丁真的错误好像也没写挂
可惜当时懒了周日晚上就不打了（主要去考模拟六级了回来太累了），不然狠狠地上分
A. Showstopper
稍加观察就可以发现我们令所有的\(a_i\)均小于等于\(b_i\)再验证即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n,a[N],b[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=n;++i) if (scanf("%d",&b[i]),a[i]>b[i]) swap(a[i],b[i]);
bool flag=1; for (i=1;i<n&&flag;++i) if (a[i]>a[n]) flag=0;
for (i=1;i<n&&flag;++i) if (b[i]>b[n]) flag=0;
puts(flag?"Yes":"No");
}
return 0;
}
B. Three Sevens
一眼倒着做，每次随便找一个在之后没出现过的数并指定它为胜者即可
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=50005;
int t,n,len[N],ans[N]; vector <int> v[N]; bool vis[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
for (scanf("%d",&len[i]),v[i].resize(len[i]),j=0;j<len[i];++j)
scanf("%d",&v[i][j]),vis[v[i][j]]=0;
int pos=-1; for (i=n;i;--i)
{
pos=-1; for (int x:v[i]) if (!vis[x]) pos=x;
if (!~pos) { puts("-1"); break; }
ans[i]=pos; for (int x:v[i]) vis[x]=1;
}
if (~pos) for (i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
}
return 0;
}
C. Candy Store
刚开始naive了想了一种合并糖果的方法，然后WA了一发后猛然悔悟
首先不难发现问题具有贪心性，对于固定的左端点，我们肯定是尽量地向右延伸区间
那么考虑如何验证一个区间\([l,r]\)是否合法，不难发现设最后标价\(C\)至少是\(lcm_{l\le i\le r} b_i\)的倍数
同时若假设我们令\(l=lcm_{l\le i\le r} b_i\)，则对于\(\forall i\in[l,r]\)，均要满足\(\frac{l}{b_i}|a_i\)，不难发现这等价于\(l|(a_i\times b_i)\)
然后就很trivial了，我们再记一个\(g=\gcd_\limits{l\le i\le r} (a_i\times b_i)\)，然后只要看\(l\)是否为\(g\)的因子即可
#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,a[N],b[N];
inline int gcd(CI n,CI m)
{
return m?gcd(m,n%m):n;
}
inline int lcm(CI n,CI m)
{
return n/gcd(n,m)*m;
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld%lld",&a[i],&b[i]);
int g=0,l=1,ans=1; for (i=1;i<=n;++i)
{
l=lcm(l,b[i]); g=gcd(g,a[i]*b[i]);
if (g%l) ++ans,l=b[i],g=a[i]*b[i];
}
printf("%lld\n",ans);
}
}
D. Shocking Arrangement
简单构造题，触发被动——构造题精通
首先不难发现右边是个定值，记这个极差为\(M\)，然后看到\(\sum_{i=1}^n a_i=0\)这个限制，第一反应就是根据之前做过的某个构造题的结论，一定可以构造一个序列使得其前缀和数组的值始终大于\(0\)
再接着考虑一段子段和其实就是两个前缀和的差值，因此我们很容易想到只要让前缀和始终小于极差即可
具体的构造过程如下，我们先把正数和负数分别按绝对值从大到小排个序，然后每次加入一个还未处理的最大的正数
若此时整个序列的前缀和大于等于极差，则一直往里面放还未处理的最小的负数，只要其小于极差或者说明无解
这个做法的正确性显然，因为前缀和中最大值不可能超过极差，同时这般构造出的数列的前缀和一定都是大于等于\(0\)的
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005,INF=1e9;
int t,n,x,pos[N],neg[N],ans[N],cp,cn,lim,mi,mx;
inline bool cmp(CI x,CI y)
{
return x>y;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j,cnt; for (scanf("%d",&n),mi=INF,mx=-INF,cp=cn=0,i=1;i<=n;++i)
{
scanf("%d",&x); mi=min(mi,x); mx=max(mx,x);
if (x>=0) pos[++cp]=x; else neg[++cn]=x;
}
sort(pos+1,pos+cp+1,cmp); sort(neg+1,neg+cn+1);
long long ret=0; for (lim=mx-mi,i=j=1,cnt=0;i<=cp;++i)
{
if ((ret+=pos[i])>=lim)
{
while (j<=cn&&ret>=lim) ans[++cnt]=neg[j],ret+=neg[j++];
if (ret>=lim) { cnt=-1; break; }
}
ans[++cnt]=pos[i];
}
while (j<=cn) ans[++cnt]=neg[j++];
if (!~cnt) puts("No"); else for (puts("Yes"),i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
}
return 0;
}
E. Multitest Generator
首先不难发现答案肯定只有\(\{0,1,2\}\)，因为我们只要把第一个数改成\(1\)然后把第二个数改成对应的长度就肯定可以构造出一个答案为\(2\)的解
同时答案为\(0\)的情况是很trivial的，那么现在问题就是如何判断\(a_i\sim a_n\)的答案是否为\(1\)，大致可以分为两类：
- 修改第一个数\(a_i\)，此时需要满足\(a_{i+1}\sim a_n\)为连续的若干个
test - 修改\([i+1,n]\)中的某个数\(j\)使得\(a_j=k\)，其实需要满足\(a_{i+1}\sim a_{j-1}\)为若干个（设为\(x\)个）
test，且\(a_{j+k+1}\sim a_n\)为若干个（设为\(y\)个）test，且要求\(x+y\ge a_i-1\)
然后考虑如何实现，很容易想到用倒着用DP来维护：
- 令\(g_i\)表示某段后缀可以是否为若干个连续的
test，若是则记录个数 - 令\(mg_i\)表示\(g_i\)的后缀最大值，即\(mg_i=\max_\limits{i\le j\le n} g_j\)
- 令\(f_i\)表示以\(i\)开头，向后跳最多能得到多少个
test（注意与\(g_i\)的细微差别） - 令\(mx_i\)表示以\(i\)开头，在向后跳了若干个
test（设为\(x\)个）来到位置\(k\)后，\(x+mx_{k+1}\)的最大值
其它的都很容易理解，就是这个\(mx_i\)的定义看起来比较抽象，其实想一想很好理解
我们在计算上面的第二个条件时，所有的方案都可以被归结为两类，一类是从最后往前然后修改前面一部分的，一类是从前往后然后修改中间一部分的
而如果只用\(mg_i\)的话就会遗漏掉修改中间某段的部分，因此需要定义这样一个奇怪的东西
不过一码归一码这些东西的转移都非常简单，看一下代码就一眼便知了的说
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005,INF=1e9;
int t,n,a[N],g[N],mg[N],f[N],mx[N],ans[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i)
scanf("%d",&a[i]),g[i]=-1,f[i]=mg[i]=mx[i]=0;
for (g[n+1]=f[n+1]=mg[n+1]=mx[n+1]=0,i=n;i;--i)
{
int t=i+a[i]+1; if (t<=n+1&&~g[t]) g[i]=g[t]+1;
mg[i]=max(mg[i+1],g[i]); if (t<=n+1) f[i]=f[t]+1;
if (t<=n+1) mx[i]=max(mx[t]+1,mg[t]+1);
if (i==n) continue;
if (~g[i+1]&&g[i+1]==a[i]) ans[i]=0; else
if (~g[i+1]&&g[i+1]!=a[i]) ans[i]=1; else
if (a[i]&&max(mg[i+1],mx[i+1])>=a[i]-1) ans[i]=1; else ans[i]=2;
}
for (i=1;i<n;++i) printf("%d%c",ans[i]," \n"[i==n-1]);
}
return 0;
}
E. Multitest Generator
其实看到题之后大概隐隐能猜到利用贪心的思想先做小的，但不知道正确性就不敢写
然后去看了Tutorial才发现要用一个叫Erdős–Ginzburg–Ziv theorem的东西，算是涨知识了
这个定理的大概意思就是对于任意正整数\(n\)，我们总可以在任意的\(2n-1\)个正整数中找出\(n\)个时的它们的和是\(n\)的倍数
大致思路就是先证对于所有\(n\)为质数的情况，在证若\(n=p_1\and n=p_2\)时成立，则对于\(n=p_1\times p_2\)亦成立，具体证明这里不赘述了看上面的论文吧
然后我们就很容易想到，我们把所有的\(s_i\)从小到大排序，然后我们分别按序处理\(s_1\sim s_{k-1}\)
不难发现当我们处理\(s_i\)时，剩下的boxes的数目为\(s_i+s_{i+1}+\cdots+s_k-1\)，由于\(s_k\ge s_i\)，这个加和是一定大于等于\(2s_i-1\)的
因此我们总能对于前\(k-1\)个class找到一种合法的分配，然后对于最后一个教室由于有一个可以随便分的，也是很trivial的
那么现在问题就是如何构造解了，显然可以通过一个很simple的DP来实现
设\(f_{i,j,k}\)表示在前\(i\)个数中，选出\(j\)个使得它们的和模\(s_i\)的余数为\(k\)的方案是否存在，然后由于又要考虑到构造方案，我们再设一个\(g_{i,j,k}\)意义和\(f_{i,j,k}\)类似但是要求强制选\(i\)这个数
因此总复杂度大概就是\(O(k\times n^3)\)的，不过DP的时候很多都跑不满（或许这个总复杂度可能就是\(O(n^3)\)的？），也是能很轻松地跑过的
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=205;
int n,m,a[N],stk[N],top; pi s[N];
bool f[N][N][N],g[N][N][N],vis[N]; vector <int> ans[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,k,r; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=m;++i) scanf("%d",&s[i].first),s[i].second=i;
for (sort(s+1,s+m+1),i=1;i<m;++i)
{
int p=s[i].first,id=s[i].second;
for (top=0,j=1;j<=2*p-1;++j) stk[++top]=a[n--];
for (j=0;j<=p;++j) for (k=0;k<p;++k) f[1][j][k]=g[1][j][k]=0;
f[1][0][0]=f[1][1][stk[1]%p]=g[1][1][stk[1]%p]=1;
for (j=2;j<=top;++j) for (k=0;k<=p;++k) for (r=0;r<p;++r)
{
f[j][k][r]=f[j-1][k][r];
if (k&&f[j-1][k-1][(r-stk[j]%p+p)%p]) f[j][k][r]=g[j][k][r]=1;
else g[j][k][r]=0;
}
for (j=1;j<=top;++j) vis[j]=0;
for (k=p,r=0,j=top;j;--j)
if (g[j][k][r]) vis[j]=1,--k,r=(r-stk[j]%p+p)%p;
for (j=1;j<=top;++j)
if (vis[j]) ans[id].push_back(stk[j]); else a[++n]=stk[j];
}
int sum=0; for (i=1;i<=n;++i) (sum+=a[i])%=(n+1);
for (i=1;i<=n;++i) ans[s[m].second].push_back(a[i]);
ans[s[m].second].push_back(n+1-sum);
for (printf("%d\n",n+1-sum),i=1;i<=m;++i,putchar('\n'))
for (int x:ans[i]) printf("%d ",x); return 0;
}
Postscript
本来这周三有下午场的CF，可惜我一个礼拜就那天有课大不了了
不过周五的晚间场还是可以尝试遛一遛的说（虽然第二天还有校赛的初赛，不过如果只是混个复赛资格应该问题不大的说）