CFR632

CFR632 div2

最近胡策胡得我太自闭了

dls的视频

以下时间中,想包括看题,写为第一次提交前,调试包括第一次提交到通过,是通过录屏记录的

B想了4min,写了1min

C想了2min,写了2min,调了5min

D想了10min,写了7min,调了2min

E想了10min,跳了

F想了16min,写了14min

剩下40min,最后15min在写E的暴力,没写完

CF1333A Little Artem

请先思考后再展开

直接B=2,W=1即可

1
fo(i,1,n){ fo(j,1,m) putchar(i==1 and j==1?'W':'B');puts(""); }

CF1333B Kind Anton

题意:给定一个序列a只含有$[-1,1]$,做若干次$i<j,a_j+=a_i$,问能否得到序列b

请先思考后再展开
1
2
3
4
5
6
7
8
int n=qread();fo(i,1,n) a[i]=qread();fo(i,1,n) b[i]=qread();
int mi=a[1],mx=a[1];bool gg=(a[1]!=b[1]);//首先这个要一样
fo(i,2,n)
{
if(a[i]<b[i] and mx!=1) gg=1;//biger
if(a[i]>b[i] and mi!=-1) gg=1;//smaller
chmin(mi,a[i]),chmax(mx,a[i]);
}puts(gg?"NO":"YES");

CF1333C Eugene and an array

题意:给定长度为$n \le 1e5$的序列,统计有多少个子区间,满足子区间内不存在子区间和为0

请先思考后再展开

考虑每个位置开始的最长和为0区间,把整个序列断开成若干段,每组内独立

1
2
3
4
5
6
7
int n=qread();fo(i,1,n) a[i]=qread()+a[i-1];ll ans=0;int mi=n;
fd(i,n,1)
{
nxt[a[i]]=i;//debug 漏考虑0的情况放在下面
if(nxt.count(a[i-1])) chmin(mi,nxt[a[i-1]]-1);
ans+=mi-i+1;
}write(ans);

CF1333D Challenges in school №41

请先思考后再展开

最少的话就每次选最多的人就是最优的,最多就是分步做这个过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n=qread(),k=qread(),tim=0;scanf("%s",str+1);fo(i,1,n) a[i]=(str[i]=='R'?0:1);int sum=0;
while(1)
{
tim++;
fo(i,1,n-1) if(a[i]==0 and a[i+1]==1) pos[tim].PB(i),a[i]^=1,a[i+1]^=1,i++;
if(!sz(pos[tim])) break;sum+=sz(pos[tim]);
}tim--;
if(k<tim or k>sum) GG();
int ned=k-tim;
fo(i,1,tim)
{
int m=sz(pos[i]),j=0;
while(j<m-1 and ned) ned--,printf("1 %d\n",pos[i][j]),j++;//debug 忘记j++
printf("%d ",m-j);fo(t,j,m-1) write1(pos[i][t]);puts("");
}

CF1333E Road to 1600

请先思考后再展开

一开始猜测n=4是最小的(因为样例给了,而且n=3手玩了一万年没整出来)

其实可以爆搜出随便一个n=3的答案(爆搜又不好写,最后没写完。。)其中有1在边界上的

那么对于更大的n,先蛇形把其他地方都以相同的方式走完,最后在这个小矩阵的拉开差距即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int a[3][3]={
{6,8,4},
{5,2,3},
{9,7,1}
};int b[1000][1000];
void main()
{
int n=qread();if(n<=2) GG();int m=0,cur=0;
while(m+1<n-2)
{
m++;
if(m&1){ fd(i,n,m) b[i][m]=++cur;fo(i,m+1,n) b[m][i]=++cur; }
else { fd(i,n,m) b[m][i]=++cur;fo(i,m+1,n) b[i][m]=++cur; }
}
fo(i,0,2) fo(j,0,2) b[n-2+i][n-2+j]=a[i][j]+cur;
fo(i,1,n){ fo(j,1,n) write1(b[i][j]);puts(""); }
}

CF1333F Kate and imperfection

题意:对于$k=2 \sim n$,在1到n中选k个不重的数构成集合S,输出最小的$\max_{x,y \in S} gcd(x,y)$

请先思考后再展开

如果不想d对答案造成贡献,一定是恰保留d自己

因此k的答案一定是k+1的子集, 每次考虑当前的ans的倍数要花费多长时间去掉即可

老年人思维缓慢+印象中写错点地方调了调,花了40min

1
2
3
4
5
6
7
8
9
10
11
12
int n=qread();int now=n/2;fo(i,1,n) on[i]=1;
for(int pos=n;pos>1;)
{
int bak=now,siz=pos;
while(1)
{
int cnt=0;for(int i=now+now;i<=n;i+=now) if(on[i]) on[i]=0,cnt++,siz--;
now--;if(cnt) break;
}
fo(i,siz+1,pos) ans[i]=bak;pos=siz;
if(now==1){ fo(i,2,siz) ans[i]=1;break; }
}fo(i,2,n) write1(ans[i]);

std是我自认为没上面做法好想但很jb优美的思路,考虑一个集合,如果一个数有某个因子不在集合内可以替换为那个因子,因此只考虑集合中每个数的因子都在里面的集合,发现答案就是max 最大非平凡因子,因此直接把最大非平凡因子排序输出即可

其实主要是我是从大往小删除的,他是从小往大加入的,基本是第一步思路就不一样了

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/92e31e33.html
转载请注明出处,谢谢!