共计 5361 个字符，预计需要花费 14 分钟才能阅读完成。
一、反复计数
题目
在一个无限的正整数序列中，有些数会多次重复呈现。请你统计每个数的呈现次数，而后按数字在序列中第一次呈现的地位程序输入数及其次数。
输出格局:
第 1 行，1 个整数 N，示意整数的个数，(1≤N≤50000)。
第 2 行，N 个正整数，每个整数 x 都满足 1 ≤ x ≤2000000000。
输入格局:
若干行，每行两个用一个空格隔开的数，第一个是数列中呈现的数，第二个是该数在序列中呈现的次数。
输出样例:
在这里给出一组输出。例如：
12
8 2 8 2 2 11 1 1 8 1 13 13
输入样例:
在这里给出相应的输入。例如：
8 3
2 3
11 1
1 3
13 2
解题思路
题目比较简单，我是先建设了一个构造体来示意这个数与它呈现的次数，想到的第一种办法就是每次读入一个数就对构造体数组进行遍历，如果存在该数 count 就 + 1 否则就将这个数退出到构造体数组中，尽管我晓得这样很大概率会超时，但我还是吧这种办法打了下来碰碰运气（过后并不会 map，呜呜呜）第一次并没有通过果然被卡了工夫，然而改了改代码就过了，哈哈哈。
参考代码
#include<stdio.h>
#define MAX 50001
struct list{
int num;
int count;
};
int t=1;
int main(){struct list a[MAX];
int N;
scanf("%d",&N);
int i,j;
int x;
scanf("%d",&x);
a[0].num=x;
a[0].count=1;
for(i=1;i<N;i++)
{scanf("%d",&x);
for(j=0;j<t;j++)
{if(a[j].num==x) {a[j].count++; break; }
}
if(j==t)
{
t++;
a[j].num=x;
a[j].count=1;
}
}
for(i=0;i<t;i++){printf("%d %d",a[i].num,a[i].count);
if(i!=t-1) printf("\n");
}
return 0;
}
二、报数游戏
题目
n 集体围成一圈，从 1 开始顺次编号，做报数游戏。现指定从第 1 集体开始报数，报数到第 m 集体时，该人出圈，而后从其下一个人从新开始报数，仍是报数到第 m 集体出圈，如此反复上来，直到所有人都出圈。总人数有余 m 时将循环报数。请输入所有人出圈的程序。
输出格局:
一行，两个整数 n 和 m。n 示意游戏的人数，m 示意报数出圈的数字，1≤n≤50000，1≤m≤100.
输入格局:
一行，n 个用空格分隔的整数，示意所有人出圈的程序
输出样例:
在这里给出一组输出。例如：
5 2输入样例:
在这里给出相应的输入。例如：
2 4 1 5 3解题思路
这个题就是一个典型的约瑟夫环问题，在大一上初学 C 语言的时候在慕课上就做过相似的作业不过那个是叫猴子选大王。这个题的思路也很简略就是建设一个数组来保留每个人的编号，之后每次出队都将该编号输入并将其删除（就是把前面的所有编号顺次前移），这样最终数组中剩下的一个就是最初出圈的（也就是大王）。
参考代码
#include<stdio.h>
int main()
{
int n;
int m;
int i,j=0;
long N[500001];
scanf("%d %d",&n,&m);
for(i=0;i<n;i++)
{N[i]=i+1;
}
while(n>1)
{j=(j+m-1)%n;
printf("%ld",N[j]);
for(i=j;i<n-1;i++)
{N[i]=N[i+1];
}
n--;
}
printf("%ld\n",N[0]);
return 0;
}
三、算数表达式计算
题目
工作: 计算算术表达式的值。
算术表达式按中断给出，以 = 号完结，包含 +,-,/ 四种运算和 (、) 分隔符。运算数的范畴是非负整数，没有正负符号，小于等于 109。
计算过程中, 如果呈现除数为 0 的状况, 表达式的后果为”NaN”; 如果两头后果超出 32 位有符号整型范畴, 仍按整型计算，不用非凡解决。输出保障表达式正确。
输出格局:
一行，包含 1 个算术表达式。算术表达式的长度小于等于 1000。
输入格局:
一行，算术表达式的值。
输出样例:
在这里给出一组输出。例如：
(1+30)/3=
输入样例:
在这里给出相应的输入。例如：
10
解题思路
这个题是谷老师提前走漏给咱们的所以我也是提前打了一下这个题还去特意温习了一下中断表达式转后缀表达式，温习温习发现上课的时候讲的是变转后缀边计算，思路就是建设两个栈来保留操作数和操作符，开始时将中断表达式保留到一个字符串当中，因为题目曾经明确所输出的肯定是非法的所以不必思考别的接下来就是从左一次读表达式如果是操作数就入栈，如果是操作符就须要依据操作符栈来决定下一步的操作，如果栈空则入栈，否则判断栈顶元素与以后元素的优先级如果以后元素优先级高则入栈（‘(’的优先级最高），如果是‘)’则将元素安抚栈中的运算符一次出栈并计算操作数，直至遇到‘(’，如果以后运算符优先级小于等于栈顶运算符等级则先对该运算符进行运算（不入栈）。读完之后如果运算符栈不空则将其全副出栈并计算即可。
参考代码
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<string.h>
#include<iostream>
#define L 1001
using namespace std;
stack<int> Stacknum;
stack<char> Stackchar;
void Fun(char e){
int temp1,temp2;
temp1=Stacknum.top(); Stacknum.pop();
temp2=Stacknum.top(); Stacknum.pop();
switch(e)
{case '+' : Stacknum.push(temp2+temp1); break;
case '-' : Stacknum.push(temp2-temp1); break;
case '*' : Stacknum.push(temp2*temp1); break;
case '/' :
if(temp1==0) {printf("NaN");exit(0);}
else
Stacknum.push(temp2/temp1); break;
}
}
int main(){char str[L];
scanf("%s",str);
int i;
int temp;
for(i=0;str[i]!='=';i++)
{if(str[i]>='0'&&str[i]<='9')
{temp=str[i]-'0';
while(str[i+1]!='=')
{if(str[i+1]>='0'&&str[i]<='9')
{temp=temp*10+str[i+1]-'0';
i++;
}
else break;
}
Stacknum.push(temp);
}
else
{
char tmp;
if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='('||str[i]==')')
{switch(str[i])
{
case '+' :
if(Stackchar.empty()) {Stackchar.push('+');break;}
tmp=Stackchar.top();
if(tmp!='+'&&tmp!='-'&&tmp!='*'&&tmp!='/') Stackchar.push('+');
else
{while(!Stackchar.empty()&&tmp!='(')
{Stackchar.pop();
Fun(tmp);
if(Stackchar.empty()) break;
else tmp=Stackchar.top();}
Stackchar.push('+');
}
break;
case '-' :
if(Stackchar.empty()) {Stackchar.push('-');break;}
tmp=Stackchar.top();
if(tmp!='+'&&tmp!='-'&&tmp!='*'&&tmp!='/') Stackchar.push('-');
else
{while(!Stackchar.empty()&&tmp!='(')
{Stackchar.pop();
Fun(tmp);
if(Stackchar.empty()) break;
else tmp=Stackchar.top();}
Stackchar.push('-');
}
break;
case '*' :
if(Stackchar.empty()) {Stackchar.push('*');break;}
tmp=Stackchar.top();
if(tmp!='*'&&tmp!='/') Stackchar.push('*');
else
{while((tmp=='*'||tmp=='/')&&tmp!='(')
{Stackchar.pop();
Fun(tmp);
if(Stackchar.empty()) break;
else tmp=Stackchar.top();}
Stackchar.push('*');
}
break;
case '/' :
if(Stackchar.empty()) {Stackchar.push('/');break;}
tmp=Stackchar.top();
if(tmp!='*'&&tmp!='/') Stackchar.push('/');
else
{while((tmp=='*'||tmp=='/')&&tmp!='(')
{Stackchar.pop();
Fun(tmp);
if(Stackchar.empty()) break;
else tmp=Stackchar.top();}
Stackchar.push('/');
}
break;
case '(' :
Stackchar.push('(');
break;
case ')' :
tmp=Stackchar.top();
while(tmp!='(')
{Stackchar.pop();
Fun(tmp);
tmp=Stackchar.top();}
Stackchar.pop();
break;
}
}
}
}
while(!Stackchar.empty())
{char tmp=Stackchar.top();
Stackchar.pop();
Fun(tmp);
}
temp=Stacknum.top();
printf("%d",temp);
return 0;
}
四、最青睐的序列
题目
小唐这段时间在钻研序列。拿来 N 个整数的序列，他给序列中的每个整数都赋予一个青睐值。青睐值也是整数，有正有负，越大表明越喜爱。他想晓得，如何从序列中间断取最多 m 个数，他取得青睐值最大。1≤N≤500000，1≤m≤N。
输出格局:
第一行是两个整数 N,m。别离代表序列中数的个数以及能取的最多个数。
第二行用空格隔开的 N 个整数，第 i 个整数 Li 代表他对第 i 个数的青睐值。│Li│≤1000
输入格局:
一行，三个数，示意取得最大青睐值，及第一个取最大青睐值的区间。
输出样例:
在这里给出一组输出。例如：
5 2
1 4 5 2 3
输入样例:
在这里给出相应的输入。例如：
9 2 3
解题思路
因为在之前的分割中做过前缀和的题所以看到这道题首先想到了用前缀和来保留青睐值的和，这样能节俭一些工夫，第一次做的时候并没有看清楚题意，认为是找 m 个数的最大区间，还认为为啥这么简略就把代码实现了一遍，后果总是有几个测试点过不去，等到课后做题的时候才发现是最大 m 个，因为青睐值也可能是负值，在课上听了同学是用枯燥队列做的，谷老师心里的解法也是枯燥队列，而且枯燥队列就是用来解决求区间的最大最小值问题的，所以我学习了同学得思路与代码，创立了一个双端队列来实现，要实现枯燥队列须要保护它的枯燥性与区间长度。
参考代码
#include<stdio.h>
#include<iostream>
#include<deque>
using namespace std;
deque<int> mon_deq;
int main(){long long sum[500000];
int left,right;// 左右端点
long long max=0;// 最大青睐值
int N,m;
scanf("%d%d",&N,&m);
int i,j;
sum[0]=0;
for(i=1;i<=N;i++)
{scanf("%lld",&sum[i]);
sum[i]+=sum[i-1];
}
mon_deq.push_front(0);
for(i=1;i<=N;i++)
{while(!mon_deq.empty()&&sum[mon_deq.front()]>sum[i])
mon_deq.pop_front();
mon_deq.push_front(i);
while(!mon_deq.empty()&&(i-mon_deq.back()>m))
mon_deq.pop_back();
if(max<sum[i]-sum[mon_deq.back()])
{max=sum[i]-sum[mon_deq.back()];
left=mon_deq.back()+1;
right=i;
}
}
printf("%lld %d %d",max,left,right);
return 0;
}
