Preface
难得的7点场CF，结果反而遇上了我最困的时候（吃完晚饭血糖上来就贼困，我一般反而凌晨场比较清醒）
但是这场表现还可以，写的题基本都是一发入魂而且速度也比较快
比较可惜的是E想复杂了没发现是个思博题，不过就算后面看出来了对排名也没什么影响了
终于跌跌撞撞又回到了冲击1900的分数了，希望下次一场过关
A1. Gardener and the Capybaras (easy version)&A2. Gardener and the Capybaras (hard version)
由于这次的分P在A题，因此就直接写A2的了，如果只是A1的话直接暴力枚举分界点即可
刚开始没仔细看题没看到只有两种字符，因此顿了一下，幸好后面被ztc提醒了
考虑在\([2,n-1]\)中是否存在a，若存在则我们可以把这个a单独拎出来作为\(b\)串，前后的就是\(a,c\)串，这样显然满足\(b\)串最小
若不存在则我们可以令\([2,n-1]\)的都为\(b\)串，\(a\)串就是开头的一个字符，\(c\)串就是结尾的一个字符，这样显然满足\(b\)串最大
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n; char s[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; bool flag=0; scanf("%s",s+1); n=strlen(s+1);
for (i=2;i<n&&!flag;++i) if (s[i]=='a')
{
for (j=1;j<i;++j) putchar(s[j]); putchar(' ');
putchar(s[i]); putchar(' ');
for (j=i+1;j<=n;++j) putchar(s[j]); putchar('\n');
flag=1;
}
if (flag) continue;
putchar(s[1]); putchar(' ');
for (i=2;i<n;++i) putchar(s[i]); putchar(' ');
putchar(s[n]); putchar('\n');
}
return 0;
}
B. Gardener and the Array
刚开始还在想那种表示法里会不会出现重复的元素，后来不管了直接Rush一发发现没有
贪心的想，我们不妨令\(a=1,2,\cdots,n\)，即将全部元素都选上的序列
考虑如果要找到一个\(b\)满足条件，显然只要找到某个位置使得去掉它之后或和和\(a\)一样即可
因此考虑开个桶记录下每个数出现的次数，如果某个位置上的数出现次数都大于\(1\)则有解
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,num,ct[N]; vector <int> p[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",&num),p[i].resize(num),j=0;j<num;++j)
scanf("%d",&p[i][j]),++ct[p[i][j]];
bool flag=0; for (i=1;i<=n&&!flag;++i)
{
bool sign=1; for (int x:p[i]) if (ct[x]==1) sign=0;
if (sign) flag=1;
}
for (i=1;i<=n;++i) for (int x:p[i]) ct[x]=0;
puts(flag?"Yes":"No");
}
return 0;
}
C. Interesting Sequence
刚开始Rush了一发挂了，结果使用经典招数#define int long long后就过了
首先枚举一个二进制位\(i\)，考虑在二进制下\(n\)的第\(i\)位\(a\)和\(x\)的第\(i\)位\(b\)的不同情况：
- \(a=0,b=1\)，此时显然不论怎么搞\(a\)始终是\(0\)，因此是无解的
- \(a=1,b=0\)，此时我们设\(c_i\)为最小的且大于\(n\)的第\(i\)位是\(0\)的数，显然我们要对所有这种情况的\(c_i\)取\(\max\)
- \(a=1,b=1\)，此时我们设\(d_i\)为最小的且大于\(n\)的第\(i\)位是\(0\)的数，显然我们要对所有这种情况的\(d_i-1\)取\(\min\)
最后看下在上述条件下有没有数满足条件即可
关于如何找到最小的且大于\(n\)的第\(i\)位是\(0\)的数，我们观察下每一位上\(0/1\)的变化规律即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
#define int long long
using namespace std;
const int N=200005;
int t,n,x;
inline int G(CI x,CI y)
{
return (x>>y)&1;
}
inline int find(CI x,CI y)
{
return (1LL<<y+1)-(x&((1LL<<y+1)-1));
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i,j; bool flag=1; for (scanf("%lld%lld",&n,&x),i=0;i<61&&flag;++i)
if (G(n,i)==0&&G(x,i)==1) flag=0; if (!flag) { puts("-1"); continue; }
int Mi=5e18,Mx=0; for (i=0;i<61;++i) if (G(n,i)==1)
{
if (G(x,i)==1) Mi=min(Mi,find(n,i)); else Mx=max(Mx,find(n,i));
}
if (Mx<Mi) printf("%lld\n",n+Mx); else puts("-1");
}
return 0;
}
D. Friendly Spiders
套路题，不得不说我还能吃点以前的老本的说
这种边数爆炸的最短路问题一眼需要搞虚点来优化建图，而这题又是和\(\gcd\)有关就很容易想到和质因数挂钩
考虑对于每个\(a_i\)，我们找出它所有的质因数\(p_{i,j}\)（设\(p_{i,j}\)是第\(k\)个质因数），并且连\(i\to n+k\)，权值为\(1\)的边，以及\(n+k\to i\)，权值为\(0\)的边
这样我们就只要对一个点数为\(O(n)\)级别，边数为\(O(n\cdot\pi(\sqrt n))\)级别的图跑最短路即可
由于边权只有\(0/1\)，因此可以用0/1-BFS来保证复杂度是关于边数的线性级别的
#include<cstdio>
#include<iostream>
#include<vector>
#include<deque>
#define RI register int
#define CI const int&
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=600005;
int n,x,prime[N],id[N],cnt,s,t,dis[N],pre[N],ans[N],tot; bool vis[N];
vector <pi> v[N]; deque <int> dq;
inline void init(CI n)
{
RI i,j; for (i=2;i<=n;++i)
{
if (!vis[i]) prime[++cnt]=i,id[i]=cnt;
for (j=1;j<=cnt&&i*prime[j]<=n;++j)
{
vis[i*prime[j]]=1; if (i%prime[j]==0) break;
}
}
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (init(300000),scanf("%d",&n),i=1;i<=n;++i)
{
for (scanf("%d",&x),j=1;j<=cnt&&1LL*prime[j]*prime[j]<=x;++j)
if (x%prime[j]==0)
{
v[i].pb(mp(n+j,1)); v[n+j].pb(mp(i,0));
while (x%prime[j]==0) x/=prime[j];
}
if (x!=1) v[i].pb(mp(n+id[x],1)),v[n+id[x]].pb(mp(i,0));
}
for (scanf("%d%d",&s,&t),i=1;i<=n+cnt;++i) vis[i]=0,dis[i]=1e9;
dq.push_back(s); dis[s]=0; vis[s]=1;
while (!dq.empty())
{
int now=dq.front(); dq.pop_front(); vis[now]=0;
for (auto to:v[now]) if (dis[to.fi]>dis[now]+to.se)
{
dis[to.fi]=dis[now]+to.se; vis[to.fi]=1; pre[to.fi]=now;
if (to.se) dq.push_back(to.fi); else dq.push_front(to.fi);
}
}
if (dis[t]==1e9) return puts("-1"),0;
for (x=t;x;x=pre[x]) if (x<=n) ans[++tot]=x;
for (printf("%d\n",tot),i=tot;i;--i) printf("%d ",ans[i]);
return 0;
}
E. The Human Equation
我去我是脑瘫，想了个naive的\(O(n^2)\)做法后就开始想着找数据结构优化，然后半个小时无果后就摸鱼去了
结果今天看了眼Tutorial一想操作的本质就顿悟了，只能说如果这种思博题放在B我说不定能做出来
先求出原序列的前缀和数组\(pfx_i\)，让\(a_i\)全变成\(0\)等价于让\(pfx_i\)全变成\(0\)
考虑两种操作的本质，其实第一种就是让前缀和数组的某些元素加\(1\)，第二种就是让某些元素\(-1\)
因此不难发现答案其实就是\(\max_\limits{1\le i\le n} pfx_i-\min_\limits{1\le i\le n} pfx_i\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,x;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; long long mi=0,mx=0,pfx=0;
for (scanf("%d",&n),i=1;i<=n;++i)
scanf("%d",&x),pfx+=x,mi=min(mi,pfx),mx=max(mx,pfx);
printf("%lld\n",mx-mi);
}
return 0;
}
F. Laboratory on Pluto
考虑对于某个确定的边长\(C\)（显然\(C\)一定是偶数），它能确定的最大面积\(S\)是多少，不难发现
- 若\(C\bmod 4=0\)时，\(S=(\frac{C}{4})^2\)
- 若\(C\bmod 4=2\)时，\(S=\lfloor\frac{C}{4}\rfloor\times \lceil\frac{C}{4}\rceil\)
因此我们只要找到一组\(h,w\)使得\(h\times w\ge n\)且\(|h-w|\)尽量小即可得到最小的周长
对于\(u=1\)的问题，显然把空都留到最后就是一种合法方案，可以轻松解决
对于\(u=2\)的问题，我们可以尝试一步步扩大\(|h-w|\)的值
若仍然有\(h\times w\ge n\)，则我们需要找出在\(h\times w\)的矩形里挖去\(n\)个方块且不改变其周长的方案数，这个显然可以预处理出来
#include<cstdio>
#include<iostream>
#include<cmath>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=400005;
int t,n,u,mod,h,w,f[1005]; vector <char> a[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; if (scanf("%d%d",&t,&u),u==2)
{
for (scanf("%d",&mod),f[0]=i=1;i<=1000;++i)
for (RI k=0;k<4;++k) for (j=i;j<=1000;++j) (f[j]+=f[j-i])%=mod;
}
for (;t;--t)
{
scanf("%d",&n); h=(int)sqrt(n); w=(n+h-1)/h;
while (w>h+1) --w,++h; if (u==1)
{
for (printf("%d %d\n",h,w),i=1;i<=h;++i) a[i].resize(w+1);
for (i=1;i<=h;++i) for (j=1;j<=w;++j) a[i][j]='.';
for (i=1;i<=h;++i) for (j=1;j<=w;++j)
if (n--) a[i][j]='#'; else break;
for (i=1;i<=h;++i,putchar('\n')) for (j=1;j<=w;++j) putchar(a[i][j]);
} else
{
int ans=0; while (h*w>=n)
(ans+=(h!=w?2LL:1LL)*f[h*w-n]%mod)%=mod,++w,--h;
printf("%d %d\n",2*(h+w),ans);
}
}
return 0;
}
Postscript
最近场次好多，前面还有一场Educational Round没补完，在下次周日比赛之前争取把之前的都补完吧
标签：CI,843,int,Codeforces,const,Div,include,RI,define From： https://www.cnblogs.com/cjjsb/p/17045002.html