T1】记数问题
试计算在区间1 到n 的所有整数中，数字x（0 ≤ x ≤ 9）共出现了多少次？例如，在1到11 中，即在1、2、3、4、5、6、7、8、9、10、11中，数字1 出现了4 次。
其实这个问题也很经典了。。。
别想很复杂，其实打暴力完全OK
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
int n,x;
int main(){
cin>>n>>x;
int ans=0;
for(int i=1;i<=n;i++){
int temp=i;
while(temp){
if(temp%10==x) ans++;
temp/=10;
}
}
cout<<ans<<endl;
return 0;
}
T2】表达式求值
这种题也是经典题
但是这下面是一种很...奇妙的做法
在加法那里处理还没处理完的乘法
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
//简单化的表达式求值
//只有加、乘
/*
stack<long long> num;
stack<char> op;
char a[100001];
int lev(char x){ //计算优先级
if(x=='+') return 1;
if(x=='*') return 2;
return 0;
}
void js(stack<long long> &num,stack<char> &op){
int y=num.top();
num.pop();
int x=num.top();
num.pop();
char xx=op.top();
op.pop();
if(xx=='+') num.push((x+y)%10000);
else num.push((x*y)%10000);
}
*/
//下面的这个写法不知道为什么超时了
//管他的，用一种简单的特殊写法
int last;
char c;
int x,a=0,b=1,sum=0;
int main(){
int i,j;
bool flag=1;
do{
if(cin>>c);
else{
flag=0;
c='+'; //在最后补一个+号
}
if(c>='0'&&c<='9'){
x=x*10+c-'0';
}
else{
a=x;
x=0;
}
if(c=='*'){
last=1;
b=(a*b)%10000; //处理乘数
}
if(c=='+'){
if(last){
a=(a*b)%10000; //a是另一个乘数
sum=(sum+a)%10000;
b=1;
last=0;
}
else sum+=a;
}
}while(flag);
cout<<sum%10000<<endl;
return 0;
}
/*
int main(){
scanf("%s",a+1);
int len=strlen(a+1);
bool flag=0;
long long temp=0;
for(int i=1;i<=len;i++){
if(a[i]>='0'&&a[i]<='9'){
temp=temp*10+a[i]-'0';
flag=true;
}
else{
if(flag){
num.push(temp);
temp=0;
flag=false;
}
while(!op.empty()&&(lev(op.top())>=lev(a[i]))) js(num,op);
op.push(a[i]);
}
}
if(flag){
num.push(temp);
temp=0;
flag=false;
}
while(!op.empty()){
js(num,op);
}
cout<<num.top()%10000<<endl;
return 0;
}
*/
T3 小朋友的数字
这道题涉及到一个细节，取余所导致的结果不同和太大值之间的问题
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1000001;
const int INF=0x3fffffff;
long long res[maxn],d[maxn],dp[maxn];
//d[i]是特征值，res是得分,dp是前i项的和，dp[i]=max(0,dp[i-1])+x
//d[i]=max(d[i-1],dp[i]) res[i]=max(res[i-1],res[i-1]+d[i-1])
long long n,p;
//但是注意结果有20分拿不到，因为数据范围，如果在计算过程种可能会超过Long long,所以必须边算边取模
//但是取模就无法比较最大值，所以不能直接用Max，但是从第二个人开始分数是没有下降的，所以再运算过程种如果超过Longlong就可以去模
//因为res[1]是不超过long long的，所以在运算过程中一旦超过long long就说明是最大的是res[n]，
int main(){
cin>>n>>p;
int x;
dp[0]=0;
for(int i=1;i<=n;i++){
cin>>x;
dp[i]=max(0LL,dp[i-1])+x; //0后面要加LL
if(i==1) {
d[i]=dp[i];
}
else{
d[i]=max(d[i-1],dp[i]);
}
}
res[1]=d[1];
res[2]=d[1]+dp[1];
bool flag=0; //判断在n>=3的过程中，有没有超过long long
for(int i=3;i<=n;i++){
res[i]=max(res[i-1],res[i-1]+d[i-1]);
if(res[i]>1e9){
flag=1;
res[i]=res[i]%p;
}
}
if(flag) cout<<res[n]%p<<endl;
else cout<<max(res[1],res[n])%p<<endl;
return 0;
}
T4】车站分级
想不到是考图吧哈哈哈，但是这道题的连线端点要注意，从小的指向大的，是在从经过的车站之间没停靠的车站都是明确小于的，所以可以连线
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
//这道题是考图，经过大于等于比当前等级的车站，就能总结出比当前等级小的和大的，让小的指向大的
//再拓扑排序，及查找深度，就能够得出至少深度得多少
int n,m;
int to[maxn],in[maxn],mapp[maxn][maxn];
int temp[maxn],vis[maxn];
int main(){
cin>>n>>m;
int num;
for(int i=1;i<=m;i++){
cin>>num;
int x,t=0,l,r;
memset(temp,0,sizeof(temp));
memset(vis,0,sizeof(vis));
memset(to,0,sizeof(to));
for(int j=1;j<=num;j++){
cin>>x;
if(j==1) l=x;
if(j==num) r=x;
temp[j]=x;vis[x]=1;
}
for(int z=l;z<=r;z++){
if(vis[z]==0){
to[++t]=z;
}
}
//把小的都指向大的
for(int j=1;j<=t;j++){
for(int z=1;z<=num;z++) mapp[to[j]][temp[z]]=1;
}
}
//下面初始化入度
for(int i=1;i<=n;i++){
in[i]=0;
for(int j=1;j<=n;j++) if(mapp[j][i]) in[i]++;
}
int ans=1;
memset(temp,0,sizeof(temp));
while(true){
bool f=0;
for(int i=1;i<=n;i++){
temp[i]=in[i];
}
for(int i=1;i<=n;i++){
if(temp[i]==0) {
for(int j=1;j<=n;j++){
if(mapp[i][j]){
mapp[i][j]=0;
in[j]--;
}
}
}
else f=1; //如果没有说明还需要继续循环
}
if(f==0) break; //如果没有更新了就可以退出
ans++;
}
cout<<ans<<endl;
return 0;
}