概览：ABF为签到题，CE模拟，D深搜，G最短路，H双指针
A.提取数字：
注意前导零的情况需要排除，由于组成的数不超过long long范围，所以直接用res承接就好了
#include<iostream>
using namespace std;
long long res;
int main()
{
char c;
while(cin>>c)
if(c>='0' && c<='9')
res=res*10+(c-'0');
cout<<res<<endl;
}
B.保龄球：
map/unordered_map的应用题。
#include<iostream>
#include<unordered_map>
using namespace std;
unordered_map<int,int>ac;
int n,x;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>x,ac[x]=i;
cin>>n;
while(n--)
cin>>x,cout<<ac[x]<<"\n";
}
C.乒乓球：
模拟，见下图解释
#include <iostream>
using namespace std;
int tot[2], now[2], k, k0, tmp[2], mark;//tot代表总比分，now代表当前局数比分，tmp代表两位发球手各自的连续发球数，k0表示当前大局谁发球，k表示当前小回合谁发的球
char c; //0代表‘L’相关操作，1代表‘Z’相关操作
string s;
void oper()//用于一大局结束时的计分与重置
{
k0 ^= 1, k = k0;//当一个数只可能为0或1时，其异或后就是对方，模拟大局结束，发球手对换的情况，同理k=k0要保持发球手的一致
if (now[0] > now[1])
tot[0]++;
else
tot[1]++;
now[1] = tmp[1] = now[0] = tmp[0] = 0;//全部重置
}
int main()
{
cin >> c, k0 = k = (c == 'Z' ? 1 : 0), cin >> s;
for (int i = 0; i < s.size(); i++)
{
c = s[i], tmp[k]++, c == 'L' ? now[0]++ : now[1]++;//统计当前发球手的连续发球次数，以及小分增加
if (now[0] == 10 && now[1] == 10)
mark ^= 1;//mark代表当前进入10:10以后的特殊模式，对应了不同的发球逻辑和胜利逻辑
if (mark)
{
tmp[k] = 0, k ^= 1;//发球是轮流的，所以在mark模式下，每次发球都清空tmp次数，并且交换发球权
if (abs(now[0] - now[1]) > 1)
mark ^= 1, oper();
}
else
{
if (tmp[k] > 1)//只有连续发两个及以上的时候才清空tmp，交换发球权
tmp[k] = 0, k ^= 1;
if (now[0] == 11 || now[1] == 11)
oper();
}
}
if (tot[1] == 4 || tot[0] == 4)
cout << "E" << endl;//大场有人胜利输出E
else
cout << (k ? 'Z' : 'L') << endl;
}
D.beam search算法：
阅读理解题，题面比较长，但是耐心读到后面发现是一个思路比较清晰的DFS，由于相乘的都是小数，n又最多为一百个，肯定会有精度问题，所以这里用cmath库里的log函数把小数乘转为对数加，然后再用exp把对数化回小数。
#include <iostream> #include <vector> #include <cmath> using namespace std; #define double long double const int N = 105; int n, m, x; vector<int> h[N][N];//存邻层之间的连边关系 double p[N][N], res = 0.0; void dfs(int i, int j, double t)//这个dfs用来求最大的小数乘积
{ if (i == n) return res = max(res, exp(t)), void(); for (int k = 0; k < h[i][j].size(); k++) dfs(i + 1, h[i][j][k], t + p[i + 1][h[i][j][k]]);//对数加等价于小数乘 } void get_ans(int i, int j, double t, string path)//求字典序最小的路径，由于我们枚举的时候从小枚举到大，所以得到的同值路径一定是字典序最小的 { if (i == n) { if (fabs(exp(t) - res) < 1e-60)//这个精度很离谱，但是这种做法如果不开到1e-60回因为精度WA掉个别测试数据 cout << path << endl, exit(0); return; } for (int k = 0; k < h[i][j].size(); k++) { int u = h[i][j][k]; get_ans(i + 1, u, t + p[i + 1][u], path + to_string(u)); } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> p[i][j], p[i][j] = log(p[i][j]); for (int i = 2; i <= n; i++) for (int j = 1; j <= m; j++) cin >> x, h[i - 1][x].push_back(j);//边从上一层连接到这一层 for (int i = 1; i <= m; i++) dfs(1, i, p[1][i]); for (int i = 1; i <= m; i++) get_ans(1, i, p[1][i], to_string(i)); }
E.50公里徒步
一个需要注意个别细节处理的模拟。(大量压行+注释,可能会影响观感)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 105;
int n, h, m, x, dist[N], tmp[N], mark[9], lim[N], t[N], T;//dist表示总步数，tmp表示从入场到给出的时间截点选手走了多少步，lim表示选手最多路程是多少
int d[8] = {0, 5, 7, 4, 5, 4, 7, 8}, a[N], st[N];//t表示选手从入场到时间截点一共有多少时间，mark表示获取i个印章至少需要mark[i]的时间
int main()
{
for (int i = 1; i <= 7; i++)
mark[i] = mark[i - 1] + d[i] * 1000;
cin >> n, mark[8] = 0x3f3f3f3f;//最后一个结点设置一个正无穷哨兵,可以省去特判
for (int i = 1; i <= n; i++)
cin >> dist[i];//由于初始微信步数也会算在最后排榜时的步数,所幸直接加到dist中
for (int i = 1; i <= n; i++)//这里虽然题目说的是长度为四的字符串,但由于时间都是严格四位的,所以直接用int输入就可以了,前导零也会自动省略
cin >> x, h = x / 100, m = x % 100, t[i] = h * 60 + m - 480;
for (int i = 1; i <= n; i++)//全程长度为40000米,加上选手起始步数和回家步数,就是选手这次比赛可能达到的最大的步数
cin >> lim[i], lim[i] += dist[i] + 40000;
cin >> x, h = x / 100, m = x % 100, T = h * 60 + m;//大T表示时间截点
for (int i = 1; i <= n; i++)
{
tmp[i] = max(0, (T - t[i]) * 60), dist[i] += tmp[i], dist[i] = min(dist[i], lim[i]);//tmp和0取max是怕选手入场时间晚于时间截点出现负步的情况
for (int j = 0, flag = false; !flag && j <= 8; j++)//为了压行不写花括号,引入flag变量,相当于break的作用了
if (tmp[i] < mark[j])
cout << j - 1 << " ", flag = true;
}
cout << endl, memcpy(a, dist, sizeof(a)), sort(a + 1, a + 1 + n, greater<int>());//这里直接sort然后reverse印象中会快一点,不必按照新的比较规则排序
for (int i = 1; i <= n; i++)
{
int rk = 1;
while (a[rk] > dist[i] || (a[rk] == dist[i] && st[rk]))//st是为了标记排名,因为步数可以重但是排名不会重,所以对于同步数也要分配不同且递增的排名
rk++;
cout << rk << " ", st[rk] = true;
}
cout << endl;
}
F.作业抽查
搞个前缀和数组,相同就标记为1,每次询问判一下区间内是否权值和等于区间长度即可.
(注:由于数据太水,放掉了对两个数组求前缀和然后判断区间权值和是否相等的做法,这是很错误的解法)
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], s[N], n, m, l, r;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + (a[i] == b[i]);
cin >> m;
while (m--)
cin >> l >> r, cout << ((s[r] - s[l - 1] == r - l + 1) ? "Yes" : "No") << "\n";
}
G.马和马车 (0个提交的原因难道是我题面写的比较模糊?自己看的时候发现其实有些歧义可能会让人把题想难)
思路其实并不难想,但是代码相对长一些,需要注意一些细节.(另外,边权为1的最短路其实也可以BFS求)
二者的朴素走法:
马:dx和dy数组进行八个方位的枚举即可
马车:由于马车横着走,改变一单位x,竖着走,改变一单位y,斜着走,同时改变x和y各一个单位,所以马车想去一个点所需的路程等价于起点和终点的x与y之差的最大值(因为斜着走可以同时改变x和y,所以x和y中较小的一方是可以斜着顺带走掉的)
怎么找最少步数:
由于马车只有一个,但是马有很多,而且马车的走法是可以O(1)求得的,所以我们容易想到先算出所有马的最步数总和,然后再讨论马车如何走的问题.
既然只讨论马的走法,那么我们对于棋盘的建图也要依据马的八个方向走法进行连接.
求多个点到一个点的最短距离和,一个常用的方法是单源最短路,从汇聚点出发,得到到达各个点的最短距离,然后把各个点的dist值加起来得到总和本题,由于R*C很小,所以我们考虑枚举各个点作为汇聚点来求所有马到汇聚点的最少步数和.
再讨论,在考虑马车的情况下如何求得最少的步数和.
马车有两种走法,由于自己是八连通的走法,所以马车到达任何点都可以靠自己的max(x距离差,y距离差)走到,也可以考虑找一匹马搭顺风车,这样由于二者结合以后只按照马的方式走,所以我们可以认为马车到汇聚点所花费的步数等于到达"搭车点"的步数,然后就是被搭车马带飞,按照它的最短路走即可.所以问题的关键是如何找到"搭车点".
不妨继续枚举搭车点,但一个显然的问题是,搭车点不一定在某个马的最短路径上,存在"马绕远去接马车然后再跳到终点的步数少于马和马车各走各的最短路径的步数和",所以如果我们能直到,马车在棋盘上任意两点之间的最短距离就可以快速算出搭车情况下的最短步数和.所以我们开二维dist做n*m次最短路得到不同点之间马的最短路.
这样,枚举汇聚点以后,对于搭车和不搭车我们都可以有直接的公式算出其最少步数和,然后对res取min即可,其计算公式如下:
要么不搭车,此时总步数和为汇聚点到所有马的初始点的dist总和+马车与汇聚点的横纵坐标之差中的最大值
要么搭车,此时枚举搭车点,然后枚举所有马的起点,此时对于搭车点b,马起点a,汇聚点c三个点而言,马车搭车点最少步数之和为"汇聚点到所有马起点的步数和减去到起点a的步数和,加上起点a到搭车点b的步数,加上搭车点b到汇聚点c的步数,加上马车到搭车点b的步数",在这个式子中找到最小值,得到答案.
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int>PII;
const int N=1e3+5,M=1e6+5;
int idx,id[30][26],cnt,dist[N][N],xx,yy,h[N],e[M],ne[M],w[M],n,m;
int dx[8]={-1,-2,-2,-1,1,2,2,1},sx,sy;
int dy[8]={-2,-1,1,2,2,1,-1,-2},id1,id2;
bool st[N];
vector<int>dot;
void add(int a,int b)
{
e[idx]=b,w[idx]=1,ne[idx]=h[a],h[a]=idx++;
}
void dj(int sx,int dist[])//堆优化迪杰斯特拉
{
priority_queue<PII,vector<PII>,greater<PII>>q;
memset(st,false,sizeof(st)),dist[sx]=0,q.push({dist[sx],sx});
while(q.size())
{
PII t=q.top();
q.pop();
int ver=t.second;
if(st[ver])
continue;
st[ver]=true;
int distance=t.first;
for(int i=h[ver];~i;i=ne[i])
{
int j=e[i];
if(dist[j]>distance+w[i])
dist[j]=distance+w[i],q.push({dist[j],j});
}
}
}
int get_dist(int x1,int y1,int x2,int y2)//马车的朴素走法所需最少步数
{
return max(abs(x1-x2),abs(y1-y2));
}
int check(int x,int y)//对于汇聚点{x,y}而言,求考虑马车的情况下的最小步数和
{
int res=get_dist(x,y,sx,sy);//初始化就定为马车朴素走法的距离,可以省略以后再次判断.
for(int i=0;i<n;i++)//枚举搭车点
for(int j=0;j<m;j++)
{
int d=get_dist(i,j,sx,sy);
if(res > d)//小剪枝
{
int a=id[x][y],b=id[i][j];
for(int k=0;k<dot.size();k++)
{
int c=dot[k];
res=min(res,d+dist[a][b]+dist[b][c]-dist[a][c]);//形似三角形的两边替换一边
}
}
}
return res;
}
int main()
{
char y;
int x;
memset(h,-1,sizeof(h)),memset(dist,0x3f,sizeof(dist));
cin>>n>>m>>y>>x,sx=x-1,sy=y-'A';
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
id[i][j]=i*m+j;
while(cin>>y>>x)
{
int i=x-1,j=y-'A';
dot.push_back(id[i][j]);
}
for(int i=0;i<n;i++)//按马走法连边
for(int j=0;j<m;j++)
for(int k=0;k<8;k++)
{
xx=i+dx[k],yy=j+dy[k];
if(xx<0||xx>=n||yy<0||yy>=m)
continue;
id1=id[i][j],id2=id[xx][yy],add(id1,id2);
}
int res=0x3f3f3f3f;
for(int x=0;x<n;x++)
for(int y=0;y<m;y++)
dj(id[x][y],dist[id[x][y]]);//求得dist数组
for(int x=0;x<n;x++)//枚举汇聚点
for(int y=0;y<m;y++)
{
int tot=0;
for(int j=0;j<dot.size();j++)
tot+=dist[id[x][y]][dot[j]];
if(tot<0)
continue;
res=min(res,tot+check(x,y));
}
if(res>1e9)//说明有的马车点走不到
cout<<"What can I say\n";
else
cout<<res<<endl;
}
H.小明刷USACO
题意简化:把一段数组划分三个部分,使得三个部分权值和相等,并且非空,问这种划分方式有多少种
首先,想划分三个等值非空数组的前提是整个数组可以被三整除,这样可以排除一些情况,还有可能数组容量不足3,但这种情况在我们的做法中是不必特判的,因为双指针找不到合适的位置安置.
然后考虑如何划分,容易想到前缀和快速判断区间权值和,我们用一个指针r从后往前划分,那么一旦划分出右侧元素和为总数的三分之一,则启用指针l从前往后划分,当该指针左侧元素和也为总数的三分之一时,二者指针中间的元素和自然也为三分之一,所以我们要做的就是找到这种{l,r}对.
但是对于极限数据,n等于十万,全是0的情况,双指针会超时(甚至种类数会爆long long),我们需要想到一种快速的计数方法:把l和r指针的成立位置记下来,升序排序,然后枚举左侧指针的位置,同时寻找第一个大于该位置的右侧指针(小于该位置的右侧指针跳过),此时还有多少个右侧指针未被跳过,就额外多有几种组合方案,加上即可.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int tot,k,s[N],a[N],n;
long long res;
vector<int>pl,pr;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],s[i]=s[i-1]+a[i],tot+=a[i];
if(tot%3)
cout<<0<<endl,exit(0);
k=tot/3;
for(int i=1;i<n-1;i++)
if(s[i]==k)
pl.push_back(i);
for(int i=3;i<=n;i++)
if(s[n]-s[i-1]==k)
pr.push_back(i);
int l=0,r=0;
while(l<pl.size())
{
while(r<pr.size() && pl[l]+1 >= pr[r])
r++;
if(r>=pr.size())
break;
res+=pr.size()-r,l++;
}
cout<<res<<endl;
}
标签：马车,now,dist,int,题解,31,哈尔滨理工大学,include,步数
From： https://www.cnblogs.com/BIOS0408/p/18109298