0%

cf2

近日写的题

这两天状态火热,小(。。。)号直接上1700+了,这段时间训练重点是1700的题,最近打算冲紫,需要多出一些1900+的题。目前希望比赛能30min出完1500-的,30min出一道1600的。剩下出个1900(。。。不太现实)。

1342c|1600|数论

模运算和模数倍数有关,模两次和lcm有关,令a小于b,则lcm余数为0,余数为0-b-1时二式相等,即每个周期中,b-lcm是不等的,统计多少个周期和多余个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const int maxn=1005;
ll gcd(ll a,ll b){
if(b == 0) return a;
else return gcd(b,a%b);
}
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
ll a,b,q;cin>>a>>b>>q;
ll l,r;
ll gg=gcd(a,b);
while(q--){
cin>>l>>r;
if(a%b==0||b%a==0){
cout<<0<<' ';
continue;
}
if(r<max(a,b)){
cout<<0<<' ';
continue;
}else if(l<max(a,b)){
ll cnt=0;
cnt+=max(a,b)-l;
ll d1=r-max(a,b)+1;
ll res=d1%(min(a,b)*max(a,b)/gg);
cnt+=max(a,b)*(d1/(min(a,b)*max(a,b)/gg));
cnt+=max(0ll,res-(min(a,b)/gg-1)*max(a,b));
cout<<r-l+1-cnt<<" ";
}else{
ll cnt1=0,cnt2=0;
ll d1=r-max(a,b)+1;
ll d2=l-max(a,b);
ll res=d1%(1ll*a*b/gg);
ll res2=d2%(1ll*a*b/gg);
cnt1+=max(a,b)*(d1/(1ll*a*b/gg));
cnt1+=max(0ll,res-1ll*(min(a,b)/gg-1)*max(a,b));
cnt2+=max(a,b)*(d2/(1ll*a*b/gg));
cnt2+=max(0ll,res2-1ll*(min(a,b)/gg-1)*max(a,b));
cout<<r-l+1-cnt1+cnt2<<' ';
}
}cout<<endl;
}
}

1340a|1500|模拟+优先队列

观察得到,count数组初始全是1,每次填数造成的影响是将pos位置的count加到pos+1上去,将pos位置0,将pos+1的新值入队。
按照给出的结果的顺序模拟即可,使用pq保存当前最大值(每次开始模拟时,将pq顶上已经填过的位置去掉,模拟结束不一定填这个位置,所以不删),如填的位置不是最大的,就判no

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const int maxn=2e5+10;
int woe[maxn];
int in[maxn];
int vis[maxn];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
int n;cin>>n;
priority_queue<pair<int ,int> > pq;
for(int i=1;i<=n;++i)woe[i]=1;
for(int i=1;i<=n;++i)vis[i]=0;
map<int ,int> ma;
for(int i=1;i<=n;++i){
cin>>in[i];
ma[in[i]]=i;
pq.push(MP(woe[i],i));
}
int tag=1;
for(int i=1;i<=n;++i){
while(1){
pair<int,int> tmp=pq.top();
if(vis[tmp.second]==1)pq.pop();
else break;
}
int pos=ma[i];
auto ttt=pq.top();
if(woe[pos]!=ttt.first){
tag=0;
break;
}

vis[pos]=1;
woe[pos+1]+=woe[pos];
woe[pos]=0;
if(pos+1<=n&&vis[pos+1]==0){
pq.push(MP(woe[pos+1],pos+1));
}
}
if(tag)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}

1340b|1700|dp

可以方便的求出一个串到0-9各需要多少代价。
首先想的是dfs发现复杂度爆炸,查看题解,使用的是dp,从低位开始,即从n开始,dp[i][j]表示,考虑完第i位后,使用j的代价能不能恰好构成数。
看起来复杂度还是很危。。。。不过是可以的
判断dp[1][k]即可知道是否可行,
最后又是一个暴力即可找到最大数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
const int maxn=2005;
string s[10]={"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
int in[2008][12];
int dp[maxn][maxn];
string tmp;
void hand(int k){
cin>>tmp;
int cnt;
for(int i=0;i<=9;++i){
cnt=0;
for(int j=0;j<=6;++j){
if(tmp[j]=='0'){
if(s[i][j]=='1')cnt++;
}else{
if(s[i][j]=='0'){
cnt=inf;
break;
}
}
}
in[k][i]=cnt;
}
}
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
int n,k;cin>>n>>k;
for(int i=1;i<=n;++i){
hand(i);
}
dp[n+1][0]=1;
for(int i=n;i>=1;--i){
for(int c=0;c<=k;++c)if(dp[i+1][c]==1)
for(int j=0;j<=9;++j){
if(in[i][j]==inf)continue;
else{
dp[i][c+in[i][j]]=1;
}
}
}
if(dp[1][k]==1){
int now=k;
for(int i=1;i<=n;++i){
for(int j=9;j>=0;--j){
if(now-in[i][j]>=0&&dp[i+1][now-in[i][j]]==1){
now=now-in[i][j];
cout<<j;
break;
}
}
}cout<<endl;
}else cout<<"-1"<<endl;
}

1476D|1700|前后缀

我们可以把每个点拆分为两个状态模拟一下,会发现两个点总是连通的,且每个点只能在一个状态出现,无论怎么走都不能到另一个状态。这使得从前向后或者后往前是等价的。
愿问题需要对每个点求能走多远,可以转换为可以从最远的点到达此点,即从两个方向来此点的总长度。可以跑出pre和las。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int maxn=3e5+100;
int pre[maxn][2];
int las[maxn][2];
char in[maxn];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
int n;cin>>n;
cin>>in+1;
pre[1][0]=pre[1][1]=1;
las[n+1][0]=las[n+1][1]=1;
for(int i=2;i<=n+1;++i){
if(in[i-1]=='L'){
pre[i][0]=pre[i-1][1]+1;
pre[i][1]=1;
}else{
pre[i][1]=pre[i-1][0]+1;
pre[i][0]=1;
}
}
for(int i=n;i>=1;--i){
if(in[i]=='L'){
las[i][1]=las[i+1][0]+1;
las[i][0]=1;
}else{
las[i][0]=las[i+1][1]+1;
las[i][1]=1;
}
}
for(int i=1;i<=n+1;++i){
cout<<pre[i][0]+las[i][0]-1<<' ';
}cout<<endl;
}
}

1475e|1600|思维+组合数

显然,最大的那一批是不能动的,只有排序后恰处于边上的那一种,总数和能进的求个组合数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
per(){
int n,k;cin>>n>>k;
map<int,int> ma;
for(int i=1;i<=n;++i){cin>>in[i];ma[in[i]]++;}
sort(in+1,in+1+n);
in[n+1]=-1;
ll tmp=in[n-k+1];
int pos=-1;
for(int i=n-k+1;i<=n+1;++i){
if(in[i]!=tmp){
pos=i;break;
}
}
int num=pos-n+k-1;
int tot=ma[tmp];
cout<<C(tot,num)<<endl;
}

1469d|1700|难构造

显然1,2我们不动,需要把其他变1,因为向上取整,大规模变1必须是小数除以大数。
如果一直除到底,那个数用2是干不掉的。
注意到,2干不掉可以用大数干,即中途选点干,为了不浪费,恰好2次即可,即i与 i方的关小,如此,每个端点只要多一次即可,而这样最多就几个端点,满足。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int hhh[15]={1,2,4,16,256,65536};
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
int n;cin>>n;
int now=-1;
for(int i=5;i>=1;--i){
if(n>hhh[i]){
now=i;break;
}
}
cout<<n-2+now<<endl;
while(now>0){
for(int i=hhh[now]+1;i<n;++i){
cout<<i<<' '<<n<<endl;
}
cout<<n<<' '<<hhh[now]<<endl;
cout<<n<<' '<<hhh[now]<<endl;
n=hhh[now];
now--;
}
}
return 0;
}

1472e|1700|RMQ+二分

他有横着和竖着,这不是问题,判两次即可。
一种很经典的问题,即一大堆数对中,找一组比当前数对两个数都小的。
范围是2e5,暴力显然炸。所以可以对一个维度排序,先二分查到这个维度最后一个满足的位置。
然后只要求出从最小到这里另一个维度有没有满足的即可,对第一维度排序后对第二维建ST表即可。
注意st表的排序判定自己写,是因为结果需要第几个数,所以用in2存起第几个数是什么,st表中存第几个即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
const int maxn=2e5+10;
int n;
int f[maxn][19];
ui in[maxn];
ui in2[maxn];
int M(int a,int b){
if(in2[a].w<in2[b].w){
return a;
}else return b;
}
//f[i][j]表示[i,i+x^j-1]范围最大值
void STinit(int n){
for(int i=1;i<=n;++i){
f[i][0]=in[i].p;
}
int t=log(n)/log(2)+1;
for(int j=1;j<t;j++){//长度2^j的区间最值分为2^{j-1}的两段
for(int i=1;i<=n-(1<<j)+1;i++ ){
f[i][j]=M(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}
//两个区间覆盖l-r即可,中间重合无妨
int STQ(int l,int r){
int k=log(r-l+1)/log(2);
return M(f[l][k],f[r-(1<<k)+1][k]);
}
int ask(int x,int y){
int l=1,r=n;
while(l!=r){
int mid=(l+r+1)/2;
if(in[mid].h<x){
l=mid;
}else r=mid-1;
}
if(in[l].h>=x){
return -1;
}
int tmp=STQ(1,l);
if(in2[tmp].w<y){
return tmp;
}else return -1;
}
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
cin>>n;
int x,y;
for(int i=1;i<=n;++i){
cin>>x>>y;
in[i]={x,y,i};
in2[i]={x,y,i};
}
sort(in+1,in+n+1);
STinit(n);
for(int i=1;i<=n;++i){
int x=in2[i].h,y=in2[i].w;
int a1=ask(x,y);
if(a1!=-1)cout<<a1<<' ';
else {
int a2=ask(y,x);
cout<<a2<<' ';
}
}
cout<<endl;
}
}

1492A|800|思维

经典小学题,注意%出0意思是不用等。

1
2
3
4
5
6
7
8
9
10
per(){
ll p,a,b,c;
cin>>p>>a>>b>>c;
ll ans=INF;
ans=min(ans,a-p%a);
ans=min(ans,b-p%b);
ans=min(ans,c-p%c);
if(p%a==0||p%b==0||p%c==0)ans=0;
cout<<ans<<endl;
}

1492B|1100|思维模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Farmer Lance 2021/2/23 18:09:36
n在最下面的时候的贡献比其他数加起来都大

Farmer Lance 2021/2/23 18:09:54
每次贪心让能移动的最大值在最下面

Farmer Lance 2021/2/23 18:10:13
如果移动n的时候把n-1动了,就不考虑n-1了

Farmer Lance 2021/2/23 18:10:39
比如123645

Farmer Lance 2021/2/23 18:10:49
上来第一步就是移动645

Farmer Lance 2021/2/23 18:10:57
然后123里继续

嗯,就这样。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int maxn=1e5+10;
int in[maxn];
int main()
{
per(){
int n;cin>>n;
map<int,int> ma;
for(int i=1;i<=n;++i){
cin>>in[i];
ma[in[i]]=i;
}
int top=n;
int now=n;
while(now>0){
int tmp=ma[now];
if(tmp>top){
now--;continue;
}else{
for(int i=tmp;i<=top;++i){
cout<<in[i]<<' ';
}
now--;
top=tmp-1;
}
}
cout<<endl;
}
}

1492C|1500|前后缀

跑pre和las即可,每个位置能合法出现的最前和最后,比较相邻位直接的最大距离即可。

这场是正式打的,状态火热,30min切到这题,已经稳上分了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int maxn=2e5+10;
char s[maxn];
char t[maxn];
int pre[maxn];
int las[maxn];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
int n,m;cin>>n>>m;
cin>>s+1;
cin>>t+1;
int now=1;
for(int i=1;i<=m;++i){
while(s[now]!=t[i]){
now++;
}
pre[i]=now;
now++;
}
now=n;
for(int i=m;i>=1;--i){
while(s[now]!=t[i]){
now--;
}
las[i]=now;
now--;
}
int ma=-1;
for(int i=1;i<m;++i){
ma=max(ma,las[i+1]-pre[i]);
}
cout<<ma<<endl;

}

1492D|1900|二进制构造

注意到1000和0001可以出0111,且1100和0101一样,即同时出现会抵消,我们发现:

  • 至少要有一个0,除非k==0
  • 至少要有一个1,k==0也不好使。
  • 。。。。总之k==0是大毒瘤,为他wa5发,最好上来就处理掉。

一般情况下构造方法是:

  • 第一个,第一为1,最后0,中间b-1个1
  • 第二个,第一为1,最后是1,中间b-2个1,多的一个0是为了不消去第一个的1,这个0和结果有关。

显然发现k最大是a+b-2,否则没法构造。
最后10minwa5次冲出来(指30min开始,一直写到110min才ac),芜湖,起飞,飞飞飞~

(改的太多,可能判断有很多重复的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
const int maxn=4e5+10;
int out[maxn];
int main()
{
int a,b,k;cin>>a>>b>>k;
if(k==0){
cout<<"Yes"<<endl;
for(int i=1;i<=b;++i)cout<<1;
for(int i=1;i<=a;++i)cout<<0;cout<<endl;
for(int i=1;i<=b;++i)cout<<1;
for(int i=1;i<=a;++i)cout<<0;cout<<endl;
return 0;
}
if(a==0){
if(k==0){
cout<<"Yes"<<endl;
for(int i=1;i<=b;++i)cout<<1;cout<<endl;
for(int i=1;i<=b;++i)cout<<1;cout<<endl;
}else{
cout<<"No"<<endl;
}
return 0;
}
if(b==1){
if(k==0){
cout<<"Yes"<<endl;
cout<<1;
for(int i=1;i<=a;++i)cout<<0;
cout<<endl;
cout<<1;
for(int i=1;i<=a;++i)cout<<0;
cout<<endl;
}else{
cout<<"No"<<endl;
}
return 0 ;
}
if(k>a+b-2){
cout<<"No"<<endl;
return 0;
}else{
cout<<"Yes"<<endl;
int tmp=a+b;
for(int i=1;i<=tmp;++i)out[i]=0;
out[1]=1;
out[tmp-k]=1;
b-=2;
int now=2;
while(b>0){
if(now==tmp-k){
now++;
continue;
}else{
out[now]=1;
now++;
b-=1;
}
}
for(int i=1;i<=tmp;++i){
cout<<out[i];
}cout<<endl;
out[tmp]=1;
out[tmp-k]=0;
for(int i=1;i<=tmp;++i){
cout<<out[i];
}cout<<endl;
}
}