1.结果填空：青蛙爬井
有一口深度为 high 米的水井，井底有一只青蛙，它每天白天能够沿井壁向上爬 up 米，夜里则顺井壁向下滑 down 米。
若青蛙从某个早晨开始向外爬，当 high = 60405，up = 105，dow = 35，计算青蛙多少天能够爬出井口？
#include<bits/stdc++.h>
using namespace std;
int main(){
int high = 60405, up = 105, dow = 35;
int day=1,ans=0;
while(ans<=high){
ans+=up;
if(ans>=high) break;
ans-=dow;
day++;
}
cout<<ans<<endl;
}
2.结果填空 倍数
一天蒜头君在想，[l,r]之间有多少个数字是 d 的倍数呢？
但是区间 [l,r]是 d 的倍数的数字太多，于是聪明的蒜头君便找到了你。
当 l = 1032，r = 12302135942453，d = 234，d 的倍数有多少个呢？
直接做肯定超时
1 到 n 有多少个是 m 倍数，个数为 n/m
#include<bits/stdc++.h>
using namespace std;
int main(){
long long int l = 1032, r = 12302135942453l, d = 234;
long long int ans = r/d-(l-1)/d;
cout<<ans<<endl;
}
3.最短路
给定一个 nn 点 mm 边的有向带权图表示一座城市，起点为 11 。送餐小哥需要给 nn 个客户送外卖，第 ii 个客户的家在第 ii 号点。由于他的车子容量很小，所以一次只能容纳一份外卖，所以送达外卖之后就要回到起点取新的外卖送下一单，直到全部送到位置。
有向图保证联通，外卖小哥一定走的最短路。
求送餐小哥走的总路程。
输入格式
第一行一个整数 TT，表示数据组数。
对于每组数据，第一行两个整数 nn 和 mm 。
接下来 mm 行，每行三个整数 u_i,v_i,c_i表示每条有向边。
输出格式
对于每组数据，输出一行一个整数表示答案。
保证答案在 long long 范围内。
样例输入
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
样例输出
46
210
50%
#include<bits/stdc++.h>
using namespace std;
const int N = 20010;
const int M = 80010;
long long int n, m;
long long int head[N], nex[M], to[M], val[M], ce,u[N],v[N],w[N];
void add(long long int u,long long int v,long long int w) {
to[++ce] =v; nex[ce] = head[u]; head[u] = ce; val[ce] = w;
}
long long int d[N];
bool used[N];
queue<int> q;
void spfa(int s) {
memset(d, 1000000007, sizeof d);
d[s] = 0;
q.push(s);
used[s] = true;
while(!q.empty()) {
int u = q.front(); q.pop();
used[u] = false;
for(int i=head[u]; i; i=nex[i]) {
int v = to[i], w = val[i];
if(d[u] + w < d[v]) {
d[v] = d[u] + w;
if(!used[v]) {
used[v] = true;
q.push(v);
}
}
}
}
}
int main(){
int qq;
cin>>qq;
while(qq--){
cin>>n>>m;
ce=0;
for(int i=1;i<=n;i++) head[i]=0;
for(int i=0;i<m;i++){
cin>>u[i]>>v[i]>>w[i];
add(u[i], v[i], w[i]);
}
memset(used,false,sizeof(used));
spfa(1);
long long int ans=0;
for(int i=1;i<=n;i++) ans+=d[i];
ce=0;
for(int i=1;i<=n;i++) head[i]=0;
for(int i=0;i<m;i++){
add(v[i],u[i], w[i]);
}
memset(used,false,sizeof(used));
spfa(1);
for(int i=n;i>=1;i--) ans+=d[i];
printf("%d\n", ans);
}
return 0;
}
4.后缀字符串
一天蒜头君得到 n个字符串Si,每个字符串的长度都不超过 10.
蒜头君在想，在这 n个字符串中，以 Si为后缀的字符串有多少个呢？
输入格式
第一行输入一个整数 n。
接下来 n 行，每行输入一个字符串 Si 。
输出格式
输出 n个整数，第 i个整数表示以Si为后缀的字符串的个数。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 100005;
string a[N];
int main() {
map<string, int>mp;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
for (int j=0;j<a[i].size();j++) {
mp[a[i].substr(j)]++;
}
}
for (int i = 0; i < n; i++) {
cout << mp[a[i]] << endl;
}
return 0;
}
5.非递归二叉树的中序遍历
给定一个层数小于等于10的二叉树，输出对其中序遍历的节点名序列。
输入包括一行，为由空格分隔开的各节点，按照二叉树的分层遍历顺序给出，每个节点形式如X(Y,num)，X表示该节点，Y表示父节点，num为0,1,2中的一个，0 表示根节点，1表示为父节点的左子节点，2表示为父节点的右子节点。输出为一行，为中序遍历的结果。
输入
A(0,0) B(A,1) C(A,2) D(B,1) E(B,2) F(C,1) G(D,1) H(D,2)
输出
G D H B E A F C
#include<iostream>
#include<map>
#include<stack>
using namespace std;
struct btNode{
char c;
btNode *left, *right;
btNode(char ch) : c(ch), left(NULL), right(NULL){}
};
bool firstFlag;
void inOrder(btNode *root){
stack<btNode*> sk;
while(root || !sk.empty()){
while(root){
sk.push(root);
root = root->left;
}
if(!sk.empty()){
root = sk.top();
sk.pop();
if(firstFlag){
firstFlag = 0;
}else{
putchar(' ');
}
printf("%c", root->c);
root = root->right;
}
}
}
int main(){
char ch, fa, lr;
map<char, btNode*> mp;
btNode *root, *p, *q;
while(scanf("%c(%c,%c) ", &ch, &fa, &lr) == 3){
if(fa == '0'){
root = new btNode(ch);
mp[ch] = root;
}else{
p = mp[fa];
q = new btNode(ch);
mp[ch] = q;
if(lr == '1'){
p->left = q;
}else{
p->right = q;
}
}
}
firstFlag=1;
inOrder(root);
cout << endl;
}