专栏首页小樱的经验随笔ECJTUACM16 Winter vacation training #4 题解&源码

ECJTUACM16 Winter vacation training #4 题解&源码

https://vjudge.net/contest/149692#overview 这周一VJ比赛,题解&源码已完成!

A.........................................................................................

题目链接→Codeforces Problem 712A Memory and Crow

【题意】 有n个数b1, b2, ..., bn

a1, a2, ..., an是通过等式ai = bi - bi + 1 + bi + 2 - bi + 3....(±)bn得到的

现给你a1, a2, ..., an这n个数,问b1, b2, ..., bn是多少

详解请参看我的随笔!下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int n,a,b;
 6     while(cin>>n)
 7     {
 8         for(int i=1;i<=n;i++)
 9         {
10             cin>>a;
11             if(i>1)
12                 cout<<a+b<<" ";
13             b=a;
14         }
15         cout<<a<<endl;
16     }
17     return 0;
18 }

B.........................................................................................

题目链接→Codeforces Problem 708A Letters Cyclic Shift

【题意】 从仅有小写字母组成的字符串s中挑选出一个非空子串

将该子串中的每个字母均替换成前一个字母,如'b'换成'a','c'换成'b',以此类推,特别的,'a'要换成'z'

问经过一次转换之后,字典序最小的字符串s为多少

详解请参看我的随笔!下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int i,k=0;
 6     char s[100005];
 7     gets(s);
 8     int len=strlen(s);
 9     for(i=0;s[i]!='\0';i++)
10         if(s[i]!='a')
11             break;
12     for(;s[i]!='\0';i++)
13     {
14         if(s[i]=='a')
15             break;
16         s[i]--;
17         k++;
18     }
19     if(!k)
20         s[strlen(s)-1]='z';
21     puts(s);
22     return 0;
23 }

C.........................................................................................

题目链接→Codeforces Problem 712B Memory and Trident

【题意】 Memory从二维坐标系的原点出发,按字符串s的指示运动

R:向右;L:向左;U:向上;D:向下

Memory最终想回到原点,问至少需要改变字符串s中的几个字符

若无论如何改变都无法回到原点,输出"-1"

详解请参看我的随笔!下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     char s[100005];
 6     int len;
 7     int a=0,b=0,c=0,d=0;
 8     while(gets(s))
 9     {
10         len=strlen(s);
11     if(len%2==1)
12     {
13         printf("-1\n");
14     }
15     else
16     {
17         for(int i=0;s[i]!='\0';i++)
18         {
19             if(s[i]=='U')
20                 a++;
21             else if(s[i]=='D')
22                 b++;
23                 else if(s[i]=='L')
24                     c++;
25                 else if(s[i]=='R')
26                     d++;
27         }
28          printf("%d\n",(abs(a-b)+abs(c-d))/2);
29          a=b=c=d=0;
30     }
31     }
32     return 0;
33 }

D.........................................................................................

题目链接→Codeforces Problem 712C Memory and De-Evolution

【题意】 现有边长为x的等边三角形,Memory想要将其变成边长为y的等边三角形

现规定Memory每秒能够改变一条边的大小,但要保证改变后的三条边仍能构成一个三角形

问,最少需要多少时间才能变为边长为y的等边三角形

详解请参看我的随笔!下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int s[3];
 6     int x,y,i;
 7     while(cin>>x>>y)
 8     {
 9         int ans=0;
10         s[0]=s[1]=s[2]=y;
11         for(i=0;s[0]<x||s[1]<x||s[2]<x;i++)
12         {
13             s[0]=s[1]+s[2]-1;
14             sort(s,s+3);
15             ans++;
16         }
17         cout<<ans<<endl;
18     }
19     return 0;
20 }

E.........................................................................................

题目链接→http://poj.org/problem?id=2352

题意:

就是求每个小星星左小角的星星的个数。坐标按照Y升序,Y相同X升序的顺序给出
由于y轴已经排好序,可以按照x坐标建立一维树状数组

详解请参看我的随笔!下面给出AC代码:

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int MAXN=32005;
 4 const int MINN=15005;
 5 int tree[MAXN];//下标为横坐标
 6 int level[MINN];//下标为等级数
 7 /*int lowerbit(int x)
 8 {
 9     return x&-x;
10 }*/
11 void add(int k,int num)
12 {
13     while(k<=MAXN)
14     {
15         tree[k]+=num;
16         k+=k&-k;
17     }
18 }
19 int read(int k)//1~k的区间和
20 {
21     int sum=0;
22     while(k)
23     {
24         sum+=tree[k];
25         k-=k&-k;
26     }
27     return sum;
28 }
29 int main()
30 {
31     int n,x,y,i;
32     memset(tree,0,sizeof(tree));
33     memset(level,0,sizeof(level));
34     while(scanf("%d",&n)!=EOF)
35     {
36         for(i=1;i<=n;i++)
37         {
38             scanf("%d%d",&x,&y);
39             int temp=read(x+1);//加入x+1,是为了避免0,X是可能为0的
40             level[temp]++;
41             add(x+1,1);
42         }
43         for(i=0;i<n;i++)
44             printf("%d\n",level[i]);
45     }
46     return 0;
47 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2017广东工业大学程序设计竞赛决赛 题解&源码(A,数学解方程,B,贪心博弈,C,递归,D,水,E,贪心,面试题,F,贪心,枚举,LCA,G,dp,记忆化搜索,H,思维题)

    心得: 这比赛真的是不要不要的,pending了一下午,也不知道对错,直接做过去就是了,也没有管太多! Problem A: 两只老虎 Description ...

    Angel_Kitty
  • Kruscal(最小生成树)算法模版

    1 const int maxn=400;//最大点数 2 const int maxm=10000;//最大边数 3 int n,m;//n表示点数,m...

    Angel_Kitty
  • 并查集(个人模版)

    并查集: 1 int find(int a) 2 { 3 int r=a; 4 while(f[r]!=r) 5 ...

    Angel_Kitty
  • 1089 狼人杀-简单版 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 快乐AC三道题---第一周

    我们要解决的无非是是否把下一个元素加入,是否开始维护一个新的子段。我们开一个数组b[] , 记录b[i],表示以a[i]结尾的全部子段中 最大的那个的 和。 这...

    用户7727433
  • 算法练习(4)-数组去重合并

    这是日常工程中,经常会遇到的场景,拿到2个list,里面有重复元素,要求去重合并最终排序输出。

    菩提树下的杨过
  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常
  • aabb

    Vincent-yuan
  • 数组问题

    输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字...

    大学里的混子
  • POJ Test for Job(DAG上拓扑排序)

           题意是给了n个点,m条边(单向边),然后每个点都有一个点权(存在负权),问从入度为0的点开始到出度为0的点,最大的权值和为多少。

    Ch_Zaqdt

扫码关注云+社区

领取腾讯云代金券