第一题
题目描述
现在给你一个只包含""括号的字符串，问你至少加多少个字符是合法的，对于字符串合法的定义为：
- 字符串为空是合法的
- 若字符串A合法，则字符串(A), [A]也是合法的
- 若字符串A和字符串B均合法，则AB合法
输入
- 第一行输入一个字符串s，保证只有题目要求的字符
- 1 <= len(s) <= 200
输出
- 输出最少需要添加几个字符可以构成合法的字符串
样例输入
样例输出
- 1
样例输入
- )(][][)(
样例输出
- 3
分析
- 如果只有一种括号的话就是leetcode921的原题
- 有2种括号的话需要用DP去搞。我们先求出来通过添加字符，从i到j能构成的合法串的最短长度是多少。然后状态转移一波(分情况讨论)。
解法
#include <bits/stdc++.h> using namespace std; int dp[205][205]; int main(){ string s; int i,j,k,p; while(cin>>s){ memset(dp,0,sizeof(dp)); if(s.size()==1){ puts("1"); continue; } for(i=0;i+1<s.size();i++){ if((s[i]=='('&&s[i+1]==')')||(s[i]=='['&&s[i+1]==']')) dp[i][i+1]=2; } for(i=3;i<=s.size();i++){ for(j=0;j+i-1<s.size();j++){ k=j+i-1; dp[j][k]=max(dp[j][k],dp[j+1][k-1]); dp[j][k]=max(dp[j][k],max(dp[j+1][k],dp[j][k-1])); if((s[j]=='('&&s[k]==')')||(s[j]=='['&&s[k]==']')){ dp[j][k]=max(dp[j][k],dp[j+1][k-1]+2); } for(p=j+1;p<k;p++){ dp[j][k]=max(dp[j][k],dp[j][p]+dp[p+1][k]); } } } cout<<s.size()-dp[0][s.size()-1]<<endl; } return 0; }
第二题
题目描述
- 求抛物线
与直线
，直线
以及x轴所围成的封闭图形的面积。
输入
- 第一行为一个整数T，表示测试数据的组数
- 接下来每行输入四个整数A, B, C, D
- 1 <= T <= 1000, 1 <= A, B <= 100, -100 <= C <= 100
输出
- 每组测试数据输出一个答案，为封闭图形的面积
样例输入
- 1
- 2 3 1 2
样例输出
- 9.16667
分析
- 简单的微积分，也可以用辛普森公式直接计算：
- 在平面直角坐标系中，由任意三点(x1, y1), (x2, y2), (x3, y3)（x1<x2<x3，x2 = (x1 + x3)/2）确定的抛物线y= f(x)在[x1, x3]的定积分为
解法
#include <bits/stdc++.h> using namespace std; double calc(int a, int b, double x) { return 1.0 * a * x * x + x + b; } int main() { int T; cin >> T; while (T--) { int a, b, c,d; cin >> a >> b >> c >> d; double mid = (c + d) / 2.0; double y1 = calc(a, b, c); double y2 = calc(a, b, mid); double y3 = calc(a, b, d); printf("%.6lf\n", 1.0/6 * (d - c) * (y1 + 4 * y2 + y3)); } return 0; }
第三题
题目描述
- 小Q所在的部门有n个人，要从这n个人中选任意数量的人组成一只队伍，再在这些人中选出一名队长，求不同的方案数对1e9+7取模的结果。如果两个方案选取的人的集合不同或者选出的队长不同，则认为这两个方案是相同的。
输入
- 一行一个数字n，1<=n <= 1e9
输出
- 一行一个数字表示答案
样例输入
- 2
样例输出
- 4
分析
- 一个组合数学题，如果不选队长的话选出k个人的方案数就是
，要考虑队长的话方案数就是
，最终的方案数为
。经过一顿推导可以得到最终的结果为
。
解法
#include <bits/stdc++.h> using namespace std; #define ll long long const ll mod = 1000000000 + 7; ll poww(ll base, ll a) { ll ans = 1; while (a != 0) { if (a & 1) { ans *= base; ans %= mod; } base *= base; base %= mod; a >>= 1; } return ans; } int main() { int n; while (cin >> n) { cout << (n* poww(2, n-1)) % mod << endl; } return 0; }
第四题
题目描述
- 我们定义集合g(x)为：与x相邻的节点的集合；从而定义图的价值为：图中满足g(x)=g(y)这样的点对(x,y)的数量
- 现在给定一个n个节点和m条边的无向联通图，请你计算出当前图的价值
输入
- 第一行输入两个正整数n和m，表示点的数量和边的数量
- 接下来m行，每行输入两个整数x和y，表示x和y之间连边
- 2<=n<=100000, 1<=m <= 200000, 1 <= x, y <= n
- 输入保证图连通，且没有重边和环
输出
- 输出结果
样例输入
- 4 3
- 1 2
- 2 3
- 2 4
样例输出
- 3
分析
- 对于每一个顶点，可以得到它相邻的点的集合，将相邻的点的列表做个哈希，最后直接判断即可过90%。
解法
#include <bits/stdc++.h> using namespace std; const int siz=100005; vector<int> G[siz]; map<int,int> mp; int main(){ int n,m,i,j,k,x,y,ans,tmp; while(scanf("%d%d",&n,&m)!=EOF){ for(i=0;i<=n;i++) G[i].clear(); for(i=0;i<m;i++){ cin>>x>>y; G[x].push_back(y); G[y].push_back(x); } ans=0; mp.clear(); for(i=1;i<=n;i++){ for(j=0;j<G[i].size();j++) mp[i]+=(G[i][j]*G[i][j]); } for(i=1;i<=n;i++){ if(G[i].size()<=1) continue; for(j=0;j<G[i].size();j++){ for(k=j+1;k<G[i].size();k++){ if(G[G[i][j]].size()!=G[G[i][k]].size()) continue; if(mp[G[i][j]]==mp[G[i][k]]) ans++; } } } printf("%lld\n",ans); } return 0; }
第五题
题目描述
现在有n个点，有m条双向路径，其中有一个宝物在n点，已知有k个传送门，每一个传送门可以从x点到达y点，传送门单向的，通过传送门传送不算距离，现在从1点开始，若能拿到宝物，输出走过的最短距离，若无法拿到，请输出-1。
输入
第一样输入3个数n, m 和k，代表有n个点，m条双向路径以及k个传送门
接下来m行，每一行输入三个数x,y,l代表双向路径从x到y的距离是l
接下来k行，每一行输入两个数x,y表示x和y之间有传送门
1<=n<=2000, 1<=m<=50000, 1<=k<=100, 1<=x,y<=n, 1<=l<=100
输出
对于每一组数据，输出一个答案代表拿到宝物走过的最短距离
样例输入
5 3 2
1 2 1
2 3 1
3 4 1
4 5
1 2
样例输出
2
分析
最直接的最短路，直接建图跑dijkstra即可
解法
#include <bits/stdc++.h> using namespace std; const int maxn = 2002; const int INF = 0x3f3f3f3f; struct Edge { int u, v, w; int next; }E[maxn *100]; int head[maxn]; int cnt; void init() { memset(head, -1, sizeof(head)); cnt = 0; } void add_edge(int u, int v, int w) { E[cnt].u = u; E[cnt].v = v; E[cnt].w = w; E[cnt].next = head[u]; head[u] = cnt++; } int n; int vis[maxn]; int dis[maxn]; int gao(int s, int t){ for(int i = 1;i <= n;i++) vis[i] = 0; for(int i = 1;i <= n;i++) dis[i] = (i == s ? 0 : INF); dis[1] = 0; for(int i = 1;i <= n;i++) { int x, minn = INF; for(int j = 1;j <= n;j++){ if(!vis[j] && dis[j] <= minn){ x = j; minn = dis[j]; } } vis[x] = 1; for(int j = head[x]; j != -1; j = E[j].next){ int y = E[j].v; int w = E[j].w; dis[y] = min(dis[y], dis[x] + w); } } if (dis[n] == INF) return -1; return dis[n]; } int main() { int m, k; while (cin >> n >> m >> k) { init(); int a, b, w; while (m--) { cin >> a >> b >> w; add_edge(a, b, w); add_edge(b, a, w); } while (k--) { cin >> a >> b; add_edge(a, b, 0); } cout << gao(1, n) << endl; } return 0; }文章首发于公众号“面鲸”，欢迎关注～
全部评论
(15) 回帖