CF1493 赛后总结
|字数总计:3.1k|阅读时长:15分钟|阅读量:
前言
仅仅是做，并没有实际参与比赛，且F题并没有代码参考。
A
题目
个数非常显然的是$n-\left\lfloor\frac{k}{2}\right\rfloor$
至于为什么，这里证明一下：
首先，在 $[1,k-1]$ 中，你选了一个数字，那么 $k-x$ 的数字就不能选，因此小于 $k$ 中你最多选 $\left\lceil\frac{k-1}{2}\right\rceil$ 个数字，同时我们也能构造出这种方案，就是$\left\lceil\frac{k}{2}\right\rceil$ 一直到 $k-1$ 全部选上。
这样子的话选了 $k-1-\left\lceil\frac{k}{2}\right\rceil+1=\left\lceil\frac{k-1}{2}\right\rceil$
刚刚好，然后把大于 $k$ 的算上就行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<cstdio>
#include<cstring>
using namespace std;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,k;scanf("%d%d",&n,&k);
int mid=(k+1)/2;
printf("%d\n",n-mid);
for(int j=mid;j<=n;j++)
{
if(j!=k)printf("%d ",j);
}
printf("\n");
}
return 0;
}
|
B
题目
这道题目就更加简单了，不难发现只有 $0,1,2,5,8$ 会翻转，直接暴力枚举，时间复杂度：$O(625n)$
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
69
70
71
72
73
74
75
76
77
78
79
| #include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int x,y;
};
int n,m;
inline bool check(node x){return x.x<n && x.y<m;}
inline int operator-(node x,node y)
{
if(x.x<y.x || (x.x==y.x && x.y<y.y))x.x+=n;
return (x.x-y.x)*m+x.y-y.y;
}
int yuan[]={0,1,2,5,8};
int huan[]={0,1,5,2,8};
node sh1,sh2;
node ans;int limitans;
node goal;
void dfs(int dep)
{
if(dep==5)
{
if(check(sh2)==1 && check(sh1)==1 && sh1-goal<limitans)limitans=sh1-goal,ans=sh1;
return ;
}
for(int i=0;i<=4;i++)
{
if(dep==1)
{
sh1.y=(sh1.y/10)*10+yuan[i];
sh2.x=(sh2.x%10)+huan[i]*10;
}
else if(dep==2)
{
sh1.y=(sh1.y%10)+yuan[i]*10;
sh2.x=(sh2.x/10)*10+huan[i];
}
else if(dep==3)
{
sh1.x=(sh1.x/10)*10+yuan[i];
sh2.y=(sh2.y%10)+huan[i]*10;
}
else
{
sh1.x=(sh1.x%10)+yuan[i]*10;
sh2.y=(sh2.y/10)*10+huan[i];
}
dfs(dep+1);
}
}
inline void getz(int &x)
{
x=0;char c=getchar();
while(c>'9' || c<'0')c=getchar();
while(c<='9' && c>='0')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x)
{
if(x<10)printf("0");
printf("%d",x);
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
getz(goal.x);getz(goal.y);
sh1.x=0;sh1.y=0;sh2.x=0;sh2.y=0;
limitans=999999999;
dfs(1);
print(ans.x);
printf(":");
print(ans.y);
printf("\n");
}
return 0;
}
|
C
题目
基本思路就是前面尽量迎合原字符串，显然，从起始位置开始和原字符串连续相同的字符越多的字符串，字典序应该是越小的。
比如说现在我在处理 $i$ 这个位置，那么，我需要干两个事情，第一个，我能不能在这个位置放上一个比这个位置大的字符，如果可以，用 $ans$ 记录下这个位置，然后再判断我现在能不能在这个放上这个位置的字符，如果不可以，直接退出输出答案。
当然，如果原来的字符串就可以满足要求先输出原来的字符串。
输出答案也很简单，再模拟一边，然后模拟到 $ans$ 时填一个尽可能接尽原位置字符的字符，然后如果还可以申请字符，就全部填充上 $a$ ，然后后面从小到达输出。
这里讲一个错误的思路：
如果不用申请字符就可以填充这个位置的话，就不去判断这个位置能不能更新 $ans$ ，这是错误的，因为存在 $z$ 这个字符是无法被超越的，比如下面这个例子：
$n=6,m=2$
$abbzzz$
这个时候，$ans$ 在 $2$ 时被更新以后在 $4$ 往后的位置都不可能被更新，如果不能在 $3$ 更新答案就错了。
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| #include<cstdio>
#include<cstring>
#define N 210000
using namespace std;
int need[30],now[30],cnt;
int n,k;
int pre;
char st[N];
inline bool check(int x)
{
if(now[x]==need[x])
{
if(cnt==n)return 0;
need[x]+=k,cnt+=k;
}
now[x]++;
return 1;
}
inline int findc(int limit)
{
if(limit==25)return -1;
else if(cnt<n)return limit+1;
else
{
for(int i=limit+1;i<=25;i++)
{
if(now[i]<need[i])return i;
}
return -1;
}
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
pre=1;memset(need,0,sizeof(need));
memset(now,0,sizeof(now));cnt=0;
scanf("%d%d",&n,&k);
scanf("%s",st+1);
if(n%k!=0)printf("-1");
else
{
need[st[1]-'a']+=k;
now[st[1]-'a']++;cnt+=k;
bool bk=1;
for(int i=2;i<=n;i++)
{
int type=0;
if((type=findc(st[i]-'a'))!=-1)
{
if(now[type]<need[type] || cnt<n)pre=i;
}
if(check(st[i]-'a')==0)
{
bk=0;
break;
}
}
if(bk==1)printf("%s",st+1);
else
{
memset(need,0,sizeof(need));
memset(now,0,sizeof(now));
cnt=0;
for(int i=1;i<pre;i++)
{
check(st[i]-'a');
printf("%c",st[i]);
}
int shit=findc(st[pre]-'a');
check(shit);
printf("%c",shit+'a');
need[0]+=n-cnt;
for(int i=0;i<=25;i++)
{
while(now[i]<need[i])
{
printf("%c",i+'a');
now[i]++;
}
}
}
}
printf("\n");
}
return 0;
}
|
D
题目
做这种题目我就比较快了。
可以发现直接离线，然后对于每一种质因子直接做一个线段树判断现在是不是所有的位置都含有这个质因子。
时间复杂度：$O((n+m)\log^2{n})$
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #include<cstdio>
#include<cstring>
#define N 210000
#define NN 410000
#define NNN 8100000
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
int n,m;
struct node
{
int lc,rc,c;
bool bk;
int lazy;
}tr[NN];int len;
void bt(int l,int r)
{
int now=++len;
if(l<r)
{
int mid=(l+r)>>1;
tr[now].lc=len+1;bt(l,mid);
tr[now].rc=len+1;bt(mid+1,r);
}
}
inline void jian(int x,int k){tr[x].lazy+=k;tr[x].c-=k;}
inline void clea(int x){tr[x].bk=1;tr[x].c=0;tr[x].lazy=0;}
inline void pushdown(int x)
{
if(tr[x].bk)clea(tr[x].lc),clea(tr[x].rc),tr[x].bk=0;
jian(tr[x].lc,tr[x].lazy);jian(tr[x].rc,tr[x].lazy);
tr[x].lazy=0;
}
inline int mymin(int x,int y){return x<y?x:y;}
inline void pushup(int x){tr[x].c=mymin(tr[tr[x].lc].c,tr[tr[x].rc].c);}
void change(int now,int l,int r,int k)
{
pushdown(now);
if(l==r){tr[now].c++;return ;}
int mid=(l+r)/2;
if(k<=mid)change(tr[now].lc,l,mid,k);
else if(mid<k)change(tr[now].rc,mid+1,r,k);
pushup(now);
}
int minin[N];
struct Query
{
int y,hou,ti;
}b[NNN];int dnt,lbst[N],hea[N];
inline void ins(int x,int y,int ti)
{
dnt++;if(!hea[x])hea[x]=dnt;
b[dnt].y=y;b[dnt].ti=ti;b[lbst[x]].hou=dnt;lbst[x]=dnt;
}
LL pre[N];
void work(int val)
{
clea(1);
for(int k=hea[val];k;k=b[k].hou)
{
int y=b[k].y;
change(1,1,n,y);
if(tr[1].c==1)
{
pre[b[k].ti]*=(LL)val;
pre[b[k].ti]%=mod;
jian(1,1);
}
}
}
int sta[N],top;
bool v[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)pre[i]=1;
for(int i=2;i<=200000;i++)
{
if(!v[i])
{
minin[i]=i;
sta[++top]=i;
}
for(int j=1;j<=top && sta[j]*i<=200000;j++)
{
v[i*sta[j]]=1;
minin[i*sta[j]]=sta[j];
if(i%sta[j]==0)break;
}
}
for(int i=1;i<=n;i++)
{
int x;scanf("%d",&x);
while(x>1)
{
ins(minin[x],i,1);
x/=minin[x];
}
}
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
while(y>1)
{
ins(minin[y],x,i);
y/=minin[y];
}
}
bt(1,n);
for(int i=1;i<=top;i++)work(sta[i]);
for(int i=2;i<=m;i++)pre[i]=(pre[i]*pre[i-1])%mod;
for(int i=1;i<=m;i++)printf("%lld ",pre[i]);
printf("\n");
return 0;
}
|
E
题目
这道题目的话比较阿巴，我还看错题了(╯‵□′)╯︵┻━┻。
首先，如果首位置不同，那么直接 $0111111…$ 和 $1000000….$ 就可以轻松达到最大。
如果首位置相同，特判一下三种情况：
两个字符串相同，直接输出。
两个字符串除了最后一个位置都相同，直接输出大的字符串。
两个字符串除了最后两个位置都相同，直接输出大的字符串。
至于为什么要特判，看完你应该就可能明白了。（可能判多了）
注：二进制第 $1$ 位为 $x[n]$
首先，一个基本的知识：$f(1,x)=?$
- $x$是奇数，那么 $n$ 除了最后一位全部保留，反之全部为 $0$ 。
- 如果 $x[n-1]=1,x[n]=0$ 或者 $x[n-1]=0,x[n]=1$ ，那么最后一位为 $1$ ，反之为 $0$ 。
那么，假设字符串在第 $k$ 个位置出现不同，记第 $k$ 个位置为 $1$ 的字符串为 $A$ ，另外一个为 $B$ 。
这里直接说结论，如果 $A$ 中 $k+1$ 到 $n$ 中存在一个为 $1$ 的数字，或者 $B$ 中 $k+1$ 到 $n$ 的位置存在一个位置为 $0$ ，那么答案为 $A$ 的 $1$ 到 $n-1$ 位以及最后一位为 $1$ ，否则为 $A$ 的 $1$ 到 $n-1$ 位以及最后一位为 $0$ 。
至于证明，比较难写下来，建议自己想，其实证明起来比较轻松。
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
| #include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1100000
using namespace std;
int n;
char a[N],b[N];
char t[N];
inline void fu1(int id){for(int i=id;i<=n;i++)t[i]='1';}
int main()
{
scanf("%d",&n);
scanf("%s",a+1);
scanf("%s",b+1);
if(n==1 && a[1]=='0' && b[1]=='0')
{
printf("0\n");
return 0;
}
if(a[1]!=b[1])
{
fu1(1);
printf("%s\n",t+1);
}
else if(a[1]==b[1])
{
int pre=n+1;
for(int i=1;i<=n;i++)
{
if(a[i]==b[i])printf("%c",a[i]);
else
{
if(b[1]=='1')swap(a,b);
pre=i;
break;
}
}
if(pre==n+1)return 0;
if(pre==n)
{
printf("1\n");
return 0;
}
if(pre==n-1)
{
printf("%c%c\n",a[n-1],a[n]);
return 0;
}
bool bk=0;
for(int i=pre+1;i<=n;i++)
{
if(b[i]=='0' || (a[i]=='1'))
{
bk=1;
break;
}
}
if(bk)a[n]='1';
for(int i=pre;i<=n;i++)printf("%c",a[i]);
printf("\n");
}
return 0;
}
|
F
题目
这道题目的要求比较苛刻，我没有做出来(╯‵□′)╯︵┻━┻。
当然，我们可以把行和列独立，并且行和列一定存在一个最小的循环节。
这些都是字符串的基本理论了。
当然，现在检验行，我们存不存在一种方法能够在$\frac{3}{2}\left\lfloor\log{(n+m)}\right\rfloor$的时间内处理出行的最小循环节。
当然是有的，首先，我们把 $m$ 质因数分解成：$\prod\limits_{i=1}^kp_{i}^{a_{i}}$，我们知道，最小循环节肯定是 $m$ 的因数，那么 $\frac{m}{循环节长度}$ 也就是被分成的节的个数也是个整数，我们尝试找出节的个数的最大值，也就是尝试能不能将字符串分成 $p_{i}^{t}(1≤i≤k,t≤a_{i})$个循环节，然后就可以得到节的个数的最大值的因子，然后乘起来即可。
至于判断能不能将字符串分成 $p_{i}^{t}(1≤i≤k,t≤a_{i})$个循环节，我们转化为一下问题，已知有 $k$ 个数字，如何花最小的步数判断他们相等。
如果 $k=2$ ，那么直接判断。
如果 $k>2$ ，如果 $k$ 是偶数，则仍然只用判断 $1,2$ 号数字，因为 $\frac{k}{2}$ 块肯定检验通过了，如果 $k$ 是奇数，那么设 $y$ 满足$2y+1=k$ ，那么只用比较 $[1,y],[y+1,k-1],[y+2,k]$ ，至于为什么，知道 $kmp$ 找循环节的人应该都知道，不知道的话我也讲不清楚。
至于为什么能过，因为这样的最坏次数是：$2log_{3}{n}=\log_{3}{4}*\log_{2}{n}$（$log$向下取整），显然满足要求。
横竖都做一遍即可。
