打了那么多cf(cross fire)，这才第一次打了高端cf(codeforces)……感觉2个小时确实有点紧，很考验选手临危不乱的心态，还有读题一定要快，结合着样例反推题意很有效果。
A. Erasing Zeroes
题目链接
题目原文
题目大意
给出一个01串，求最少删除多少个0，保证字符串中所有的1都是相邻的。
思路
模拟。假设当前位i是1，上一个1的位置是j，那么中间就有i-j-1个0。所以开一个变量记录上一个1的位置，不断累加答案即可。
代码
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
| #include < cstdio >
#include < cstring >
#include < algorithm >
using namespace std;
const int maxn=105;
char str[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(str,0,sizeof(str));
scanf("%s",str+1);
int n=strlen(str+1);
bool f=false;int last=0,ans=0;
for(int i=1;i<=n;i++)
{
if(str[i]=='1')
{
if(!f)
{
f=true;
last=i;
}
else
{
ans+=(i-last-1);
last=i;
}
}
}
printf("%d\n",ans);
}
return 0;
}
|
B. National Project
题目链接
题目原文
题目大意
给出要修的路的长度n，能修出好路的周期时间g，不能修出好路的周期时间b。现在从能修出好路的周期开始，问在保证修的所有路中好路的比例要大于或等于一半的条件下，至少需要多少天。
思路
我用的二分答案，然后尽量在能修出好路的周期时间里修，看是否满足条件
代码
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
| #include < cstdio >
#include < cstring >
#include < algorithm >
using namespace std;
const int maxn=200005;
long long n,g,b,T;
int main()
{
#ifdef lemon
freopen("B.txt","r",stdin);
#endif
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld%lld",&n,&g,&b);
long long left=n,right=1e18,ans=-1;
while(left<=right)
{
long long mid=(left+right)>>1;
long long cc=mid/(b+g);
long long res=mid%(b+g);
long long gd=g*cc+min(res,g);
long long bd=b*cc+max(0ll,res-g);
long long temp=mid-n;
if(bd-temp<0)
{
gd+=(bd-temp);
bd=0;
}
else bd-=temp;
bool flag=false;
long long tot=gd+bd;
if((tot+1)/2<=gd) flag=true;
if(flag) ans=mid,right=mid-1;
else left=mid+1;
}
printf("%lld\n",ans);
}
return 0;
}
|
C. Perfect Keyboard
题目链接
题目原文
题目大意
有一个键盘，只有一行26个小写字母。现在一个人想每次只按相邻的两个键，比如说这次按了pos位置的键，下一次只能按pos-1或者pos+1位置的键。现在给出一个字符串，问能不能通过这样的方式按出，如果能，请输出键盘布局。
思路
搜索。直接上dfs完。
代码
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
| #include < cstdio >
#include < cstring >
#include < algorithm >
using namespace std;
const int maxn=205;
char str[maxn],ans[505];
bool vis[maxn],used[maxn];
int n,flag,T;
void dfs(int x,int pos)
{
if(x==n+1)
{
flag=1;
return;
}
if(vis[pos+1]&&ans[pos+1]==str[x]) dfs(x+1,pos+1);
if(vis[pos-1]&&ans[pos-1]==str[x]) dfs(x+1,pos-1);
if((!vis[pos+1])&&(!used[str[x]]))
{
vis[pos+1]=true;
ans[pos+1]=str[x];
used[str[x]]=true;
dfs(x+1,pos+1);
if(flag!=-1) return;
vis[pos+1]=false;
used[str[x]]=false;
}
if((!vis[pos-1])&&(!used[str[x]]))
{
vis[pos-1]=true;
ans[pos-1]=str[x];
used[str[x]]=true;
dfs(x+1,pos-1);
if(flag!=-1) return;
vis[pos-1]=false;
used[str[x]]=false;
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
memset(str,0,sizeof(str));
memset(ans,0,sizeof(ans));
memset(vis,false,sizeof(vis));
memset(used,false,sizeof(used));
scanf("%s",str+1);
n=strlen(str+1);
flag=-1;
ans[250]=str[1];
vis[250]=true;used[str[1]]=true;
dfs(2,250);
if(flag==-1)
{
printf("NO\n");
continue;
}
printf("YES\n");
int now=250,left=250,right=250;
while(vis[now+1]) now++,right=now;
now=250;
while(vis[now-1]) now--,left=now;
for(int i=left;i<=right;i++) printf("%c",ans[i]);
for(int i='a';i<='z';i++) if(!used[i]) printf("%c",i);
printf("\n");
}
return 0;
}
|
D. Fill The Bag
题目链接
题目原文
题目大意
给出一个数字n和m个数，这m个数都是2的幂次方。
现在每次操作你可以把m个数中的一个平均地一分为2，比如32 操作一次得到两个16，再操作一次就是4个8，现在问最少要操作多少次，可以在操作后把这些数字恰好凑为n。如果无解请输出-1。
思路
比赛的时候只有20分钟了，思路比较混乱，刚预处理出来比赛就结束了。
首先如果这m个数之和是大于或者等于n的，那么一定有解，反之一定无解，可以通过数的二进制表示来证明。
如果有解的话，我们先预处理出这m个数所对应的二进制位并存入cnt数组。然后我们去找n的二进制下为1的位置i是否在m个数存在（检测cnt数组即可），若存在，那么我们就不用拆了。若不存在，那么我们就拆第i+1个数，并且ans++，依次做下去即可。
代码
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
| #include < cstdio >
#include < cstring >
#include < algorithm >
using namespace std;
const int maxn=100005;
long long n,m,a[maxn],cnt[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(cnt,0,sizeof(cnt));
long long ans=0,sum=0;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
for(long long j=0;;j++)
{
if((1ll<<j)&a[i])
{
cnt[j]++;
break;
}
}
}
if(sum<n)
{
printf("-1\n");
continue;
}
for(long long i=0;i<63;i++)
{
long long now=(n>>i)&1;
cnt[i]-=now;
if(cnt[i]>=2) cnt[i+1]+=cnt[i]/2;
if(cnt[i]<0) cnt[i+1]--,ans++;
}
printf("%lld\n",ans);
}
return 0;
}
|
E. Erase Subsequences
题目链接
题目原文
题目大意
给定字符串s1和s2，问能否用至多两个s1的非重叠子序列相加构造出s2
思路
和寒假集训第五天的H题相似而略有不同。上次的题是刚好拼出，两个子序列长度相加等于字符串总长，这道题要求存在子序列即可（只要长度等于s2即可）。所以只需要将转移改成位置就好了。
代码
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
| #include < cstdio >
#include < cstring >
#include < algorithm >
using namespace std;
const int maxn=405;
const int inf=0x7f7f7f7f;
char s1[maxn],s2[maxn],s3[maxn];
int T,nxt[maxn][26],f[maxn][maxn];
int main()
{
scanf("%d",&T);
while(T--)
{
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
scanf("%s%s",s1+1,s2+1);
int l1=strlen(s1+1),l2=strlen(s2+1);
for(int i=0;i<26;i++) nxt[l1][i]=inf;
for(int i=l1;i;i--)
{
for(int j=0;j<26;j++) nxt[i-1][j]=nxt[i][j];
nxt[i-1][s1[i]-'a']=i;
}
bool flag=false;
for(int i=1;i<=l2;i++)
{
int l3=l2-i;
for(int j=i+1;j<=l2;j++) s3[j-i]=s2[j];
f[0][0]=0;
for(int j=0;j<=i;j++)
for(int p=0;p<=l3;p++)
{
if(!j&&!p) continue;
f[j][p]=inf;
if(j&&f[j-1][p]!=inf) f[j][p]=min(f[j][p],nxt[f[j-1][p]][s2[j]-'a']);
if(p&&f[j][p-1]!=inf) f[j][p]=min(f[j][p],nxt[f[j][p-1]][s3[p]-'a']);
}
if(f[i][l3]<=l1) flag=true;
if(flag) break;
}
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}
|
剩下的等我做出来再补。
