A - Cutting Out
Codeforces Round #521 (Div. 3)
还没做，待补。
B - Vasya and Books
Educational Codeforces Round 53 (Rated for Div. 2)
题目大意
给出一个栈里书的编号，每次能拿出栈顶的一本书，每次询问拿出某本编号的书需要拿几次。
思路
水题，直接模拟。开一个指针记录取到哪里了。
代码
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
| #include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=200005;
int n,a[maxn],b[maxn],pos[maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
pos[a[i]]=i;
}
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
int now=0;
for(int i=1;i<=n;i++)
{
if(pos[b[i]]>now)
{
printf("%d ",pos[b[i]]-now);
now=pos[b[i]];
}
else printf("0 ");
}
return 0;
}
|
C - Vasya and Robot
Educational Codeforces Round 53 (Rated for Div. 2)
题目大意
给一串命令L、R、D、U，问是否到达终点(x,y)。可以改变任意字串的命令，改变长度为最远的-最近的+1；问最小的长度，或者不行就-1；
思路
最开始理解错题意了，还没改，待补。
D - Frog Jumping
Codeforces Round #521 (Div. 3)
题目大意
水题。青蛙一共跳k次，跳第奇数次时跳到x+a位置，跳第偶数次时跳到x-b位置（x为当前位置），求跳k次之后青蛙的位置。
思路
直接算出来向左跳多远，向右跳多远，两个值带符号相加即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=100005;
int T;
long long a,b,k;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld",&a,&b,&k);
if(k&1) printf("%lld\n",(k/2)*(a-b)+a);
else printf("%lld\n",(k/2)*(a-b));
}
return 0;
}
|
E - Good Array
Codeforces Round #521 (Div. 3)
题目大意
有n个数，现在要去掉某个位置的数，使得剩下的序列钟当且仅当有一个数是其他所有数的和。独立检查所有项，输出答案个数和所有符合条件可以去掉的位置编号。
思路
预处理出3个值，前缀和、从左到右的前缀最大值、从右到左的后缀最大值，这样我们每次查询的时候都可以O(1)完成检查。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=200005;
long long n,a[maxn],mx1[maxn],mx2[maxn],sum[maxn],ans[maxn],cnt=0;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
for(int i=1;i<=n;i++) mx1[i]=max(mx1[i-1],a[i]);
for(int i=n;i>=0;i--) mx2[i]=max(mx2[i+1],a[i]);
for(int i=1;i<=n;i++)
{
long long tx=max(mx1[i-1],mx2[i+1]);
long long ss=sum[n]-a[i]-tx;
if(tx==ss) ans[++cnt]=i;
}
printf("%lld\n",cnt);
for(int i=1;i<=cnt;i++) printf("%lld ",ans[i]);
return 0;
}
|
F - Disturbed People
Codeforces Round #521 (Div. 3)
题目大意
对于一个给定的长度为n的01序列
a1,a2,...,an
如果存在
1<i<n
满足
ai−1=ai+1=1,ai=0
那么这个序列是不优美的,求最少需要将多少个1变为0,使得原序列变为优美的序列。
思路
贪心。如果遇到一个值为0的位置，两边的值都是1，那就要把右边的变成0以满足条件。并且显然这是最优的。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=100005;
int n,a[maxn],ans=0;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=2;i<=n;i++)
{
if(!a[i]&&a[i-1]&&a[i+1])
{
a[i+1]=0;
ans++;
}
}
printf("%d\n",ans);
return 0;
}
|
G - Diverse Substring
Educational Codeforces Round 53 (Rated for Div. 2)
题目大意
找一个字符串的子串中有没有任何字母个数不超过n/2的子串，有就输出，没有就输出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
| #include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=1005;
char str[maxn],s[maxn],ch[maxn];
int n,cnt[maxn];
int main()
{
scanf("%d",&n);
scanf("%s",str+1);
for(int i=1;i<=n;i++)
{
memset(ch,0,sizeof(ch));
memset(cnt,0,sizeof(cnt));
int k=0,mx=0;
for(int j=i;j<=n;j++)
{
s[++k]=str[j];
cnt[str[j]]++;
mx=max(mx,cnt[str[j]]);
if(mx<=(double)k/2.0)
{
printf("YES\n");
for(int p=1;p<=k;p++) printf("%c",s[p]);
return 0;
}
}
}
printf("NO\n");
return 0;
}
|
H - Berland Fair
Educational Codeforces Round 53 (Rated for Div. 2)
题目大意
一个博览会有n个摊位，这些摊位围成一个圆圈，第i个摊位糖果的价格为ai，每个摊位都有无限数量的糖果出售。
有一个人带了T块钱去参观，他从1号摊位开始，依次顺时针参观，每到一个摊位，只要买得起，就买一个糖果。求他到一个糖果都买不起的时候，一共买了多少个糖果。
思路
想试一下暴力能不能过，然后优化了一下：每逛完一圈，就统计还可以完全相同地重复逛多少圈，然后就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
| #include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=200005;
long long n,money,a[maxn],ini=0,cnt=0,ans=0;
int main()
{
scanf("%lld%lld",&n,&money);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
bool flag=true;
while(flag)
{
cnt=0;ini=0;flag=false;
for(int i=1;i<=n;i++)
{
if(a[i]<=money-ini)
{
ini+=a[i];
cnt++;
flag=true;
}
}
if(!ini) break;
ans+=cnt*(money/ini);
money-=ini*(money/ini);
}
printf("%lld\n",ans);
return 0;
}
|
总结
8道题明显感觉自己英语水平和算法水平都有点不小的问题。还有就是开题顺序一定要找对，不要一直纠缠在一道没有开对的题上。
