2020-2021:teams:no_morning_training:week1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:week1 [2020/05/09 00:13] 发源于 [冯宇扬] |
2020-2021:teams:no_morning_training:week1 [2020/06/05 15:27] (当前版本) shaco ↷ 链接因页面移动而自动修正 |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| ===== 王瑞琦 ===== | ===== 王瑞琦 ===== | ||
| - | ---- | ||
| **专题** | **专题** | ||
| - 树 | - 树 | ||
| 行 21: | 行 20: | ||
| - 没打 | - 没打 | ||
| - | ---- | ||
| ===== 常程 ===== | ===== 常程 ===== | ||
| - | ---- | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| - | * [[2020-2021:teams:no_morning_training:尺取法|尺取法]] | + | * [[2020-2021:teams:no_morning_training:shaco:知识点:基础:尺取法|尺取法]] |
| - | * [[2020-2021:teams:no_morning_training:前缀和|前缀和]] | + | * [[2020-2021:teams:no_morning_training:shaco:知识点:基础:前缀和|前缀和]] |
| （由于我太菜了所以写一点基础的） | （由于我太菜了所以写一点基础的） | ||
| === 比赛 === | === 比赛 === | ||
| 行 39: | 行 36: | ||
| ==== 王瑞琦 ==== | ==== 王瑞琦 ==== | ||
| - | 给出一个以=结尾的包含+-*/%()的式子，按运算规则计算其值。 | + | 一个模板题，[[2020-2021:teams:no_morning_training:表达式的计算]] |
| - | + | ||
| - | 给出的式子是中缀表达式，将其转化为后缀表达式求解。 | + | |
| - | + | ||
| - | 转换方法： | + | |
| - | + | ||
| - | 用队列存储运算符，栈辅助处理。对每个字符，规则如下： | + | |
| - | + | ||
| - | 1）若为数字，直接入队（当然，多位数字要提前处理一下） | + | |
| - | + | ||
| - | 2）若为运算符： | + | |
| - | + | ||
| - | 1.栈为空直接入栈 | + | |
| - | + | ||
| - | 2.优先级大于栈顶元素入栈 | + | |
| - | + | ||
| - | 3.优先级小于等于栈顶元素，则栈顶元素出栈入队，直到优先级大于栈顶元素。 | + | |
| - | + | ||
| - | 3）若为（，直接入栈 | + | |
| - | + | ||
| - | 4）若为），栈顶元素出栈入队，直到（，两个括号不入队。 | + | |
| - | + | ||
| - | 计算方法： | + | |
| - | + | ||
| - | 对于一个后缀表达式，用栈辅助计算 | + | |
| - | + | ||
| - | 从左至右扫描，若为数字，直接入栈，若为运算符，则将栈顶两个元素计算，计算结果入栈。 | + | |
| - | + | ||
| - | 直到最后留下一个数字，即为结果。 | + | |
| - | + | ||
| - | #include <stdio.h> | + | |
| - | #include <string.h> | + | |
| - | #include <stdlib.h> | + | |
| - | char stack[500]; | + | |
| - | int queue[500]; | + | |
| - | void calcu(int r,int top) | + | |
| - | { | + | |
| - | switch (stack[top]){ | + | |
| - | case '+':queue[r-1]=queue[r]+queue[r-1];break; | + | |
| - | case '-':queue[r-1]=queue[r-1]-queue[r];break; | + | |
| - | case '*':queue[r-1]=queue[r]*queue[r-1];break; | + | |
| - | case '/':queue[r-1]=queue[r-1]/queue[r];break; | + | |
| - | case '%':queue[r-1]=queue[r-1]%queue[r];break; | + | |
| - | } | + | |
| - | } | + | |
| - | int main() | + | |
| - | { | + | |
| - | char s[500]; | + | |
| - | int pr[300]={0}; | + | |
| - | pr[(int)'+']=pr[(int)'-']=1; | + | |
| - | pr[(int)'*']=pr[(int)'/']=pr[(int)'%']=2; | + | |
| - | pr[(int)'(']=0; | + | |
| - | gets(s); | + | |
| - | int top=0,r=0,i=0; | + | |
| - | while (s[i]!='=') | + | |
| - | { | + | |
| - | if (s[i]>='0'&&s[i]<='9') | + | |
| - | { | + | |
| - | int x=(int)s[i]-48; | + | |
| - | i++; | + | |
| - | while (s[i]>='0'&&s[i]<='9') | + | |
| - | { | + | |
| - | x=x*10+(int)s[i]-48; | + | |
| - | i++; | + | |
| - | } | + | |
| - | queue[++r]=x; | + | |
| - | i--; | + | |
| - | } | + | |
| - | else if (s[i]!='('&&s[i]!=')'&&s[i]!=' '){ | + | |
| - | if (top==0) stack[++top]=s[i]; | + | |
| - | else { | + | |
| - | if (pr[(int)s[i]]>pr[(int)stack[top]]) stack[++top]=s[i]; | + | |
| - | else { | + | |
| - | while (top!=0&&pr[(int)s[i]]<=pr[(int)stack[top]]) calcu(r--,top--); | + | |
| - | stack[++top]=s[i]; | + | |
| - | } | + | |
| - | } | + | |
| - | } | + | |
| - | else if (s[i]=='(') stack[++top]=s[i]; | + | |
| - | else if (s[i]==')') { | + | |
| - | while (stack[top]!='(') calcu(r--,top--); | + | |
| - | top--; | + | |
| - | } | + | |
| - | i++; | + | |
| - | } | + | |
| - | for (int i=top;i>=1;i--) calcu(r--,top--); | + | |
| - | printf("%d",queue[1]); | + | |
| - | return 0; | + | |
| - | } | + | |
| ==== 冯宇扬 ==== | ==== 冯宇扬 ==== | ||
| - | 搓了一道 [[www.luogu.com.cn/problem/P1600|P1600 天天爱跑步]] | + | 搓了一道 [[https://www.luogu.com.cn/problem/P1600|P1600 天天爱跑步]] |
| 发现了绝妙的做法，但是还没有debug出来 | 发现了绝妙的做法，但是还没有debug出来 | ||
| 行 143: | 行 52: | ||
| 将前缀和排序，排序后每两个位置的前缀和之差代表一个原来的区间的和的绝对值(妙啊），同时在这个排序后的前缀和序列中随区间增缩所取的区间和的绝对值也增缩。这样运用尺取法是一个好的选择。 | 将前缀和排序，排序后每两个位置的前缀和之差代表一个原来的区间的和的绝对值(妙啊），同时在这个排序后的前缀和序列中随区间增缩所取的区间和的绝对值也增缩。这样运用尺取法是一个好的选择。 | ||
| - | #include<cstdio> | + | [[2020-2021:teams:no_morning_training:poj2566|代码]] |
| - | #include<algorithm> | + | |
| - | #define INF 0x3f3f3f3f | + | |
| - | using namespace std; | + | |
| - | int n,k,a; | + | |
| - | typedef pair<int,int> unit; | + | |
| - | unit sum[100005]; | + | |
| - | int main() | + | |
| - | { | + | |
| - | while(scanf("%d%d",&n,&k)&&n) | + | |
| - | { | + | |
| - | for(int i=1;i<=n;i++) | + | |
| - | { | + | |
| - | scanf("%d",&a); | + | |
| - | sum[i]=unit(sum[i-1].first+a,i); | + | |
| - | } | + | |
| - | sort(sum+1,sum+1+n); | + | |
| - | for(int i=1;i<=k;i++) | + | |
| - | { | + | |
| - | scanf("%d",&a); | + | |
| - | int t=INF,l,r; | + | |
| - | for(int left=1,right=1;right<=n;right++) | + | |
| - | { | + | |
| - | while(sum[right].first-sum[left].first>a) | + | |
| - | { | + | |
| - | if(sum[right].first-sum[left].first-a<t) | + | |
| - | { | + | |
| - | t=sum[right].first-sum[left].first-a; | + | |
| - | l=sum[left].second; | + | |
| - | r=sum[right].second; | + | |
| - | } | + | |
| - | left++; | + | |
| - | } | + | |
| - | if(a-sum[right].first+sum[left].first<t) | + | |
| - | { | + | |
| - | t=a-sum[right].first+sum[left].first; | + | |
| - | l=sum[left].second; | + | |
| - | r=sum[right].second; | + | |
| - | } | + | |
| - | } | + | |
| - | printf("%d %d %d\n",sum[r].first-sum[l].first,l,r); | + | |
| - | } | + | |
| - | } | + | |
| - | return 0; | + | |
| - | } | + | |
2020-2021/teams/no_morning_training/week1.1588954438.txt.gz · 最后更改: 2020/05/09 00:13 由 发源于
